Kevin's Math Page    
     

Analysis of Tic-Tac-Toe

Kevin Gong

July 29th, 2006

Recently, after playing a game involving dice, I asked myself the question: how much luck is involved? In general, I started asking questions about the nature of the game. I'll probably follow up with an analysis of that game, but for starters, I'd like to analyze the simple game of Tic-Tac-Toe.

Here are the general questions I'd like to answer about the game:

  • How complicated is the game?
  • How much of an advantage does the first player have?
  • How much luck is involved? (the analagous question is, how much skill is involved)?

How complicated is the game? One quantitative way to answer that question is to answer the question of how many possible games there are. The first player can make any of 9 moves, the second any of 8 remaining moves, etc. So at first glance there would be 9! = 362880 possible games. However, some games end before the 9th move. There are actually only 255168 possible games. I calculated this by simply writing a brute-force computer program to execute all the games. Note that many games are symmetrical, so you could argue that there are even fewer than that many games. I leave it as an exercise to the reader to determine how many duplicate games there are. In any case, 255168 is a very small number compared with other games. In future analysis, I'll try to compare this number to other games.

How much of an advantage does the first player have? There are a few possible ways to answer this question. One might ask the question of how often the first player wins when two players of average ability play each other. Unfortunately, there would be no price definition of an "average" player, and it's hard to make that comparison between different types of games. So I propose two different answers: what happens when two players who play completely randomly play, and what happens when two players who play perfectly play?

When two players who play completely randomly play, the first player wins 58.49% of the time, the second player wins 28.81% of the time, and the game is a draw 12.70% of the time. This is equivalent to a 64.84% - 35.16% advantage. I obtained this result based on a computer program I wrote to enumerate all the possibilities.

When two players who play the game perfectly play, the game is always a draw. In fact, there can only be three possible answers for this question for a deterministic game - either the first player always wins, the second player always wins, or the game is always a draw. In non-deterministic games (such as backgammon), then the answer would be more interesting.

How much luck is involved? One way to answer this question is to ask how often a perfect player will win when playing against a random player. I wrote a computer program to calculate this. It is important to define what a perfect player is. The way I implemented it, the perfect player assumes that the opponent is also perfect -- in other words, when two moves both lead to the same result with perfect play, the computer does not distinguish between them. If you wanted to truly program a perfect player, you would program the computer to choose the move which provides the most opportunity for the opponent to make a mistake. I did not do this, so the truly perfect player will play even better than my program.

Nevertheless, the results are still interesting. When the random player moves first, the random player wins 0.00% of the time, the perfect player wins 80.64% of the tme, the game is drawn 19.36% of the time. This is equivalent to a 90.32% - 9.68% advantage. When the perfect player moves first, the random player wins 0.0% of the time, the perfect player wins 99.47% of the time, and the game is drawn 0.53% of the time. This is equivalent to a 99.74% - 0.26% advantage. Combining these two results, we find the perfect player enjoys a 95.03% - 4.97% advantage.

All of these results aren't necessarily interesting when looked at in a vaccuum, but will be more interesting when compared to other games, which I will analyze in the future.

 

 Kevin's Math Page    
Copyright © 1996-2008 Kevin L. Gong