ソフトマックス戦略と実現確率による深さ制御を用いたシンプルなゲーム木探索方式

• Item type: Symposium(1)
• 公開日: 2016-10-28
• タイトル: ソフトマックス戦略と実現確率による深さ制御を用いたシンプルなゲーム木探索方式
• タイトル / 言語: en
• タイトル: A Simple Game-Tree Search Algorithm Based on Softmax Strategy and Search Depth Control Using Realization Probablity
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: Computer shogi, Softmax strategy, Realization probability, Boltzmann distribution function
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 芝浦工業大学工学部情報工学科
• 著者所属: 芝浦工業大学工学部情報工学科
• 著者所属: （株）コスモ・ウェブ
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Engineering, College of Engineering, Shibaura Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Engineering, College of Engineering, Shibaura Institute of Technology
• 著者所属(英): en
• 著者所属(英): en
• 著者所属(英): Cosmoweb Co., Ltd.
• 著者名: 原, 悠一; 五十嵐, 治一; 森岡, 祐一; 山本, 一将
• 著者名(英): Yuichi, Hara; Harukazu, Igarashi; Yuichi, Morioka; Kazumasa, Yamamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ソフトマックス戦略に基づくシンプルな探索方式を提案し，コンピュータ将棋へ適用した実験結果を報告する．本探索方式では探索木中のノードの評価値は子ノードの評価値を選択確率で重み付けした期待値であり，再帰的に定義される．選択確率は選択先のノードの評価値を目的関数とするボルツマン分布を用いる．探索は実現確率を良さの度合いとする最良優先探索であり，深さの制御には実現確率の閾値を用いた反復深化を用いる．各ノードへの実現確率はルートノードからの選択確率の積で定義する．したがって，将棋の有効な指し手に関するヒューリスティクスは使用せず，最終的には局面評価関数だけに依存する．本発表ではこの探索方式の詳細と評価実験の結果を報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a new simple game-tree search algorithm based on a softmax strategy and report our experimental results with it after applying it to computer shogi. In this algorithm, each node’s value in a search tree is defined by the expectation of the values of its child nodes. The selection probabilities of the child nodes are used as weights when calculating the expectations. A child node’s selection probability is given by the Boltzmann distribution function, including the node’s value as its objective function. A game tree is searched by the best-first search algorithm where the realization probability is used as the node’s goodness for reaching a goal. The realization probability is also used as a threshold in iterative deepening to control a search’s depth. We defined a node’s realization probability as the product of the selection probabilities from the root node to the node itself. That means the realization probabilities depend on the values of the leaf nodes, not on the heuristics based on the statistics of moves in shogi as in the traditional research. Only a state evaluation function is necessary for calculating the realization probabilities. The details of our new search algorithm and experimental results are shown in this short report.
• 書誌情報: ゲームプログラミングワークショップ2016論文集; 巻 2016, p. 108-111, 発行日 2016-10-28
• 出版者 / 言語: ja
• 出版者: 情報処理学会