クアルトとは

ちょっとマイナーなゲームなので少し説明すると、クアルト(Quarto)は、スイスの数学者ブレイズ・ミュラーによって1991年に考案された2人用のボードゲームである。by Wikipedia
ルールの説明にはこの動画がわかりやすいので、このあとの解説のためにも一度見てほしい。

なぜクアルトのAIにモンテカルロ木探索を選んだか

クアルトのAIを作ることになったとき、当初は将棋などに使われている評価関数の概念をうまく実装できないか検討していたが、クアルトのコマは敵味方の区別がなく、ある時点の盤面を見たときにどちらのプレイヤーが有利か判断が難しいと思ったのでこれを断念。
そんな中なにか良い方法は無いかとネット上を探し回ってモンテカルロ木探索という手法を発見。
理屈が比較的簡単なうえ、クアルトは適当にプレイしても最大16手(コマ選択も含めると32手？)で必ずゲームが終了するという点からも相性がいいと考えてこの手法を採用。
最終的に１ヶ月強しかなかった開発期間でかなりの性能が発揮できたのでこの選択はあたりだったと思う。

モンテカルロ木探索の仕組み

モンテカルロ木探索は以下のステップを繰り返すことで最適解を見つけ出すアルゴリズムである。

ノードの選択
展開済みのゲーム木のノードの中からプレイアウトを行うノードを選択していく。葉ノードに到達するまで選択を繰り返す。
ゲーム木の展開
１で選択した葉ノードからゲーム木を展開する。これを無制限に行うと膨大なゲーム木を生成してすぐにメモリを食い潰してしまうので実際に行う際は『５回以上プレイアウトが行われた場合』のように無駄に展開されないよう制限をかける
プレイアウト
乱数によるシミュレーションを行う。要は適当に手を進めてゲームを終了させる。
プレイアウト結果の伝達
葉ノードで行ったプレイアウトの勝敗をゲーム木の根の方へ伝達させる。

これらのステップを決まった回数、または時間が許す限りひたすら繰り返し、勝率の高い手を見つけ出す。

自分がクアルトAIを作成した時は、イベントのルールでAIの応答時間に制限があったため、シミュレーションは時間制限の中できる限り行うようにした。

プレイアウトの制度を上げる

アルゴリズム手順3.プレイアウトをクアルト用に最適化する
１回のプレイアウトの制度が上がればより少ない回数で最適解を見つけることができる。
クアルトのプレイアウトでは具体的に以下の制御を組み込むことでプレイアウトの制度を上げた。

自分から負ける手を選択肢から外す
クアルトの特徴としてコマを選んで相手に渡すというルールがある。つまりリーチになっている種類のコマを選んで相手に渡すと負けとなる。実際のプレイでこのコマを選択することは無いのでプレイアウトでも選択肢から外す。
必ず勝てる手があるときはその選択肢を選ぶ
リーチとなっている種類のコマを相手から渡された場合当然その場で勝利が確定する。実際のプレイでこれをわざわざ見逃すことは無いのでプレイアウトでも必ず勝利する選択肢を選ばせる。

バランスよくノードを選択する（UCT）

アルゴリズムの手順1.ノードの選択では勝率が高いノードにできるだけ多くのプレイアウトを行いつつ、試行回数の少ないノードにもある程度プレイアウトを行いたい。
これをバランスよく行う手法にUCT（Upper Confidence Tree）というものがある。
これは木探索にUCB1(Upper Confidence Bound 1)というアルゴリズムを組み込んだものだ。
UCB1値は以下の計算式で求めることができる。これを各ノードで計算し、一番数値が高くなったものを選択していくことでバランスを良くノードを選択できる。

\begin{align}
UCB1 &= \frac{勝利数}{プレイアウト数} + 定数\sqrt{\frac{2*\log{総プレイアウト数}}{プレイアウト数}}\\
\end{align}

定数は必要に応じて調整する。
この数値を低くするとより勝率の高い手が選ばれやすくなり、
高くすればプレイアウト回数が少ない手が選ばれやすくなる

作成したAI「クトゥアルト」と対戦する

GitHub Pagesに作成したAIを公開している。ぜひ対戦してみてほしい
対戦ページ