タブーリストを内包したモンテカルロ木探索の詰碁と9路盤囲碁への応用

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2015/03/01

タイトル(英語): An Application of Monte-Carlo Tree Search Including Tabu Lists for Tsumego and 9×9 Go

著者名: 太田　雄大（愛知工業大学大学院経営情報科学研究科），伊藤　雅（愛知工業大学情報科学部）

著者名(英語): Takehiro Ohta (Graduate School of Business Administration and Computer Science, Aichi Institute of Technology), Masaru Itoh (Faculty of Information Science, Aichi Institute of Technology)

キーワード: コンピュータ囲碁，詰碁，モンテカルロ木探索，タブーリスト，多様性，最良優先探索　　computer go，tsumego，Monte-Carlo tree search，tabu list，diversity，best-first search

要約(英語): This paper proposes a new approach to solving tsumego and playing games in computer go. The approach is based on the Monte-Carlo tree search (MCTS) algorithm. To be more specific, the proposed method improves how to execute a single playout on a leaf node. Our method brings diversity to playout so that only a particular part of the Monte-Carlo tree will not grow in the depth direction. The diversity of playout can be brought to realization by embedding tabu lists into all leaf nodes. Here, the tabu list means a short memory which is very popular in the tabu search algorithm. Tabu lists impose restriction on several moves from the first move during the playout so as to control the points of prohibited moves. If a candidate move corresponds with an element contained in the tabu list, then the move is treated as the prohibited move. It is possible that the diversity of playout could induce the behavior of MCTS to the best-first search on a more uniformly-broadened tree. This works well for solving tsumego which has the only path without branching. Furthermore, the variable-length tabu lists embedded into the MCTS would have an advantage in playing 9×9 go.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.135 No.3 （2015）

本誌掲載ページ: 331-339 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/135/3/135_331/_article/-char/ja/