n人ゲームの木探索における枝刈りアルゴリズム

• 梶浦 正浩

  慶應義塾大学大学院理工学研究科

• 安西 祐一郎

  慶應義塾大学大学院理工学研究科

書誌事項

タイトル別名

• A Pruning Algorithm for N-person Game Tree Search.
• nニン ゲーム ノ キタンサク ニ オケル エダカリ アルゴリズム

抄録

チェスやオセロゲームに代表される2人零和完全情報ゲームでは,ゲーム本探索には一般にMin-Maxアルゴリズムが用いられる.そして,効率良く探索するためにα-β法やSSS法などの枝刈りアルゴリズムが併用される.これに対し,n人完全情報ゲームでのゲームの木の探索では,一般にMAX^Nアルゴリズムが用いられるが,併用される枝刈りアルゴリズムは特定の条件の下で有効なものしか提案されていない.本論文ではその条件が成り立たない別種のゲームにおける新しい枝刈りアルゴリズム「限界増分枝刈りアルゴリズム」を提案する.そしてこの種のゲームの一つである「ダイヤモンドゲーム」に適用し,評価結果を示す.

収録刊行物

• コンピュータ ソフトウェア

  コンピュータ ソフトウェア 9 (1), 1_42-1_51, 1992-01-16

  日本ソフトウェア科学会

詳細情報

• CRID: 1390564238038121600
• NII論文ID: 130007505792
• NII論文ID: 110003743679
• NII書誌ID: AN10075819
• DOI: 10.11309/jssst.9.1_42
• NDL書誌ID: 3751560
• ISSN: 02896540
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I3751560
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • NDL
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可