Quarto Solvers' Club 2021 Activity Report

This article was machine-translated from the Japanese version.

This article is for Day 9 of Table Game Tansu Advent Calendar 2021.

The previous article was Kurenainoushi-san’s Texas Hold’em Poker Rules Explanation.

Starting April 11 of this year, the Quarto Solving by Computer Group (hereafter, Quarto-kai) has been holding regular sessions with four members: Kagurazaka Annon-san, Kimunii-san, Atesaki-san, and myself. This article summarizes the founding history of Quarto-kai and its 2021 activities.

Prerequisite knowledge such as Quarto’s rules will not be explained here. Please refer to external sites such as Quarto! | Nicobodo | Board Game Review & Info Blog.

Founding History

After playing Quarto, I was muttering to myself on my Pleroma account.

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

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

(Translated) I figured there’d be a solver for Quarto given its rules, and sure enough, I found solvers, papers, and slides, which put a massive grin on my face.

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

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

(Translated) Wait, based on what I’m reading here, the number of possible draw patterns in Quarto is 414,298,141,056, so does that mean I just need to aim for one of those states without listing all the intermediate ones? Either way, it sounds like a right pain to scan through every single draw pattern each turn to calculate whether it’s reachable or not…

At this point, I couldn’t find any documentation on whether an AI that would never lose to a human¹ was implementable, so I invited Kimunii-san and Atesaki-san, who had responded to these posts, and also Kagurazaka Annon-san, and we founded Quarto-kai.

Activities

Reading “An artificial intelligence for the board game ‘Quarto!’ in Java”

Various ideas were proposed, such as performing a full search, applying machine learning, and enumerating standard openings, but first as a survey we read An artificial intelligence for the board game ‘Quarto!’ in Java, which was freely available on the internet, and each member took charge of specific sections and summarized them in slides and other formats.

Through this paper, we primarily learned the following:

• Generating a complete game tree² from a blank board is difficult
  • In other words, it is difficult to perfectly determine the best move in the early stages of a game
• In Quarto, boards that can be considered equivalent under the winning conditions can be generated not only through rotation and reflection
  • These are called mid flip and inside out³
• An AI that functions to some extent can be implemented using alpha-beta pruning⁴

However, since the execution speed of an AI based on alpha-beta pruning cannot be considered very fast, and there were lingering doubts about the implementation of the evaluation function for judging the game’s win/loss state, we decided to investigate alternative algorithms.

Implementing an AI Using Monte Carlo Tree Search

While searching for the aforementioned paper, I had also found a Qiita article titled Building a Quarto-Specific Competitive AI with Monte Carlo Tree Search, so we started by investigating what Monte Carlo Tree Search is.

As a result of the following findings:

• It is a proven algorithm in the game of Go
• Its adoption conditions are compatible with Quarto’s specifications and rules
• The playable AI published by the author of the Qiita article was absurdly strong, and none of the members could defeat it

we attempted to analyze the AI source code published on GitHub in order to gain a deeper understanding of Monte Carlo Tree Search behavior. As of December 2021, we have set each member’s goals based on this source code analysis and are working toward achieving them.

Individual goals include making the board state treatable as game records and identifying Quarto-specific tuning points, but my personal goal is to create an AI stronger than the one in the Qiita article. To achieve this, I need an environment where AIs can easily compete against each other and the introduction of ELO rating to quantify and compare AI strength, so I am currently building an environment that realizes these two features. After the environment is built, I plan to perform AI tuning and other adjustments to implement an even stronger AI.

The above is the 2021 activity report for Quarto-kai.

If anyone is interested in these activities or would like to join the group, please contact Unigiri via a mention on the Fediverse, or at the email address listed on the top page of this website. I would be happy to share detailed information about our activities.

Tomorrow is Kagurazaka Annon-san’s “I’ll talk about Mancala or board games you can play in VRC.”