What Algorithm for a Tic-Tac-Toe Game Can I Use To Determine the "Best Move" for the AI?

Question

In tic-tac-toe implementation I guess the challenging part is to determine the best move to be played by the machine. What are some of the algorithms that can pursued? I'm looking into implementation from simple to complex. How would I go about tackling this part of the problem?

Answer 1

Rank each of the squares with numeric scores. If a square is taken, move on to the next choice (sorted in descending order by rank). You're going to need to choose a strategy (there are two main ones for going first and three (I think) for second). Technically, you could just program all of the strategies and then choose one at random. That would make for a less predictable opponent.

Answer 2

The brute force method of generating every single possible board and scoring it based on the boards it later produces further down the tree doesn't require much memory, especially once you recognize that 90 degree board rotations are redundant, as are flips about the vertical, horizontal, and diagonal axis.

Once you get to that point, there's something like less than 1k of data in a tree graph to describe the outcome, and thus the best move for the computer.

Answer 3

Since you're only dealing with a 3x3 matrix of possible locations, it'd be pretty easy to just write a search through all possibilities without taxing you computing power. For each open space, compute through all the possible outcomes after that marking that space (recursively, I'd say), then use the move with the most possibilities of winning.

Optimizing this would be a waste of effort, really. Though some easy ones might be:

• Check first for possible wins for the other team, block the first one you find (if there are 2 the games over anyway).
• Always take the center if it's open (and the previous rule has no candidates).
• Take corners ahead of sides (again, if the previous rules are empty)

Answer 4

You can have the AI play itself in some sample games to learn from. Use a supervised learning algorithm, to help it along.

Answer 5

The strategy from Wikipedia for playing a perfect game (win or tie every time) seems like straightforward pseudo-code:

Quote from Wikipedia (Tic Tac Toe#Strategy)

A player can play perfect tic-tac-toe if they choose the move with the highest priority in the following table[3].

1) Win: If you have two in a row, play the third to get three in a row.

2) Block: If the opponent has two in a row, play the third to block them.

3) Fork: Create an opportunity where you can win in two ways.

4) Block Opponent's Fork:

Option 1: Create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork or winning. 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, block that fork.

5) Center: Play the center.

6) Opposite Corner: If the opponent is in the corner, play the opposite corner.

7) Empty Corner: Play an empty corner.

8) Empty Side: Play an empty side.

Recognizing what a "fork" situation looks like could be done in a brute-force manner as suggested.

Note: A "perfect" opponent is a nice exercise but ultimately not worth 'playing' against. You could, however, alter the priorities above to give characteristic weaknesses to opponent personalities.

Answer 6

What you need (for tic-tac-toe or a far more difficult game like Chess) is the minimax algorithm, or its slightly more complicated variant, alpha-beta pruning. Ordinary naive minimax will do fine for a game with as small a search space as tic-tac-toe, though.

In a nutshell, what you want to do is not to search for the move that has the best possible outcome for you, but rather for the move where the worst possible outcome is as good as possible. If you assume your opponent is playing optimally, you have to assume they will take the move that is worst for you, and therefore you have to take the move that MINimises their MAXimum gain.