title: A Genetic Algorithm for Tic-Tac-Toe
body: <p>So I was assigned the problem of writing a 5x5x5 tic-tac-toe player using a genetic algorithm.  My approach was to start off with 3x3, get that working, and then extend to 5x5, and then to 5x5x5.  </p>
  
  <p>The way it works is this:  </p>
  
  <ul>
  <li><p>Simulate a whole bunch of games, and during each turn of each game, lookup in a corresponding table (X table or O table implemented as a c++ stdlib maps) for a response.  If the board was not there, add the board to the table.  Otherwise, make a random response.  </p></li>
  <li><p>After I have complete tables, I initialize a bunch of players (each with a copy of the board table, initialized with random responses), and let them play against each other.</p></li>
  <li>Using their wins/losses to evaluate fitness, I keep a certain % of the best, and they move on.  Rinse and repeat for X generations, and an optimal player should emerge.</li>
  </ul>
  
  <p>For 3x3, discounting boards that were reflections/rotations of other boards, and boards where the move is either 'take the win' or 'block the win', the total number of boards I would encounter were either 53 or 38, depending on whether you go first or second.  Fantastic! An optimal player was generated in under an hour.  Very cool!</p>
  
  <p>Using the same strategy for 5x5, I knew the size of the table would increase, but did not realize it would increase so drastically.  Even discounting rotations/reflections and mandatory moves, my table is ~3.6 million entries, with no end in sight.  </p>
  
  <p>Okay, so that's clearly not going to work, I need a new plan.  What if I don't enumerate all the boards, but just <em>some</em> boards.  Well, it seems like this won't work either, because if each player has just a fraction of possible boards they might see, then they are going to be making a lot of random moves, clearly steering in the opposite direction of optimality.</p>
  
  <p>What is a realistic way of going about this? Am I going to be stuck using board features? The goal is to hard-code as little game functionality as possible.</p>
  
  <p>I've been doing research, but everything I read leads to min/max with A-B pruning as the only viable option.  I can certainly do it that way, but the GA is really cool, my current method is just exceeding reality a bit here.</p>
  
  <p><em>EDIT</em> Problem has been pretty much solved:</p>
  
  <p>Using a similarity function that combines hamming distance of open spaces, the possible win conditions, and a few other measures has brought the table down to a very manageable 2500 possibilities, which a <code>std::map</code> handles in a fraction of a second.  </p>