The Complexities of Random-Turn Hex, Square, and Triangle Games

In random-turn games, players toss a coin to decide who moves. This article studies the complexities of the algorithms for playing random-turn connection games perfectly on regular tessellations. Our study theoretically shows that there are algorithms playing random-turn hex, square, and triangle perfectly in <inline-formula><tex-math notation="LaTeX">$O(n^9\cdot 2.618^n)$</tex-math></inline-formula>, <inline-formula><tex-math notation="LaTeX">$O(n^9\cdot 2.746^n)$</tex-math></inline-formula>, and <inline-formula><tex-math notation="LaTeX">$O(n^9\cdot 3.645^n)$</tex-math></inline-formula> time for each move, respectively, where <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> is the board size. We then implement the perfect-playing algorithm for the random-turn square and measure the actual running time it costs for each move. We then compute and analyze the game lengths on random-turn square, hex, and triangle and conjecture that the asymptotic complexity of their game lengths are the same. We finally compare the perfect-playing algorithm with the sampling algorithm by competing against each other, and the numbers of their wins and losses are reported.