Some ideas:

* host a tournament of many different PRNG seeds.

* generate long strings of moves (random numbers) up front and then use a genetic algorithm to breed and mutate the winning strings.