# hex game

hex   prop   hist   tips   solve   ttt states   hex states   hexbots   super

## properties

properties
• on any board, draws are not possible

• on nxn board, exists 1st-player winning strategy

• on nx(n+k) board, for player whose sides are closer, exists (1st or 2nd)-player winning strategy: pairing

• solving arbitrary Hex states (who wins?) is P-space complete

## history

• 1942 Piet Hein invents game (then called Polygon)

• 1948 John Nash and David Gale introduce game to Princeton game theory group, including John Milnor, Robert Enderton

• 1950 Claude Shannon built machines to play Hex and birdcage

• 1950 Hex copyright by Parker Brothers

• 2000 Computer Games Olympiad Hex event

• 2003 Jing Yang finds winning 1st-player strategy for 9x9 Hex

• 2013 Pawlewicz Hayward et al. solve 10x10 Hex (2 openings)

• MoHex (Arneson H Henderson Huang Pawlewicz et al) current strongest Hexbot, stronger than most humans on sizes up to 13x13

• how long until superhuman hexbot?

## solving hex vs solving ttt

do we need a new algorithm? will αβ search work ? it worked for tic-tac-toe

## number ttt states

• number states at most number nodes in search tree

• so number states ≤ 9! = 362 880

• why ≤ ?

• some terminal nodes not at max depth (because win is a leaf node)

• transpositions

• better: number states at most number different positions

• so number states ≤ 39 = 19 683

• each of 9 board positions is empty/ x / o

• represent each location with 0 / 1 / 2

• so each board position is represented by a 9-digit base 3 number

• better: many of these positions are not reachable

• also better: many of these states isomorphic

• from root state: only 3 non-iso moves, so expect 6 500 nodes

• alphabeta search from root examines 3025 non-iso states

ttt board representation example
```eg. this position       represented by this number:

x . o
x o .           102 120 010 (base 3) = 8 427 (decimal)
. x .

an unreachable ttt position:

x . o
x . o
x . o
```

## number of hex states

• 3x3: ≤ 39 = 19 683

• 6x6: ≤ 336 > 1.5 1017

• 10x10: ≤ 3100 > 5 1047

• 10x10 number of states at most half full: 1.2 1043

• solving checkers: about 1020 positions

• so 10x10 hex has too many states to search exhaustively

• so far: 2 10x10 opening hex moves have been solved

• center wins

• b9 wins (2nd position on obtuse-corner-to-obtuse-corner diagonal)

## towards superhuman hex

• 28 jan 2016

• announcement: Lee Sedol 9p v AlphaGo

• based on the 5 FH-AG games, LS should beat AG

• unpublished: AG was continuing to learn and improve, about 50 elo week

• 50 elo x 25 weeks = 1250 elo = 0.9993 win rate

• 9 mar 2016 1-0 AG-LS

• 15m summary

• Redmond: I think we just have to admire what AlphaGo did

• 12 mar 2016 3-0 AG-LS

• 13 mar 2016 (move 78: escape, AG: 1/10000) 3-1 AG-LS

• 15 mar 2016 4-1 AG-LS

• AG now considered world's strongest go player … but not playing

• game of hex

• mohex: superhuman(?) 11x11 hex player

• mcts, proof number search, 10 person-years

• how to build a superhuman 19x19 hex player ?

• alphago approach: machine learning + dcnn + mcts hex player/solver

• MSc projects

• solve 6 x 6 go

• solve 1 x 30 go