hexwiki (with some Piet Hein puzzles )
Hex, a playful introduction: ualberta ccid login access
login to your ualberta account and click the link for access to the whole book
chapter 2 basics
hex the full story (access this link when signed in to your UAlberta account for free access to this book, courtesy the UAlberta library)
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?
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
virtual connections
inferior cells
do we need a new algorithm? will αβ search work ? it worked for tic-tac-toe
3x3 hex will be no problem (similar to 3x3 ttt), what about larger sizes?
up to 5x5
easy for humans to learn how to play perfectly (from any position)
6x6
not easy for humans to learn how to play perfectly (from any position)
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
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: ≤ 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)
in class repo: mcts player (python3: Luke Schultz)
other hex bots e.g. morat (C: Timo Ewalds), benzene (C, berkeley db, boost: Arneson Bjornsson Hayward Huang Johanson Kan Pawlewicz)
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
