hex game

hex   prop   hist   tips   solve   ttt states   hex states   hexbots   super  

hex

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

    • D Pankratz visualizer

    • the following visualizer bug has now been resolved by D Pankratz (issue in the streaming assets file corrected)

    • old visualizer bug: (1.Be5) 2.We6 (3.Bd6) 4.Wb9 (5.Bd7) 6.Wd8 (7.Bf7) 8.We7 (9.B g5]) 10.Wg1 at this point program freezes and weird things happen

  • 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?

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

playing tips

solving hex vs solving ttt

  • 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 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)

hexbots (and other gamebots)

  • 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)

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

  • 10 mar 2016 (move 37: shoulder hit, LS: 1/10000) 2-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