On 12/11/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
Hello all. I've been lurking on the list for a few years now. In amongst the usual musings on the meaning of AI and social justice, etc., there's been a sharp increase in the amount of useful information posted here of late. I'll try to contribute. My engine is AntIgo. It's been a speed bump on CGOS and in several KGS tournaments so I've turned to MC UCT. I have a Pentium 1.86 GHz laptop. From an empty board, without using the "mercy rule", I get about 22,000 pps (1 pps: playout per second including scoring, if needed, and restoring the board). I use the rules discussed on the list and get an average of 107 moves/game not counting passes. With the mercy rule, I get about 29,000 pps and the average game length is around 99. Here are a few speedup tricks that have helped me. 1. The mercy rule. Since I'm incrementally keeping track of a list of empty points, it's no real extra pain to keep track of the number of black and white stones on the board. If the difference between them exceeds a threshold, the game is over. Ending early has an added bonus that I know the outcome without needing to score the board. (You can shoot yourself in the foot here. Best to pick a more conservative threshold the closer you are to interior nodes of the tree.) For exterior nodes far from any interior nodes, I use a threshold of 25 stones.
Thanks for that, I implemented this in libgoboard
2. Pseudo liberties (I think that this wheel has been reinvented many times with many different names; "Pseudo liberties" is a good name). Checking whether a potential move would be suicide, fill an eye, etc. is complex enough to entail a function call inside a tight loop. If an empty space on the board has one or more pseudo liberties, it is an acceptable move. It can't be suicide or Ko or fill any kind of single point eye. So I make that test first and usually skip the function call.
Isn't adding an integer faster than memory access? Best Regards and thanks, Lukasz
3. For every space on the board, I pre-calculate the addresses of all its neighbors. I treat the off-edge as one super-safe third-color group, so a space next to the edge doesn't need to be treated as any kind of special case. 4. At every move, I update the pseudo liberties, group membership, stone counts, and empty spaces list. When a stone is removed due to capture, I place that position at the end of the empty spaces list. When a stone is added, the space it's about to occupy is already at the end of the list, so I just decrement the counter. I never need to regenerate the empty spaces list. Dave Hillis ________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
