# Re: [computer-go] Efficiently selecting a point to play in a random playout

```Jason House wrote:
```

```

```
On 6/6/07, *Rémi Coulom* <[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>> wrote:
```
>
> Á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émi

```
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.
```
Rémi
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
```