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
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?
virtual connections
inferior cells
do we need a new algorithm? will αβ search work ? it worked for tic-tac-toe
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 ≤ 3^{9} = 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
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
3x3: ≤ 3^{9} = 19 683
6x6: ≤ 3^{36} > 1.5 10^{17}
10x10: ≤ 3^{100} > 5 10^{47}
10x10 number of states at most half full: 1.2 10^{43}
solving checkers: about 10^{20} 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)
Timo Ewalds’ morat has a strong hex player, c++
other bots here including benzene (hard to build, needs berkeley db, boost)
alphago architecture: machine learning + deep convolution neural nets + 10 deepmind employees + google machines
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
10 mar 2016 (move 37: shoulder hit, LS: 1/10000) 2-0 AG-LS
Redmond: I think we just have to admire what AlphaGo did
12 mar 2016 3-0 AG-LS
15 mar 2016 4-1 AG-LS
AG now considered world's strongest go player … but not playing
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