Game Theory and Mathematics in Chess

Authors note: This was written a few years ago for a game design class. This was also written when I was on a game theory kick. Its possibly one of the most analytic things I've written.

            Checkmate: It’s one of the most dreaded words in the western lexicon. Its mere utterance has the ability to strike fear into the heart of even the most battle-tested opponent. The ubiquity of chess cannot be overstated, as it is possibly the most widely recognized game in the western world; but what is really happening inside the minds of the players and on the chessboard itself? Here we will take a deeper look into the game and analyze it using a branch of behavioral science known as game theory (that is, the way in which the players make decisions and interact with each other during play), and then examine how those decisions manifest themselves on the chessboard from a mathematical perspective using payoff matrices and decision trees.

            Everyday we make decisions and every time we undergo the process of making them, we play a game. The original necessity that brought about the development of game theory, according to its creators John Von Neumann and Oskar Morgenstern, was “…the attempt to find an exact description of the endeavor of the individual to obtain a maximum utility, or, in the case of the entrepreneur, a maximum of profit.”[1] Originally, game theory was a method of understanding the way in which individuals interact given their competing self interests in economic terms. Chess, although no explicitly economic entity, also fits the description of what may be subjected to game theory analysis; instead of “maximum of profit” read “maximum chances of winning”, seeing as how “profit” in an economic game is the equivalent of “winning” in a board game.

            The payoff matrix is the most common way to model decisions in games. Chess is a two-person, non-cooperative, zero-sum game. Non-cooperative in that “…the players are unable to make contractual agreements with one another.” [2] and zero-sum in that the game “represents a closed system: everything someone wins must be lost by someone else.”[3] Because chess is so complicated we will select a simpler two-person non-cooperative game to illustrate with a matrix, and then do the same for chess. The following is the payoff matrix for rock-paper-scissors (the left column being what the player chooses):[4]

Player 1	Scissors	Rock	Paper
Scissors	0	-1	1
Rock	1	0	-1
Paper	-1	1	0

In this example, 0’s represent ties, 1’s represent wins, and -1’s represent losses. Conversely, this is the table for the second player:[5]

Player 2	Scissors	Rock	Paper
Scissors	0	1	-1
Rock	-1	0	1
Paper	1	-1	0

Notice how if both players’ payoff matrices were arithmetically added, the sum would be zero ([Player 1] + [Player 2] = 0), hence the mathematical model for zero-sum games.

            The question arises: what is the payoff matrix for chess look like? The following is the payoff matrix for chess (assume board is reset into starting position and ellipses indicate intermediate moves):

	a3	a4	b3	b4	…	Na3	Nc3	Nf3	Nh3
a3	0	0	0	0	…	0	0	0	0
a4	0	0	0	0	…	0	0	0	0
b3	0	0	0	0	…	0	0	0	0
b4	0	0	0	0	…	0	0	0	0
…	…	…	…	…	…	…	…	…	…
Na3	0	0	0	0	…	0	0	0	0
Nc3	0	0	0	0	...	0	0	0	0
Nf3	0	0	0	0	…	0	0	0	0
Nh3	0	0	0	0	…	0	0	0	0

It becomes obvious that the matrix for chess is vastly more complicated than for rock-paper-scissors, but also that every combination of moves results in a 0. Unlike rock-paper-scissors, chess is a multi-stage game and neither combination of moves by either player on the first turn would end the game, thus resulting in a temporary tie until the next turn. Chess is still considered a zero-sum game regardless of the limitations of the payoff matrix because the end of the game always results in a player winning, a player losing, or a stalemate. So, the implied payoff matrix over the course of the entire game looks like this (and of course vice versa for the other player):

	Player 1 Strategy A	Player 1 Strategy B	Player 1 Strategy C
Player 2 Strategy A	0 (Stalemate)	-1	1
Player 2 Strategy B	1	0	-1
Player 2 Strategy C	-1	1	0

           

It becomes clear that a chess player would find using a payoff matrix rather impractical, seeing as how the matrix tells the player nothing about what their next move should be (granted as more pieces are captured the matrix becomes simpler and simpler, but even so the values would remain 0’s unless one particular set of moves would result in a checkmate for either player). The preferred way to model complex decisions by those actually playing chess are decision trees, which are more suited to the multi-stage/multi-decision nature of chess.  As was done with the payoff matrices, a simple game will be chosen to explain the process then the decision tree will be applied to chess.

            Consider this tree that is created by a plaintiff carrying out a legal dispute with a defendant:[6]

As one can see, multi-stage games are much more complex than a single decision game. The tree allows the players to see all possible outcomes before they even start the game, unlike payoff matrices which only allow the player to see one move into the future. Game theory comes into play when the players try to influence the tree to achieve their own objectives. For example the ideal objective for the defendant would be for the plaintiff to drop the case, if the defendant is unable to get the plaintiff to drop then defendant tries to settle and if that fails proceeds to go to court. Conversely the defendant may wish to do the opposite and go directly to court, if they believe that variable y is insufficient or that their legal counsel is superior to the plaintiffs’.

            If one were to create a complete decision tree for a game of chess, it would take them an extraordinary amount of time to complete, seeing as how there are 400 possible moves in the first turn alone. So instead here is the implied tree:

It’s important to point out here that chess players rarely think on such a large, general scale as implied by the figure above, instead when considering their next move they think of only the moves relevant to their strategy. For example, a seasoned player would never even consider moving a pawn c5:c6 if there are only five other pieces on the board (that is, during endgame stage), doing so would result in essentially a wasted move and would give the opponent offensive control of the board unless the player as a reason for doing so (block check, set a trap, or others). So rather than keeping a complete tree in their head (which is impossible), or the implied tree (which is essentially useless), they focus on specific sections of the complete tree that are relevant to the conditions on the board and to their overall or current strategy.

            Any casual observer of chess can easily see that it is an incredibly deep game, but what often goes unappreciated is the degree of mental acuity that chess demands of the players. However, this intensity is possibly what gives chess its mystique and appeal. To the unaware onlooker it is just two people quietly moving pieces around a board, but for the players themselves it is a struggle; planning traps for the opponent ten moves in advance, keeping large sections of a massively elaborate decision tree in mind at all times, and patiently waiting till the moment that they make their final move and are able to say loudly and confidently: “Checkmate”.

Works Cited

Burger, Ewald. Introduction to the Theory of Games. Englewood Cliffs, NJ: Prentice Hall, INC, 1963.

                                   

Friedman, James W. Game Theory With Applications to Economics. Oxford, NY: Oxford University Press, 1986.

                                   

Gintis, Herbert. Game Theory Evolving. Princeton, NJ: Princeton University Press, 2000.

                                   

Owen, Guillermo. Game Theory. Philadelphia, PA: W.B. Saunders Co., 1968.

                                   

Von Neumann, John, and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton, NJ: Princeton University Press, 1947

---

[1] Neumann 1

[2] Friedman 2

[3] Owen 12

[4] Burger 4

[5] Burger 4

[6] Gintis 101