[computer-go] A small optimization for scoring random playouts

[dhillismail at netscape.net]

Depending on your rule set, you might not want to use stones captured. 

I use more-or-less Tromp-Taylor rules; same as CGOS.
- Some form of mercy rule: if whiteStonesOnBoard == 0, I know who won. Early in the game, blowouts are *very* comon.
- I maintain an array of empty spaces. At scoring time, Every empty space should be a single point eye. I just check the eyes/empty spaces?to find a neighbor and I know who owns it.
- white terr = whiteStonesOnBoard?+ whiteEyes
It's fast.

If you are using a different rule set for playouts, my suggestions are worthless-ignore them. Is anyone using a different scoring system for playouts?

-Dave Hillis

-----Original Message-----
From: Imran Hendley <imran.hendley at gmail.com>
To: computer-go <computer-go at computer-go.org>
Sent: Wed, 19 Dec 2007 5:18 pm
Subject: [computer-go] A small optimization for scoring random playouts


I'm not sure if everyone does this already, but I realized that at the end of a random playout there are no territories bigger than one intersection, so you don't really need to call your area score method in most cases. 

Let D = blackStonesOnBoard - whiteStonesOnBoard + whiteStonesCaptured - blackStonesCaptured - komi. If abs(D) > K for some small threshold K (I use size/2 = 4 for a 9x9 board, but you can use size if you want to be super safe) then D>0 means black wins, white wins otherwise. The only problem is when D is close to 0, since the real area score also counts each eye as one point and this is not reflected in D. So depending on how many eyes each side has, the result might go one way or another. We can either keep track of the number of eyes and update D accordingly, or we can just call the area score method for these borderline cases. If we do the latter we are still saving a lot of time in most cases if we choose K small enough. 

This gave me a nice speedup of 10% or so if I remember correctly.



_______________________________________________
computer-go mailing list
computer-go at computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


________________________________________________________________________
More new features than ever.  Check out the new AIM(R) Mail ! - http://webmail.aim.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20071219/354c5404/attachment.htm