May 29, 2007

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.

1 comment:

Leo Andres said...

I've made a modification on Random-Turn Hex to incorporate a cryptographic coin-flip into the protocol. Instead of the person playing taking a turn based on the coin flip, both players move simultaneously. If the players move to the same spot, the player who takes the spot is determined by the cryptographic coin flip. The losing player then chooses an alternate spot uncontested.

Given that the strategy that I used for the AI was derived from Random-Turn Hex, I believe that the game that I've designed is more a variant of this than traditional Hex. However, like traditional Hex, all information is available to the player (other than what the opponent's move with be, including the outcome of the cryptographic coin-flip). I'd like to put my game out to the math community for comment, and see if there is any interest in my variation of Random-Turn Hex.

I've programmed a JavaScript version to simulate most of the game, and I would appreciate comment. The link is included below. On the page is also a link to instructions on how the game is played.

Battle-Hex