期待値法によるゲーム木探索

その他

Minimax method，which is the most basic game tree search for zero-sum two-person game such as Chess，Othello，Shogi，and Igo，selects the best move within the limits of the search depth. But it is impossible for minimax method to deal with the rapid changes beyond the search depth．In this paper we propose expected-value method，which is an algorithm using expected values inspecting evaluation values beyond the search depth. We also show that expected-value method is more effective than minimax method by some simulations.

チェス、オセロ、将棋、囲碁などの零和2人ゲームにおける最も基本的なゲーム木探索法であるミニマックス法は、先読みした範囲で最も良い手を選択するが、先読みした先での急激な変化には対応できない。我々は、この問題を解決するために、探索したさらに先を予測する値である期待値を用いて探索するアルゴリズムとして、期待値法を提案する。また、様々なシミュレーションによって、期待値法がミニマックス法より有効な探索法であることを示す。