artificial intelligence - A Genetic Algorithm for Tic-Tac-Toe -

so assigned problem of writing 5x5x5 tic-tac-toe player using genetic algorithm. approach start off 3x3, working, , extend 5x5, , 5x5x5.

the way works this:

• simulate whole bunch of games, , during each turn of each game, lookup in corresponding table (x table or o table implemented c++ stdlib maps) response. if board not there, add board table. otherwise, make random response.

• after have complete tables, initialize bunch of players (each copy of board table, initialized random responses), , let them play against each other.

• using wins/losses evaluate fitness, keep % of best, , move on. rinse , repeat x generations, , optimal player should emerge.

for 3x3, discounting boards reflections/rotations of other boards, , boards move either 'take win' or 'block win', total number of boards encounter either 53 or 38, depending on whether go first or second. fantastic! optimal player generated in under hour. cool!

using same strategy 5x5, knew size of table increase, did not realize increase drastically. discounting rotations/reflections , mandatory moves, table ~3.6 million entries, no end in sight.

okay, that's not going work, need new plan. if don't enumerate boards, some boards. well, seems won't work either, because if each player has fraction of possible boards might see, going making lot of random moves, steering in opposite direction of optimality.

what realistic way of going this? going stuck using board features? goal hard-code little game functionality possible.

i've been doing research, read leads min/max a-b pruning viable option. can way, ga cool, current method exceeding reality bit here.

edit problem has been pretty solved:

using similarity function combines hamming distance of open spaces, possible win conditions, , few other measures has brought table down manageable 2500 possibilities, std::map handles in fraction of second.

my knowledge of ga pretty limited, in modeling board configurations, aren't asking wrong question? task isn't enumerate possible winning configurations -- you're trying find sequence of moves leads winning configuration. maybe population should looking @ isn't set of boards, set of move sequences.

edit: wasn't thinking of starting particular board starting empty board. it's obvious on 3x3 board move sequences starting (1,1) work out best x. important thing isn't final board has x in middle, it's x placed in middle first. if there's 1 or more best first moves x, maybe there's best second, third, or fourth move x, too? after several rounds of fitness testing , recombining, find x's second move same, or 1 of small set of values? , third move?

this isn't minimax because you're not looking best moves 1 @ time based on previous state of board, you're looking best moves @ same time, hoping converge on winning strategy.

i know doesn't solve problem, if idea evolve winning strategy seems natural you'd want @ sequences of moves rather board states.