Quoting Carter Cheng <[EMAIL PROTECTED]>:
1) How typically do UCT bots score simulations quickly? I am not too familiar with Chinese scoring rules.
In the end of a random games. There are only Black stones and Black Eyes, as well as White stones and eyes. If your playouts are smart enough there may also be points in seki. In that case at least one black and a white stone is adjascent to the point in seki which is simply not counted. If the playouts is even smarter it might avoid capturing some dead stones, but then you have to deal with that in counting. Although counting may be slower your random playouts become shorter so there may be a gain in efficency.
Also some people stop the random playout prematurely after very large captures that makes it clear that one side has won the game.
2) How do machines define eyes analytically (mathematically) and are there approximations which are faster to calculate for more traditional or UCT designs (is this information even used for UCT bots?).
Mathmatically speaking there are eyes that are not detected by 3x3 patterns. For example a living group can be made having the corners (1,1) and (19, 19) empty. If then all stones on the first line of the board has the same color then this is a live group. This violates 3x3 patterns because it does not matter if the (2,2) and (18,18) point belong to the opponent.
But these types of eyes are so rare in real games that it can be ignored, and simply looking at 3x3 patterns are good enough to make a strong program.
3) What sort of algorithm is used to match patterns once you have mined them from some data source?
If there is a general approach you probably want to take your pattern (whatever shape it has) and make a hash score of it and put it in a hash table. In the table you will store only those patterns that appear most frequently in games if you use large patterns.
The best approach imho that is also well documented is that for Crazystone so go and check the papers at http://remi.coulom.free.fr/CrazyStone/
My program Valkyria rely completly on handwritten pattern recognition, basically using a decision tree which sometimes calls quick algorithms for tricky cases. This is a very time consuming approach for the programmer.
4) And lastly how does UCT cope with ladders?
Valkyria reads ladders in the playouts. The ladder code is special because it can only read ladders and do not implement proper go rules. It also gives up if the ladders gets complicated. So it actually returns a) A stone can be captured for sure b) It does not know if it can be captured. This way the ladder code will be as fast as possible and still return a lot of helpful information. The ladder implementation uses a stack to record all changes to the board and then restores the board to the original state. This is because my board representation is too complex to use with the ladder code which must be super fast.
The ladder information can be used to play better moves in the playouts, and bias the search in the UCT tree.
Thanks in advance,
Good luck! Magnus _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
