tic tac toe AI

Started by
12 comments, last by Poigahn 11 years, 1 month ago
So each node or branch represents a potential action and the leaves are end conditions?

Yes. You should search the web for the term "minimax". Since it is the basis of computer chess, there is a lot of information about it out there. The algorithm has been around since around 1950, but it is so natural that a lot of people have rediscovered it (including myself).
Advertisement

You dont necessarily need to use Minimax. Here's the xkcd's optimal tic-tac-toe moves for each player.

And this is the list of rules you need to check if you choose to implement this kind of method(from tic-tac-toe page on wikipedia);

  1. Win: If the player has two in a row, they can place a third to get three in a row.
  2. Block: If the [opponent] has two in a row, the player must play the third themself to block the opponent.
  3. Fork: Creation of an opportunity where the player has two threats to win (two non-blocked lines of 2).
  4. Blocking an opponent's fork:
    • Option 1: The player should create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork. For example, if "X" has a corner, "O" has the center, and "X" has the opposite corner as well, "O" must not play a corner in order to win. (Playing a corner in this scenario creates a fork for "X" to win.)
    • Option 2: If there is a configuration where the opponent can fork, the player should block that fork.
  5. Center: A player marks the center. (If it is the first move of the game, playing on a corner gives "O" more opportunities to make a mistake and may therefore be the better choice; however, it makes no difference between perfect players.)
  6. Opposite corner: If the opponent is in the corner, the player plays the opposite corner.
  7. Empty corner: The player plays in a corner square.
  8. Empty side: The player plays in a middle square on any of the 4 sides

You dont necessarily need to use Minimax. [...]

While that's true, using a game-specific recipe doesn't teach you anything you can apply in another game, and the whole point is to use tic-tac-toe as a learning tool.

You can also make a graph with all the positions in the game and use retrograde analysis to assign values to every node. This will also solve the game, and it will teach you how to create endgame tablebases.

If anyone cares, There is a chapter for Tic-Tac-Toe in the book called "Begining C++ through Game Programming. That solves the problem

Your Brain contains the Best Program Ever Written : Manage Your Data Wisely !!

This topic is closed to new replies.

Advertisement