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