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