Thinking about chess

I am fascinated by chess. Not the actual playing of the game, but finding a way to solve it; to beat the game using a computer and come up with a strategy that always wins.

Chess has approximately 64! / (32! x 8!^2 x 2!^6) = 4.6E42 possible states the game can be in. That's a four followed by 42 zeroes, a humongous number. It would take the fastest supercomputer in the world 3 billion billion years to just enumerate them. That is, if it had anywhere to store the data, because it would require a memory the size of the earth.

Some of those moves are perhaps never reached or illegal. But coming up with all possible play variations is equally futile. At the first move white can play 20 different moves. After black has moved, there are 400 different variations. At the seventh move, there are over 3 billion variations, and it just continues expanding from there.

Limiting the game to only six pieces gives 54 billion possible states, still an intimidating number. Modern computers have solved such games to analyze so called "end games", where most pieces have already been captured.

Nim

My coworker introduced me to Nim, a simple game with three rows of markers; the first with five, the second with four and the third with three markers. You take turn picking markers. At your turn, you can take as many markers you like, but from one row at a time only, and you must pick at least one marker. The person picking the last marker on the table loses.

My buddy won all the games, I didn't stand a chance. Frustrated by this I went home and wrote some software to analyze all possible permutations of the game, and found that there are certain safe game states or "stepping stones". When it is your turn you should pick markers to reach one of the stepping stones, and you are guaranteed to win. All I had to do was to memorize them.

Below: The starting position of Nim in red. Many variations exist, this is just the one we used. The safe positions are in black. Notice that no matter what the opponent does at a black state, you can always pick markers to get to the next black state, so they are true stepping stones. For example at the 5-4-1 state, if the opponent takes two from the second row, then you take two from the first row, and you are at 3-2-1. Since the starting position is not a safe state, the player that starts will always win, if he knows this system.

This fueled my interest in the much more complicated game of chess, and whether there is an equivalent to the Nim stepping stones.

Chess theory

Chess is an abstract strategy game with perfect information, where nothing is left to chance. This means that there is such a thing as perfect play, so that there is always a best move that will lead to the best outcome for the player, and this move can be calculated in advance. Sometimes several moves are equally good.

Chess computers have already beaten humans in chess, but they are very far from perfect play. Perfect play requires chess to be solved for all its possible states.

To solve chess is easy in theory. Enumerate all possible states the board can be in, taking into account special rules such as en passant, castling, pawn promotion and who's turn it is. Analyze each state and determine if any side has won or if there is a draw, and mark it as such. Then continue step by step and analyze the states that lead to the final states, and mark them as winning or losing states. Having such a table of states, you can know that a certain move will make you win in X moves or less. But of course this can't be done in real life because of all the permutations, as mentioned above.

Limiting the permutations

One way forward is to find a way to limit the permutations. The idea behind this is that although chess has many possible states, most of them do not matter, because there are stepping stones along the way to avoid them. 

Imagine crossing an ocean in a row boat. Spread out in the ocean are numerous islands with supplies. As long as you can visually see the next island you are safe, and can continue. The same idea applies here. As the computer is about to make its move, it enumerates all possible states, one, two, three, etc, moves into the future, until it finds an island, a safe state to be in, that is guaranteed to lead to victory. The computer takes a step towards that island. No matter what the opponent does in return, there is always an island within reach to move towards.

How can those safe states be found without enumerating all states? You can start working your way backwards from the end games that have already been solved. But at some point the enumerations become too many to keep track of, and you'd have to take a chance and bet on a few that seem promising. So it would be a big gamble, that may or may not pay off.

Anyways, it is a fascinating subject.