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.
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
