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. RémiI'm not clear on how you efficiently index into which line to select. Ithink the discussion here is still relevant to that. If we take asimple 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), Idon't know to jump instantly to the 3rd entry; other information isneeded if a sequential check is to be avoided. Tokens of 5 could makeit easy to pick a number from 1 to 20 and then jump to the row owned bythat token, and a binary tree could result in ~3 comparisons... not muchbetter 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.`

Rémi _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/