終盤ソルバ
現在オセロは残り40手ぐらいまでは解析が終わっているらしい。出典を探してみたのだけど今すぐに見つからない。それが正しいとすると、残り40手終盤データーベースを搭載したオセロプログラム同士の対戦は24手までさしたところで勝敗が決まる。
一般的なオセロプログラムは今のところ
- 序盤: opening book(定石)
- 中盤: 評価関数を使った探索
- 終盤: 終盤ソルバ
という感じの構成になっている。将棋でも終盤ソルバ（いわゆる詰将棋ソルバ）を搭載しているソフトウェアが多いが、将棋と違いオセロはパスがなければ必ず64手で終わるため(そしてパスが2回続くことはないので)、将棋と違い終盤ソルバの使いところが明確で、簡単だ。
将棋の場合終盤であることを認識すること、詰将棋ソルバで答えが出る見込がある状態で詰将棋ソルバを走らせることは難しいが、オセロであれば終盤ソルバの能力を予め測っておけば、例えば5秒で12手先までの終盤探索ができるような終盤ソルバを1手5秒マッチで使うのであれば終盤12手は終盤ソルバを使えばよい。
終盤ソルバには他の使い道もある。評価関数のパラメータ学習だ。
棋譜を用いた教師付き学習でも、棋譜を用いない強化学習でも、終盤ソルバを利用することで学習の質を高めることができることが知られている。 例えば棋譜を用いた学習をするとき、棋譜をどこかのゲームサーバーから提供を受けて使うとする。その棋譜の中には上級者同士の素晴らしい戦いもあれば、初心者同士の悪手続きの戦いもある。学習時に、この棋譜の終盤n手について終盤ソルバで修正をかけた棋譜を使うと、修正をかけない場合よりも勝率が高くなることが知られている。
終盤ソルバのアルゴリズム
拙作Flat Reversiでは終盤ソルバにPNS（証明数探索）を使っています。
これがそこそこのスピードで動くので、搭載されているアホみたいな評価関数（手調整）を補って何とか腕の立つ初心者ぐらいの強さになっているようです。
もっと賢いアルゴリズムとしてはdf-pnがあります。PNSが証明数（そのノードを詰ますのに詰みであることを示さなければならないリーフノードの数）だけに依存してノードを調べていくのに対して、df-pnは反証数（そのノードが不詰であることがわかるのに不詰であることを示さなければならないリーフノードの数）も加えてノードを調べるので、効率が良いそうです。
参考文献: df-pn を用いた詰将棋解法の性能向上
さらに普通のミニマックス/アルファベータ探索でも終盤ソルバを作ることができます。終盤以外の点数に意味を持たせなければ必ず終端までノードを展開していくことになるので、終端ノード込みのアルファベータ探索ができます。
さて、今PNS探索をHaskellに移植しています。必要なのはテストケースです。盤面を与えてPNS探索をさせる。結果を期待されている答えと比べる。この手の探索ルーチンの実装はなんとなくでやっているととにかくバグの温床なので、注意深く実装する必要があります。
Zeblaの作者謹製の終盤ソルバをMacで使う
さて、本題ですが、このテストケースを最強オセロソフトの一角、Zeblaに手伝ってもらうことを考えます。Zeblaには超高速な終盤ソルバが入っています。 Zeblaの作者がこの終盤ソルバだけを抽出したコードをウェブ上で提供しているので、これを利用させていただくことにしましょう。
Othello Solver Documentation: Othello Solver: Main Page
$ cc solver.c
でコンパイルできます。出力バイナリにファイル名をつけてあげてもいいです。私はmv ./a.out solverとしておきました。
解凍したzipファイルの中に盤面のファイルがいくつか含まれています。そのファイルの一部を抜き出してtest1.scrを作ってみます。
$ cat test1.scr --OOOOO-X-OOXO--XXOXXOOOXOXXXOOOXXOXXOOOXXXOXOOO--XXOXO----XXXXO O
こんな感じです。-は空白、Xは先手、Oは後手です。最後にスペースを挟んで今どちらの手番かを加えて一行、一盤面です。
解かせるとこんな感じです。
$ ./solver -vv ./test1.scr
実はこれは単なる終盤解析だけでなく、石差を大きくするような探索をしているようです。つまりミニマックス探索の結果です。勝敗探索だけの場合は
$ ./solver -vv -wdl ./test1.scr
とすると出力されます。探索ノード数を見ると勝敗探索のみの場合、ノード数が圧倒的に少ないことがわかります。
というわけで
終盤ソルバを手に入れたので、答え合わせがいつでもできますね。実装に入りましょう。
参考文献: