@yuichirominato 2019.02.21更新 369views

マルバツゲームをイジングで解く


はじめに

数独が解けましたので、次はマルバツゲームです。

どうやらマルバツゲームは一筋縄では行かないようです。

戦略

本当は2手先まで読みたいところですが、1手先を読んで相手の勝ちを阻止しながら自分が勝てるようなイジングモデルを作ります。事前に少し検討をしましたが、最初の数手だけはモデルを少し変えてやります。

先手

先手、イジングマシンです。1手先しか読まないのでどこでもいいです。まずはマス目の量子ビットを下記にします。

q0 q1 q2
q3 q4 q5
q6 q7 q8

これでマルバツゲームします。まずは9マスのうち1マスを選びます。

from blueqat.opt import Opt
a = Opt().add("(q0+q1+q2+q3+q4+q5+q6+q7+q8-1)^2",N=9).run()
print(np.reshape(a,(3,3)))

イジングマシン様に選んでいただきました下記です。

[[0 0 0]
 [o 0 0]
 [0 0 0]]

次人間

当然ですが、真ん中を選びます。

[[0 0 0]
 [o x 0]
 [0 0 0]]

次イジング

次、イジングマシン様ですが、縦横斜めがなるべく揃うように選んでもらいます。すでに選ばれているところ、相手が選んでいるところはそれぞれ指定します。

縦横斜めが揃った時に使うのは、縦一列、横一列それぞれの量子ビットを足して二乗します。それを全ての行列でやるともっともコストが高い状態になります。今回はまずは、縦横の条件を使います。

a = Opt().add("10*(q0+q1+q2+q3+q4+q5+q6+q7+q8-2)^2-(q0+q1+q2)^2-(q3+q4+q5)^2-(q6+q7+q8)^2-(q0+q3+q6)^2-(q1+q4+q7)^2-(q2+q5+q8)^2",N=9).add(np.diag([0,0,0,-100,100,0,0,0,0])).run()
print(np.reshape(a,(3,3)))

選ばれました、

[[0 0 0]
 [o x 0]
 [o 0 0]]

次人間

攻略されないようにこちらを選びます。

[[x 0 0]
 [o x 0]
 [o 0 0]]

次イジング

イジングマシンさんの番です。どうやらここで問題発生です。相手が次の手で勝たないように、相手の手を読む必要があります。ということで、ここでは自分の勝ちを最大にする代わりに相手の価値が最大になるパターンを想定してみます。そこにうてば相手の勝ちを阻止できます。

a = Opt().add("10*(q0+q1+q2+q3+q4+q5+q6+q7+q8-3)^2-(q0+q4+q8)^2-(q2+q4+q6)^2+q1*0+q3*0+q5*0+q7*0",N=9).add(np.diag([-100,0,0,100,-100,0,100,0,0])).run()
print(np.reshape(a,(3,3)))

下記が選ばれました、

[[x 0 0]
 [o x 0]
 [o 0 o]]

次人間

もちろん阻止です。

[[x 0 0]
 [o x 0]
 [o x o]]

そしてイジング

この状況で再度一手先を考えます。

[[x 0 0]
 [o x 0]
 [o x o]]
 a = Opt().add("10*(q0+q1+q2+q3+q4+q5+q6+q7+q8-4)^2-(q0+q1+q2)^2-(q3+q4+q5)^2-(q6+q7+q8)^2-(q0+q3+q6)^2-(q1+q4+q7)^2-(q2+q5+q8)^2",N=9).add(np.diag([-100,0,0,100,-100,0,100,-100,100])).run()
print(np.reshape(a,(3,3)))

慣れてきました。

[[x o 0]
 [o x 0]
 [o x o]]

そして人間、最後イジング

引き分けになりました。

[[x o x]
 [o x o]
 [o x o]]

勝敗つきませんでした。縦横斜めのコスト関数の設計が難しくて、斜めパターンと縦横パターンを分けて使っちゃいました。blueqatのOptの設計が甘くて苦労しましたが、ツールを直せばよくなりそうです。

ハイパーパラメータで苦労するかと思いましたが、思いの外いけました。以上です。次回はもちょいリファクタリングしてみたいです。