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.)