A Game Tree Search Using Expectation

IPSJ Web Site 3 Citations 13 References

Bibliographic Information

Other Title
  • 期待値を用いたゲーム木探索
  • キタイチ オ モチイタ ゲーム キ タンサク
  • 探索

Search this article

Description

ミニマックス法は，チェス，オセロ，将棋，囲碁などの零和2人ゲームにおける最も基本的なゲーム木探索法である．ミニマックス法では，葉ノードに評価値を与え，子ノードの値の最大値または最小値として親ノードの返り値を求めている．葉ノードに与えられた評価値がゲームの結果を正確に反映している場合には，このミニマックス法による探索は最善の手を選択するが，葉ノードに与えられた評価値がゲームの結果を正確に反映していない場合には，ミニマックス法の返り値を求める方法は，最善の方法とは限らない．ミニマックス法の返り値を求める方法に対する様々な改善案が提案されている．本論文では，我々は，探索した葉ノードからさらに2手先を予測することができる期待値法を提案する．また，オセロゲームによる実験によって，期待値法がミニマックス法に対し改良されていることを示す．

Minimax is the most basic game-tree search method for zero-sum two-person games such as Chess,Othello, Shogi, and Go.Minimax uses evaluation values at leaf nodes and calculates returned values by taking the maximum or minimum of the successors.If evaluation values given at leaf nodes exactly reflect the result of the game,minimax selects the best move.However, if evaluation values given at leaf nodes do not properly reflect the result of the game,minimax may not be the best approach.Various improved methods for minimax have been proposed.This paper proposes the so-called Expectation method which at the level of the leaf nodes takes some probability information of two additional ply into consideration for every position.Experiments within the domain of Othello show that the Expectation method is an improvement of minimax.

Journal

Citations (3)*help

See more

References(13)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top