もともと大学の課題なので、データ構造等は結構適当に定められてしまっています。私が実際に書いたのは、yuha.pl のみ。

tplace.pl

tplace.pl は、reversi の実装のための、簡単な gprolog のプログラムです。今回は、これを用いて reversi を実装することにします。以下、tplace.pl を簡単に説明し、それを使った簡単な思考ルーチンの実装である mak.pl を用いて、対戦させるところまでを一通り見ていきましょう。

ここでは、reversi の盤面を、次の様なリストで表します。

tplace.pl には、次のようなサービス関数(?)が含まれています。

mak.pl は、reversi の思考ルーチンのとても簡単な実装で、盤面に点数を付け、それが最も高いところに置くというものです。いくつか置ける場所がある場合は、もっとも石の数が多くなるところに置く様になっています。これは、実装をみてもらえば、すぐに理解出来るでしょう。

付属の othello.pl による、mak.pl 同士の対戦方法を示しておきます。まず、othello.pl を次の様に起動します。othello.pl の結果保存 directory を適切に変更してから起動して下さい。

次に、別のコンソール等で、次の様に mak.pl を起動します。

これで mak 同士が対戦している筈です。

negascout

alpha-beta pruning については大体の人が分かっていることとして、ここでは、alpha-beta pruning の亜種である、negascout という枝狩り方法について、簡単に説明しておきましょう。

negascout では、alpha-beta pruning の前に、scout (偵察) を行うことで、枝刈りの回数を減らそうと試みます。この scout には、null window search が使われます。null window search は、alpha, beta の値をそれぞれ (alpha, alpha + 1) とすることで、必ず失敗する探索を行い、実際の alpha-beta pruning の範囲を絞り込むことを目的とします。null window search では、制約条件が (alpha, alpha + 1) ととてもきついため、沢山の枝刈りが行われ、この探索は早く終了します。

詳しくは、次のリソース等を参照して下さい。

• null window search

null window search によって値の範囲が絞り込めたら、それをもとに alpha-beta pruning による検索を行います。次のような手順を踏むことになるでしょう。

1. null window search によって得られた score を s とする。
2. s ≧ beta なら、beta pruning する。
3. alpha ≦ s < beta なら、s は実際の値の lower bound になっていることを利用して、(s, beta) で re-search する。
4. s < alpha なら、探索してもどうせ上の階層で alpha-pruning されるので、この node は無視する。
5. alpha, beta を更新し、次の node を search する。

辺と隅の攻防

reversi の醍醐味はなんといっても辺と隅の攻防です。ここでは、プログラムしやすい辺と隅の攻防の典型例についてさらっと書いておきます。こんなことはここで解説することではなくて、その辺のリバーシ講座を見て頂ければと思います。

一般に、辺に打つとき、隅の隣を C 打ち、その隣を A 打ち、真ん中を B 打ちと呼びます。また、隅の斜め隣に打つことを、星打ち (X 打ち) と言います。

1. 隅の隣 (C 打ち、星打ち)は危険なので、通常は評価を下げる。
2. 相手が C 打ちしてきた場合、反対側 A 打ちの評価をあげる (隅が確定するため。)
3. 一般にウィングは悪形。山は好形。ボックスは微妙だが、悪形と普段は見てもよいかも知れない。尚、この評価には大いに例外があるので、要注意。
4. 確定石が取れる場合は評価をあげる。

ちなみに、よくある俗説として、A 打ちが有利というのがありますが、大嘘です。そんなことはありません。また、角を取れば勝てるというものではありません。ストナーズトラップというものがあります。また、星打ちは常に不利ではありません。ウィングを攻撃するときには一般に星打ちをします。

評価関数の作成

reversi において、終盤は全て読み切りすればその評価は最も正しいのですが、中盤は、全て読みきれる訳ではない為、この局面ではどのくらい勝てそうか、ということを適当な評価関数を以て評価しなければなりません。これが最も難しいところで、唯一コンピュータに人間が勝ることが出来る可能性のあるところでもあります。

私は、次のパラメータの線型結合を以て評価関数としましたが、これはとても一般的なものです。最強を目指すにはほど遠いかも知れませんが、この程度でも殆どの人間には勝てます。といいますか、私自身、このプログラムにはまず勝てません。この程度でも、reversi を結構やっている人でないとまず勝てないものが出来ます。

1. 発展的開放度理論
2. 着手可能手数
3. 辺・隅のパターンマッチによる評価

これもその辺のリバーシ講座を探せばいくらでも載っているので、それを探して下さい。ここの記述は、一応参考までに。

尚、マス目に点数をつけるという評価関数では、一般にあまり強くないものが出来てしまいます。得点を動的に変化させる等の手段を講じて対策することも可能ですが、それでもやはりあまり強いものは出来ない様です。

これ以上を目指そうと思うと、数学的根拠や、今までの対戦棋譜から得られる情報等に裏付けられた評価関数が必要になります。興味のある人は logistello に関する論文を読むのが良んで下さい。

ソース一覧

ここで作成したソース等を公開します。ISer の人は、このソースを参考にすること自体は構いませんが、このソースを使うなどして不正行為とみなされても当方責任は負えませんので、そこのところをよろしくお願いします。一応 gprolog で動く筈です。他の prolog は知りません。

ちなみに、学科で行われる 2002 年の reversi 大会は優勝でした。negascout によって、高速な最終読み切りが書けたことが大きかった様です。このプログラムは二級から一級くらいの実力はあるのかもしれません。或いは、凡人がきちんと作れば、すぐに初段レベルのプログラムは作れるのが reversi です。(prolog では多少面倒ですが)

• othello.pl
• tplace.pl
• mak.pl
• yuha.pl

時間があれば、MPC や置換表を実装したかったのですが、如何せん prolog ということもあり、なかなか思うようには行きませんでした。OCaml や C/C++ で再実装しなおせば、より良いものが出来たと思います。

以下のソースはおまけ。

• jouseki.txt (定石集を書こうと思ったが面倒くさくなった。)
• jouseki.ml (定石集を書いて OCaml で処理しようと思ったが、定石集が完成しなかった。手抜き実装。)

References

reversi を実装する際に参考になると思われるところ。

• 日本オセロ連盟
• 鶯教 コンピュータリバーシ講座
• LOGISTELLO’s Homepage
• scout / negascout
• オセロプログラムの作り方
• 強いオセロプログラムについて
• MTD(f)