Jason House wrote:

On 6/6/07, *Rémi Coulom* <[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>> wrote:

     > I wonder if other people had thought about this before...
     > Álvaro.

    Yes, I did it in the beginning. But I found that it is faster to divide
    by more than two. Currently, I keep the probability of the whole board,
    each line, and each point. It is simple, and more efficient than a
    binary tree.


I'm not clear on how you efficiently index into which line to select. I think the discussion here is still relevant to that. If we take a simple example of a 5x5 board where the line weights are {15,10,30,20,25}, and I roll the dice and compute 44 (out of 100), I don't know to jump instantly to the 3rd entry; other information is needed if a sequential check is to be avoided. Tokens of 5 could make it easy to pick a number from 1 to 20 and then jump to the row owned by that token, and a binary tree could result in ~3 comparisons... not much better than a sequential check at such a small number of lines.

I do a sequential check.

It is important to understand that it is worthless to be able to pick a move extremely rapidly, if updating the related data takes a lot of time. With 3x3 patterns, 8 points have their urgencies updated after each move. Updating the probability distribution is the time-critical part of the algorithm, not picking one move at random. With my algorithm, I have to update 3 values each time the urgency of a move changes. With a binary tree, I would have to update 8 in 9x9, and 10 in 19x19.

Also, if you have a clever probability distribution, the range of values for each move will be very large. For instance, here are two 3x3 shapes used by Crazy Stone (# to move):

 O O #
 # . .
 # O #
Gamma = 143473;

 . # #
 . . .
 . . .
Gamma = 20;

Playing in the empty corner has gamma = 1. So that would be a lot of tickets to distribute.

Simple straightforward algorithms often work well. I do not do anything extraordinary in Crazy Stone, and, on 9x9 from the empty board, it still runs 21,700 simulations per second on a 2.6 GHz opteron (20,400 with the tree-search logic).

I am sure it could be made significantly faster, but adding knowledge and high-level algorithmic improvements is tremendously more profitable in terms of playing strength than finding tricks to accelerate playouts.

computer-go mailing list

Reply via email to