実現確率探索のゲーム全般への応用―Lines of Actionを題材にして―

• Item type: Symposium(1)
• 公開日: 2002-11-15
• タイトル: 実現確率探索のゲーム全般への応用―Lines of Actionを題材にして―
• タイトル / 言語: en
• タイトル: Application of Realization Probability Search for Any Games - a case study using Lines of Action -
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 静岡大学工学部
• 著者所属: 静岡大学情報学部
• 著者所属: 静岡大学情報学部
• 著者所属: Department of Computer Science, Universiteit Maastricht
• 著者所属: 静岡大学情報学部／科学技術振興事業団さきがけ研究21「機能と構成」領域
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Shizuoka University
• 著者所属(英): en
• 著者所属(英): Faculty of Information, Shizuoka University
• 著者所属(英): en
• 著者所属(英): Faculty of Information, Shizuoka University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Universiteit Maastricht
• 著者所属(英): en
• 著者所属(英): Faculty of Information, Shizuoka University / 'Information and Systems', PRESTO, Japan Science and Technology Corporation
• 著者名: 橋本, 剛; 長嶋, 淳; 作田, 誠; Jos, Uiterwijk; 飯田, 弘之
• 著者名(英): Hashimoto, Tsuyoshi; Nagashima, Jun; Sakuta, Makoto; Uiterwijk, Jos; Iida, Hiroyuki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 鶴岡は実現確率探索を考案し，プログラム「激指」に実装して2002年世界コンピュータ将棋選手権を見事に制した．実現確率探索は局面の実現確率を閾値として探索することで，より「有りそう」な手の場合はどんどん深く読み，「無さそう」な手の場合はほとんど読まない．これまで前向き枝刈りと探索延長によって行ってきたことをシステマティックに非常に簡単なアルゴリズムで行う優れた探索法であるといえる．ところが，激指の手法ではプロの棋譜から指し手の確率を計算しており，参考となる棋譜が十分に存在しない多くのゲームではこの手法は通用しない．本稿ではコンピュータの自動学習により指し手の確率を自動で計算し，実現確率探索をあらゆるゲームに応用させる手法，ARPS（自動実現確率探索）を提案する．実験には連結型の二人ゲームLines of Action（LOA）を選び13種類の分類を与えてARPSを実装し分類の確率を計算した．一般的な反復深化探索との対戦結果は，ARPSが反復深化に比べてより深くよりより絞り込んだ読みで大きく勝ち越しその優位性を示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Recently, Realization-Probability Search was proposed and implemented in the shogi program GEKISASHI, which won the World Computer Shogi Championship in 2002. It searches deeper after "probable" moves and shallower after "improbable" moves. It can efficiently perform a selective search similar to forward pruning and search extensions, while using a considerably simpler algorithm in an systematic way. However, since the method in GEKISASHI calculates move-category probabilities form many games by professional players, it cannot be used for games that lack the availability of a sufficient quantity of game records. This paper proposes a technique called Automatic Realization-Probability Search (ARPS), which can be applied to any game. We have selected Lines of Action (LOA), which is a connection-based two-player game and is considered very different from chess-like games. ARPS has been implemented and examined in a LOA program. The results of our experiments have shown that ARPS is superior to normal iterative deepening in strength and perform narrower and deeper searches.
• 書誌情報: ゲームプログラミングワークショップ2002論文集; 巻 2002, 号 17, p. 81-86, 発行日 2002-11-15
• 出版者 / 言語: ja
• 出版者: 情報処理学会