## Saturday, June 23, 2012

### How many games of chess are possible?

I like playing chess, and so I couldn't escape the opportunity to talk at least once about some mathematics related to chess.

In my lifetime, I've played probably 500 or more games of chess, and I often wonder -- how many more games do I have to play to have played them all?  Even though I've played hundreds of games, I've never seen the same game twice, so there must be over 500.

To begin, let's try to figure out how many different opening moves are possible. First, a quick explanation of the pieces that are possible:
 From left to right: King, Queen, Bishop, kNight, Rook, pawn
Each piece in chess has different moves.

• King: The king is the most valuable piece -- the point of the game is to keep your king alive, and to attack the opponents king. The king can move one piece in any direction -- horizontally, vertically, or diagonally.
• Queen: The queen is the most powerful piece on the board. As long as there are no pieces in her way (only the kNight is allowed to jump over pieces) she can move as many spaces as she wants horizontally, vertically, or diagonally.
• Bishop: The bishop is similar to the queen, but is restricted to just diagonal motion, and as such, is a weaker piece
• kNight: (by the way, I've purposely miscapitalized the word because when annotating moves, the letter N is used to indicate kNight moves, because the K is used for kings). The night has the most interesting move -- it always moves in an L shape, two spaces vertically and one space horizontally. If desired you can also move two spaces horizontally and one space vertically. If there are pieces in the way, the kNight can jump over them.
• Rook: The rook, or castle, moves similarly to the queen, but is restricted to only horizontal or vertical motion.
• Pawn: The pawn moves only forward, usually only one space at a time. On a pawn's first move, they can move two spaces, but after that it's only forward and one space at a time. When they want to attack the opponent, they move diagonally forward one space.
There are other rules, but this brief description will do for today.  So, here's the opening position of every game:
White always moves first, and has a limited number of moves -- let's count them:
• The king (on e1) is currently trapped by its own pieces, and so cannot move yet
• The queen (on d1) is also trapped, and unable to move. Typically players will use some of their first moves to open up lanes for the queen to move.
• The bishops (on c1 and f1) are also blocked in and unable to move (fun game eh?)
• The knights (on b1 and g1) DO have options, because they are allowed to jump over those pawns that are blocking them in. They move forward to the 3rd row (rank is the typical word used) and over one space to the left or the right. So the knight on b1 can move to a3, or c3, or the knight on g1 can move to f3, or h3. Thus, 4 possible moves (Na3, Nc3, Nf3, Nh3)
• The rooks (on a1 and h1) cannot move yet, as they are blocked in.
• Each of the pawns (on a2 through h2) can move forward either one space or two spaces forward, that's 2*8 = 16 possible moves.
As a whole, white has 20 possible options.

After white moves, black is faced with the exact same set of options. To calculate how many total games are possible after just the first two moves, you need to multiply each of whites moves with each of blacks, to get 20x20 = 400 possible positions. Though I've played 400 games, I know for a fact I have not played every one of my 20 possible first moves (I stick to the immensely popular d- or e- pawn moves), so I am a long ways away from playing every possible game. And we're a long ways away from being done with the game.

Every opening move will open up new opportunities for the other pieces, and so on white's second move, he will have more twenty options available. The most freeing move is moving the e-pawn forward to e3 or e4. That move gives the bishop on f1 5 possible moves, the king 1 move, and the queen 4 possible spaces. Depending on where black moved, white would have possibly the original 20 - 1 (because the pawn no longer has the option to move forward two spaces) plus the additional 10, or 29 possible moves. (By the way, the worst move is moving an a or h pawn forward one space -- that only frees up one additional rook move, but takes away a knight and pawn move and would reduce your options to only 19).

Analysis from here becomes much complicated because you need to account for the possibility of interactions among pieces, and the fact that different moves allow different amounts of moves. I won't go into an analysis of how many moves are possible for each of the 400 different positions so far -- I'll assume there are 24 possible moves now for each player -- a rough average of the worst (19) and best (29) possible outcomes.

That leaves (20*20)*(24*24) or 230,400 possible positions after just two moves! Most of these positions will leave players with even more options available on their next moves. (By the way, 8 of those possible positions result in checkmate (game over) with black winning -- how many of you knew it was possible to lose in just two moves?) Lets assume, conservatively, that each player has 28 moves available now.  That leaves (20*20)*(24*24)*(28*28) or 180,633,600 possible positions after just three moves. To put that in perspective, if you paired everyone in the United States up (311 million/2 players per game) and assigned everyone else a different sequence of moves, you still wouldn't cover all the possible positions after just three moves.

During the majority of the game, players typically have around 20-30 possible moves to consider, although most of those can be filtered out as "blunders" like moving your piece into a space where it can be taken without consequence. Typically, I find I am considering 5-10 "real" moves per turn, and I try to look at about 3 of my opponents responses for each of those, so I'm juggling maybe 15-30 possible positions in my head.  If from this point on, we assume there are 5 moves worth considering per player, and games typically last at least 20 moves, I estimate (on the low side) that there are at least
180,633,600 *(5*5)^20 = 1.64*10^36 different games. That's around 1 billion, billion, billion, billion different games (of only 20 moves, many games go much longer!)

As of this writing, the true answer of how many different games are possible is yet to be determined.  The often quoted number, called the Shannon number, is 10^120, or 100 billion billion google games. But even that is probably an underestimate, as it cuts games off at 40 moves.
So, I guess I just need to keep playing.

By the way, many of the positions after three moves are more popular than others. The most popular positions typically have names associated with them, like the Ruy Lopez, the Sicilian, Nimzo-Indian defense, etc.  These names typically refer to one of the 180,633,600 possible positions after three or so moves, in an attempt to bring some order and description to the moves. See my chess page on my class website for links to videos others have made regarding these openings if you're interested. My favorite opening is probably the London.