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