0

I was challenged by coworker into creating a Tic Tac Toe game AI that plays five-in-a-row games (not the traditional 3). My initial thoughts are that I create a "scoreboard", i.e. every cell in the game gets a score between 0 and infinite. The AI finds shapes and determines which places hold how much value and give score to the cells. In the end, highest scored cell is the choice.

Is there a better way to approach this problem?

Tower
  • 98,741
  • 129
  • 357
  • 507
  • You can look answers in this theme: http://stackoverflow.com/questions/1545158/what-algorithm-would-you-use-to-solve-a-very-large-tic-tac-toe-game – Tiendil Feb 22 '12 at 13:11
  • I don't really have any idea how to apply Monte Carlo or such complex beasts in practice to a game like Tic Tac Toe / Gomoku. – Tower Feb 22 '12 at 14:18
  • The 'scorecard' thing is basically what minimax is...an algorithm to assign values to state transitions (possible moves). That is often combined with pruning, which is cutting down on computation by ignoring (not recursing down) certain transitions that you know aren't going to be optimal. This is probably the most straight-forward way to tackle this problem (assuming it can't be solved directly as mentioned below, which would take all the fun out of it). For more info, see: http://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with_alternate_moves – prelic Feb 22 '12 at 19:32
  • @prelic, it's not quite that simple. Some squares are only valuable in combination with others. The relationship won't be additive, or even linear. It's a start, but not the whole picture. – Novak Feb 22 '12 at 20:58

1 Answers1

1

5x5 Tic-Tac-Toe might still be small enough to solve directly, depending on your time constraints, if you're clever about the board symmetries. Oddly enough, I just wrote a description of the general technique last night, for this question:

How to code simple AI for a windows phone board game?

If not, that's still a good starting point. The next most obvious thing to me would be to change the board evaluation function and search only as deep in the tree as is feasible for your time constraints. The idea is that you, as a human, might have some ideas about what strong and weak positions are. So, as a guess, we know five in a row wins, so assign X wins as +5 and O wins as -5. One way to win is to get four in a row prior to that, so if X has four in a row, that might be worth 4, and if O has four in a row, that might be worth -4. The idea is that if you can't search all the way down the tree, you search as far as you can with the minimax technique, confident that you're working your way toward a strong position.

That board eval function is only an example. Coming up with a good board evaluation function can be tricky, and the one I described misses some obvious details.

Another thing to try is to use a genetic algorithm and neural networks to evolve the board evaluation function. Now the idea is to feed board positions into neural networks, which do the board evaluations, and let them play according to the technique I described above, tournament style. Then, after tournament rounds, new neural networks are created (through genetic algorithm) from the winners and losers are eliminated. The board evaluation function evolves naturally.

Community
  • 1
  • 1
Novak
  • 4,687
  • 2
  • 26
  • 64
  • Something I don't get is that how trees have anything to do with a Tic Tac Toe game? How can you map a two-dimensional array of cells to a tree? – Tower Feb 23 '12 at 08:34
  • @rFactor, don't confuse board locations (cells) with board positions. A typical 3x3 Tic Tac Toe game has 9 board locations, but a vastly larger number of board positions. A board position is the complete state of the game. There's a good illustration here: http://scienceblogs.com/goodmath/2008/07/solving_tictactoe_game_tree_ba.php – Novak Feb 23 '12 at 14:38