Re: [computer-go] Random weighted patterns
I'm about to implement this. Since I have multiple features (patterns, is in atari, is adjacent to last play, etc.), the weight is the product of the weight of all matching features. I'm thinking about having a table of weights, storing the sum of each row and the total (like Rémi suggested). I want to do this incrementally, so if I find a new feature match in a position, I can multiply its weight by the feature's weight. If I remove a feature, I can divide. My question/problem: How do I deal with features that have a weight of zero? I'm sure there are certain 3x3 patterns that have the weight zero, such as ### #*. #.. with * to be played. It's clear that when this pattern matches, the total weight is set to zero. How do I find the resulting weight when removing this pattern, though? Since I can't divide by zero, I would have to reconstruct the weight by checking all features, which would be relatively slow. Is there a way this can be avoided, such as setting all weights to a very low value instead of zero? Regards, Isaac___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Isaac Deutsch kirjoitti: My question/problem: How do I deal with features that have a weight of zero? I'm sure there are certain 3x3 patterns that have the weight zero, such as ### #*. #.. with * to be played. It's clear that when this pattern matches, the total weight is set to zero. Hmm. Say this is a black group, surrounded by white stones and involved in an unsettled semeai: #..# #..# W needs to play in one of the liberties, and they all match your pattern. JP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
In my example, #=border/edge of the board, not black. I was just trying to come up with an example feature that might have weight zero to illustrate my problem. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Isaac Deutsch kirjoitti: In my example, #=border/edge of the board, not black. I was just trying to come up with an example feature that might have weight zero to illustrate my problem. I see. I was already thinking there may be no 3x3 patterns that should never be played. But I cannot think of a counter example to your corner case. Assuming your multiplicative weighting is the best way in the first place, then the epsilon-sized minimum weight seems reasonable. JP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Isaac Deutsch wrote: I'm about to implement this. Since I have multiple features (patterns, is in atari, is adjacent to last play, etc.), the weight is the product of the weight of all matching features. I'm thinking about having a table of weights, storing the sum of each row and the total (like Rémi suggested). I want to do this incrementally, so if I find a new feature match in a position, I can multiply its weight by the feature's weight. If I remove a feature, I can divide. My question/problem: How do I deal with features that have a weight of zero? I'm sure there are certain 3x3 patterns that have the weight zero, such as ### #*. #.. with * to be played. It's clear that when this pattern matches, the total weight is set to zero. How do I find the resulting weight when removing this pattern, though? Since I can't divide by zero, I would have to reconstruct the weight by checking all features, which would be relatively slow. Is there a way this can be avoided, such as setting all weights to a very low value instead of zero? Cache what features you have, then recomputing the weight will be fast. GNU Go incrementally keeps track of the following features: Black suicide (true/false) White suicide (true/false) Black self-atari (true/false) White self-atari (true/false) Number of stones captured by black move (0, 1, 2, 3+) Number of stones captured by white move (0, 1, 2, 3+) Color to the southeast (empty, white, black, off board) Color to the northeast (empty, white, black, off board) Color to the northwest (empty, white, black, off board) Color to the southwest (empty, white, black, off board) Color to the east (empty, white, black, off board) Color to the north (empty, white, black, off board) Color to the west (empty, white, black, off board) Color to the south (empty, white, black, off board) This information is stored in 24 bits of an integer. The 16 bits related to the local 3x3 pattern are mapped by table lookup to the 1107 rotation/mirroring invariant patterns. The remaining 8 bits are mapped to the following features: Opponent suicide (1 bit) Our self-atari (1 bit) Opponent self-atari (1 bit) Our captures (2 bits) Opponent captures (2 bits) by simple bit transposition depending on color to play. Additionally nearness to the previous move is added as a feature giving 1107*256 combinations, which are finally mapped to pattern weight by table lookup. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Thanks to both for the elaborate feedback! I was wondering about pattern symmetry, too, and I also had a lookup table in mind since there are only about 65000 combinations (and only a fraction of them legal). I had another idea for the zero weight problem: Keep a counter of how many times this weight was multiplied by zero. This counter can be stored in 1 byte or less, depending on the number of features. If the counter is 0, the weight is the floating point value. Else, the weight is zero. When adding a zero-weight-feature, increase the counter by one, else decrease it by one. This way, the weight doesn't have to be recomputed, although it uses slightly more memory than nicely packing the features in an int like in GNU Go. It seems like the rounding errors that are accumulated this way are insignificant, according to my tests. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
This code should work with r -= weights[i++] in the loop body, and comes down
to a linear search through
cumulative sum of the weights. If the weights will be static for a number of
selections, you can store the
cumulative weights in an array and use binary search for selecting the move.
So setting up the table is O(n),
but selecting moves based on those weights is O(log n).
If the weights are constantly being updated, there's a tradeoff between Peter's
code and the tree-based approach:
Peter's code is O(1) for updating weights and O(n) for selections, while the
tree-based approach is O(log n) for updates
and selections.
[You can get practically quicker selection using Peter's code if you keep the
weights sorted in decreasing order, but then updates
become O(n) worst-case (probably O(1) amortized, though).]
Steve
On Thu, 16 Jul 2009, Don Dailey wrote:
In the loop i is always zero. I think your code is wrong.
You probably meant to loop over all the weights (or I should say on average
half the weights), and this code is slow if there are a lot of weights.
2009/7/16 Peter Drake dr...@lclark.edu
I must be missing something. Isn't the obvious trick:
int r = random(sum of weights);
int i = 0;
while (r weights[i]) {
r -= weights[i];
}
return i;
This way, you only have to generate one random number.
Peter Drake
http://www.lclark.edu/~drake/
On Jul 15, 2009, at 8:55 PM, Zach Wegner wrote:
On Wed, Jul 15, 2009 at 10:37 PM, David Fotlandfotl...@smart-games.com
wrote:
So many complex ideas :) Why not just multiply the weight of each
pattern
by a random number and pick the biggest result?
David
That involves generating N random numbers and then doing N-1
comparisons. The n-ary tree has only 1 random number and log N
comparisons, but has to be
incrementally updated (log N adds).
Also, I don't think the distribution is the same. Imagine two moves a
and b, with weights 2 and 1. The probabilities should be a=2/3 b=1/3,
but if you select two random numbers in a finite range, there's only a
1/4 chance that the second number is more than twice the first, which
is needed for b to be selected. I could be wrong here though.
Zach
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
--
Steve Kroon | Computer Science Division, Stellenbosch University
(084) 458 8062 (Cell) | (086) 655 4386 (Fax) | kroonrs (Skype)
http://www.cs.sun.ac.za/~kroon | kr...@sun.ac.za___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
Thanks! I had never seen the alias method before and it is quite ingenious! - George On Thu, Jul 16, 2009 at 3:04 AM, Martin Muellermmuel...@cs.ualberta.ca wrote: If you want to take many samples from a fixed, or infrequently changing, distribution, you can do it in O(1) time per sample, with O(n) initial setup costs. This is quite clever and goes by the name of alias method. See http://cg.scs.carleton.ca/~luc/rnbookindex.html, page 107-111 For weighted patterns, the row sum method by Rémi is probably hard to beat. It was discussed here a while ago. Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
When using patterns during the playout I had improvised some code to select patterns randomly, but favour those with higher weights more or less proportionally to the weight.. How many patterns, and are the weights constant for the whole game? If relatively few, and constant, you can make a lookup table (with e.g. 1024 entries) where the number of entries for each pattern is proportional to its weight. You then choose with a 0..1023 random number. When more patterns, but only a few distinct weights you can split them into buckets. E.g. a bucket of weight 1 patterns, weight 1.5 patterns, weight 2 patterns, etc. The weight of each bucket is the number of patterns in it times the pattern weight. You first choose a bucket (e.g. using the above lookup table algorithm), then choose uniformly from within the bucket. Darren P.S. I suspect you have already came up with the above algorithms. I had the same question before, and like you realized it wasn't quite as easy as I thought it would be. I'd also like to hear what the standard computer science approach is, if there is one. (I just saw Jason's reply; do you have a good reference describing row sum in more detail?) -- Darren Cook, Software Researcher/Developer http://dcook.org/gobet/ (Shodan Go Bet - who will win?) http://dcook.org/mlsn/ (Multilingual open source semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
You might look in the genetic algorithm literature, where they have to do this for fitness-proportional reproduction. A useful buzzword is roulette wheel. Peter Drake http://www.lclark.edu/~drake/ On Jul 15, 2009, at 4:06 PM, Mark Boon wrote: When using patterns during the playout I had improvised some code to select patterns randomly, but favour those with higher weights more or less proportionally to the weight.. I was wondering though if there's an established algorithm for something like this. To be a little more precise, if I have a set of values and two of those are represented by A and B. If A is twice as high as B it should have twice the chance to be selected. If there's a third value C that is 1.5 times A then it should be 1.5 times as likely to be selected as A and 3 times as likely as B. Etc. There are many strategies I can think of that make a randomly weighted selection from a set. But none of them are really straightforward. So I'd be interested to hear how others handled something like this. And if there's maybe a standard known algorithm, this kind of thing must appear in a lot of fields. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
If your weights are all between 0 and 1: do double r = rand(0 to 1) int i = rand(0 to weightCount - 1) until weight[i] r I think that's right. Mark Boon wrote: When using patterns during the playout I had improvised some code to select patterns randomly, but favour those with higher weights more or less proportionally to the weight.. I was wondering though if there's an established algorithm for something like this. To be a little more precise, if I have a set of values and two of those are represented by A and B. If A is twice as high as B it should have twice the chance to be selected. If there's a third value C that is 1.5 times A then it should be 1.5 times as likely to be selected as A and 3 times as likely as B. Etc. There are many strategies I can think of that make a randomly weighted selection from a set. But none of them are really straightforward. So I'd be interested to hear how others handled something like this. And if there's maybe a standard known algorithm, this kind of thing must appear in a lot of fields. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
I think you could do this with a binary tree - at each node keep a total of the weight values of the subtree below the node. If the pattern was hashed, then each bit could define a branch of the tree, 0 = left branch 1 = right branch. Then you have a very simple divide and conquer algorithm. The tree would not be perfectly balanced, but even with a lousy (fast) hash function it would be more than adequate. You could have a massive populations of things to select from probabilistically and this would still be very fast. - Don On Wed, Jul 15, 2009 at 7:06 PM, Mark Boon tesujisoftw...@gmail.com wrote: When using patterns during the playout I had improvised some code to select patterns randomly, but favour those with higher weights more or less proportionally to the weight.. I was wondering though if there's an established algorithm for something like this. To be a little more precise, if I have a set of values and two of those are represented by A and B. If A is twice as high as B it should have twice the chance to be selected. If there's a third value C that is 1.5 times A then it should be 1.5 times as likely to be selected as A and 3 times as likely as B. Etc. There are many strategies I can think of that make a randomly weighted selection from a set. But none of them are really straightforward. So I'd be interested to hear how others handled something like this. And if there's maybe a standard known algorithm, this kind of thing must appear in a lot of fields. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Random weighted patterns
So many complex ideas :) Why not just multiply the weight of each pattern by a random number and pick the biggest result? David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Mark Boon Sent: Wednesday, July 15, 2009 4:07 PM To: computer-go Subject: [computer-go] Random weighted patterns When using patterns during the playout I had improvised some code to select patterns randomly, but favour those with higher weights more or less proportionally to the weight.. I was wondering though if there's an established algorithm for something like this. To be a little more precise, if I have a set of values and two of those are represented by A and B. If A is twice as high as B it should have twice the chance to be selected. If there's a third value C that is 1.5 times A then it should be 1.5 times as likely to be selected as A and 3 times as likely as B. Etc. There are many strategies I can think of that make a randomly weighted selection from a set. But none of them are really straightforward. So I'd be interested to hear how others handled something like this. And if there's maybe a standard known algorithm, this kind of thing must appear in a lot of fields. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
So many complex ideas :) Why not just multiply the weight of each pattern by a random number and pick the biggest result? Good for 5 patterns, not so good for 5000 patterns. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Random weighted patterns
You would only do this for patterns that match in a position. For Many Faces that is typically a few dozen. Many Faces only has about 1800 total patterns in its go knowledge base. Playouts use Mogo patterns, about a dozen total. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Darren Cook Sent: Wednesday, July 15, 2009 8:47 PM To: computer-go Subject: Re: [computer-go] Random weighted patterns So many complex ideas :) Why not just multiply the weight of each pattern by a random number and pick the biggest result? Good for 5 patterns, not so good for 5000 patterns. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
On Wed, Jul 15, 2009 at 10:37 PM, David Fotlandfotl...@smart-games.com wrote: So many complex ideas :) Why not just multiply the weight of each pattern by a random number and pick the biggest result? David That involves generating N random numbers and then doing N-1 comparisons. The n-ary tree has only 1 random number and log N comparisons, but has to be incrementally updated (log N adds). Also, I don't think the distribution is the same. Imagine two moves a and b, with weights 2 and 1. The probabilities should be a=2/3 b=1/3, but if you select two random numbers in a finite range, there's only a 1/4 chance that the second number is more than twice the first, which is needed for b to be selected. I could be wrong here though. Zach ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
I must be missing something. Isn't the obvious trick:
int r = random(sum of weights);
int i = 0;
while (r weights[i]) {
r -= weights[i];
}
return i;
This way, you only have to generate one random number.
Peter Drake
http://www.lclark.edu/~drake/
On Jul 15, 2009, at 8:55 PM, Zach Wegner wrote:
On Wed, Jul 15, 2009 at 10:37 PM, David Fotlandfotl...@smart-games.com
wrote:
So many complex ideas :) Why not just multiply the weight of each
pattern
by a random number and pick the biggest result?
David
That involves generating N random numbers and then doing N-1
comparisons. The n-ary tree has only 1 random number and log N
comparisons, but has to be
incrementally updated (log N adds).
Also, I don't think the distribution is the same. Imagine two moves a
and b, with weights 2 and 1. The probabilities should be a=2/3 b=1/3,
but if you select two random numbers in a finite range, there's only a
1/4 chance that the second number is more than twice the first, which
is needed for b to be selected. I could be wrong here though.
Zach
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
In the loop i is always zero. I think your code is wrong.
You probably meant to loop over all the weights (or I should say on average
half the weights), and this code is slow if there are a lot of weights.
2009/7/16 Peter Drake dr...@lclark.edu
I must be missing something. Isn't the obvious trick:
int r = random(sum of weights);
int i = 0;
while (r weights[i]) {
r -= weights[i];
}
return i;
This way, you only have to generate one random number.
Peter Drake
http://www.lclark.edu/~drake/ http://www.lclark.edu/%7Edrake/
On Jul 15, 2009, at 8:55 PM, Zach Wegner wrote:
On Wed, Jul 15, 2009 at 10:37 PM, David Fotlandfotl...@smart-games.com
wrote:
So many complex ideas :) Why not just multiply the weight of each pattern
by a random number and pick the biggest result?
David
That involves generating N random numbers and then doing N-1
comparisons. The n-ary tree has only 1 random number and log N
comparisons, but has to be
incrementally updated (log N adds).
Also, I don't think the distribution is the same. Imagine two moves a
and b, with weights 2 and 1. The probabilities should be a=2/3 b=1/3,
but if you select two random numbers in a finite range, there's only a
1/4 chance that the second number is more than twice the first, which
is needed for b to be selected. I could be wrong here though.
Zach
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
On Wed, Jul 15, 2009 at 11:37 PM, David Fotland fotl...@smart-games.comwrote: So many complex ideas :) Why not just multiply the weight of each pattern by a random number and pick the biggest result? This is fine if you are looking for the slowest algorithm you can find. But it does have the merit of being straightforward, which is what he was asking for. The binary approach is O(log n) time on average, very efficient. Your approach is O(n). It's like the difference between doing a binary search to find something or scanning the whole list sequentially. If you are looking at less than 5 or 10 patterns there may not be much difference, but I assumed he was choosing among many patterns. - Don David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Mark Boon Sent: Wednesday, July 15, 2009 4:07 PM To: computer-go Subject: [computer-go] Random weighted patterns When using patterns during the playout I had improvised some code to select patterns randomly, but favour those with higher weights more or less proportionally to the weight.. I was wondering though if there's an established algorithm for something like this. To be a little more precise, if I have a set of values and two of those are represented by A and B. If A is twice as high as B it should have twice the chance to be selected. If there's a third value C that is 1.5 times A then it should be 1.5 times as likely to be selected as A and 3 times as likely as B. Etc. There are many strategies I can think of that make a randomly weighted selection from a set. But none of them are really straightforward. So I'd be interested to hear how others handled something like this. And if there's maybe a standard known algorithm, this kind of thing must appear in a lot of fields. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
A reasonable xor+shift random (similar to Marsaglia's, but only 64bit
instead of 128 bits), using the pentium's rdtsc-instrunction to add
additional entropy (i used gnu's inline assembler) :::
#define rdtscll(val) \
__asm__ __volatile__(rdtsc : =A (val))
typedef unsigned long long BIGTHING;
BIGTHING rdtsc_rand(void);
/**/
BIGTHING rdtsc_rand(void)
{
static BIGTHING val=0xULL;
BIGTHING new;
rdtscll(new);
val ^= (val 15) ^ (val 14) ^ 9 ^ new;
return val;
}
/**/
The extra ^9 at the end can be omitted if the new is nonzero.
(is only meant to avoid the val becoming all-zeros. And shifting zeros won't
change the value ;-)
HTH,
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
The question I have is how much does RDTSC slow this down?I may do
some tests to see.
- Don
A van Kessel wrote:
A reasonable xor+shift random (similar to Marsaglia's, but only 64bit
instead of 128 bits), using the pentium's rdtsc-instrunction to add
additional entropy (i used gnu's inline assembler) :::
#define rdtscll(val) \
__asm__ __volatile__(rdtsc : =A (val))
typedef unsigned long long BIGTHING;
BIGTHING rdtsc_rand(void);
/**/
BIGTHING rdtsc_rand(void)
{
static BIGTHING val=0xULL;
BIGTHING new;
rdtscll(new);
val ^= (val 15) ^ (val 14) ^ 9 ^ new;
return val;
}
/**/
The extra ^9 at the end can be omitted if the new is nonzero.
(is only meant to avoid the val becoming all-zeros. And shifting zeros won't
change the value ;-)
HTH,
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
The question I have is how much does RDTSC slow this down?I may do I don't know. If I understand correctly, rdtsc can be executed in parallen with *some* other instructions (and places no barrier in the code), in which case it could be executed at no additional cost (except the instruction fetching, of course) I have not yet been able to instruct GCC to use the mmx or sse3 instructions/ registers to do the shifting. Code could be reshuffeled to allow the compiler more freedom. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
I did a simple test. I compiled this version and the version below to
get a sense of how fast it is.
Your version with RDTSC is quite slow compared to the version below.
I determined that RDTSC is taking almost all the time however, because
just for fun I took out that call and it was much faster.
I generated 100 million random numbers in a for loop with and extra test
to print out the last 10 numbers and here are the times:
CMWC4096 = 0.712 seconds
KESSEL = 4.504 seconds
Here is the loop I used
for (i=1; i0; i--) {
cur = CMWC4096();
if (i = 10) {
printf(%20u %20d\n, cur, (int) cur - last);
}
last = cur;
}
And the code for CMWC4096 (without the initialization code)
static unsigned long Q[4096], c=362436;
unsigned int CMWC4096(void)
{
unsigned long long t, a=18782LL, b=4294967295LL;
static int i=4095;
unsigned int x, r=b-1;
i=(i+1)4095;
t=a*Q[i]+c;
c=(t32);
t=(tb)+c;
if(tr) {c++; t=t-b;}
return(Q[i]=r-t);
}
A van Kessel wrote:
A reasonable xor+shift random (similar to Marsaglia's, but only 64bit
instead of 128 bits), using the pentium's rdtsc-instrunction to add
additional entropy (i used gnu's inline assembler) :::
#define rdtscll(val) \
__asm__ __volatile__(rdtsc : =A (val))
typedef unsigned long long BIGTHING;
BIGTHING rdtsc_rand(void);
/**/
BIGTHING rdtsc_rand(void)
{
static BIGTHING val=0xULL;
BIGTHING new;
rdtscll(new);
val ^= (val 15) ^ (val 14) ^ 9 ^ new;
return val;
}
/**/
The extra ^9 at the end can be omitted if the new is nonzero.
(is only meant to avoid the val becoming all-zeros. And shifting zeros won't
change the value ;-)
HTH,
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
I doesn't seem too fast based on my test, but perhaps there are ways to optimize it. I would like to mention that your generator is 64 bit and the other generator was 32 bits but I'm running on a 64 bit core 2 duo OS and do not know how much of a factor this is or isn't. If RDTSC actually is too slow, a way around it is to design the RDTSC to be called only occasionally. But this involves a branching instruction which is probably going to hurt it too. I wonder if you could have a burst version that generates several at a time and queues them up? Then you grab them off the queue until you run out, then you insert some entropy with RDTSC and generate 16 more numbers or something like that.This still requires a branch instruction. Of course you are inserting far less entropy into the system if you only do it occasionally, but I would bet that you have several bits of entropy in this case, because a lot is going on before you get to the next call. - Don A van Kessel wrote: The question I have is how much does RDTSC slow this down?I may do I don't know. If I understand correctly, rdtsc can be executed in parallen with *some* other instructions (and places no barrier in the code), in which case it could be executed at no additional cost (except the instruction fetching, of course) I have not yet been able to instruct GCC to use the mmx or sse3 instructions/ registers to do the shifting. Code could be reshuffeled to allow the compiler more freedom. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
I would like to mention that your generator is 64 bit and the other That is correct. My timings (Haven't profiled yet): WITH TSC: real0m0.902s user0m0.870s sys 0m0.002s WITHOUT: real0m0.613s user0m0.582s sys 0m0.000s That's for 100 M random numbers. And inlining would probably help a lot, too. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
That's way different that what I'm getting. Something is wrong here. I'm getting 4.08 with RDTSC and when I just set new to 0ull I get 0.696 One of us must have done something wrong. - Don A van Kessel wrote: I would like to mention that your generator is 64 bit and the other That is correct. My timings (Haven't profiled yet): WITH TSC: real0m0.902s user0m0.870s sys 0m0.002s WITHOUT: real0m0.613s user0m0.582s sys 0m0.000s That's for 100 M random numbers. And inlining would probably help a lot, too. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
#include stdio.h
#include stdlib.h
I'm including my code below. Also, here are my reported times:
Without RDTSC
real0m1.008s
user0m0.668s
sys 0m0.004s
With RDTSC
real0m5.790s
user0m3.956s
sys 0m0.016s
To turn on or off RDTSC see the rdtsc_rand line that says, if (1)
- Don
--[ snip ]
#define rdtscll(val) \
__asm__ __volatile__(rdtsc : =A (val))
unsigned long long rdtsc_rand(void);
/**/
unsigned long long rdtsc_rand(void)
{
static unsigned long long val=0xULL;
unsigned long long new = 0llu;
if (1) {
rdtscll(new);
}
val ^= (val 15) ^ (val 14) ^ 9 ^ new;
return val;
}
void kessel()
{
int i;
unsigned long long last = 0;
unsigned long long cur = 0;
for (i=1; i0; i--) {
cur = rdtsc_rand();
if (i = 10) {
printf(%20llu %20lld\n, cur, (int) cur - last);
}
last = cur;
}
}
int main(int argc, char **argv)
{
kessel();
return(0);
}
A van Kessel wrote:
I would like to mention that your generator is 64 bit and the other
That is correct.
My timings (Haven't profiled yet):
WITH TSC:
real0m0.902s
user0m0.870s
sys 0m0.002s
WITHOUT:
real0m0.613s
user0m0.582s
sys 0m0.000s
That's for 100 M random numbers.
And inlining would probably help a lot, too.
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
I Just omitted the new variable:
/**/
BIGTHING rdtsc_rand(void)
{
static BIGTHING val=0xULL;
#if WANT_RDTSC
BIGTHING new;
rdtscll(new);
val ^= (val 15) ^ (val 14) ^ new;
#else
val ^= (val 15) ^ (val 14) ^ 9 ;
#endif
return val;
}
/**/
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Has anyone looked at the resultant distributions, to Well, mine was pretty random. Maybe a bit too random. Changing the 14 and 15 shifts effectively cripples it. I have not looked at sequential correlation, only at the distribution, by binning the values into a histogram. As far as I could see it has a good spreading. YMMV. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
terry mcintyre wrote:
Has anyone looked at the resultant distributions, to
determine how random they are?
They should be run against the dieharder tests before any confidence is
placed in them. But I did look at them visually to see if there was
anything wrong that was immediately obvious to me. Visual inspection may
find an obvious bug, but it's not worth much after that.
If I could get van Kessel's numbers I would consider packaging it up and
running it through the diharder tests, but otherwise I see no reason
since I am not yet happy with the performance.
- Don
--- Don Dailey [EMAIL PROTECTED] wrote:
#include stdio.h
#include stdlib.h
I'm including my code below. Also, here are my
reported times:
Without RDTSC
real0m1.008s
user0m0.668s
sys 0m0.004s
With RDTSC
real0m5.790s
user0m3.956s
sys 0m0.016s
To turn on or off RDTSC see the rdtsc_rand line
that says, if (1)
- Don
--[ snip ]
#define rdtscll(val) \
__asm__ __volatile__(rdtsc : =A (val))
unsigned long long rdtsc_rand(void);
/**/
unsigned long long rdtsc_rand(void)
{
static unsigned long long
val=0xULL;
unsigned long long new = 0llu;
if (1) {
rdtscll(new);
}
val ^= (val 15) ^ (val 14) ^ 9 ^ new;
return val;
}
void kessel()
{
int i;
unsigned long long last = 0;
unsigned long long cur = 0;
for (i=1; i0; i--) {
cur = rdtsc_rand();
if (i = 10) {
printf(%20llu %20lld\n, cur, (int) cur -
last);
}
last = cur;
}
}
int main(int argc, char **argv)
{
kessel();
return(0);
}
A van Kessel wrote:
I would like to mention that your generator is 64
bit and the other
That is correct.
My timings (Haven't profiled yet):
WITH TSC:
real0m0.902s
user0m0.870s
sys 0m0.002s
WITHOUT:
real0m0.613s
user0m0.582s
sys 0m0.000s
That's for 100 M random numbers.
And inlining would probably help a lot, too.
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Terry McIntyre lt;[EMAIL PROTECTED]gt;
“Wherever is found what is called a paternal government, there is found state
education. It has been discovered that the best way to insure implicit
obedience is to commence tyranny in the nursery.”
Benjamin Disraeli, Speech in the House of Commons [June 15, 1874]
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Ok, please check your number again.I set mine up like yours just in
case and I still get at least a 5x slowdown.
I think yours are probably wrong because I have seen numbers that
indicate RDTSC is really slow.
- Don
A van Kessel wrote:
I Just omitted the new variable:
/**/
BIGTHING rdtsc_rand(void)
{
static BIGTHING val=0xULL;
#if WANT_RDTSC
BIGTHING new;
rdtscll(new);
val ^= (val 15) ^ (val 14) ^ new;
#else
val ^= (val 15) ^ (val 14) ^ 9 ;
#endif
return val;
}
/**/
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Are you using the same hardware? I was looking over the instruction timings, and there's a lot of variation depending on the architecture. --- Don Dailey [EMAIL PROTECTED] wrote: That's way different that what I'm getting. Something is wrong here. I'm getting 4.08 with RDTSC and when I just set new to 0ull I get 0.696 One of us must have done something wrong. - Don A van Kessel wrote: I would like to mention that your generator is 64 bit and the other That is correct. My timings (Haven't profiled yet): WITH TSC: real0m0.902s user0m0.870s sys 0m0.002s WITHOUT: real0m0.613s user0m0.582s sys 0m0.000s That's for 100 M random numbers. And inlining would probably help a lot, too. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Terry McIntyre lt;[EMAIL PROTECTED]gt; Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery. Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Measurements ar pretty consistent. Hardware: Linux localhost.localdomain 2.6.23.1-42.fc8 #1 SMP Tue Oct 30 13:55:12 EDT 2007 i686 athlon i386 GNU/Linux (I didnot even know it was an athlon !) AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Mine: cat /proc/cpuinfo processor : 0 vendor_id : AuthenticAMD cpu family : 6 model : 10 model name : AMD Athlon(tm) XP 2800+ stepping: 0 cpu MHz : 2079.595 cache size : 512 KB fdiv_bug: no hlt_bug : no f00f_bug: no coma_bug: no fpu : yes fpu_exception : yes cpuid level : 1 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic mtrr pge mca cmov pat pse36 mmx fxsr sse syscall mmxext 3dnowext 3dnow up ts bogomips: 4160.98 clflush size: 32 AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Michael Williams wrote:
I don't think Don was saying to use many calls to RDTSC to generate a
single random number.
I think he meant do something like (FastBadRand() XOR RDTSC).
The first part has low quality low-order bits and the second part has
low quality high-order bits.
That was my exact idea, to xor or add RDTSC to the results.If that
really is a slow operation then it basically kills the idea. The cycle
time should be published somewhere though.
- Don
Also, I can't imagine why executing a RDTSC would take 50 cycles. But
I couldn't find any docs on that aspect of the instruction.
steve uurtamo wrote:
the only thing to watch is that you'll likely need
30+ bits from these guys to seed a prng, and
getting those bits in any organized way is likely
going to happen on a regular schedule (i.e. if
you get them in a loop, you're likely going to
space them out in an organized way).
s.
On 5/15/08, Don Dailey [EMAIL PROTECTED] wrote:
For a long time I have pondered whether you could build a very high
quality
random number generator that was extremely fast using the pentium RDTSC
instruction as a low order bit entropy source. The idea would be
to use
an extremely fast (but low quality) pseudo random number generator,
but
modify the output (or the internal state of the generator) with the
time
stamp register at each call.
RDTSC reads the pentiums internal clock and is basically just a 64 bit
counter.However it increments very quickly and could be viewed
as an
entropy source in the lowest bits as it would introduce at least a
little
bit of non-determinism, and I think a little is all you would need to
transform a horrible generator into a good practical one for many
applications. I think the lowest 2 or 3 (or more) bits would
appear to
modern processors as almost unpredictable since there is so much
going on
inside modern computers that are unpredictable.
I don't know if the call to RDTSC is fast or how it would affect the
parallelism of todays modern machines. I'm not particularly
interested in
non-deterministic generators as I sometimes depend on this for
testing and
debugging, but it's an idea I thought I would throw out there.
- Don
Don Dailey wrote:
If you are looking for a cheap fast and simple random number
generator, A
post by George Marsaglia, an expert/guru on random number generation
has
several and a C implemention.
These are one line generators, coded as macros.He also
discusses the
period and quality of each of them. This is a gem of a post on
sci.stat.math,sci.math if you are interested in RNG:
http://www.math.niu.edu/~rusin/known-math/99/RNG
- Don
Heikki Levanto wrote:
In addition, xor_shift is better than builtin rand() and faster and
much smaller than MT.
I don't know that much about random numbers, so excuse my
ignorance. But
a
bit of googling got me to the Park - Miller Minimal Standard random
number
generator
http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
From what I read, it should be quite sufficient for go programs.
It is
dead simple and fast:
long int pmrand() {
const long int a=16807;
const long int m= ( 1 31 ) -1;
pmrandseed = ( pmrandseed * a ) % m ;
return pmrandseed;
} /* pmrand */
Should I worry about this not being good enough?
- Heikki
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Michael Williams wrote:
I don't think Don was saying to use many calls to RDTSC to generate a
single random number.
I think he meant do something like (FastBadRand() XOR RDTSC).
The first part has low quality low-order bits and the second part has
low quality high-order bits.
I also intended for RDTSC to change the state of the random number
generator which would be extremely chaotic over time. Some
FastBadRand() generators use the last value returned as the state.
- Don
Also, I can't imagine why executing a RDTSC would take 50 cycles. But
I couldn't find any docs on that aspect of the instruction.
steve uurtamo wrote:
the only thing to watch is that you'll likely need
30+ bits from these guys to seed a prng, and
getting those bits in any organized way is likely
going to happen on a regular schedule (i.e. if
you get them in a loop, you're likely going to
space them out in an organized way).
s.
On 5/15/08, Don Dailey [EMAIL PROTECTED] wrote:
For a long time I have pondered whether you could build a very high
quality
random number generator that was extremely fast using the pentium RDTSC
instruction as a low order bit entropy source. The idea would be
to use
an extremely fast (but low quality) pseudo random number generator,
but
modify the output (or the internal state of the generator) with the
time
stamp register at each call.
RDTSC reads the pentiums internal clock and is basically just a 64 bit
counter.However it increments very quickly and could be viewed
as an
entropy source in the lowest bits as it would introduce at least a
little
bit of non-determinism, and I think a little is all you would need to
transform a horrible generator into a good practical one for many
applications. I think the lowest 2 or 3 (or more) bits would
appear to
modern processors as almost unpredictable since there is so much
going on
inside modern computers that are unpredictable.
I don't know if the call to RDTSC is fast or how it would affect the
parallelism of todays modern machines. I'm not particularly
interested in
non-deterministic generators as I sometimes depend on this for
testing and
debugging, but it's an idea I thought I would throw out there.
- Don
Don Dailey wrote:
If you are looking for a cheap fast and simple random number
generator, A
post by George Marsaglia, an expert/guru on random number generation
has
several and a C implemention.
These are one line generators, coded as macros.He also
discusses the
period and quality of each of them. This is a gem of a post on
sci.stat.math,sci.math if you are interested in RNG:
http://www.math.niu.edu/~rusin/known-math/99/RNG
- Don
Heikki Levanto wrote:
In addition, xor_shift is better than builtin rand() and faster and
much smaller than MT.
I don't know that much about random numbers, so excuse my
ignorance. But
a
bit of googling got me to the Park - Miller Minimal Standard random
number
generator
http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
From what I read, it should be quite sufficient for go programs.
It is
dead simple and fast:
long int pmrand() {
const long int a=16807;
const long int m= ( 1 31 ) -1;
pmrandseed = ( pmrandseed * a ) % m ;
return pmrandseed;
} /* pmrand */
Should I worry about this not being good enough?
- Heikki
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Regarding the time used by RDTSC: From http://smallcode.weblogs.us/2007/12/07/performance-measurements-with-rdtsc/ Intel and Agner Fog recommend measuring the overhead of RDTSC function and subtracting it from your result. The overhead is relatively low (150-200 clock cycles) and it occurs in all tested functions, so you can neglect it when measuring long functions (e.g., 100 000 clock cycles). NOTE: the page above recommends flushing the cache before calling RDTSC, when using it for timing purposes. There is probably no need to do so when grabbing LSBs. I wonder, however, if the LSBs would be as random as all that, when called frequently in quasi-deterministic code which takes a predictable number of cycles between invocations. Terry McIntyre lt;[EMAIL PROTECTED]gt; Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery. Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
terry mcintyre wrote: Regarding the time used by RDTSC: From http://smallcode.weblogs.us/2007/12/07/performance-measurements-with-rdtsc/ Intel and Agner Fog recommend measuring the overhead of RDTSC function and subtracting it from your result. The overhead is relatively low (150-200 clock cycles) and it occurs in all tested functions, so you can neglect it when measuring long functions (e.g., 100 000 clock cycles). NOTE: the page above recommends flushing the cache before calling RDTSC, when using it for timing purposes. There is probably no need to do so when grabbing LSBs. I wonder, however, if the LSBs would be as random as all that, when called frequently in quasi-deterministic code which takes a predictable number of cycles between invocations. I'm not interested in using it here to measure performance, but as a possible way to have a very fast and very high quality random number function. But this won't happen if RDTSC isn't fast and it doesn't appear to be very fast. I don't expect RDTSC to be very random either, I'm more interested in the chaos it presents to the random number system which is produced even with very little agitation added to the system. Even an occasional 1 bit change would cure many of the problems of some fast random number generators. If you were to call this random number generator consecutively, many time in a tight loop, I suspect that you will get a LOT of variation in the number of cycles that have passed between calls, certainly enough to make it completely unpredictable in the long run. Like weather predictions you might predict the next day (or call) with some level of reasonable accuracy but not a specific day in the next month. Every deterministic pseudo random number generator in existence always has some kind of structure. The main difference between what we consider good and bad ones is how well that structure is obfuscated or hidden from view. We try to be clever so that statistical tests cannot see the structure. One of primary methods to hide this structure is to make it so big (by long cycle lengths) that we can only see a tiny portion of it. For instance if every zillion'th bit alternated between 0 and 1, it would be hard to observe. So if you can add a small amount of non-determinism you can probably bust up the hidden structure. At any rate, it seems like it's not workable as a fast alternative to RNG. It might be combined with a slow very high quality generator to produce numbers that are somewhat closer to true random numbers. - Don Terry McIntyre lt;[EMAIL PROTECTED]gt; “Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery.” Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Zach Wegner wrote: What you could do is XOR the RDTSC into the seed (or array or whatever your RNG uses) at the beginning of each playout. That adds to the chaos but doesn't slow it down much at all. I like your idea. Yes, you could probably use a really fast simple RNG and do this. AnchorMan had a very trivial RNG and I noticed that if you played enough games, you start getting the same games over and over. So I could only play a few hundreds before this started happening (for instance playing anchor vs anchor.) It seems like with 4 billion possible seeds that this would not happen (each games started with a seed based on the time() call.) But apparently something was going on that I didn't understand because there seemed to be only a few hundred games possible (at any fixed level.) I switched over to Mersenne Twister and this problem went away. MT did not improve the playing quality in any way I could notice, so I don't believe MC in general requires a very good RNG. I once built a card playing program, and while developing a playing strategy I tested different versions against each other. But then I tried as a sanity check, testing the same version against itself, and I noticed a systematic bias, one particular side was winning something like 53 or 54 percent of the games even though the conditions were unbiased. I discovered the problem was with the RNG in the C library (this was a long time ago.)I solved the problem by changing the way I shuffled the cards.Originally I created a deck from scratch which always had the same ordering, then I would apply the standard Fischer-Yates shuffle. The fix was to reuse the deck from the last game and shuffle THAT deck. Basically I grabbed up all the cards in the players hands and on the table and put them back in the deck just like us humans do when playing cards, then I would shuffle them.The effect was that I implicitly created a more sophisticated RNG with lots of state and more than likely a very long cycle time compared to the simple one I started with. This could be done with your go program too. If you have some sort of list of all the legal points at the beginning of the game that you work with and manipulate, just leave it alone instead of reinitializing it.Or let the move sequences of the previous game impact the initial ordering or how the game is played.You would be getting a more sophisticated RNG for free. Of course you have to save state between program invocations and that's probably too ugly. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Hi, As mentioned before, Monte Carlo simulations in physics was my thesis topic, and there we need REALLY good PRNGs or we see the effect in the results. There is always a tradeoff between fast and good. If the newer Mersine Twister algorithms (which are very good) is too slow and you want to test an alternative, you can use the trick that is in Knuth that I used for my thesis work. It is a 2 step generator that shuffles. You build an array that holds a set of PRNGs straight from your crude but very fast generator (I was partial to a list of 273), Your first PRNG call mod(arraysize) picks the PRN you will use, and then the second refills that spot. No promises that this is any faster, but for lattice simulations where any correlations pop right out at you sort of like a herringbone pattern, this shuffling worked great for me. Personally, I think that much of the really high quality issues are not that important for MC Go right now. I think that other things like not having a reasonable distribution function (which UCT does a remarkable job of smoothing over) completely overwhelm the effects of a poor PRNG. Cheers, David On 16, May 2008, at 10:42 AM, Don Dailey wrote: terry mcintyre wrote: Regarding the time used by RDTSC: From http://smallcode.weblogs.us/2007/12/07/performance-measurements-with-rdtsc/ Intel and Agner Fog recommend measuring the overhead of RDTSC function and subtracting it from your result. The overhead is relatively low (150-200 clock cycles) and it occurs in all tested functions, so you can neglect it when measuring long functions (e.g., 100 000 clock cycles). NOTE: the page above recommends flushing the cache before calling RDTSC, when using it for timing purposes. There is probably no need to do so when grabbing LSBs. I wonder, however, if the LSBs would be as random as all that, when called frequently in quasi-deterministic code which takes a predictable number of cycles between invocations. I'm not interested in using it here to measure performance, but as a possible way to have a very fast and very high quality random number function. But this won't happen if RDTSC isn't fast and it doesn't appear to be very fast. I don't expect RDTSC to be very random either, I'm more interested in the chaos it presents to the random number system which is produced even with very little agitation added to the system. Even an occasional 1 bit change would cure many of the problems of some fast random number generators. If you were to call this random number generator consecutively, many time in a tight loop, I suspect that you will get a LOT of variation in the number of cycles that have passed between calls, certainly enough to make it completely unpredictable in the long run. Like weather predictions you might predict the next day (or call) with some level of reasonable accuracy but not a specific day in the next month. Every deterministic pseudo random number generator in existence always has some kind of structure. The main difference between what we consider good and bad ones is how well that structure is obfuscated or hidden from view. We try to be clever so that statistical tests cannot see the structure. One of primary methods to hide this structure is to make it so big (by long cycle lengths) that we can only see a tiny portion of it. For instance if every zillion'th bit alternated between 0 and 1, it would be hard to observe. So if you can add a small amount of non-determinism you can probably bust up the hidden structure. At any rate, it seems like it's not workable as a fast alternative to RNG. It might be combined with a slow very high quality generator to produce numbers that are somewhat closer to true random numbers. - Don Terry McIntyre lt;[EMAIL PROTECTED]gt; “Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery.” Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Personally, I think that much of the really high quality issues are not that important for MC Go right now. I think that other things like not having a reasonable distribution function (which UCT does a remarkable job of smoothing over) completely overwhelm the effects of a poor PRNG. I agree with that. By the way, I have spent time on the use of improved forms of Monte-Carlo (quasi-random, stratification, ...) but I've never found an efficient trick. OT ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
That's very interesting and I believe it explains everything perfectly. If I understand this correctly, my 4 billion possible seeds (I used a 32 bit seed) cannot produce 32 billion different games (against the same deterministic opponent.) In my implementation there were also issues with the lower ordered bits which of course are less random. - Don terry mcintyre wrote: An interesting note from http://en.wikipedia.org/wiki/Knuth_shuffle which appears to be pertinent to Don's remarks about a limited number of games: quote Limited PRNG state space An additional problem occurs when the Fisher-Yates shuffle is used with a pseudorandom number generator: as the sequence of numbers output by such a generator is entirely determined by its internal state at the start of a sequence, a shuffle driven by such a generator cannot possibly produce more distinct permutations than the generator has distinct possible states. Even when the number of possible states exceeds the number of permutations, the irregular nature of the mapping from sequences of numbers to permutations means that some permutations will occur more often than others. Thus, to minimize bias, the number of states of the PRNG should exceed the number of permutations by at least several orders of magnitude. For example, the built-in pseudorandom number generator provided by many programming languages and/or libraries may often have only 32 bits of internal state, which means it can only produce 232 different sequences of numbers. If such a generator is used to shuffle a deck of 52 playing cards, it can only ever produce a vanishingly small fraction of the 52! #8776; 2225.6 possible permutations. Thus, it's impossible for a generator with less than 226 bits of internal state to produce all the possible permutations of a 52-card deck, and for a (reasonably) unbiased shuffle, the generator must have at least about 250 bits of state. A further problem occurs when a simple linear congruential PRNG is used with the divide-and-take-remainder method of range reduction described above. The problem here is that the low-order bits of a linear congruential PRNG are less random than the high-order ones: the low n bits of the generator themselves have a period of at most 2n. When the divisor is a power of two, taking the remainder essentially means throwing away the high-order bits, such that one ends up with a significantly less random value. Also, of course, no pseudorandom number generator can produce more distinct sequences than there are distinct seed values it may be initialized with. Thus, it doesn't matter much if a generator has 1024 bits of internal state if it is only ever initialized with a 32-bit seed. /quote The page also describes several other sources of bias which may be pertinent to the development of MC programs. Terry McIntyre lt;[EMAIL PROTECTED]gt; “Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery.” Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
These shuffles are different than the one I used and attempted to describe. Cheers, David On 16, May 2008, at 12:55 PM, terry mcintyre wrote: An interesting note from http://en.wikipedia.org/wiki/Knuth_shuffle which appears to be pertinent to Don's remarks about a limited number of games: quote Limited PRNG state space ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
If you are looking for a cheap fast and simple random number generator,
A post by George Marsaglia, an expert/guru on random number generation
has several and a C implemention.
These are one line generators, coded as macros.He also discusses
the period and quality of each of them.
This is a gem of a post on sci.stat.math,sci.math if you are
interested in RNG:
http://www.math.niu.edu/~rusin/known-math/99/RNG
- Don
Heikki Levanto wrote:
In addition, xor_shift is better than builtin rand() and faster and
much smaller than MT.
I don't know that much about random numbers, so excuse my ignorance. But a
bit of googling got me to the Park - Miller Minimal Standard random number
generator
http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
From what I read, it should be quite sufficient for go programs. It is
dead simple and fast:
long int pmrand() {
const long int a=16807;
const long int m= ( 1 31 ) -1;
pmrandseed = ( pmrandseed * a ) % m ;
return pmrandseed;
} /* pmrand */
Should I worry about this not being good enough?
- Heikki
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
For a long time I have pondered whether you could build a very high
quality random number generator that was extremely fast using the
pentium RDTSC instruction as a low order bit entropy source. The
idea would be to use an extremely fast (but low quality) pseudo random
number generator, but modify the output (or the internal state of the
generator) with the time stamp register at each call.
RDTSC reads the pentiums internal clock and is basically just a 64 bit
counter.However it increments very quickly and could be viewed as an
entropy source in the lowest bits as it would introduce at least a
little bit of non-determinism, and I think a little is all you would
need to transform a horrible generator into a good practical one for
many applications. I think the lowest 2 or 3 (or more) bits would
appear to modern processors as almost unpredictable since there is so
much going on inside modern computers that are unpredictable.
I don't know if the call to RDTSC is fast or how it would affect the
parallelism of todays modern machines. I'm not particularly interested
in non-deterministic generators as I sometimes depend on this for
testing and debugging, but it's an idea I thought I would throw out
there.
- Don
Don Dailey wrote:
If you are looking for a cheap fast and simple random number
generator, A post by George Marsaglia, an expert/guru on random
number generation has several and a C implemention.
These are one line generators, coded as macros.He also discusses
the period and quality of each of them.
This is a gem of a post on sci.stat.math,sci.math if you are
interested in RNG:
http://www.math.niu.edu/~rusin/known-math/99/RNG
- Don
Heikki Levanto wrote:
In addition, xor_shift is better than builtin rand() and faster and
much smaller than MT.
I don't know that much about random numbers, so excuse my ignorance.
But a
bit of googling got me to the Park - Miller Minimal Standard random
number
generatorhttp://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
From what I read, it should be quite sufficient for go programs. It is
dead simple and fast:
long int pmrand() {
const long int a=16807;
const long int m= ( 1 31 ) -1;
pmrandseed = ( pmrandseed * a ) % m ;
return pmrandseed;
} /* pmrand */
Should I worry about this not being good enough?
- Heikki
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Heikki Levanto wrote:
In addition, xor_shift is better than builtin rand() and faster and
much smaller than MT.
I don't know that much about random numbers, so excuse my ignorance. But a
bit of googling got me to the Park - Miller Minimal Standard random number
generator
http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
That reference goes back to 1988 and what it comes to random number
generators that is ancient.Is there a modern analysis of this
generator anywhere?
- Don
From what I read, it should be quite sufficient for go programs. It is
dead simple and fast:
long int pmrand() {
const long int a=16807;
const long int m= ( 1 31 ) -1;
pmrandseed = ( pmrandseed * a ) % m ;
return pmrandseed;
} /* pmrand */
Should I worry about this not being good enough?
- Heikki
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
the only thing to watch is that you'll likely need
30+ bits from these guys to seed a prng, and
getting those bits in any organized way is likely
going to happen on a regular schedule (i.e. if
you get them in a loop, you're likely going to
space them out in an organized way).
s.
On 5/15/08, Don Dailey [EMAIL PROTECTED] wrote:
For a long time I have pondered whether you could build a very high quality
random number generator that was extremely fast using the pentium RDTSC
instruction as a low order bit entropy source. The idea would be to use
an extremely fast (but low quality) pseudo random number generator, but
modify the output (or the internal state of the generator) with the time
stamp register at each call.
RDTSC reads the pentiums internal clock and is basically just a 64 bit
counter.However it increments very quickly and could be viewed as an
entropy source in the lowest bits as it would introduce at least a little
bit of non-determinism, and I think a little is all you would need to
transform a horrible generator into a good practical one for many
applications. I think the lowest 2 or 3 (or more) bits would appear to
modern processors as almost unpredictable since there is so much going on
inside modern computers that are unpredictable.
I don't know if the call to RDTSC is fast or how it would affect the
parallelism of todays modern machines. I'm not particularly interested in
non-deterministic generators as I sometimes depend on this for testing and
debugging, but it's an idea I thought I would throw out there.
- Don
Don Dailey wrote:
If you are looking for a cheap fast and simple random number generator, A
post by George Marsaglia, an expert/guru on random number generation has
several and a C implemention.
These are one line generators, coded as macros.He also discusses the
period and quality of each of them. This is a gem of a post on
sci.stat.math,sci.math if you are interested in RNG:
http://www.math.niu.edu/~rusin/known-math/99/RNG
- Don
Heikki Levanto wrote:
In addition, xor_shift is better than builtin rand() and faster and
much smaller than MT.
I don't know that much about random numbers, so excuse my ignorance. But
a
bit of googling got me to the Park - Miller Minimal Standard random
number
generator
http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
From what I read, it should be quite sufficient for go programs. It is
dead simple and fast:
long int pmrand() {
const long int a=16807;
const long int m= ( 1 31 ) -1;
pmrandseed = ( pmrandseed * a ) % m ;
return pmrandseed;
} /* pmrand */
Should I worry about this not being good enough?
- Heikki
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
IIRC the RDTSC instruction is very slow, on the order of 50 cycles. In addition, I like having deterministic generators so that hypothetically I could reproduce any result. In my chess program I use a modified version of Agner Fog's Ranrot. It's very fast and very random. There's a paper on his site on the theory behind it: http://www.agner.org/random/theory/ (the first link). You can see the actual generator I use here: http://zct.cvs.sourceforge.net/*checkout*/zct/zct/rand.c?revision=1.2 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
I don't think Don was saying to use many calls to RDTSC to generate a single
random number.
I think he meant do something like (FastBadRand() XOR RDTSC).
The first part has low quality low-order bits and the second part has low
quality high-order bits.
Also, I can't imagine why executing a RDTSC would take 50 cycles. But I
couldn't find any docs on that aspect of the instruction.
steve uurtamo wrote:
the only thing to watch is that you'll likely need
30+ bits from these guys to seed a prng, and
getting those bits in any organized way is likely
going to happen on a regular schedule (i.e. if
you get them in a loop, you're likely going to
space them out in an organized way).
s.
On 5/15/08, Don Dailey [EMAIL PROTECTED] wrote:
For a long time I have pondered whether you could build a very high quality
random number generator that was extremely fast using the pentium RDTSC
instruction as a low order bit entropy source. The idea would be to use
an extremely fast (but low quality) pseudo random number generator, but
modify the output (or the internal state of the generator) with the time
stamp register at each call.
RDTSC reads the pentiums internal clock and is basically just a 64 bit
counter.However it increments very quickly and could be viewed as an
entropy source in the lowest bits as it would introduce at least a little
bit of non-determinism, and I think a little is all you would need to
transform a horrible generator into a good practical one for many
applications. I think the lowest 2 or 3 (or more) bits would appear to
modern processors as almost unpredictable since there is so much going on
inside modern computers that are unpredictable.
I don't know if the call to RDTSC is fast or how it would affect the
parallelism of todays modern machines. I'm not particularly interested in
non-deterministic generators as I sometimes depend on this for testing and
debugging, but it's an idea I thought I would throw out there.
- Don
Don Dailey wrote:
If you are looking for a cheap fast and simple random number generator, A
post by George Marsaglia, an expert/guru on random number generation has
several and a C implemention.
These are one line generators, coded as macros.He also discusses the
period and quality of each of them. This is a gem of a post on
sci.stat.math,sci.math if you are interested in RNG:
http://www.math.niu.edu/~rusin/known-math/99/RNG
- Don
Heikki Levanto wrote:
In addition, xor_shift is better than builtin rand() and faster and
much smaller than MT.
I don't know that much about random numbers, so excuse my ignorance. But
a
bit of googling got me to the Park - Miller Minimal Standard random
number
generator
http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
From what I read, it should be quite sufficient for go programs. It is
dead simple and fast:
long int pmrand() {
const long int a=16807;
const long int m= ( 1 31 ) -1;
pmrandseed = ( pmrandseed * a ) % m ;
return pmrandseed;
} /* pmrand */
Should I worry about this not being good enough?
- Heikki
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random
Following url may help.
http://softwarecommunity.intel.com/isn/Community/en-US/forums/thread/30235396.aspx
-Hideki
Michael Williams: [EMAIL PROTECTED]:
I don't think Don was saying to use many calls to RDTSC to generate a single
random number.
I think he meant do something like (FastBadRand() XOR RDTSC).
The first part has low quality low-order bits and the second part has low
quality high-order
bits.
Also, I can't imagine why executing a RDTSC would take 50 cycles. But I
couldn't find any
docs on that aspect of the instruction.
steve uurtamo wrote:
the only thing to watch is that you'll likely need
30+ bits from these guys to seed a prng, and
getting those bits in any organized way is likely
going to happen on a regular schedule (i.e. if
you get them in a loop, you're likely going to
space them out in an organized way).
s.
On 5/15/08, Don Dailey [EMAIL PROTECTED] wrote:
For a long time I have pondered whether you could build a very high quality
random number generator that was extremely fast using the pentium RDTSC
instruction as a low order bit entropy source. The idea would be to use
an extremely fast (but low quality) pseudo random number generator, but
modify the output (or the internal state of the generator) with the time
stamp register at each call.
RDTSC reads the pentiums internal clock and is basically just a 64 bit
counter.However it increments very quickly and could be viewed as an
entropy source in the lowest bits as it would introduce at least a little
bit of non-determinism, and I think a little is all you would need to
transform a horrible generator into a good practical one for many
applications. I think the lowest 2 or 3 (or more) bits would appear to
modern processors as almost unpredictable since there is so much going on
inside modern computers that are unpredictable.
I don't know if the call to RDTSC is fast or how it would affect the
parallelism of todays modern machines. I'm not particularly interested in
non-deterministic generators as I sometimes depend on this for testing and
debugging, but it's an idea I thought I would throw out there.
- Don
Don Dailey wrote:
If you are looking for a cheap fast and simple random number generator, A
post by George Marsaglia, an expert/guru on random number generation has
several and a C implemention.
These are one line generators, coded as macros.He also discusses the
period and quality of each of them. This is a gem of a post on
sci.stat.math,sci.math if you are interested in RNG:
http://www.math.niu.edu/~rusin/known-math/99/RNG
- Don
Heikki Levanto wrote:
In addition, xor_shift is better than builtin rand() and faster and
much smaller than MT.
I don't know that much about random numbers, so excuse my ignorance. But
a
bit of googling got me to the Park - Miller Minimal Standard random
number
generator
http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
From what I read, it should be quite sufficient for go programs. It is
dead simple and fast:
long int pmrand() {
const long int a=16807;
const long int m= ( 1 31 ) -1;
pmrandseed = ( pmrandseed * a ) % m ;
return pmrandseed;
} /* pmrand */
Should I worry about this not being good enough?
- Heikki
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
--
[EMAIL PROTECTED] (Kato)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
Probably the reason that it is so slow is that it's aiming for a cryptographically random number sequence. These are usually derived ultimately from kernel timings (often via /dev/random on linux systems) and it can take a while to establish a degree of confidence in the randomness of these bits. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] wrote: Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
A couple of things I did: I edited the Mersenne Twister code I'm using to get it's seed from the system time in nanoseconds rather than in miliseconds to fix the problem of wanting to generate more than one random number in a millisecond. Instead of generating a new random number every time I want to pick a move in a random playout, I fill a large circular array with random numbers when my go program launches (before it is actually playing a game) and I have a method that just gets the next number out of the array instead of generating a new random number in real time. Actually I have a different array for each possible board size, since I need a random integer from a different range for each. Sure the array repeats after 500,000 numbers or however many you use, but this is not a big deal when your playouts are only 100 moves long each - and it is unlikely to start repeating from the same position. This approach was much faster than generating random numbers on the fly. On Dec 19, 2007 3:51 AM, Stuart A. Yeates [EMAIL PROTECTED] wrote: Probably the reason that it is so slow is that it's aiming for a cryptographically random number sequence. These are usually derived ultimately from kernel timings (often via /dev/random on linux systems) and it can take a while to establish a degree of confidence in the randomness of these bits. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] wrote: Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
That was not the problem, as the source code is available and it doesn't call system libraries at all. I was initializing with known seed in my tests anyway. Thanks though, in the process of composing a reply demonstrating the problem, I found a partial solution. Now random number generation takes 3% of running time, compared to 60% of older version and ~1% of a hypothetical ideal solution. Berk. Stuart A. Yeates wrote: Probably the reason that it is so slow is that it's aiming for a cryptographically random number sequence. These are usually derived ultimately from kernel timings (often via /dev/random on linux systems) and it can take a while to establish a degree of confidence in the randomness of these bits. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] wrote: Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
A sorry about that. Glad to hear you fixed the problem. What was your solution? It seems you mentioned the global list approach in your email which I missed too. Why did you think this was an ugly approach? I just put my random array in a Singleton object (call it MyRandomNumberGenerator) which internally stores the next index and has a method for getting the next random number. So I just replace all my calls to Random.getNextInt() with MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of people would still call this ugly... But it's just a lookup so I think it will beat any other solution that involves generating a new random number by a reasonable margin. On Dec 19, 2007 5:15 AM, Berk Ozbozkurt [EMAIL PROTECTED] wrote: That was not the problem, as the source code is available and it doesn't call system libraries at all. I was initializing with known seed in my tests anyway. Thanks though, in the process of composing a reply demonstrating the problem, I found a partial solution. Now random number generation takes 3% of running time, compared to 60% of older version and ~1% of a hypothetical ideal solution. Berk. Stuart A. Yeates wrote: Probably the reason that it is so slow is that it's aiming for a cryptographically random number sequence. These are usually derived ultimately from kernel timings (often via /dev/random on linux systems) and it can take a while to establish a degree of confidence in the randomness of these bits. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] wrote: Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
Your solution would still be way faster, as I still have to generate a new random number every time I need one. The problem is lack of side effects in Clean. If I stick to functional programming paradigm -and that is the whole point of my effort- I can't write function which returns a different number each time it is called. A function is supposed to return same result every time it is called with same parameters so I can't/shouldn't write an analogue of getNextInt() (whether or not getNextInt() returns a number from a list or from a random number generator.) I just shaved off time by not initializing a new random generator each time a node is visited. Instead, when a leaf node is visited, first maxMoves terms of random list is sent to MC evaluation, and remaining terms are used to create a new list. Sharing this list across whole search tree would be ugly and complicated. So I still initialize a new random list for each new tree node but reuse it for subsequent MC evaluations from that node. Berk. Imran Hendley wrote: A sorry about that. Glad to hear you fixed the problem. What was your solution? It seems you mentioned the global list approach in your email which I missed too. Why did you think this was an ugly approach? I just put my random array in a Singleton object (call it MyRandomNumberGenerator) which internally stores the next index and has a method for getting the next random number. So I just replace all my calls to Random.getNextInt() with MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of people would still call this ugly... But it's just a lookup so I think it will beat any other solution that involves generating a new random number by a reasonable margin. On Dec 19, 2007 5:15 AM, Berk Ozbozkurt [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: That was not the problem, as the source code is available and it doesn't call system libraries at all. I was initializing with known seed in my tests anyway. Thanks though, in the process of composing a reply demonstrating the problem, I found a partial solution. Now random number generation takes 3% of running time, compared to 60% of older version and ~1% of a hypothetical ideal solution. Berk. Stuart A. Yeates wrote: Probably the reason that it is so slow is that it's aiming for a cryptographically random number sequence. These are usually derived ultimately from kernel timings (often via /dev/random on linux systems) and it can take a while to establish a degree of confidence in the randomness of these bits. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
Berk, Why do you need to initialize the seed more than 1 time?You should use zobrist hashing. Initialize the random number generator once when you start the programs. Fill an array with random numbers from the generator at program startup too. The array looks something like this for a 9x9 board: zob[3][81] Basically xor each point of the 9x9 board with the random number on the point. The first index is 3 because I assume you have white/black/empty points.So xor the appropriate one for each point. A major enhancement is that you can do this incrementally. You have a master key that you keep up to date. If you add a stone to the board, you can update the key with only 2 xor operations.Since the point is no longer empty you must undo the xor with the empty point.XOR is great because you can undo it with the same xor operation.So you get: if mv is the move you are about to make with a black stone then: master_hash = master_hash ^ zob[EMPTY][ mv ] master_hash = master_hash ^ zob[BLACK][ mv ] and you are done. Of course if a white group is captured, you must undo all the white stones that were captured in some kind of loop, but it still runs rings around updating the entire board on each move. There is a variation of this - you can choose to hash only 2 colors: (black and empty), (white and empty), or (black and white) and so the other color is inferred.The natural expression of this in a program is to hash only white and black because you never change state from black to white in a single move. - Don Berk Ozbozkurt wrote: Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
On Dec 19, 2007 10:24 AM, Don Dailey [EMAIL PROTECTED] wrote: Why do you need to initialize the seed more than 1 time?You should use zobrist hashing. By design, my program reinitializes the random seeds. This is done at the start of each genmove and is intended for repeatability. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
Instead of generating a new random number every time I want to pick a move in a random playout, I fill a large circular array with random numbers when my go program launches (before it is actually playing a game) and I have a method that just gets the next number out of the array instead of generating a new random number in real time. Actually I have a different array for each possible board size, since I need a random integer from a different range for each. Sure the array repeats after 500,000 numbers or however many you use, but this is not a big deal when your playouts are only 100 moves long each - and it is unlikely to start repeating from the same position. This approach was much faster than generating random numbers on the fly. That could affect your caches. This is generally the type of thing that can create unexpected problems if you are not very careful. You have essentially just created a very low period RNG. I would not play long autotest matches unless you re-initalize this before each game.I would also hope that you have enough to get you through a complete game (or nearly so.) Then you might get away with it. Years ago a wrote a rummy card game player and was testing different strategies against each other. I discovered that the RNG was low period and was getting consistently biased results (where identical programs were not scoring 50/50 but more like 52/48 over thousands of games.)It turned out to be the short period of the RNG causing the problem.It's very difficult if not impossible to predict how this will affect the period of your application. You could fall into a winning or losing cycle against another similarly deterministic player and it could be short or fairly long. (A cycle where you will lose or win more games than you should and games will repeat.) This behavior is guaranteed, it's a just a matter of how long or short the cycle will be. I improved the problem with the card game by adding more chaos. It wasn't the ideal solution but it was an improvement.Instead of re-initializing a new pack of cards, I kept the old pack around and re-shuffled it. Effectively, this is like creating a slightly more sophisticated RNG with a longer period. So each new game began with a deck of cards that were in chaos from the previous game (similar to real card games.) I'm surprised that this represents a large speedup. How long does it take to initialize a new set of random numbers? I would think this would happen very quickly. However long it takes, I would think that an upper bound on how much time you can save (minus some caching effects perhaps) would be this same time spent building a new set of numbers. So if it takes about 5 seconds, you should only lose about 5 seconds for the whole game assuming you initialized just enough numbers to play a full game. - Don On Dec 19, 2007 3:51 AM, Stuart A. Yeates [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: Probably the reason that it is so slow is that it's aiming for a cryptographically random number sequence. These are usually derived ultimately from kernel timings (often via /dev/random on linux systems) and it can take a while to establish a degree of confidence in the randomness of these bits. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go
Re: [computer-go] random numbers with functional languages
Hold on, I just re-read this.Do you think you must initialize the generator after each number? You only need to initialize MT once, when your program starts and then it will provide very good numbers for the next several billion years. - Don Imran Hendley wrote: A couple of things I did: I edited the Mersenne Twister code I'm using to get it's seed from the system time in nanoseconds rather than in miliseconds to fix the problem of wanting to generate more than one random number in a millisecond. Instead of generating a new random number every time I want to pick a move in a random playout, I fill a large circular array with random numbers when my go program launches (before it is actually playing a game) and I have a method that just gets the next number out of the array instead of generating a new random number in real time. Actually I have a different array for each possible board size, since I need a random integer from a different range for each. Sure the array repeats after 500,000 numbers or however many you use, but this is not a big deal when your playouts are only 100 moves long each - and it is unlikely to start repeating from the same position. This approach was much faster than generating random numbers on the fly. On Dec 19, 2007 3:51 AM, Stuart A. Yeates [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: Probably the reason that it is so slow is that it's aiming for a cryptographically random number sequence. These are usually derived ultimately from kernel timings (often via /dev/random on linux systems) and it can take a while to establish a degree of confidence in the randomness of these bits. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: Hi, I'm currently writing a UCT based go program in Clean to see if it is feasible to write one in a functional language. This is my first attempt at functional languages, and I'm having trouble with random numbers. A mersenne twister module is available for Clean. Once initialized it is reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
Imran Hendley wrote:
A sorry about that. Glad to hear you fixed the problem. What was your
solution?
It seems you mentioned the global list approach in your email which
I missed too. Why did you think this was an ugly approach? I just put
my random array in a Singleton object (call it
MyRandomNumberGenerator) which internally stores the next index and
has a method for getting the next random number. So I just replace all
my calls to Random.getNextInt() with
MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of
people would still call this ugly... But it's just a lookup so I think
it will beat any other solution that involves generating a new random
number by a reasonable margin.
You are spending time before the game to save time during the game - a
good principle in general but you do have a few issues:
1. How does this affect cache? (probably not much but you have to
consider it.)
2. Can you get enough numbers to last a complete game?
If this is so slow, then there would be a long delay each time you
generate a new set of random numbers and I really think you should do
this between games. I wonder how long the delay is?
If the delay is unduly long (it must be, otherwise you wouldn't have to
do this) then an alternative is to change a fraction of the numbers
between games:
// code to randomly change 1000 values:
for (i=0; i1000; i++) {
ix = randomInt( RANDOM_ARRAY_SIZE );
randArray[ ix ] = newRandomNumber();
}
In other words, pick a few array locations at random and change their
value.
This will prevent any serious cycles with long testing sequences.
You could also perform such a routine between moves. You only need to
change a few so change as many as you can in a fraction of a second.
- Don
On Dec 19, 2007 5:15 AM, Berk Ozbozkurt [EMAIL PROTECTED]
mailto:[EMAIL PROTECTED] wrote:
That was not the problem, as the source code is available and it
doesn't
call system libraries at all. I was initializing with known seed in my
tests anyway.
Thanks though, in the process of composing a reply demonstrating the
problem, I found a partial solution. Now random number generation
takes
3% of running time, compared to 60% of older version and ~1% of a
hypothetical ideal solution.
Berk.
Stuart A. Yeates wrote:
Probably the reason that it is so slow is that it's aiming for a
cryptographically random number sequence. These are usually derived
ultimately from kernel timings (often via /dev/random on linux
systems) and it can take a while to establish a degree of confidence
in the randomness of these bits.
If you want a sequence of numbers that is very unlikely to
repeat but
that doesn't have to be cryptographically random, standard
practice is
to initialise the random number generator with the current time
(usually a long expressed in milliseconds). This naturally fails if
you ever create more than one sequence per millisecond.
cheers
stuart
On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED]
mailto:[EMAIL PROTECTED] wrote:
Hi,
I'm currently writing a UCT based go program in Clean to see if
it is
feasible to write one in a functional language. This is my
first attempt
at functional languages, and I'm having trouble with random
numbers.
A mersenne twister module is available for Clean. Once
initialized it is
reasonably fast to extract a new random number from the generator.
However, it is about a hundred times slower to initialize it
with a new
random seed. Therefore my first attempt at generating random
numbers by
storing seeds at tree nodes and creating a new random list and
a new
seed each time random numbers are required for mc evaluation is
very
slow. The alternative seems to be passing around an index to a
global
random list, which is both ugly and complicated. Is there
another way?
___
computer-go mailing list
computer-go@computer-go.org mailto:computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
On Dec 19, 2007 11:25 AM, Don Dailey [EMAIL PROTECTED] wrote:
Imran Hendley wrote:
A sorry about that. Glad to hear you fixed the problem. What was your
solution?
It seems you mentioned the global list approach in your email which
I missed too. Why did you think this was an ugly approach? I just put
my random array in a Singleton object (call it
MyRandomNumberGenerator) which internally stores the next index and
has a method for getting the next random number. So I just replace all
my calls to Random.getNextInt() with
MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of
people would still call this ugly... But it's just a lookup so I think
it will beat any other solution that involves generating a new random
number by a reasonable margin.
You are spending time before the game to save time during the game - a
good principle in general but you do have a few issues:
1. How does this affect cache? (probably not much but you have to
consider it.)
2. Can you get enough numbers to last a complete game?
If this is so slow, then there would be a long delay each time you
generate a new set of random numbers and I really think you should do
this between games. I wonder how long the delay is?
If the delay is unduly long (it must be, otherwise you wouldn't have to
do this) then an alternative is to change a fraction of the numbers
between games:
// code to randomly change 1000 values:
for (i=0; i1000; i++) {
ix = randomInt( RANDOM_ARRAY_SIZE );
randArray[ ix ] = newRandomNumber();
}
In other words, pick a few array locations at random and change their
value.
This will prevent any serious cycles with long testing sequences.
You could also perform such a routine between moves. You only need to
change a few so change as many as you can in a fraction of a second.
- Don
Don,
I probably go through my entire array 5 times per second during a UCT
search. So far I have been relying on the hope that I do not come back to
the beginning of my array at exactly the same position in a random playout
which would cause a bad cycle. If I come back at a different position then I
will not start replaying the same set of playouts in the search of that
particular game position, and I will also play a different sequence of moves
in this run through the array because I will reject different numbers I
get because they correspond to illegal board positions but didn't last time
through the array and vice versa.
I think the chance of a bad cycle is very small. I just did some more
analysis of this just now and it got a little complicated, so I'll leave it
out. However, I do think making a bad cycle impossible is important. Your
idea of reinitializing some random positions in the array looks really good.
Unfortunately there is no way I can do this each time through the array for
any meaningful portion of the whole array...since just resetting my index to
0 when I get to the end is pretty expensive in terms of average cost, and if
I'm going through the array a few times a second I can't do much more than
that each time. What do you think of resetting my index to a random position
between 0 and some small n every time to make the probability of getting
stuck in a cycle forever go to zero, and then finding some free time to
reset the numbers like right after playing a move and before starting to
ponder for example?
And about the cache...I've never really thought about it. How do think the
cache would be affected? I don't really know much about cache's to be
honest. Are you saying that the numbers in my array would get stored in the
cache? Is this good or bad?
Imran
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
Yes, the large amount of state in a playout will probably enable you to safely get away with what you are doing, but I would certainly want to test the overall strength of the engine using this method this versus using the straight-forward method of seeding the RNG once and generating a new random number anytime you need it. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
I probably go through my entire array 5 times per second during a UCT search. So far I have been relying on the hope that I do not come back to the beginning of my array at exactly the same position in a random playout which would cause a bad cycle. If I come back at a different position then I will not start replaying the same set of playouts in the search of that particular game position, and I will also play a different sequence of moves in this run through the array because I will reject different numbers I get because they correspond to illegal board positions but didn't last time through the array and vice versa. I think the chance of a bad cycle is very small. Hopefully that is true. I just did some more analysis of this just now and it got a little complicated, so I'll leave it out. However, I do think making a bad cycle impossible is important. Your idea of reinitializing some random positions in the array looks really good. Unfortunately there is no way I can do this each time through the array for any meaningful portion of the whole array...since just resetting my index to 0 when I get to the end is pretty expensive in terms of average cost, and if I'm going through the array a few times a second I can't do much more than that each time. What do you think of resetting my index to a random position between 0 and some small n every time to make the probability of getting stuck in a cycle forever go to zero, and then finding some free time to reset the numbers like right after playing a move and before starting to ponder for example? Certainly that's better than nothing. I assume you will use the random number generator to do this? If so, it will be an improvement. And about the cache...I've never really thought about it. How do think the cache would be affected? I don't really know much about cache's to be honest. Are you saying that the numbers in my array would get stored in the cache? Is this good or bad? If you use a lot of memory to store something that could be generated on the fly, you could slow your whole program down due to caching issues between the processor and memory.When you use a piece of data for the first time, it is slow. But after that it is much faster because it is stored in super-fast memory. But you only have so much of that super-fast memory. I don't think it's likely to be an issue for you, but it's something to keep in mind. I have created cache unfriendly software by going too crazy with tables but modern processors are pretty well designed and generous. - Don Imran ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random move selection (was) Crazystone patterns
Good information. Thanks. - Dave Hillis -Original Message- From: Jacques Basaldúa [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Fri, 21 Sep 2007 7:44 am Subject: [computer-go] Random move selection (was) Crazystone patterns 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/ Check Out the new free AIM(R) Mail -- Unlimited storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
