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.
The way it works is this:
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++ std lib maps) for a response. If the board was not there, add the board to the table. Otherwise, make a random response.
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.
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.
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 was either 53 or 38, depending on whether you go first or second. Fantastic! An optimal player was generated in under an hour. Very cool!
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.
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 some 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.
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.
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.
EDIT Problem has been pretty much solved:
Using a similarity function that combines the hamming distance of open spaces, the possible win conditions, and a few other measures have brought the table down to a very manageable 2500 possibilities, which an std:: map handles in a fraction of a second.