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?

Solution 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.

Solution 2

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.

Solution 3

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.

-Adam

Solution 4

A typical algo for tic-tac-toe should look like this:

Board : A nine-element vector representing the board. We store 2 (indicating Blank), 3 (indicating X), or 5 (indicating O). Turn: An integer indicating which move of the game about to be played. The 1st move will be indicated by 1, last by 9.

The Algorithm

The main algorithm uses three functions.

Make2: returns 5 if the center square of the board is blank i.e. if board[5]=2. Otherwise, this function returns any non-corner square (2, 4, 6 or 8).

Posswin(p): Returns 0 if player p can’t win on his next move; otherwise, it returns the number of the square that constitutes a winning move. This function will enable the program both to win and to block opponents win. This function operates by checking each of the rows, columns, and diagonals. By multiplying the values of each square together for an entire row (or column or diagonal), the possibility of a win can be checked. If the product is 18 (3 x 3 x 2), then X can win. If the product is 50 (5 x 5 x 2), then O can win. If a winning row (column or diagonal) is found, the blank square in it can be determined and the number of that square is returned by this function.

Go (n): makes a move in square n. this procedure sets board [n] to 3 if Turn is odd, or 5 if Turn is even. It also increments turn by one.

The algorithm has a built-in strategy for each move. It makes the odd numbered move if it plays X, the even-numbered move if it plays O.

Turn = 1    Go(1)   (upper left corner).
Turn = 2    If Board[5] is blank, Go(5), else Go(1).
Turn = 3    If Board[9] is blank, Go(9), else Go(3).
Turn = 4    If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn = 5    if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn = 6    If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn = 7    If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn = 8    if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn = 9    Same as Turn=7.

I have used it. Let me know how you guys feel.

Solution 5

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)

View more solutions

Comments

[Daniel Spiewak]

Well, if you want to get really complex... ;-) The brute-force approach is probably better than my wimpy ranking idea, though a little harder to implement.

[Andrew Szeto]

How would you suggest implementing the forking parts of the strategy then?

[tooleb]

So what you are saying is: The only winning move is not to play.

[guidot]

Missing here is a vital piece of information: the thing to be maximized is the value of an evaluation function assumed to return a numeric value for any (hypothetical, but especially reachable by placing the next piece) board position. Something cheap like (piece on center field worth 100 points, corners 30, side 5) might do, but will lack any of the high-level information discussed above like existing pair, existing fork, ... So this would not be my first choice.

[Nick Johnson]

@guidot Tic-tac-toe's search space is so small, your evaluation function is trivial: +inf if the game is a winning state, -inf if it's a losing state, 0 if it's a tie.

[guidot]

Minimax or alpha-beta is surely not the first idea to pursuit for such a trival game (this limits the value of the original answer). If you do, however (perhaps with the idea of proceeding to more complex games like go-moku), you need an evaluation function. Such a function is only sensible for the given algorithms, if it produces a result for ANY intermediate position, the suggested (very generic) one, which is restricted to completed games is only helpful to select the final winning message.

[Nick Johnson]

On the contrary, minimax or alpha-beta with an all-or-nothing evaluation function are applicable to any game you want to exhaustively search. Alpha-beta reduces the search space substantially over brute-force; minimax is simply a sensible way to do search the game tree and find the best available move.

[guidot]

I agree starting from sentence 2. Your picture of exhaustive search seems to be, that an analysis until end of game is possible. For many non-trivial games this is a bit optimistic. In that (general) case one needs an evaluation for intermediate positions, since its return value is the comparison value for mini-maxing (see wikipedia, alpha-beta-pruning diagram, the numbers in the nodes). Substantial references (as opposed to general remarks) to disprove this are welcome.

[Nick Johnson]

I didn't say you could always do exhaustive search, just that when you can - such as in Tic Tac Toe - an all-or-nothing evaluator is all you need.

[Admin]

Actually I meant, an attempt without using game tree which is optimal solution for that kind of decision problems. Only to hope to have some more insight.

[Daniel Kobe]

Wouldnt a center fork be more valuable than other forks?

[djechlin]

@Nick "try yourself" is a bit useless here without any information on how to find the counterexample. Is there a configuration reachable by this strategy where following (6) instead of (7) would create a losing game, for instance? Would be helpful to post more information on your counterexample.

[djechlin]

This begs the question. If the implementation of minimax requires the fact that the search space is small, just brute force the problem in the first place.

[djechlin]

At a human level, starting with the corner as P1 produces wins much more often. Your opponent mistakenly thinks that since you didn't take the center, maybe they shouldn't either, for some reason.

[djechlin]

P1 can start anywhere. There are moves P2 can make in response to P1's first move that create a winning game for P1 if both players subsequently play optimally, for any possible first move.

[Ant Kutschera]

I'm fun at parties too - we should get together... And as such, I disagree with your claim that P1 playing in a corner produces wins far more often. Do you have a reference for that? My analysis shows the centre is best, although it does depend on the type of player: blog.maxant.co.uk/pebble/2018/04/07/1523086680000.html

[djechlin]

@AntKutschera no reference, just personal experience, but I was feeling confident because the psychology/intuition is so strong that unorthodox openings require unorthodox responses. If for some other reason the player has prior suppositions or is primed otherwise, it wouldn't work I guess.