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

2021/12/09

この記事は卓ゲ箪笥 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手番ごとに引き分けパターンを全部舐めて到達可能/不可を計算するのしんどそうだが…

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

活動内容

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

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

この論文により、主に

が分かりました。

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

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

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

その結果

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

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


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

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

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


  1. Luc Goossensの論文(1998)によりプレイヤー2人が共に最善手を出し続けた場合は必ず引き分けになることが証明されている。そのため必ず勝つAIは実装不可能。 ↩︎

  2. Algorithms with Python / ミニマックス法とアルファベータ法 ●ゲームの木 ↩︎

  3. Quarto! - quarto.pdf p.35 ↩︎

  4. Algorithms with Python / ミニマックス法とアルファベータ法 ●ミニマックス法 及び ●アルファベータ法 ↩︎