Quartoを計算機に解かせる会 2021年活動報告書

この記事は卓ゲ箪笥 Advent Calendar 2021 の9日目の記事です。
前回は紅ノ牛さんのテキサスホールデムポーカーのルール説明 でした。

今年4月11日より、Quartoを計算機に解かせる会 (以下Quarto会) を神楽坂あんのんさん , きむにぃさん , 宛先さん , 私の4人で定期開催しています。
この記事ではQuarto会の発足経緯と2021年の活動内容をまとめます。

Quartoのルール等の前提知識はここでは説明しません。【ゲーム紹介】クアルト (Quarto!) | ニコボド｜ボードゲームレビュー＆情報系ブログ 等の外部サイトをご参照ください。

発足経緯

Quartoで遊んだ後、私がPleromaアカウントでぶつぶつと呟いていました。

https://pleroma.unigiri.net/notice/A4soOvGzreImtG7vXs

クアルトのルール的にソルバ転がってそうなので調べたら案の定ソルバやら論文やらスライドやらが出てきてにこにこ笑顔になった

https://pleroma.unigiri.net/notice/A4t9b9DRwudwe58dYO

いやこれ読む限りQuartoで引き分けになるパターン数は414298141056なので、途中の状態を列挙せずともこれらのうちいずれかの状態となるようにしていけばいいのか？ どっちにしろ1手番ごとに引き分けパターンを全部舐めて到達可能/不可を計算するのしんどそうだが…

この時点で人間に必ず負けない¹AIが実装可能かが書かれている資料が見つからなかったため、この呟きに反応していたきむにぃさんと宛先さん、更にあんのんさんも誘いQuarto会を発足しました。

活動内容

An artificial intelligence for the board game ‘Quarto!’ in Javaを読む

全探索する、機械学習させる、定石を列挙する等の色々な案が出ましたが、まずはサーベイということでインターネットに無料で転がっていたAn artificial intelligence for the board game ‘Quarto!’ in Java を読み、メンバー各自で担当箇所を決めてスライド等にまとめました。

この論文により、主に

• まっさらな盤面からの完全ゲーム木²生成は難しいこと
  • つまり、ゲームの序盤でどの手が最善手かを完璧に判断することは難しい
• Quartoでは勝利条件的に同等とみなしてよい盤面が回転と鏡写し以外でも生成可能なこと
  • mid flip と inside out と呼ばれる³
• アルファ・ベータ法⁴により、ある程度動くAIは実装可能なこと

が分かりました。

しかしアルファ・ベータ法によるAIは実行速度があまり速いと言えないこと、またゲームの勝敗状況を判断するための評価関数の実装に疑問が残るということから、別のアルゴリズムを調べることになりました。

モンテカルロ木探索によるAIの実装

先述の論文を探していた時にモンテカルロ木探索で作るクアルト専用対戦AI というQiitaの記事を見つけていたため、モンテカルロ木探索とは何かという所から調べました。

その結果

• 囲碁で実績のあるアルゴリズムであること
• 採用条件的にQuartoの仕様やルールに合っているということ
• Qiitaの記事の人が公開している対戦可能なAI が鬼強くメンバー全員が勝てなかったこと

から、このモンテカルロ木探索の挙動をより深く知るためにGitHubに公開されているAIのソースコード の解析を試みました。
2021年12月時点ではこのソースコードの解析を元に各メンバーのゴールを決め、その達成に向けて活動をしています。

盤面を棋譜として扱えるようにする、Quarto特有のチューニング箇所を見つけ出す等の個々人のゴールがありますが、私のゴールとしてはQiita記事のAIよりも強いAIを作ることです。
そのためには手軽にAI同士で対戦できる環境とAIの強さを数値化し比較可能にするためのELOレーティング導入が必要なため、現在はこの2つを実現する環境を構築しています。
環境の構築後にAIのチューニング等を行い、より強いAIの実装を実現させる予定です。

以上がQuarto会の2021年活動報告書です。

もしこの活動内容に興味がある、もしくは本会へ参加したい方がおりましたら、Fediverse経由でUnigiri 宛へのメンションか本サイトのトップページに記載されているメールアドレス宛へご連絡をよろしくお願いします。
喜んで詳細な活動内容をお伝えいたします。

明日は神楽坂あんのんさんの「マンカラの話かVRCでできるボドゲの話をします」です。