はじめに

どうも、y-tetsuです。

今年のオセロの一番の話題と言えば、何と言っても「Othello is Solved(オセロが解かれた)」という論文だったのではないでしょうか。そして、論文発表にどよめき立っている最中、タイムリーに書かれた、にゃにゃんさんの解説記事「Othello is Solved 論文解説 (私見)」にも、これまた大きな衝撃を受けました。

論文の内容や解説記事に触れて、一口にゲームを解くといっても、"弱解決"や"強解決"といった考え方がある、という事に個人的に新たな気付きがありました。

本記事は、ゲームを「解く」という言葉に当てられた筆者が、サイズの小さな様々な形の盤面にて、リバーシゲームの"強解決"を行い、最善手の棋譜を手に入れてみよう！というものです。

最終的には、自分で作った好きな盤面で神のごときAIと遊べる、リバーシのゲームが(ついでに)完成しました。

ここでは8x8以外の盤面形状や、通常とは異なる石の初期配置にて、以下のオセロと同じルールに基づいたゲームをリバーシと呼ぶものとします。

相手の石を自分の石で挟むとひっくり返せる
より多く石を取った方の勝ち

リバーシの強解決までの道のり

強解決とは

8x8オセロは"弱解決"された、という事なのですが、これはすごく乱暴に言うと、結局全手を読んでいる時間がないため、引き分けとなるであろう結果を前提に工夫して、読む手を減らすことで最善手を求めた、と考えられます。

もっと空いているマス目が少なければ、当然ながら、探索の総数が大幅に減り、全ての手を読んで最善手を求める"強解決"が試みれます。実際にマス目の少ない、4x4や6x6は全ての手が解析されていますからね。強解決ができるなら神AIも作れるはず！

みなさん、"強"って響き、よくないですか？弱よりも"強"で行ってみましょう！！

ところで、8x8の空きマスが60マスより少ない任意の盤面にて、一体どこまで"強解決"ができるものなのでしょうね。

強豪ソフトの力を借りる

「Othello is Solved」の論文では、ゲームの解析のために、Edaxという強豪ソフトが使われておりました。

マス目を少なくするとはいえ、得たいの知れない形を変えたボードの最終局面までを一気に読み切るには、なるべく高速で正確な探索能力が欲しいところ。今回の試みでは、1からソフトを作り上げるよりも、既に実績のあるEdaxの力を借りる方が、一番の近道だと判断しました。

強解決のための設定変更

Edaxはオプション指定により、読む手の深さを変えることができるようになっております。

今回は、終局まで読み切る神のモードとして、60手先まで読むようにデフォルトの設定を変えます。通常の8x8の盤面ですと、一生かかっても計算は終わりませんが、今回は小さな盤面を想定しているため、ある程度の時間で終了するはずです。

また、ボードの形も通常と異なるものを想定しているため、Book(8x8での良い打ち手のデータベース)を元に手を選ぶ機能は無効化しておきます。

ソースの変更内容を以下に示します。

(src/options.c)

	false, // debug cassio
	true, // transgress cassio

-	21, // max level
+	60, // max level
	TIME_MAX, // infinite time
	EDAX_FIXED_LEVEL, // play-type
	true, // can ponder

	:

	NULL, // book file
-	true,            // book usage allowed
+	false,           // book usage not allowed
	0,               // book randomness

変形ボードの実現

Edaxの盤面表現には、ビットボードが用いられています。下図のように8x8=64マスに置かれた黒と白の石を、2つの64ビット変数を使って表しています。また、黒と白の両方が置かれていない部分は"空きマス"として扱っています。

上図は、盤面の行ごとに石のあり(1)、なし(0)をビットで表したものです。プログラム内部では、これを上から順番につなぎ合わせて、64マスを1列にし、64ビット変数に格納して扱っております。

本記事では、変形ボードを表現するために、上記に加えて"Hole(穴)"という概念を導入します。黒でも白でも空きマスでもない、ぽっかり空いた穴として、64ビット変数をもう1つ追加しています。

イメージを以下の図に示します。(黒く塗りつぶされた部分が"穴"を表しています)

ここからどのようにEdaxを改造するかというと、結果は単純なものです。

ずばり、プレイヤーが次に打てる手の候補から"穴"の部分を除外するという変更を加えます。

具体例として、以下のような盤面を考えてみます。

上図にて、黄色の星印が8x8の盤面で打てる手の候補になります(手の候補もまた、同様に64ビット変数で表現されています)。

ここで、一番右下の手は"穴"の位置に存在しています。今回の改造では、この様に穴の位置にある候補手を、強制的に除外し、打てないようにします。

Edaxに備わっている、"候補手を求める"といったコアなビットボードの演算部分を下手にいじってしまうと、結果が合っているのかどうかすら怪しくなりそうでした。そのため、筆者の理解が辛うじて可能なものとして、このような変更方針をとっております。

Edaxの実装では、黒と白いずれも次に打てる手がなくなったらゲーム終了と判断しており、結果オーライではありますが、今回の対応でも成り立つようです。

ソースの変更内容を以下に示します。

(src/board.c) … 初期ボードを4x4に変更

	#include "count_last_flip_kindergarten.c"
#endif

+unsigned long long H = 0xFFFFC3C3C3C3FFFFULL;  /* 4x4 square */

/** edge stability global data */
static unsigned char edge_stability[256][256];

(src/board.c) … 打てる手の候補から穴を除外

		| get_some_moves(P, O, 8)   // vertical
		| get_some_moves(P, mask, 7)   // diagonals
		| get_some_moves(P, mask, 9))
-		& ~(P|O); // mask with empties
+		& ~(P|O|H); // mask with empties

#endif
}

Pがプレイヤー、Oが相手の石の配置を表しています。もともと~(P|O)にて空きマスを表し、手の候補(get_somve_movesで取得た前準備のもの)とANDを取って、最終の手の候補としていました。穴を表すHを空きマスから除外することで、穴の位置には手を打てないようにしています。

その他、以下の変更を加えておりますが、煩雑なためソース差分の説明は割愛させていただきます。詳細は、以降に記載しております「補足1」で示している、改造ソースを参照して下さい。

ユーザー入力の場合においても、穴の箇所は打てないようにする
空きマスの表示文字を変える
空きマス数の表示から、穴の数を減らす
"setboard"コマンドで、任意の盤面に設定変更できるようにする

棋譜の表示オプション

おまけで、現在までのゲーム進行の"棋譜"を表示するコマンドを追加しておきます。元々の機能でファイルに出力するものはあったのですが、個人的な「画面上で素早く棋譜を確認したいなぁ」という思いを叶えるものは無さそうでしたので、追加しています。

(src/edax.c) … コマンドを追加

			} else if (strcmp(cmd, "a") == 0 || strcmp(cmd, "analyze") == 0 || strcmp(cmd, "analyse") == 0) {
				play_analyze(play, string_to_int(param, play->n_game));

+			// display a game record
+			} else if (strcmp(cmd, "d") == 0 || strcmp(cmd, "display") == 0) {
+				play_display(play);
+
			// set a new initial position
			} else if (strcmp(cmd, "setboard") == 0) {
				play_set_board(play, param);

(src/play.c) … 棋譜表示をする関数を追加

+/**
+ * @brief Display the game record.
+ *
+ * @param play Play.
+ */
+void play_display(Play *play)
+{
+	int i, org_player;
+	char s[4];
+	Move *move;
+
+	org_player = play->player;
+	play->player = play->initial_player;
+	for (i = 0; i < play->i_game; i++) {
+		move = play->game + i;
+		if (move->x != PASS) {
+				fprintf(stdout, "%s", move_to_string(move->x, play->player, s));
+		}
+		play->player ^= 1;
+	}
+	putc('\n', stdout);
+	play->player = org_player;
+}

ゲーム中に

>d

や

>display

と打てば、以下のようにコンソールに棋譜が表示されるものとなっています。

>d

F5f6E6

先手(黒)は大文字、後手(白)は小文字で表記しております。

最初のターゲット

4x4で早速試してみましょう。こちらは後手(白)が必勝(黒:3、白:11、空:2)という解析結果が既に出ております。その通りの結果が出たら「OK」と判断することにしましょう。


  A B C D E F G H            BLACK            A  B  C  D  E  F  G  H
1                 1         0:00.000       1 |  |  |  |  |  |  |  |  | 1
2                 2    2 discs   4 moves   2 |  |  |  |  |  |  |  |  | 2
3     - . - -     3                        3 |  |  |  |  |  |  |  |  | 3
4     . O * -     4  ply  1 (12 empties)   4 |  |  |  |()|##|  |  |  | 4
5     - * O .     5    Black's turn (*)    5 |  |  |  |##|()|  |  |  | 5
6     - - . -     6                        6 |  |  |  |  |  |  |  |  | 6
7                 7    2 discs   4 moves   7 |  |  |  |  |  |  |  |  | 7
8                 8         0:00.000       8 |  |  |  |  |  |  |  |  | 8
  A B C D E F G H            WHITE            A  B  C  D  E  F  G  H

>

以下のコマンドを打つと、Edax同士の対戦が始まります。

>m 2

出ました！


  A B C D E F G H            BLACK            A  B  C  D  E  F  G  H
1                 1         1:10.298       1 |  |  |  |  |  |  |  |  | 1
2                 2    3 discs   0 moves   2 |  |  |  |  |  |  |  |  | 2
3     * - - *     3                        3 |  |  | 5|  |  | 7|  |  | 3
4     O O O O     4       Game over        4 |  |  |10|()|##| 4|  |  | 4
5     O O O O     5       White won        5 |  |  | 8|##|()| 1|  |  | 5
6     * O O O     6                        6 |  |  | 9| 6| 3| 2|  |  | 6
7                 7   11 discs   0 moves   7 |  |  |  |  |  |  |  |  | 7
8                 8         0:00.937       8 |  |  |  |  |  |  |  |  | 8
  A B C D E F G H            WHITE            A  B  C  D  E  F  G  H

*** Game Over ***

上記の通り、3-11で白の勝ちです。狙い通り動いていそうです！！

>d

F5f6E6f4C3d6F3c5C6c4

という事で、4x4の最善手の棋譜をゲットしました。

いくつかの最善手の棋譜

この調子でどんどん調べていきましょう！

お次は"6x6"で！！

……と行きたいところでしたが、残念ながら32マス空きは、すぐには終わる気配がなく、断念しました。ちょい残念…。

6x6の神との対戦は、以下にお任せすることにします。

結局、20マス空きぐらいの小さな盤面限定ですが、いくつか調べてみました。小さくても、ひっそりと眠っていた答え(最善手の棋譜)が、得られたことには変わりはありません！

筆者選りすぐりの「Reversi is Solved」な結果(No.1～No.7)を列挙しておきたいと思います。是非みなさん、ご覧ください！！

No.	1
名称	4x4
盤面	" ---- -wb- -bw- ---- b"
棋譜	F5f6E6f4C3d6F3c5C6c4
スコア	先手:3、後手:11
進行

No.	2
名称	十字
盤面	" -- -- --wb-- --bw-- -- -- b"
棋譜	E6f4D3e7G4e3F5g5E2d2D7d6C4b4B5c5
スコア	先手:8、後手:12
進行

No.	3
名称	風車
盤面	" -- ----- -wb-- --bw- ----- -- b"
棋譜	F5d6C4f4C5f6G4b5B6e3F7c3D3c6E6f3C2e7G3d2
スコア	先手:15、後手:9
進行

No.	4
名称	卍
盤面	" ---- - -- - --wb-- --bw-- - -- - ---- b"
棋譜	D3c5B6b5B4e3F5e6D7e7F7g5G4g3E2f4c2D2c4B2d6
スコア	先手:15、後手:10
進行

No.	5
名称	X
盤面	"-- ----- --- ---- wb bw ---- --- ----- --b"
棋譜	E6f6D3d6F7e3G7c3F3h8C6c7H7B2a1C2A2
スコア	先手:11、後手:10
進行

No.	6
名称	外側に石
盤面	"wwwwbbbbwbbbwwwbwb----wbwb----wbbw----bwbw----bwbwwwbbbwbbbbwwwwb"
棋譜	F3c3F4f6E3d3C6c4C5f5D6e6
スコア	先手:30、後手:30
進行

No.	7
名称	リング
盤面	" ---- -wwbb- -wwwbbb--ww bb--bb ww--bbbwww- -bbww- ---- b"
棋譜	A3a5D1h3H5c8F8f1E8d8G2c1B2e1H6a6A4b7h4g7
スコア	先手:18、後手:30
進行

※こちらは打てる手が多く、解析にやや時間がかかります(最大2分程度)。試される場合はご注意ください。

対戦方法

ここでは、お好きな盤面で、最強AIと対戦する方法をご紹介します。事前にページ下部の「補足1」「補足2」を参照し、改造ソフトのビルドが済んでいる事を前提に話を進めます。

Edaxの起動

コンソールにてEdaxを起動してください。正常に動いている場合、以下の画面が表示されると思います。

>edax-4.4

>edax-4.4

  A B C D E F G H            BLACK            A  B  C  D  E  F  G  H
1                 1         0:00.000       1 |  |  |  |  |  |  |  |  | 1
2                 2    2 discs   4 moves   2 |  |  |  |  |  |  |  |  | 2
3     - . - -     3                        3 |  |  |  |  |  |  |  |  | 3
4     . O * -     4  ply  1 (12 empties)   4 |  |  |  |()|##|  |  |  | 4
5     - * O .     5    Black's turn (*)    5 |  |  |  |##|()|  |  |  | 5
6     - - . -     6                        6 |  |  |  |  |  |  |  |  | 6
7                 7    2 discs   4 moves   7 |  |  |  |  |  |  |  |  | 7
8                 8         0:00.000       8 |  |  |  |  |  |  |  |  | 8
  A B C D E F G H            WHITE            A  B  C  D  E  F  G  H

>

ボードの設定を変える

以下のように、setboardコマンド使うと、任意の盤面に変更できます。

>setboard "           --      --    --wb--  --bw--    --      --           b"

>setboard "           --      --    --wb--  --bw--    --      --           b"


  A B C D E F G H            BLACK            A  B  C  D  E  F  G  H
1                 1         0:00.000       1 |  |  |  |  |  |  |  |  | 1
2       - -       2    2 discs   4 moves   2 |  |  |  |  |  |  |  |  | 2
3       . -       3                        3 |  |  |  |  |  |  |  |  | 3
4   - . O * - -   4  ply  1 (16 empties)   4 |  |  |  |()|##|  |  |  | 4
5   - - * O . -   5    Black's turn (*)    5 |  |  |  |##|()|  |  |  | 5
6       - .       6                        6 |  |  |  |  |  |  |  |  | 6
7       - -       7    2 discs   4 moves   7 |  |  |  |  |  |  |  |  | 7
8                 8         0:00.000       8 |  |  |  |  |  |  |  |  | 8
  A B C D E F G H            WHITE            A  B  C  D  E  F  G  H

>

setboardコマンドの引数は、64マスのマス目を1行で表したものです。最後の65マス目は手番を表しています。

文字の種類	意味
b	黒の石
w	白の石
-	空きマス
" "(半角スペース)	穴

対戦相手を変える

以下のように、modeコマンド使うと、対戦相手を変更できます。

>m 2

引数の値	意味
0	先手:ユーザ、後手:Edax
1	先手:Edax、後手:ユーザ
2	先手:Edax、後手:Edax
3	先手:ユーザ、後手:Edax

盤面の情報


  A B C D E F G H            BLACK            A  B  C  D  E  F  G  H
1                 1         0:00.000       1 |  |  |  |  |  |  |  |  | 1
2       - -       2    2 discs   4 moves   2 |  |  |  |  |  |  |  |  | 2
3       . -       3                        3 |  |  |  |  |  |  |  |  | 3
4   - . O * - -   4  ply  1 (16 empties)   4 |  |  |  |()|##|  |  |  | 4
5   - - * O . -   5    Black's turn (*)    5 |  |  |  |##|()|  |  |  | 5
6       - .       6                        6 |  |  |  |  |  |  |  |  | 6
7       - -       7    2 discs   4 moves   7 |  |  |  |  |  |  |  |  | 7
8                 8         0:00.000       8 |  |  |  |  |  |  |  |  | 8
  A B C D E F G H            WHITE            A  B  C  D  E  F  G  H

>

左側のマス目について、表示文字はそれぞれ以下を表しています。

表示文字	意味
*	黒の石
O	白の石
_	空きマス
" "(半角スペース)	穴
.	手を打てる箇所

手を打つ

以下のように、マス目を指定すると、手を打てます。

>f5

また、打てる場所がない場合は、passを指定するとパスできます。

>pass

pasやpaでも同じくパス可能です。

ゲーム終了後もう一度遊ぶ

以下のように、initコマンド使うと、もう一度初期盤面から遊べます。

>i

必勝の手番をEdaxに設定する事で、最善手しか打たない、全てを見通す神との対決が可能です。是非お好きな盤面で遊んでみて下さい。

逆に、必勝の手番を自身に設定し、如何に最善の立ち回りができるかを試すのも一興です！

おわりに

今回は盤面を変えた"リバーシ"の強解決を試みて、最善手の棋譜を探してみてはどうだろう？と、筆者なりに模索してみました。

大した工夫をしていない、という事もありますが、ゲームとして遊べるサイズは思ったより小さかったなという感想でした。

冬休みにでも、本記事を元に、まだ見ぬ神の棋譜探しに挑戦していただける方がおられましたら、大変うれしく思います。

それでは皆様、よきリバーシ・ライフを！

補足1 : Edaxの改造ソース

今回改造したソースは以下においております。

以下の「Download ZIP」よりダウンロードしてください。

補足2 : Edaxのビルド

Windowsの例ですが、ビルド方法を残しておきます。「補足1」のソース取得後に実施して下さい。

1. MinGWのインストール

以下を参照しました。
https://qiita.com/kzrashi/items/4e0ab5949b69d4b333dd

2. makeのインストール

以下を参照しました。
https://qiita.com/avimigo/items/f501f44a8d44e3fd6987

3. binフォルダ作成

アプリケーションの実行体作成用にbinフォルダを用意します。

edax-reversi-4.4
  bin/      ← 作る
  include/
  src/
  .hgignore
  README.md

4. srcフォルダに移動

scrフォルダに移動してください。

5. ビルド実行

以下を実行してください。(Windows用)

make build ARCH=x64 COMP=gcc OS=windows

6. アプリケーションの生成

binフォルダ以下に、"wEdax-x64.exe"が生成されると思います。

本記事のコードで動かすためには、"wEdax-x64.exe"を"edax-4.4"にファイル名を変更(拡張子も削除)した後、所定のフォルダに置いて下さい。

7. eval.dat配置

6.で"edax-4.4"を置いた場所に、下記の"eval.7z"をダウンロード&解凍して得られた"data"フォルダを配置して下さい。

補足3 : 変形ボードの設定値

変形ボードの一行表記の設定値は、以下のサイトを使うと簡単に取得できます。(筆者作)

上記サイトにアクセスすると、以下のような画面が表示されます。

さらに下にスクロールするとさらに、次の画面が表示されます。

これは何かというと、リバーシの盤面を自由に編集できるウェブアプリケーションです。(JavaScript製)

パレットから、空きマスや石を選んでキャンバスをクリックすると、お好きな盤面が描けるようになっております。

盤面が完成したら、変形ボードの設定値が以下に表示されるので、コピペしてEdaxに入力して下さい。

(操作のイメージ)

補足4 : 棋譜の再生

先ほどと同じサイトで、棋譜を入力して再生することができます。

本記事を元に探索して手に入れた、あなただけの神の棋譜を、お酒でも飲みながら是非眺めてみて下さい。