artificial intelligence - What algorithm for a tic-tac-toe game can I use to determine the "best move" for the AI?

Question

In a tic-tac-toe implementation I guess that the challenging part is to determine the best move to be played by the machine.

What are the algorithms that can pursued? I'm looking into implementations from simple to complex. How would I go about tackling this part of the problem?

Answer 1

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 a perfect game of Tic-tac-toe (to win or, at least, draw) if they choose the first available move from the following list, each turn, as used in Newell and Simon's 1972 tic-tac-toe program.[6]

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.