Tweet

Edax + Unified Book 2010 (Beta)

(世界のトップレベル リバーシプログラムの一例)
2013年2月17日放送のTV番組「ほこ×たて」で、「最強のオセロプログラム」が取り上げられました。 リバーシ(オセロ)プログラムを取り上げていただくのはありがたいことですが、 両者確かにそこそこ強いプログラムではありましたが、頂上決戦と言うには少々残念な内容でした。 「最強のプログラムと言ったら、Logistello, Zebraの流れを汲む、 SAIO, Edax, NTest, MasterReversi とかじゃないの?」と思われた方も多いのではないでしょうか。

リバーシはまだ解かれてはいませんが、トッププログラムの間では、最善進行の研究(Book)が相当進んでいます。 これらは各開発者が、プログラムを24時間、何年間も走らせて求めたもので、 対戦時にはBookを抜けたときにはもう完全読み、ということも珍しくなくなりました。
wikipediaによれば、 トッププログラムが負ける率は1%以下とのこと。 トッププログラム同士の対戦は、ほとんどが引き分けと、矛盾のない結果になります。

バラエティ番組の演出についてとやかく言うつもりはありませんが、 「最強」を鵜呑みにされる方がいても困りますので、Edaxの最新バージョンに、 Booby Reversi風GUIと、先人たちが長年に渡り積み上げ、ネット上で公開しているBook を統合して作ったBook(独自形式・編集は不可)を組み合わせて、そのまま実行可能なパッケージを作ってみました。
公開されているデータだけを使用していますので、これより強いBookを持っている人もいると思いますし、 また最新のデータともいえませんが、トッププログラムのベンチマークにはなるのではないでしょうか。
これらはオープンソースですので、誰でも派生物として(GPLライセンスの元で)、 このレベルのプログラムを作ることが可能です。

下のリンクの ZIP ファイルをダウンロードして、すべて展開してから、 edax+ub\bin ディレクトリ内の sreversi.exe を起動してください。


Book Sources

Edax Opening Book Skeleton 2009 by Richard Delorme
Edaxを用いて数年かけて生成した最善進行Bookで、24ヶ所空きでの引き分け確定の進行が10万通り以上含まれます。 最善進行(引き分け)のみのBookですので、31手目以降の主な(負けになる)変化を補ってあります。

NTest s26 book 2010 (80001 draws) by Daniel Lidstrom
Chris Welty による NTest は 2004 - 2005 にかけて「最強のプログラム」「不敗のプログラム」と呼ばれていました。 NTestは2005年に引退しましたが、その後Daniel Lidstromが分散コンピューティングも可能なBook構築環境と、 得られたBookを公開しています。このBookには 29ヶ所空きで引き分け確定の進行が80001通り含まれるとのことです。
(必然的に、Edax Bookとは多くの部分が重複します。)

Logistello book skeleton 1998 by Michael Buro
歴史的には重要なBookですが、現在では精度的に前記2者に劣ります。敬意を表し補助的に使用しています。 サイトで公開されているBookは24ヶ所空き勝敗読みですが、30ヶ所空き完全読みで修正してあります。

WZebra extra-large Book 2008 (tosapyのHP)
Jan C. de Graaf がWZebraで構築したBook。サイズ的には非常に充実していますが、中盤の精度はやや劣ります。 部分的に参考にしています。

定石&終盤30手最善手順 (長谷川 彰氏)
最善手順の部分を検証の参考にさせてもらっています。

2014.1 追記: HAYABUSAの技術概要

2013年9月22日放送の「ほこ×たて」でふたたび勝利を収めたHAYABUSA、 こちら で技術概要が公表されています。 これを読むと、現在のトッププログラムと同様の手法を用いているようです。

Logistello, Edaxと共通

Edaxと共通

Bookの構築も進んでいるようですので、現在はトッププログラムの域に達していてもおかしくはありません。 あまり目新しいところはないものの、短期間でキャッチアップするのはさすがプロ、といったところでしょうか。
ただ、
・対戦成績から考察すると、ブック次第ではあるが、現状では、Edaxを、若干、上回る程度の強さと思われる。
は本当でしょうか。
両者Bookなしで対戦させて勝ち越すようなら、(同様のアルゴリズムを用いているなら) 評価値テーブルのチューニングがより優れている、または実装が優っていてより深く探索できるということで、 それはそれで評価に値しますが、それならそのように書いた方がいいですね。
Book使用での優劣はまさにBook次第なのですが、Edaxは自身のBookは上記のSkeleton 2009を除いて公開していないと思いますが、 どのようにして比較したのでしょうか。 仮にここにあるようなBookを使って評価しているなら、上に書いたようにこれは最新のBookではありませんし、 私も私家版としてはさらに研究の進んだBookを持っています。自信がおありなら、挑戦お待ちしております。


奥原 俊彦

Booby Reversi Home