Answers.Body: <p>You can probably get away with a relatively low X for two reasons:</p>
  
  <ol>
  <li><a href="https://en.wikipedia.org/wiki/Central_limit_theorem" rel="nofollow noreferrer">The Central Limit Theorem</a>. 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. </li>
  <li>In a GA, you don't need an absolute ranking of individuals, because your selection mechanism (see "related articles" <a href="https://en.wikipedia.org/wiki/Selection_(genetic_algorithm)" rel="nofollow noreferrer">here</a>) 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.</li>
  </ol>
  
  <p>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. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T15:12:39.367Z
Answers.LastActivityDate: 2018-08-16T15:12:39.367Z
Answers.UserDisplayName: John Doucette
Body: <p>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.</p>
  <p>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.</p>
  
Tags: <optimization><genetic-algorithms><fitness-functions><bias-variance-tradeoff>
Title: Can I compute the fitness of an agent based on a low number of runs of the game?
UserDisplayName: OrangeMan
ThreadText: # Can I compute the fitness of an agent based on a low number of runs of the game?
  
  (Asked by: username_0 on 2018-08-16)
  
  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.
  
  **Tags:** optimization, genetic-algorithms, fitness-functions, bias-variance-tradeoff
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-08-16. Score: 3 | Accepted answer
  
  You can probably get away with a relatively low X for two reasons:
  
  1. [The Central Limit Theorem](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Selection_(genetic_algorithm))) 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.
  
  
  ---
  
  