オセロ（リバーシ）の作り方 ～高速化～

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

αβ以外にも様々な高速化の為のアルゴリズムは存在します。しかしながら今回の実装では行わなかったので多くは触れませんし、基本はαβに基づくものなので、その関連の書籍を見る事をお勧めします。

研究報告でもこの様に記述されています。

「ゲーム木探索アルゴリズムはαβ探索を中心としてさまざまなものが提案されいる。これらはコンピュータチェスやコンピュータリバーシ及びコンピュータ将棋においてその探索効率の比較が行われている。αβ探索、aspiration探索、PVS探索、negascout探索を実装した将棋プログラムにより、将棋のゲーム木に対し探索効率の比較を行った。その結果、PVS探索とnegascout探索においてはチェスと同様に将棋のゲーム木探索においてもαβ探索よりも効率的であることが確認できた。」

【引用】鈴木豪, 乾伸雄, 小谷善行: "将棋におけるゲーム木探索アルゴリズムの比較",
ゲーム情報学, 1999, pp. 1-11

αβ法以外のゲーム木探索

現在私自身が調査中です。理解したり、内容が分かり次第載せていきたいと思います。

・MTD-best

評価値の最大値を求めるものではなく、最善手だけを求める手法。具体的には、ある手の評価値の下界が他の手の評価値の上界よりも大きければそれは最善手である、と言う事象を利用し、上界と下界だけから最善手を探すも。これだけ聞くと凄いが、オセロやチェス等で実際にテストしてみると MTD-f よりも遅い時がある。

・MTD-bi

上限と下限の値の中間値を次の閾値に設定する手法。

・MTD-step

開始時の閾値を+∞とし、次の閾値にかんしては、得られた値よりもいくらかの幅(step)だけ、マイナス方向へ大きく飛ぶようにする手法。つまり一回のMT呼出しごとに小さなジャンプを繰り返すのではなく、一回で大きなジャンプを行なおうとする手法。

・MTD+∞

一つ目の設定項目である閾値の初期値を+∞に設定し、次の閾値に前回の探索の結果得られた値を使用する手法。上限の値を徐々にミニマックス値へと近づける手法。その場合Maxノードは全展開し、Minノードは一つだけ展開するようになる。SSS*と同様の探索手法。

・MTD-∞

MTD+∞との相違点は、開始時の閾値を-∞にすることである。一見するとMTD+∞と差がないように思われるが、実際にはある深さにおける探索量に変化が現れる。下限値を徐々にミニマックス値へと近づける手法。その場合Maxノードは一つだけ展開し、Minノードは全展開するようになる。

・NegaC*

MTD-f とたいして変はらないらしい。正確には MTD-bi に近いアルゴリズム。

・SSS*

探索が効率良く行なえるが、記憶容量を多大に必要とすることや手の並び変えに時間を要するなどの理由で、実際に実行するのは難しいとされている。この後、SSS*のような最良優先探索を深さ優先探索に置き換えて実行するMTDという手法が提案された。

・DUAL Credit 探索

先手と後手のそれぞれの指し手にクレジットを与え、どちらか片方のクレジットが貯まった時点で深さに変換して、探索延長を行う。

・DUAL*

・PAB探索

Principal Variation Alpha-Beta。前回の最善手を最初に探索して、それ以外の手はすべて悪いだろう、という仮定の元にαβの範囲を+1にして探索する方法。探索が成功すれば（悪いことが判明すれば）効率は上がる。もし、失敗した場合は再度、αβの範囲を広げて再探索する必要がある。

・PVS探索

PABで、再探索をした場合にも、その下のノードで新たに+1の幅の探索をする方法。

オススメ書籍

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

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

ページの先頭へ移動