Random-turn Hex and tug-of-war

Yuval Peres, UC Berkeley

The game of Hex has two players who take turns placing stones of their colors on the hexagons of a rhombus-shaped hexagonal grid. Black wins by completing a crossing between two opposite edges, while White wins by completing a crossing between the other pair of opposite edges. Although ordinary Hex is famously difficult to analyze, random-turn Hex---in which players toss a coin before each turn to decide who gets to place the next stone---has a simple optimal strategy. We describe the optimal strategy and study the expected length of the game under optimal play for random-turn Hex and several other ``selection games''. We also study another class of random-turn games, called tug-of-war, which furnish an interesting bridge from the discrete to the continuum.
(The Talk is based on joint works with Oded Schramm, Scott Sheffield and David Wilson.)