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

[Rémi Coulom]

Jason House wrote:
> 
> 
> On 6/6/07, *Rémi Coulom* <Remi.Coulom at univ-lille3.fr 
> <mailto:Remi.Coulom at univ-lille3.fr>> 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é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