Tweet

Edax + Top Level Book 2024

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

2024.6 追記: Othello is Solved 不敗ブックを反映

Othello is Solved で使われた15億局面の36か所空き勝敗読みの結果は https://doi.org/10.6084/m9.figshare.24420619 に、それを使って不敗ブックを構成する方法が https://github.com/eukaryo/reversi-scripts にあります（数百G のストレージと長時間の処理が必要）。2024 年版の Top Level Book ではその知識を反映し、着手 - Book 値を表示 で、60か所空き〜36か所空きの確定評価値が太字で、 勝敗が証明された評価値に下線が表示されます ( 0 は引き分け以下)。不敗ブックと異なり手作業が入っているため、多少の誤りはご容赦ください。
ただし次の理由により不敗ブックは進行の追加にはほぼ利用せず、NTest Book と不敗ブックの応手が異なる場合には基本的に NTest Book を採用しています。したがって証明された評価値が表示されるのは NTest Book と一致する部分までになります。 NTest Book にない不敗ブックの分枝（多くは悪手で、普通に応じて勝ちになる）は、ブックサイズを抑えるため記録として分岐後の一手のみ入れてあります。

NTest Book で評価値が同じ応手が複数あった場合には、不敗ブックで証明された応手を優先しています。
NTest Book の未確定評価値が +2 だった場合のみ、不敗ブックで勝ちが証明された進行 (36か所空き以降を補完) で置き換えた部分があります。
NTest Book で +2 だった枝のいくつかが +4 になりましたが、勝敗に関わる誤りが発見されたことはありませんでした。

旧バージョン (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