3
$\begingroup$

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 agents 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 quite inaccurate. Alternatively, I could go for a high X e.g. 100 and would move very slowly but with a more accurate function.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.