Tic-Tac-Toe

Let’s look at a simple game that we all know and have played called Tic-Tac-Toe. The three-by-three board is filled by two players (“X” and “O”), and the winner is the player who successfully connects three of his Xs or Os in a row (horizontal, vertical, or diagonal).

In Tic-Tac-Toe, the player who goes first (say, “X”) can choose one of nine spaces to mark with an “X” (as in the above diagram spaces one to nine). Then “O” has a turn and can mark any of the remaining eight empty spaces. This gameplay continues until either player has won (three connecting marks) or all of the spaces are filled (no player wins). In mathematics, we call this process “factorial,” and in Tic-Tac-Toe it is 9! or nine factorial (9 * 8 * 7 * 6 * 5 * 4 *3* 2 * 1).

This means that the full tree structure or game path would have 9! ending states (or “nodes”), which is 362,880 win, lose, or draw (tie) states.

When playing Tic-Tac-Toe, there are two methods of selecting a space to mark with your X or O: randomly marking an empty space or logically examining each empty space through an iterative process and selecting the space that leads to a non-losing result (a winning or tying result). All games use one of these methods, but obviously the second, non-random method gives us a better game and stronger competition.

The following sample game will indicate the “side to play” (X or O) and the next available space to mark.

X wins (3, 5, 7 diagonal connection).

The “Min-Max” search would return a result of 1 for X and –1 for O, meaning a win for the player X worth 1 point and a loss to player O and worth –1 points. The process would terminate or prune lower branches, since the game is over at step (G). The result of –1 in step (F) would trigger a more favorable result for O to find elsewhere.

O evaluates the next empty space, which is space 7 in step (F), in lieu of the losing choice step (F) marking space 6.

X wins (1, 5, 9 diagonal connection).

Again the “Min-Max” search would return a result of 1 for X and –1 for O, meaning a win for the player X worth 1 point and a loss to player O worth –1 points. The process would terminate or prune lower branches since the game is over at step (G). The result of –1 in step (F) would trigger a more favorable result for O to find elsewhere.

O evaluates the next empty space, which is space 8 in step (F), in lieu of the losing choice step (F) marking space 7.

Finally O evaluates the next empty space, which is space 9 in step (F), in lieu of the losing choice step (F) marking space 8.

After looking at the various paths, O will evaluate step (D), O mark 4, as the critical mistake and evaluate (D), O mark 5.

In step (E), X must stop O from winning by marking space 8 (forced move).

In step (F) below, O finds the next free space and marks space 4.

In step (G), X must once again stop O from winning by marking space 6 (forced move).

In step (H), O must stop X from winning by marking space 9 (forced move).

Finally, X marks space 7, the only remaining space, and a tie or draw occurs.

Let’s examine the following Tic-Tac-Toe scenario:

This scenario has player O select and mark an empty space. The iterating method would require that each empty space (spaces 3, 4, 6, 7, 8, and 9) be examined and evaluated. After spending time and effort evaluating the empty spaces, the process would recognize that player O is forced to mark space 9 to stop player X from winning. The best method of handling the selection and marking our next space would be to first check to see if any empty space would give us the immediate win and then if we can’t win, check if any empty space would give our opponent the immediate win before examining each empty space in order.

Forced Move

Our thinking would lead us to the following thought process:

TOP:

Set current Tic-Tac-Toe board to current scenario.

Is there an empty space to mark so that I win?

If YES, select and mark this space and

set result to WIN.

If NO, continue.

Is there an empty space to mark so that I won’t lose?

If YES, select and mark this space and

set result to Forced Mark.

If NO, continue.

Are there any empty spaces left?

If YES, continue.

If NO, set the result to the game is over

(a tie).

Place your mark on the next empty space.

Set side to play to the other player.

Go back to label TOP.

To properly design the function “Forced Move,” we need to know which player is to mark X (marked as +1) or O (marked as –1). This function “Forced Move” will return a +100 value if we win, a –100 value if our opponent could win (we are forced to block them), and a zero if no winning situation is found. We know that to win at Tic-Tac-Toe, we must have three connecting spaces marked with matching Xs or Os.

Forced Move Revised

The flowchart describing a “Forced Move” looks (obviously) like a process that can be better defined and easier to express. We can define an array called wp (win path), which has two dimensions—paths and linked spaces.

Let’s look at how we can use the knowledge we just learned to program Tic-Tac-Toe in Visual Basic and Visual C++.