A Search Algorithm for Finding Multi Purpose Moves in Sub Problems of Go

• Item type: Symposium(1)
• 公開日: 2005-11-18
• タイトル: A Search Algorithm for Finding Multi Purpose Moves in Sub Problems of Go
• タイトル / 言語: en
• タイトル: A Search Algorithm for Finding Multi Purpose Moves in Sub Problems of Go
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: Graduate School of Information Science and Technology
• 著者所属: University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): University of Tokyo
• 著者名: Yoshizoe, Kazuki
• 著者名(英): Yoshizoe, Kazuki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Because of the difficulty in evaluating the board positions, the successes in chess variants does not directly strengthen Go player programs. It is believed that most Go playing programs use subgoal oriented search to decide moves. Subgoals are local targets with well defined evaluation functions, such as capturing, connection and living. Currently, the overall strength of Go playing programs are weak. On the other hand, current state-of-the-art algorithms for solving life-and-death problems overtook professional Go players in terms of speed and accuracy. To improve Go playing programs, it is necessary to fill in the gap between the strength of single subgoal searches and strength of overall play. It is critical to solve the dependencies between subgoals. For this purpose, it is necessary to maintain the information of each subgoal search. The information required includes not only the search result but also the possible inversions of the subgoals. The intersections of inversions are the candidates for multi purpose moves. In this paper we focus on presenting a new algorithm for searching inversions. Target problems are capturing problems of Go. We have tested the algorithm on test problems and measured the number of nodes searched.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Because of the difficulty in evaluating the board positions, the successes in chess variants does not directly strengthen Go player programs. It is believed that most Go playing programs use subgoal oriented search to decide moves. Subgoals are local targets with well defined evaluation functions, such as capturing, connection and living. Currently, the overall strength of Go playing programs are weak. On the other hand, current state-of-the-art algorithms for solving life-and-death problems overtook professional Go players in terms of speed and accuracy. To improve Go playing programs, it is necessary to fill in the gap between the strength of single subgoal searches and strength of overall play. It is critical to solve the dependencies between subgoals. For this purpose, it is necessary to maintain the information of each subgoal search. The information required includes not only the search result but also the possible inversions of the subgoals. The intersections of inversions are the candidates for multi purpose moves. In this paper we focus on presenting a new algorithm for searching inversions. Target problems are capturing problems of Go. We have tested the algorithm on test problems and measured the number of nodes searched.
• 書誌情報: ゲームプログラミングワークショップ2005論文集; 巻 2005, 号 15, p. 76-83, 発行日 2005-11-18
• 出版者 / 言語: ja
• 出版者: 情報処理学会