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