4

I'm developing an AI to play a card game with a genetic algorithm. Initially, I will evaluate it against a player that plays randomly, so there will naturally be a lot of variance in the results. I will take the mean score from X games as that agent's fitness. The actual playing of the game dominates the time to evaluate the actual genetic algorithm.

My question is: should I go for a low X, e.g. 10, so I would be able to move through generations quite fast but the fitness function would be quite inaccurate? Alternatively, I could go for a high X e.g. 100 and would move very slowly but with a more accurate function.

nbro
  • 39,006
  • 12
  • 98
  • 176
Ryxuma
  • 237
  • 1
  • 5

1 Answers1

3

You can probably get away with a relatively low X for two reasons:

  1. The Central Limit Theorem. This tells us that the accuracy in the estimate of an agent's fitness will improve as the square root of the number of games played.
  2. In a GA, you don't need an absolute ranking of individuals, because your selection mechanism (see "related articles" here) typically isn't completely elitist. For example, if individuals in the top half of the population are allowed to breed, then your fitness function really just needs to separate the good from the bad reasonably well. It need not be perfect to work.

The correct value of X will still depend on the variance in the scores an agent might receive from playing the game, but this is easy to track. A good approach might be to incorporate this directly into your estimate. Compute the variance, and then prefer agents that not only score highly, but do so with low variance.

John Doucette
  • 9,147
  • 1
  • 17
  • 52