# jemdoc: addcss{rbh.css}, addcss{jacob.css}
= some games
~~~
{}{raw}
go
hex
solhex
hexbots
icga
darkhex
soldark
simpdark
other
complexity
~~~
~~~
{}{raw}
go
~~~
~~~
- [https://en.wikipedia.org/wiki/Go_(game) Go] (Martin Mueller)
- [http://webdocs.cs.ualberta.ca/~hayward/670gga/jem/go.html breakthrough]
~~~
~~~
{}{raw}
hex
~~~
~~~
- [https://en.wikipedia.org/wiki/Hex_(board_game) wiki] ~ [http://www.trmph.com/hexwiki/ hexwiki]
- properties
-- no draw (proofs by Pierce, Schensted)
-- nxn: exists 1pw strategy (Nash strategy stealing)
-- nx(n-1): explicit 2pw pairing strategy for player joining closer sides
-- Pspace complete (Reisch)
- [http://webdocs.cs.ualberta.ca/~hayward/papers/puzzlingHexPrimer.pdf playing tips]
-- virtual connections
-- inferior cells
- variants
-- Bridg-it (aka Gale) ~ [https://en.wikipedia.org/wiki/Y_(game) Y] ~ [https://en.wikipedia.org/wiki/Shannon_switching_game Shannon switching] ~ [https://en.wikipedia.org/wiki/Maker-Breaker_game maker-breaker]
-- [http://webdocs.cs.ualberta.ca/~hayward/papers/rex.llncs.pdf reverse hex] ~ ~ Kriegspiel Hex (aka Dark Hex, aka Phantom Hex)
-- [https://en.wikipedia.org/wiki/Havannah Havannah]
~~~
~~~
{}{raw}
solving hex
~~~
~~~
{concepts}
- virtual connection: a cell-to-cell second-player connection strategy
- mustplay region: intersection of carriers of all known
opponent side-to-side vconns
- dead cell
- captured cell
- inferior cell
- [http://webdocs.cs.ualberta.ca/~hayward/talks/hex.sol10.pdf solving 10x10 hex]
~~~
~~~
{solving hex: papers}
- [http://webdocs.cs.ualberta.ca/~hayward/papers/puzzlingHexPrimer.pdf puzzling hex primer]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/pton.pdf berge]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/Elsevier.pdf hex and combinatorics]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/bergeParis.pdf dead cells in the shannon game]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/s7x7hex1.pdf solving 7x7] ~ ~ ~ [http://webdocs.cs.ualberta.ca/~hayward/papers/s7x7hex2.pdf part 2]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/verify.pdf verifying]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/probe432.pdf probing the 432]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf solving 8x8]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/xhsearch.pdf xh-search]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/handicap.pdf handicap]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/solve.beyond.pdf solving 9x9]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/revDom.pdf capture-reversible, star-domination]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/rex.llncs.pdf reverse hex]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/pawlhayw.pdf solving 10x10]
~~~
~~~
{}{raw}
hexbots
~~~
~~~
{mohex etc}
- [http://webdocs.cs.ualberta.ca/~hayward/talks/hex.mohexchamp2010.pdf mohex]
- [http://webdocs.cs.ualberta.ca/~hayward/talks/hex.m2icga.pdf mohex 2.0]
- [https://acg2015.files.wordpress.com/2015/07/takada.pdf global/local network eval: takada]
~~~
~~~
{hexbots: papers}
- [http://webdocs.cs.ualberta.ca/~hayward/papers/m2.pdf mohex 2.0]
- [http://webdocs.cs.ualberta.ca/~hayward/papers/mcts-hex.pdf MCTS in Hex]
~~~
~~~
{}{raw}
icga
~~~
~~~
- [http://icga.leidenuniv.nl/ international computer games association]
- [http://www.game-ai-forum.org/icga-tournaments/event.php?id=44 olympiads]
- [http://webdocs.cs.ualberta.ca/~hayward/670gga/jem/icgahexgames.html icga hex events]
~~~
~~~
{}{raw}
darkhex
~~~
~~~
{rules}
- each player sees only their stones
- an umpire advises each player when it is their turn to move
- on their turn, a player reports their desired move to the umpire;
the umpire then advises them (and not the opponent) whether the move is legal
(so the move is accepted) or not (so the player tries again; this repeats
until some move is accepted)
- the umpire advises players once a player has won
~~~
~~~
{}{raw}
solving dark hex
~~~
~~~
{dark hex}
- on larger board, computing minimax solution might be infeasible
- so what to do ?
~~~
~~~
{2x2 dark hex}{}
assume * * *
- * plays 1st a b
- cell labels: c d
* * *
~~~
~~~
{2x2 dark hex}
possible 1p strategies
- ab(c) ab(d) ac(b) ac(d) ad(b) ad(c)
- ab(d) never wins
- b useless in ac(b), d useless in ac(d),
so call each of these ac()
- ab(c) wins then ac() wins
- so among these strategies, sufficient to consider only ac()
- if 1st move to b, sufficient to consider only
bc(d), bd(c): each of these wins always
- if 1st move to c, sufficient to consider only
cb(a), ca(b): each of these wins always
maximal 1p strategies
- ac(), db()
- bc(d), bd(c) ~ ~ win
- cb(a), ca(b) ~ ~ win
~~~
~~~
{restricted 2x2 dark hex}
- assume first move not allowed on main diagonal
- nash equilibrium ?
-- 1p: mixed strategy .5 ac() .5 db()
-- 2p: mixed strategy .5 ba(c) or bc(a), .5 cb(d) or cd(b)
-- expected win rate .5
~~~
~~~
{}{raw}
simple dark hex
~~~
~~~
{Polya: how to solve it}
[https://en.wikipedia.org/wiki/How_to_Solve_It by George PĆ³lya]
~~~
~~~
{motivation: find 4x4 dark hex minimax strat?}
- many strategies, each awkward to describe
- strategy notation ?
- simpler problem ?
~~~
~~~
{simple dark hex}
- a restriction of dark hex
-- first stone must touch own edge
-- each subsequent stone must touch own previous stone
-- must reach other side within 4 moves
-- can we solve this ?
~~~
~~~
{notation: label SDH strategies by 1st move}{}
* * * * * p1 p2
~ ~ ~ ~ D+ C+ B+ A+ d- a+
~ ~ ~ ~ c- b+
~ ~ ~ ~ b- c+
~ ~ ~ ~ A- B- C- D- a- d+
* * * *
~~~
~~~
{p1 minimax win probability matrix ?}{}
a- b- c- d- a+ b+ c+ d+
A- ? 1 ? ? ? 1 1 1 D+ C+ B+ A+
B- c- b+
C- b- c+
D- A- B- C- D-
A+
B+
C+
D+
what if collision and player sees opponent stone?
minimax ? equiprobable ?
eg: A-a- .5 if p2 plays minimax = equiprob. {d-,a+}
eg: A-d- .25 if p2 moves 2,3 uniform {left/right}
~~~
~~~
{expanding matrix entries}{}
A-- move 2 towards opponent -
A-+ " " " " +
a- c- d- a+- a++
A-- ? 0 0 1 .5
A-+ ? 1 .5 1 0
so if p2 plays a- and sees a stone at A-,
then p2 minimax is equiprob {d-, a++}, 1p win rate .25
~~~
~~~
{}{raw}
other games
~~~
~~~
- [https://en.wikipedia.org/wiki/Game_of_the_Amazons amazons] (Martin Mueller)
- [https://en.wikipedia.org/wiki/Reversi reversi/othello] (Michael Buro)
- [https://en.wikipedia.org/wiki/Skat_(card_game) skat] (Michael Buro)
- [https://chessprogramming.wikispaces.com/KriegSpiel kriegspiel (phantom chess)] ~ ~
[https://chessprogramming.wikispaces.com/Paolo+Ciancarini Ciancarini] ~ ~
[https://scholar.google.com/citations?hl=en&user=71mmi78AAAAJ&view_op=list_works&sortby=pubdate Cian. pubs]
~~~
~~~
{}{raw}
complexity
~~~
~~~
- compare chess, checkers, go, hex, reversi
- need to search state space, eg. with game tree
-- game tree or directed acyclic graph (dag) ? use trans.table
-- hex: reachable nxn states with at most nxn/2 stones
-- 1 1 ~ 2 9 ~ 3 554 ~ 4 7.6e5 ~ 5 4.0e9 ~ 6 4.0e14 ~ 7 1.5e20 ~ 8 1.0e27 ~ 9 2.7e34 ~ 10 1.2e43 ~ 11 2.2e52 ~ 12 6.3e62~ 13 7.4e73 ~ 14 1.4e86
-- [https://en.wikipedia.org/wiki/Game_complexity game complexity]
- solving trick:
-- chess: evaluation function
-- checkers: endgame databases
-- hex: [https://webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf virtual connection and inferior cell pruning]
-- reversi: ?
~~~