Random-Turn Hex and Other Selection Games

DOI10.1080/00029890.2007.11920428MaRDI QIDQ3529170zbMATH OpenOpenAlexWikidataFDO

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

Publication date 20 October 2008

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0508580

zbMATH Keywords

hexoptimal strategyrandom-turn hexrandom-turn selection gameswin or lose selection games

Mathematics Subject Classification ID

Recreational mathematics (00A08) Combinatorial probability (60C05) Combinatorial games (91A46)

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.

Recommendations

• Publication:4864309
• scientific article; zbMATH DE number 2124098
• Efficient winning strategies in random-turn maker-breaker games
• A difficulty in particular Shannon-like games
• How to play Reverse Hex

Cited in

(19)

• Bidding games and efficient allocations
• The expected time to end the tug-of-war in a wedge
• Non-convex Hamilton-Jacobi equations with gradient constraints
• Bidding chess
• Artificial intelligence for bidding hex
• Tug-of-war and the infinity Laplacian
• scientific article; zbMATH DE number 845730 (Why is no real title available?)
• Remarks on history and presence of game tree search and research
• Efficient winning strategies in random-turn maker-breaker games
• OUTCOME UNCERTAINTY AND INTERESTEDNESS IN GAME-PLAYING: A CASE STUDY USING SYNCHRONIZED HEX
• Oded Schramm's contributions to noise sensitivity
• Minimizing the time to a decision
• Sparse reconstruction in spin systems. I: iid spins
• Average-case deterministic query complexity of Boolean functions with fixed weight
• The complexity of games with randomised control
• Average-case query complexity of fixed-weight Boolean functions and k-CNFs
• Random-player maker-breaker games
• Tug-of-war with noise: a game-theoretic view of the \(p\)-Laplacian
• Quantitative noise sensitivity and exceptional times for percolation

This page was built for publication: Random-Turn Hex and Other Selection Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3529170)