MTD(f)の改良と評価  [in Japanese] Improvement and Estimate of MTD-f  [in Japanese]

記憶容量を多大に必要とし、実際に実行することが難しいとされた最良優先探索を、深さ優先探索に置き換えて実行可能にしたMTDという手法がある。MTDはnull-window探索を複数回使用することによって探索を行う手法であり、状況によってはαβ探索木よりも小さな探索木でゲーム木探索を実行する事が可能である。MTDは、初期値設定の違いによっていくつかの手法に分かれており、あらかじめ近似値fを用意して探索を行うMTD-fが有望な方法である事が示されている。本研究では、ランダム木の探索を行う事で、MTD-fの性質について調査した。また、MTD-fは近似値fの設定がミニマックス値から離れている場合、αβ探索よりも悪くなるという次点がある。これを解決するため、MTD-fに対し、MTD-stepを組み合わせたMTD-f-stepと、ウィンドウ探索を組み合わせたMTD-f-αβを提案する。これらの手法を本研究室で開発した将棋プログラムに対して適用し、その性能を調査した。その結果、通常のMTD-fに比べ、約3%速くなることが示された。

The best-first search is an ideal algorithm but is practically difficult to use because of the problem of strage. MTD is an advanced best-first search which explores a game-tree in a depth-first manner. MTD uses a NULL-window search at a root node in several times and is able to find a solution with less number of search node than an alpha-beta search. Previous researches reported that MTD-f, which uses an approximate minimax value at first for the NULL-window search, showed the best results. We show the nature of MTD-f for random-game trees in this paper. From this observation, we propose several methods for the improvement and analyze these performances. These method are concerned how to determine initial values of NULL-windows. As a consequence, MTD-f with MTD-step, called MTD-f-step, and MTD-f-alphabeta can find solutions 3 percent faster than MTD-f in our experiments.