On Sun, Jun 27, 2010 at 9:26 AM, Petr Baudis <[email protected]> wrote: > On Sun, Jun 27, 2010 at 08:49:57PM +0900, Darren Cook wrote: > > >> I guess moving to whole board patterns doesn't actually add much CPU, > > >> because they are only 3x3: a list of matching patterns can be > > >> maintained, and after each move only a few points need to be > considered > > >> for new pattern matches. > > > > > > Yes, but then you need to choose from a probability distribution over > > > all the moves, which actually does slow things down *quite* a lot. > > > But apparently the slowdown is worth it. > > > > That is the Crazy Stone way? I imagined Fuego's way: just have a list of > > moves and choose one of them randomly. > > Fuego does not check patterns over the whole board, just in the > neighborhood; it does consider defending/capturing all endangered groups > on the board, but it is easy to keep these lists incrementally and > process them quickly in a rule-based manner. CrazyStone needs to keep > "probabilities" of _all_ possible moves all the time and choose from all > of them. >
There is a pretty fast way to do this: You have a non-normalized probability per square (this means they don't have to add up to 1), and you also keep track of the sum of the probabilities in each row, and also the total probability. Now you through a number between 0 and the total probability. Go row by row, subtracting the probability of the row from the random number. When the number would become negative, it means you found your row. So now go square by square in that row, subtracting the individual probabilities from the number. When it would become negative, you found your move. Precision is a tricky issue to deal with when implementing this. John Tromp and I resorted to using integers as probabilities to avoid precision problems.
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
