Random-Turn Hex and Other Selection Games

Authors: Peres, Yuval; Schramm, Oded; Sheffield, Scott; Wilson, David B.

Source: American Mathematical Monthly, Volume 114, Number 5, May 2007 , pp. 373-387(15)

Publisher: Mathematical Association of America

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content

Abstract:

The game of Hex has two players who take turns placing stones of their respective 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. It belongs to a general class of random-turn games—called selection games—in which the expected payoff when both players play the random-turn game optimally is the same as when both players play randomly. We also describe the optimal strategy and study the expected length of the game under optimal play for Random-Turn Hex and several other selection games.

Document Type: Research article

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$20.00 plus tax      Refund Policy

 

OR

Back to top

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages.
Page Help Click here for Page Help
Shopping cart
Tools
Sign in






Need to register?
Sign up here
Text size: A | A | A | A