Tic Tac Toe Analysis
Study the game of tic-tac-toe and try to develop an optimal strategy (on an NxN board if possible).
Tic-Tac-Toe is a relatively simple game which can be analyzed and completely solved. Since it is a finite-length 2-player game, one of the following must be true: Player 1 has a winning strategy, Player 2 has a winning strategy, or optimal play results in a tie. One way of analyzing a game such as this is to create a game tree, i.e. map out every possible game. However, as the board size increases, this becomes less and less feasible as the number of possible games increases exponentially.
Make an educated guess about the outcome of optimal play on an NxN Tic-Tac-Toe board (where a player has to attain N symbols in a row). If you believe there is a winning strategy for either Player 1 or Player 2, develop it and state it explicitly. If you believe optimal play results in a tie, show how Player 1 can prevent Player 2 from winning and vice versa. Remember, these outcomes may be dependent on our value of N.
- Pen and Paper
- Computer if you would like to map out a game tree.
The “brute force” method of determining the outcome of a game based on optimal play is by mapping a game tree. This is done by first drawing how the game looks when it starts. You then draw all of the next possible states the game board could be in (in other words, all of the moves the first player can make). On the first move, we only have to draw 3 different states, since choosing one corner is the same as choosing any other, by reflection and rotation. Note that the same will not be true on subsequent moves. From each of these we can expand each of the second player’s possible moves, and so on, until we have mapped every possible game. You may wish to leave out trivial choices of moves (e.g. the player has the chance to win but picks another space).
Once you have mapped out a whole game tree, the game becomes easier to analyze. If you can show that no matter how Player 2 picks his/her moves, Player 1 has some way of winning, then you are guaranteed Player 1 has a winning strategy. However, if Player 2 can always pick a move which will lead to a tie, then you know the game will result in a tie given optimal play.
Mapping out a game tree takes a lot of time and space, and is not feasible for larger boards. However, by mapping out games on smaller boards, you may be able to develop a general strategy for any size board. Alternatively, you may wish to develop a strategy without mapping every possible game. Be sure that this strategy still covers every possibility.
Did you develop either a winning strategy or an argument that shows one isn’t possible? Is it rigorous (does it cover all possibilities)?
Was your hypothesis correct? If so, what steps did you take to prove it? If not, what did you learn that was not obvious when you started?
- Instead of requiring N symbols to be lined up to win in an NxN board (i.e. filling in a whole row, column, or diagonal), try requiring only N-1, 3, N/2, or √N symbols in a row.
- Consider an NxM Tic-Tac-Toe board. Note that the most number of symbols in a row that still allow for a game to be won is min(N, M).