[computer-go] Random move selection (was) Crazystone patterns

[Jacques Basaldúa]

Dave Hillis, wrote:

> Suppose I can generate scores for all of the moves quickly enough. 
> I still face the problem of quickly choosing a move biased by the 
> scores. Tournament selection is fast, but that is a function of 
> relative ranking of the scores, not the values of the scores. 
> Roulette wheel selection gives me an answer, but it is slow slow 
> slow, the way I implement it anyway. Can anybody describe a good 
> way to do this?

We posted about that before this summer when I was implementing it.
I proposed a "ticket based lottery", but that, of course, restricts
the difference to small values. It can be implemented using a linked
list so that each extra ticket allocation cost few clock cycles (I don't 
remember exactly how many, but less than 10 asm instruction for sure).

My final version uses 2 values for the tickets HI and LO where

 1 HI = 32 LO

The default (when the pattern is not in the database) is 1 HI.

The score goes from 1 (= 1 LO) to 1024 (= 32 HI). If you round the scores
it the database to avoid such values as 927 (= 28 HI, 31 LO) and round 
it as 928 (= 29 HI) you can have a nice dynamic range from default/32 to
default*32 having not too many tickets to allocate.

Jacques.

PD. Search the threads (about May-June 2007) because other good ideas 
were proposed. Binary trees, etc.