# 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
~~~