Tweet

Edax + Top Level Book 2023

(世界のトップレベル リバーシプログラムの一例)
2013年にTV番組「ほこ×たて」（その後他テーマでのやらせ問題で打ち切りになってしまいました）で「最強のオセロプログラム」が取り上げられられたのをきっかけに、 当時公開されていたトッププログラムと先人たちの Book を統合した例として、このページで Edax + Unified Book 2010 を公開しました。
それから10年、ついにオセロが引き分けであることが証明されたとの論文 "Othello is Solved" が出され、 オセロ対戦に矛盾が入る余地がないことが証明されました。 (ただし弱解決ですので、最善進行から勝ちになる変化がないことが証明されただけで、他にも多数の引分け進行があることが予想されていますが、それらが引分けか負けかは求められていません。)
もはや「最強」を論ずる必要もなくなりましたが、その間には NTest の作者 Chris Welty と Edmund Yiu による力作 NTest Opening Book の公開もありましたので、 Unified Book にそれも統合して 2023年時点でのトッププログラムのベンチマークとして Edax + Top Level Book 2023 を作ってみました。 (Book は独自形式・編集不可)
Unified Book 2010 の 32か所空きまでの引き分け進行は NTest Opening Book でほぼ網羅されており、 結果的には Top Level Book 2023 は NTest Opening Book に対し 32か所空き以降のバリエーションを追加したものに近くなっています。 これも NTest Opening Book の完成度の高さを示していると言えるでしょう。もちろん上記論文の最善進行も含まれています。
Top Level Book と NTest Opening Book の対戦はほぼ 100% 引き分けになります。Book 外の勝ち筋はもちろん、新たな引き分け筋を見つけるのもかなり難しくなっているように感じます。

NTest もトッププログラムの一つで、NTest + NTest Opening Book で現在でもほぼ「不敗のプログラム」になりますが、マルチスレッドに対応していないため速度の点では劣ります。 そのため今回もエンジンには Edax を組み合わせています。
Edax は Richard Delorme による有名なプログラムですが、強さはそのままに (対応CPUではAVX2を使い) 私が 高速化したバージョンを同梱しています。 （高速化の手法はbitboardとそれ以外の各ページで解説しています。） Top Level Book は使用できませんが、高速な Edax として単体でもご使用いただけます。"Othello is Solved" 論文でも、Edax-AVX の改良版が使用されています。

ダウンロードが始まらない場合は・・
If download does not start . . .

このサイトは https に対応していません。「安全でないダウンロードがブロックされました」などが表示された場合は、 ブラウザのダウンロード履歴から「保存」を選んでください。
This site does not support https secure transfer. If a message like "(file) can't be downloaded securely" is shown, click "Save" button in the download history menu of the browser.

旧バージョン (2013-22): Edax + Unified Book 2010

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

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

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

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ですが、現在では精度的に前記２者に劣ります。敬意を表し補助的に使用しています。 サイトで公開されているBookは24ヶ所空き勝敗読みですが、30ヶ所空き完全読みで修正してあります。

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

定石＆終盤30手最善手順 (長谷川 彰氏)
最善手順の部分を検証の参考にさせてもらっています。
market://search?q=Booby+Reversi

2020.8 追記: Android 版

Booby Reversi 有料版 (¥200) のレベル５で、Edax + Unified Book 2010 を使用するようになりました。
neon を含む arm64 ネイティブで最適化されています。
Android リバーシアプリとして世界最速最強レベルになりました。

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