Question

Suppose that the first four moves of a tic-tac-toe game are as shown. Does the first player (whose moves are marked by Xs) have a strategy that will always win?

Short answer

1. The first player can win in his second next move.
2. This game will end in a draw with optimal play
3. The first player can win in his second move.
4. The game will end in optimal way since no file can contain three same symbols.

Step-by-step solution

Define the values of all vertices in a game tree in a way that enables us to determine the outcome of this game when both players follow optimal strategies,

By a strategy mean a set of rules that tells a player how to select moves to win the game. An optimal strategy for the first player is a strategy that maximizes the payoff to this player and for the second player is a strategy that minimizes this payoff. We now recursively define the value of a vertex.

One needs to find whether the first player (marked with X) will win the following first case.

Let us consider the following case,

If the first player moves to the centre (second column, second row) in next move. the second player's threat can be blocked. Also, he can create two threats to second player (diagonally) and the second player can block only one in his next move.

Therefore, the first player can win in his second next move.

One needs to realize whether the first player (marked with X) will win the following second case.

In his next move the first player should block the second player's threat in the second column so that second player will not win in his next move. In that case if the second player moves to first or third column and it blocks the first player.

Therefore, none of them can win the game. This game will end in a draw with optimal play.

One needs to notice whether the first player (marked with X) will win the following third case.

The first player can move to middle row of the third column. This creates two threats to the second player (threat in third column and in middle row). Only one can be blocked by the second player in his next move.

Hence, the first player can win in his second move.

One needs to discover whether the first player (marked with X) will win the following fourth case.

In the next move first player should block second player's threat and, in that case, if the second player blocks the first player's threat in the first row, the first player again should block his threat in second column.

Therefore, if both the players block the threat of each other in net three moves, the game will end in optimal way since no file can contain three same symbols.