オセロ（リバーシ）の作り方 ～ＭＴＤ（ｆ）探索法～

このサイトでは、C言語でのオセロ（リバーシ）のプログラム開発方法を解りやすく説明しています。初級者、初心者でも作れるオセロ実装のコツが満載です。

MTD(f)とは、最良優先探索アルゴリズムSSS*を、Alpha-Beta とTransposition Table (TT)を用いて再定式化したものです。

このアルゴリズムは、ルートノードの探索窓を(f － 1,f)としたAlpha-Beta 探索(=NullWindow 探索)を行い、解がf の上下どちらに含まれるかを得ることで、解の含まれる範囲を限定することを繰り返すことにより探索を行う手法です。

置換表 (transposition table) 付きαβ法

置換表に前回の計算結果を保持しておく事で再探索時の計算を削減しています。

このため、置換表に強く依存し探索の非安定性などの問題が存在します。

MTD(f)探索法

あるノードを探索窓(Alpha, Beta)で探索した場合のMinimax値と探索結果の関係

(Alpha, Beta) → x(探索結果)
x <= Alpha → Minimax値はx以下
Alpha < x < Beta →Minimax値はx
Beta <= x → Minimax値はx以上

この関係を用いて、Minimax値の含まれる範囲を限定していくことで解を探索

幅1の窓でのAlpha-Beta探索（NullWindow探索)を繰り返し、あらかじめ用意した解の範囲を制限

オススメ書籍

オセロに強くなりたい人は下記を読むことをお勧めします。

オセロ（将棋等）のプログラムを開発したい人・ゲームプログラマーになりたい人は下記は持っていて損はないでしょう。

ページの先頭へ移動