some games

go   hex   solhex   hexbots   icga   darkhex   soldark   simpdark   other   complexity  

go

hex

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

  • playing tips

    • virtual connections

    • inferior cells

  • variants

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

  • solving 10x10 hex

solving hex: papers

hexbots

mohex etc
hexbots: papers

icga

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

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

simple dark hex

Polya: 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

other games

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

    • game complexity

  • solving trick: