タブーサーチを内包したモンテカルロ木探索に基づく囲碁アルゴリズム

• Item type: Symposium(1)
• 公開日: 2013-11-01
• タイトル: タブーサーチを内包したモンテカルロ木探索に基づく囲碁アルゴリズム
• タイトル / 言語: en
• タイトル: An Igo Algorithm of Monte Carlo Tree Search Including Tabu Search
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 愛知工業大学大学院経営情報科学研究科
• 著者所属: 愛知工業大学情報科学部情報科学科
• 著者所属(英): en
• 著者所属(英): Graduate School of Business Administration and Computer Science, Aichi Institute of Technology
• 著者所属(英): en
• 著者所属(英): Faculty of Information Science, Aichi Institute of Technology
• 著者名: 太田, 雄大; 伊藤, 雅
• 著者名(英): Takehiro, Ohta; Masaru, Itoh
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: モンテカルロ木探索におけるプレイアウトの効率化の研究は活発に行われてきた.しかし,プレイアウトの多様性についての研究はあまりされていない.そこで,本研究ではモダンヒューリスティクスの一つであるタブーサーチをプレイアウトに適用することを提案する.プレイアウトを行った局面をタブーリストに追加し,タブー期間探索するのを禁止する.また,タブー期間を過ぎた局面をタブーリストから取り除く.それによりプレイアウトの多様性を確保することができる.数値実験を対局及び詰碁にて行い,タブーサーチを内包したモンテカルロ木探索は単純なモンテカルロ木探索に比べて良い性能が得られた.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Efficiency of playout in Monte Carlo tree search (MCTS) have been extensively studied up to now. However, diversity of playout is not really investigated. Because of that, this paper refers to the diversity in MCTS. So this paper proposes to combine MCTS with tabu search (TA), which is a modern heuristic technique for combinatorial problems, into the computer igo algorithm. Once a phase of the playout is added into a tabu list, the searching method prohibits the adoption of the same phase during a given tabu tenure. When the number of trials for playouts is greater than the tabu tenure, the phase is removed from the tabu list. And then the phase could be adopted again. Thus the proposed method can be obtained to ensure the diversity of playout as a whole. The numerical results for some life-and-death igo problems shows that the method of MCTS including TA have obviously got an advantage over the simple MCTS algorithm with the view of the right moves.
• 書誌情報: ゲームプログラミングワークショップ2013論文集; p. 90-93, 発行日 2013-11-01
• 出版者 / 言語: ja
• 出版者: 情報処理学会