# jemdoc: addcss{rbh.css}, addcss{jacob.css} = hex game ~~~ {}{raw} hex   prop   hist   tips   solve   ttt states   hex states   hexbots   super   ~~~ ~~~ {}{raw}

hex

~~~ ~~~ - [https://en.wikipedia.org/wiki/Hex_(board_game) hex (board game) wiki] - [http://hexwiki.amecy.com/index.php/Main_Page hexwiki] ~ (with [https://www.hexwiki.net/index.php/Piet_Hein%27s_puzzles some Piet Hein puzzles] ) - [http://webdocs.cs.ualberta.ca/~hayward/talks/hex.someques.pdf intro talk] - [http://webdocs.cs.ualberta.ca/~hayward/396/hexhandout.pdf 396 handout] ~ - [http://webdocs.cs.ualberta.ca/~hayward/396/hexnotesp1.pdf 396 hexnotes (part 1)] ~ [http://webdocs.cs.ualberta.ca/~hayward/396/hexnotesp2.pdf (part 2)] ~ - [http://webdocs.cs.ualberta.ca/~hayward/396/hexboards.pdf boards] ~ - [http://webdocs.cs.ualberta.ca/~hayward/396/hexdotpaper.pdf dot paper] ~ - [http://webdocs.cs.ualberta.ca/~hayward/396/6x6open.pdf 6x6 open] ~ ~~~ ~~~ {}{raw}

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 ~~~ ~~~ {}{raw}

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 [http://ec2-34-227-158-207.compute-1.amazonaws.com/fldb/hex99.html 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? ~~~ ~~~ {}{raw}

playing tips

~~~ ~~~ - virtual connections - inferior cells - [http://webdocs.cs.ualberta.ca/~hayward/papers/puzzlingHexPrimer.pdf puzzling hex primer] - [http://webdocs.cs.ualberta.ca/~hayward/papers/pton.pdf Berge and the art of hex] ~~~ ~~~ {}{raw}

solving hex vs solving ttt

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

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 ~~~ ~~~ {}{raw}

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) ~~~ ~~~ {}{raw}

hexbots (and other gamebots)

~~~ ~~~ - [https://github.com/tewalds/morat Timo Ewalds' morat] has a strong hex player, c\+\+ - [http://webdocs.cs.ualberta.ca/~hayward/670gga/jem/gga.html other bots here] including benzene (hard to build, needs berkeley db, boost) ~~~ ~~~ {}{raw}

towards superhuman hex

~~~ ~~~ - [http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html 28 jan 2016] -- [https://gogameguru.com/i/2016/01/Fan-Hui-vs-AlphaGo.jpg oct 2015 0-5 FH.2p-AG no handicap] -- 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 - [https://www.youtube.com/watch?v=l-GsfyVCBu0&t=77m40s 10 mar 2016 (move 37: shoulder hit, LS: 1/10000) 2-0 AG-LS] -- [https://www.youtube.com/watch?v=1aMt7ulL6EI 15m summary] -- Redmond: I think we just have to admire what AlphaGo did - 12 mar 2016 3-0 AG-LS - [https://www.youtube.com/watch?v=yCALyQRN3hw&t=190m0s 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 - [http://webdocs.cs.ualberta.ca/~hayward/talks/hex.someques.pdf 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 ~~~