On Tue, Oct 30, 2007 at 12:43:35PM -0400, Joshua Shriver wrote: > There has been a lot of talk about monte carlo and while I have the > jist not sure exactly what it is? Would someone explain it?
Here is my (amateurish) understanding: Evaluation of a go position is very difficult. Monte Carlo (MC) is one way to shortcircuit this. The idea is to play the game to the bitter end, very quickly, and badly, on the assumption that if the position favours white, then white is likely to win, even if both players play equally bad quality moves. Taken to the extreme, they play pure random games. This can be done very quickly, and doing it many times gives some sort of measure of how good the position is. Now all is left for a pure MC player is to try every legal move, evaluate them with enough MC playouts, and choose the one that is most likely to win. This works surprisingly well, although there are some drawbacks. Evaluating positions this way prefers safe, solid groups. And in the end game, when the result is decided, the programs play unnatural moves, since all moves lead to the same result - the resulting score is usually not considered, so to the program it is the same if it wins by 0.5 points or the whole board... On its own MC is not all too strong, but it solves the evaluation problem. This can be included in some tree-search based programs, most commonly UCT or similar. And the results are surprisingly good. Lukasz Lew has written a simple C library that makes it easy to experiment with the thing. Google on 'Lew libEGO' and you should find him. - Heikki P.S. If any of the above is not right, I am sure the better informed people will rush in to correct me. I welcome that! -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/