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 $O(n^9cdot 2.618^n)$ , $O(n^9cdot 2.746^n)$ , and $O(n^9cdot 3.645^n)$ time for each move, respectively, where $n$ 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.