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

加藤, 修, 飯塚, 博幸, 山本, 雅人

二人零和有限確定完全情報ゲームにおいてすでにAIは人間に匹敵する強さとなっており，最近では麻雀や人狼など，多人数ゲーム，不完全情報ゲーム，不確定ゲームが新たな研究対象として注目を集めている．そのような中で不確定ゲームとしてデジタルカーリングがある．デジタルカーリングはカーリングの二人用コンピュータゲームであり，AIどうしを競わせカーリングの戦略を解析することを目的とした不確定ゲームのテストベッドとして開発された．本研究ではデジタルカーリングにボードゲームの探索手法を適用し，投球目標座標と回転方向を候補手，盤面状態を局面としてデジタルカーリングにExpectimaxによるゲーム木探索を適用する手法を提案する．Expectimaxではゲーム木内で確率的に推移するノードを用いており，ゲームの不確定性を考慮した探索が可能となっている．提案手法の有効性を検証するため，不確定性を考慮する場合としない場合それぞれにおいて探索の深さを変化させ既存AIとの対戦実験を行った．その結果，提案手法による不確定性の考慮を行った場合に勝率が上昇し，また不確定性を考慮した場合のみ探索の深さを増やすことで勝率が上昇したことから，デジタルカーリングにおける提案手法による不確定性を考慮した先読みの有効性が明らかとなった．

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.

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

Bibliographic Information

Search this article

Abstract

Journal

Related Projects

Keywords

Details 詳細情報について

Export

Report a problem