こちらの記事でアニーリングでゲーム木を解けることがわかったので、実際に量子アニーリングマシンで○×ゲーム（三目並べ、Tic-Tac-Toe）を解くことを目標に、まずBlueqatのシミュレータでやってみます。
今回は○×ゲームのルールそれ自体を量子コンピュータが扱う想定ではなく、予めゲーム木を作成した状態から解くことを目標にします。
○×ゲームのルールに踏み込んで手を考えるやり方はガチプロのブログ記事をご覧ください。
○×ゲームのゲーム木
まず○×ゲームにおいて初期局面から到達可能な局面とその遷移関係を列挙します。
○×ゲームは他の多くのゲームより単純ですが、分岐はそれなりに多いので、合流と対称形の縮約によって局面数を減らしておきます。
| 処理 | 局面数 | 二分木変換後のノード数 |
|---|---|---|
| （なし） | 549946 | 510335 |
| 合流 | 5478 | 12605 |
| 合流+対称形 | 765 | 1607 |
※二分木変換の際に子ノードが1つの局面は子局面に統合される
合流と対称形を考慮すると、先手の初手は中央、隅、端の3手に絞られます。
2x2の○×ゲームを解いてみる
まず小さい問題を解いてみます。
2x2の○×ゲームは明らかに先手の勝ちで、対称形を考慮すると4局面しかありません。
q0とq1を先手勝ちの末端局面、q2を後手の手番局面、q3を初期局面とします。
import numpy as np
from blueqat.opt import Opt
print(Opt().add("(q2-(q0+q1)/2-1/4)^2 + (q3-(q0+q2)/2+1/4)^2").add(np.diag([-1,-1,0,0])).run(shots=100))
結果、4局面すべてで先手勝ちという結果が得られました。
動作が確認できたので3x3の問題に戻ります。以下ではソルバーに投げる目的関数の式は自動生成しています。
全体を一気に解いてみる
1607変数くらいならと思って手元のマシンでやってみましたが、ソルバーの初期化に時間がかかり過ぎるので諦めました。
4手進めて100変数程度にしたところ、たまに解けることもあるのですが失敗が多かったです。
ですので全体を一気に解くのは、工夫しないと精度的にも難しそうでした。
妥協して、少しずつ解いて全体の結果を得る
本来なら全体を一気に解きたいところですが、仕方がないので小さな問題ごとに解いてみました。
ゲーム木における値が未確定なノードを末端側から順に抽出し、子ノードと合わせて一定ノード数程度の小さな部分グラフ（連結である必要はない）を抜き出してそれを解きます。
解かれたノードはand/orノードから末端ノードに変化し、どのノードからも遷移が無くなった（全ての親の値が定まった）ノードは消去します。
残ったノードがなくなるまでこれを繰り返すことで、最終的には全ての局面の勝敗がわかります。
今回は部分グラフのノード数が10以上になったところで、抽出を終了しアニーリングに入る設定としました。
結果
引き分けを先手勝ちとした場合と負けとした場合の違いは末端ノードの初期値だけで、手順に差はありません。ともにアニーリングを338回繰り返すことで解けました。
| 条件 | 解析結果 | 先手勝ち局面数 |
|---|---|---|
| 引き分け先手勝ち | 先手勝ち | 563/765 |
| 引き分け後手勝ち | 後手勝ち | 412/765 |
条件によって勝敗が異なるので、○×ゲームの結果は引き分けという結果になりました。
また下記の判定により全ノードで正しい値が得られていることが確認できたため、○×ゲームの解を示すことができたと言えます。
解けたかどうかの判定
今回アニーリングによって最小化した目的関数は、全ての項の最小値を達成した場合に全体が最小になることがあらかじめわかっており、目的の解以外で最小値を達成することができません。
そのため目的関数の値を見て解けたかどうかを判定することができます。
解けたかどうかの古典計算での判定
全てのandノード、orノードにて結果が矛盾していないかを確かめることで答えの正しさをチェックしています。
NP完全のパズルと異なり、ゲームの計算量は一般にPSPACE困難に属するので、解（局面の勝敗、最善応手列）を与えられても正解かどうかを判定する簡単な（ゲーム木の展開が不要な）方法は一般にはないだろうと予想されています。
おわりに
アニーリングにする意味があったのか考えてはいけません。
もっと長所が活かせるといいですね。