局面評価関数を使う新たなUCT探索法の提案とオセロによる評価

• 橋本, 剛

• 前原, 彰太

• 川島, 哲哉

• 小林, 康幸

書誌事項

タイトル別名

• A New UCT Search Method Using Position Evaluation Function and its Evaluation by Othello

抄録

新たなゲーム木探索法としてモンテカルロ木探索，特にUCTが成功を収め広く研究されている．だが主なターゲットであるコンピュータ囲碁では局面評価関数の計算が困難であるため，パターンマッチングなどにより手の評価値を計算し強いプレイヤに近いモンテカルロシミュレーションを目指す研究がさかんに行われているものの，局面評価関数を使ったUCTの研究はこれまでほとんどなかった．本研究では新たに局面評価値をUCB値に加える手法，UCT+を提案する．初めて探索する局面で評価関数の値が高い子局面を優先的に探索するので，性能の良い評価関数があれば簡単にUCTを強くすることが期待される．実験ではすでに優れた局面評価関数が存在するオセロに提案手法を実装し評価を行った．評価関数はオープンソースで世界最強プログラムZebraのものを使った．その結果，提案手法はUCTに対し圧倒的な性能を示しその有効性が実証された．

The Monte Carlo tree search, particularly UCT, is extensively studied as a new game tree search method. Study of evaluation function on UCT is mainly focused on move evaluation functions such as using pattern matching. However, UCT using position evaluation function has not been studied because of the difficulty in calculating position evaluation function in the game of GO, which is the main target of UCT research. We propose a new method UCT+ that adds position evaluation values to the UCB value. This method is expected easily to make UCT strong in case of existing good position evaluation function, as it gives priority to child positions of high evalation value that has not searched yet. Experiments are performed using the game of Othello, that already has strong position evaluation functions. Evaluation function of the Zebra, the strongest open source othello program, is used for the experiments. The results show the overwhelming ability of proposed method and its effectiveness is verified.

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 54 (7), 1930-1936, 2013-07-15

キーワード

• [一般論文] UCT+，オセロ，モンテカルロ木探索，評価関数

詳細情報

• CRID: 1050001337903240832
• NII論文ID: 110009586574
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00094371/
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles