Go (Martin Mueller)
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)
virtual connections
inferior cells
variants
Bridg-it (aka Gale) Y Shannon switching maker-breaker
reverse hex Kriegspiel Hex (aka Dark Hex, aka Phantom Hex)
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
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
on larger board, computing minimax solution might be infeasible
so what to do ?
assume * * * - * plays 1st a b - cell labels: c d * * *
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
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
many strategies, each awkward to describe
strategy notation ?
simpler problem ?
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 ?
* * * * * p1 p2 ~ ~ ~ ~ D+ C+ B+ A+ d- a+ ~ ~ ~ ~ c- b+ ~ ~ ~ ~ b- c+ ~ ~ ~ ~ A- B- C- D- a- d+ * * * *
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}
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
amazons (Martin Mueller)
reversi/othello (Michael Buro)
skat (Michael Buro)
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
solving trick:
chess: evaluation function
checkers: endgame databases
reversi: ?