Quote:
Originally Posted by Mark_K
Are there any good links describing this?
|
you could try here:
http://senseis.xmp.net/?UCT
and elsewhere on that wiki, or
http://en.wikipedia.org/wiki/Compute...-Carlo_methods
Basically, there are two major problems with computer go:
1) the branching factor is huge - typically 200 possible moves at any given time
2) there's no easy way to undertake position evaluation midgame
1) is serious, but the way to solve it is a combination of filtering out crap and improving speed, much like chess.
2) is less obvious, but when a computer looks 5, 6, 7, whatever moves ahead, it has to decide how good a given resulting position is in order to compare alternatives. In chess, the obvious way to do it is comparing pieces. There are probably other things that come into play in the good bots, but basically you can rule out all alternatives where you lose a piece. Position evaluation in the mid game of Go is much harder and much more fuzzy.
So the way that they solved it is monte carlo simulation. Basically the bot simulates 5 moves or w/e in the future, and then to evaluate how good a position results, it plays out the rest of the game a large number of times, with both sides playing at total random. So you get a stat like white won 544, black won 456, which gives it an estimate of how good a position is, and the bot can then track back to find a best move using standard minimax. It sounds nuts, but has worked insanely well. Go bots were nowhere 10 years ago, maybe even 5, and now are really very good.
Two Plus Two
It happened quicker, but not much quicker, than i expected.
Linear Mode
