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