Integrate Monte Carlo techniques in GNU Go

[gunnar]

With the success of Monte Carlo based programs over the last year or so there's little question that this approach is useful. What is less clear is how to use it in GNU Go.

An early attempt can be found in this  mailing list thread from April of 2006. It could be interesting to modify this to use  UCT search instead.

A possibly more interesting idea is to use Monte Carlo for dragon strength estimation.

A characteristic of Monte Carlo methods is that speed is of utmost importance. On the other hand neither undo, nor many of the complicated board functions in GNU Go are of much use. Therefore a more lightweight board implementation could be faster and easier to adapt for multithreading.

[gunnar]

First attempt on Monte Carlo specific board code.

[gunnar]

Updated Monte Carlo board code and UCT implementation.

[gunnar]

Tip of the day: if you're using this code, change the two occurences of board![...] near the end of mc_is_self_atari() to mc->board![...].

[gunnar]

Monte Carlo patch ready for merge.

[gunnar]

The patch gunnar_7_12.3.diff contains a cleaned up version of the code with command-line options to turn it on. Notice that it's hardcoded to only allow 9x9 (or smaller). The code simply doesn't scale to larger boards so I think it's reasonable to require people wanting to try that to be competent enough to modify the source first.

[gunnar]

Tunable local patterns for random playouts.

[gunnar]

These patches are in the engine as of GNU Go 3.7.12 and are a reasonable first implementation of Monte Carlo techniques in GNU Go. There's no point in keeping this ticket open any longer. Further Monte Carlo improvements had better go into tickets of their own.