review interactive way to go 11-19
important: early win detection
determine final score before reaching a terminal position
recognize blocks that cannot be killed
unconditionally alive
alive under alternating play
more advanced
also important: graph history interaction
if you understand these papers and are a strong coder, you can solve 6x6 go
go has big search space (check it yourself: write a program to count all legal 2x2 go positions. hint: go2.py in simple/go)
in theory (with enough time/memory), any go state can be solved by minimax
in practice, search space infeasible for boards 8x8 or bigger
up to 30-cells (does not use psk) erik van der werf
open problems
solve all 6x6 go openings (msc/ugrad: theory there, just needs coding)
solve 1xn opening for n ≥ 13 (msc/ugrad: theory + coding)
needed linear go theory: move pruning, move ordering
solving 1xn go open for n over 12: why ?
many early-win-detection observations do not apply in linear go
eg. linear go blocks have no interior region, so blocks have no true eyes
eg. there are no local safe linear go patterns
need linear go early-win-detection/pruning observations
- - - | - x -
- - - -
|
- x - -
/ \
- x o - - x - o
| |
- x * x - x x - o cannot play at *: ko
find minimax value and principal variation for each x - o - - o - x - - x - - o - o - - x - o - - - - - o - - - - - o - -
1 2 3 4 5 x - o - - val 0 pv x:4 o:2 x:1 o:2 pass pass o - x - - val x+5 pv x:4 p x:2 x - - o - val x-5 pv x:2 o:3 x:2 o:1 o - - x - val x+5 pv x:2 o - - - - val x+5 pv x:4 ... (use 3rd result above) - o - - - val 0 pv x:4 - - o - - val 0 pv x:2 o:4 (o:1 loses) x:5 o:4
- x - - x x - - x - x - - x x x - - x x x x - - x - x x - - x x x x x - - x - x x x - - x x - x x - - x - x - x - ... not necessarily safe x - x - - x - x x x - x - - - x - x - x - - x x x - - x - x x x x x - ...
** if x has never played at each ! cell ** then whole board for x - x ! ! x - - x ! ! x x - - x ! ! x x - x - - x ! ! x - x x - - x ! ! x ! ! x - ... not necessarily safe (why?) - x ! ! ! x -