D-Waveなどの量子アニーリングマシンでゲーム木を解くことができるのか、アニーリングのシミュレータで確かめてみます。
and演算とor演算
ゲーム木の2値バージョンであるand/or木を解くために、and演算とor演算の結果を解とする目的関数を構成します。
具体的には以下の式です。
| 演算 | QUBO目的関数 |
|---|---|
| q0 = q1 and q2 | (q0 - (q1 + q2)/2 + 1/4)^2 |
| q0 = q1 or q2 | (q0 - (q1 + q2)/2 - 1/4)^2 |
詳しく見てみると、
| q0 | q1 | q2 | q0-(q1+q2)/2+1/4 | q0-(q1+q2)/2-1/4 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1/4 | -1/4 |
| 0 | 0 | 1 | -1/4 | -3/4 |
| 0 | 1 | 0 | -1/4 | -3/4 |
| 0 | 1 | 1 | -3/4 | -5/4 |
| 1 | 0 | 0 | 5/4 | 3/4 |
| 1 | 0 | 1 | 3/4 | 1/4 |
| 1 | 1 | 0 | 3/4 | 1/4 |
| 1 | 1 | 1 | 1/4 | -1/4 |
確かにandとorそれぞれが成り立っているときに、二乗した値が最小値を取っていることがわかります。
二分and/or木を解く
実際にシミュレータを使って解いてみます。
今回はオープンソースの量子計算ライブラリであるBlueqatを使っています。
以下のand/or木を解きます。
青ノード 0 をorノード（自分の手番）、赤ノード 1,2 をandノード（相手の手番）、黄ノード 3,4,5,6 を末端ノードとします。
シミュレータで解いてみる
from blueqat.opt import Opt
qstr = '(q0-(q1+q2)/2-1/4)^2 + (q1-(q3+q4)/2+1/4)^2 + (q2-(q5+q6)/2+1/4)^2'
tree = Opt().add(qstr)
print('q0 q1 q2 q3 q4 q5 q6')
for _ in range(10):
print(tree.run())
結果
ノード0~ノード6までの値がリスト形式で得られます。
$ python3 search.py
q0 q1 q2 q3 q4 q5 q6
[1, 0, 1, 0, 0, 1, 1]
[0, 0, 0, 1, 0, 0, 1]
[1, 1, 0, 1, 1, 0, 0]
[0, 0, 0, 0, 1, 1, 0]
[1, 1, 0, 1, 1, 0, 1]
[0, 0, 0, 1, 0, 0, 1]
[1, 1, 0, 1, 1, 0, 0]
[0, 0, 0, 0, 1, 0, 1]
[0, 0, 0, 1, 0, 0, 0]
[1, 0, 1, 0, 1, 1, 1]
確かに q0 = q1|q2 、q1 = q3&q4 、q2 = q5&q6 を満たす組み合わせが返ってきました。
末端ノードに値を入れた状態で解いてみる
実際にゲーム等を解くように、末端ノードに以下のように値を入れて解いてみます。
1が先手の勝ち、0が負けとします。
| ノード | 値 |
|---|---|
| 3 | 1 |
| 4 | 1 |
| 5 | 0 |
| 6 | 1 |
ソルバーの設定の部分だけ変更します。
1を与えるノードには-1、0を与えるノードには+1の重みを設定します。
最小化問題なので、q3^2...の項に欲しい値の逆の符号を掛けることでそちらに引っ張ることができます。
import numpy as np
tree = Opt().add(qstr).add(np.diag([0,0,0,-1,-1,1,-1]))
結果
$ python3 search.py
q0 q1 q2 q3 q4 q5 q6
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 0, 1]
このゲームの値が1（先手の勝ち）であるという結果が返ってきたので成功です。
応用
分岐数の多いand/or木を解く
3つ以上の分岐があるノードを分割して二分木に変換すれば、変数は増えますが同様に解くことができます。
勝敗分の3値のゲーム木を解く
and/or木は2値しか対応していませんが、取りうる値の種類が有限な場合は、最高と最低の値の中間を勝ちと負けのどちらに含めるかを全パターン試すことで解けます。
例えば勝敗分の3値があるゲーム木に対しては、「引き分けを勝ちとした結果」と「引き分けを負けとした結果」の両方の値を得て、勝敗判定結果が変われば引き分けとすることで解決できます。
おわりに
アニーリングでゲーム木を解くことが一応できたので、次回はもっと大規模な問題にチャレンジします。