ターン制ストラテジーゲームにおける戦術決定のためのUCT探索とその効率化

情報処理学会

書誌事項

タイトル別名
  • UCT and Its Enhancement for Tactical Decisions in Turn-based Strategy Games

説明

ターン制ストラテジーゲームは，囲碁や将棋と比べて1 ターンの候補手があまりにも膨大である．この性質が，ターン制ストラテジーゲームの分野において強いAI を作る妨げとなっている．しかしながら，一方で，ターン制ストラテジーゲームには戦術レベルでは盤面の局所性や，候補手の類似性が存在し，これによって探索空間を減らすことが可能である．そこで，本研究では，コンピュータによる問題の枝刈り，それによる探索空間の縮小を考える．探索にはゲームの分野で成果を上げているUpper Confidence Bound applied to Trees を用い，選択肢を枝刈りし，本研究用に作成したゲームを用いて，探索の効率化と強さの評価を行う．結果として，単純なUCT に対して良い成績を収め，枝刈りが有効であることを確認できた．

The number of possible actions at each turn in turn-based strategy games can be prohibitively large compared to that of Go and Shogi, and this makes it hard to build strong AI engines for such strategy games. However, the possible actions in turn-based strategy games usually have at least two characteristics that one could take advantage of in order to reduce the branching factor: locality of each battle field and similarity between actions. In this work, we propose a simple pruning method for reducing the search space. We implement the pruning method in the UCT algorithm and evaluate its effectiveness in terms of playing strength and computational cost, using a simple turn-based strategy game that we have developed for a research purpose. Our experimental results show that the proposed pruning method has improved the performance of the UCT search.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ