# jemdoc: addcss{rbh.css}, addcss{jacob.css}
= go algorithms
~~~
{}{raw}
solve
linear
trees
ex
safe
~~~
~~~
{}{raw}
solving go
~~~
~~~
- review [http://playgo.to/iwtg/en/ interactive way to go] 11-19
- important: early win detection
-- determine final score before reaching a terminal position
-- recognize blocks that cannot be killed
-- [https://webdocs.cs.ualberta.ca/~mmueller/ps/gpw97.pdf playing it safe]
-- unconditionally alive
-- alive under alternating play
-- more advanced
--- [https://webdocs.cs.ualberta.ca/~mmueller/ps/goeval.pdf position evaluation in computer go]
--- [https://webdocs.cs.ualberta.ca/~mmueller/ps/safetysolver2.pdf open boundary safe-territory solver]
- also important: [https://webdocs.cs.ualberta.ca/~mmueller/ghi.html graph history interaction]
- if you understand these papers and are a strong coder, you can solve 6x6 go
- [http://tromp.github.io/java/go/twoxtwo.html tromp code for 2x2]
~~~
~~~
{small boards}
- [http://webdocs.cs.ualberta.ca/~hayward/396/ssgo.pdf read this handout]
- in theory (with enough time/memory),
any go state can be solved by minimax
- in practice, search space infeasible for boards 8x8 or bigger
- [http://erikvanderwerf.tengen.nl/pubdown/solving_go_on_small_boards.pdf up to 5x5] (does not use psk) erik van der werf
- [http://erikvanderwerf.tengen.nl/mxngo.html 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
~~~
~~~
{}{raw}
linear go
~~~
~~~
{solving}
- [https://webdocs.cs.ualberta.ca/~hayward/396/lgo_small.pdf small boards]
- 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
~~~
~~~
{}{raw}
some linear go proof trees
~~~
~~~
{1x3}{}
- - -
|
- x -
~~~
~~~
{1x4}{}
- - - -
|
- x - -
/ \
- x o - - x - o
| |
- x * x - x x - o cannot play at *: ko
~~~
~~~
{}{raw}
some linear go exercises
~~~
~~~
{x-to-move}{}
find minimax value and principal variation for each
x - o - -
o - x - -
x - - o -
o - - x -
o - - - -
- o - - -
- - o - -
~~~
~~~
{answers}{}
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
~~~
~~~
{}{raw}
some safe linear go positions
~~~
~~~
{unconditionally safe whole-board positions}{}
- 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 -
...
~~~
~~~
{some conditionally safe whole-board positions}{}
** 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 -
~~~