# some games

go   hex   solhex   hexbots   icga   darkhex   soldark   simpdark   other   complexity

## hex

• 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

• captured cell

• inferior cell

• solving 10x10 hex

mohex etc
hexbots: papers

## 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(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
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
```

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

• chess: evaluation function

• checkers: endgame databases

• reversi: ?