不確定性を含むデジタルカーリングにおけるゲーム木探索

• Item type: Journal(1)
• 公開日: 2016-11-15
• タイトル: 不確定性を含むデジタルカーリングにおけるゲーム木探索
• タイトル / 言語: en
• タイトル: A Method of Game Tree Search in Digital Curling Including Uncertainty
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：ゲームプログラミング（特選論文）] デジタルカーリング，不確定ゲーム，ゲーム木探索，Expectimax
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate Schoool of Information Science and Technology Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate Schoool of Information Science and Technology Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate Schoool of Information Science and Technology Hokkaido University
• 著者名: 加藤, 修; 飯塚, 博幸; 山本, 雅人
• 著者名(英): Shu, Katoh; Hiroyuki, Iizuka; Masahito, Yamamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 二人零和有限確定完全情報ゲームにおいてすでにAIは人間に匹敵する強さとなっており，最近では麻雀や人狼など，多人数ゲーム，不完全情報ゲーム，不確定ゲームが新たな研究対象として注目を集めている．そのような中で不確定ゲームとしてデジタルカーリングがある．デジタルカーリングはカーリングの二人用コンピュータゲームであり，AIどうしを競わせカーリングの戦略を解析することを目的とした不確定ゲームのテストベッドとして開発された．本研究ではデジタルカーリングにボードゲームの探索手法を適用し，投球目標座標と回転方向を候補手，盤面状態を局面としてデジタルカーリングにExpectimaxによるゲーム木探索を適用する手法を提案する．Expectimaxではゲーム木内で確率的に推移するノードを用いており，ゲームの不確定性を考慮した探索が可能となっている．提案手法の有効性を検証するため，不確定性を考慮する場合としない場合それぞれにおいて探索の深さを変化させ既存AIとの対戦実験を行った．その結果，提案手法による不確定性の考慮を行った場合に勝率が上昇し，また不確定性を考慮した場合のみ探索の深さを増やすことで勝率が上昇したことから，デジタルカーリングにおける提案手法による不確定性を考慮した先読みの有効性が明らかとなった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Computer AI game players have beaten human expert players in two players zero-sum perfect information games such as Go and Japanese Chess and the focus is moving to multiple players, imperfect information games and even with uncertainty such as Mah-jong and Werewolf. Digital curling is one of the games with uncertainty. It has been developed as a testbed of the games with uncertainty to compete computer AI programs and to analyze the curling strategies of human players. This paper proposes an expectimax game tree search method for the digital curling where candidate moves are represented as the combination of the throwing-target position and rotational direction of stones and the discretized board states are nodes of the tree. The method can take into account uncertainty using stochastic transition in the game tree. To evaluate our proposed method, we compare the winning rates of the methods with and without the stochasticity while changing the searching depth. Our results show that our proposed method with the stochasticity is better than without the stochasticity and can only show the effective look ahead. From those results, it is shown that our proposed method could handle uncertainty and perform effective tree search on digital curling.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 57, 号 11, p. 2354-2364, 発行日 2016-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764