Random-Turn Hex

In most two-person games, players take turns, proceeding from turn to turn in an orderly manner. If, instead of alternating turns, the players use a coin toss to decide who makes each move, a deterministic pastime becomes a random-turn game.

Interestingly, random-turn games can be easier to analyze than their deterministic counterparts, Yuval Peres, Oded Schramm, Scott Sheffield, and David B. Wilson report in the May American Mathematical Monthly. Such games also "exhibit surprising structure and symmetry," the researchers say.

The game of Hex, for example, is played on a diamond-shaped board made up of hexagons. Each player has pieces (or stones) of a particular color. The two players alternately place stones of their respective colors on unoccupied hexagons. A player wins by completing an unbroken chain of stones, creating a path that connects the two opposite sides of his or her color.

The game can't end in a tie. One player can block the other only by completing his or her own chain. It's possible to prove that there exists a winning strategy for the first player on a board of any size, but there is no known optimal strategy for the standard 11 by 11 board (or for larger boards).

In random-turn Hex, the players toss a coin to decide who places the next stone. Peres and his colleagues show that the probability that the first player wins when both players play optimally is the same as the probability that the first player wins when both players play randomly.

So, winning the game is akin to creating a path that crosses from one side of the board to the other after filling in empty hexagons at random—a process known as independent Bernoulli percolation.

"In this and other games, the set of moves played during an entire game (when both players play optimally) has an intriguing fractal structure," Peres and his colleagues observe.

The researchers also prove that, in a random-turn selection game such as Hex, any optimal strategy for one of the players is also an optimal strategy for the other player.

It turns out that the best first move in random-turn Hex is the site that is most likely to be crucial for a percolation crossing. For the standard board, the best first move is near the center.

The authors note that "random-turn games are natural models for real-world conflicts, where opposing agents (political parties, lobbyists, businesses, militaries, etc.) do not alternate turns. Instead, they continually seek to improve their positions incrementally."

References:

Browne, C. 2000. Hex Strategy: Making the Right Connections. A K Peters.

Gardner, M. 1959. The game of Hex. In Hexaflexagons and Other Mathematical Diversions: The First Scientific American Book of Mathematical Puzzles and Games. University of Chicago Press.

Peres, Y., O. Schramm, S. Sheffield, and D.B. Wilson. 2007. Random-turn hex and other selection games. American Mathematical Monthly 114(May):373-387.