Thursday, November 17, 2011

Solving Chess

The beauty and complexity of chess has drawn admirers from all walks of life for centuries. Even with over 50 years of computer-aided study, new mysteries are discovered about chess on a daily basis. With all of its rich complexity, chess is still on the radar to be solved by computers, maybe sooner than we think.

Endgame Tablebase
An endgame tablebase is a computer database which contains precalculated, exhaustive analysis of a chess endgame position. For example, you can place a black king on a8, black rook on h7, black knight on b8, white king on b2, white queen on b6 and the endgame tablebase will demonstrate that Qd8 is a forced checkmate in 26 moves. It is able to do this because it already contains information on all of the possible moves and subsequent responses by the opponent, all the way to checkmate. No analysis or thinking on the part of the computer is required.

An endgame tablebase contains information on all positions with three, four, and five pieces in any configuration and all positions with six pieces except those which are five pieces versus one lone king. The endgame tablebase is approximately 1.2 Terabytes of digital information.

An Entire Game Tablebase
If this feat is possible with only six pieces, is it possible with 32? Could an entire game be conclusively solved before the first pawn is pushed? Absolutely. There are a finite number of legal positions possible that can arise from a game of chess.  It is estimated that there are somewhere around 1043  number of positions that can appear on a chess board after the clock is pressed.

Just how big is 1043? Well by comparison, it is estimated that there are less than 1024 number of stars in the sky, everywhere, period. Also don’t make the mistake of thinking that 1043 is about double the amount of 1024, actually 1025 is exactly ten times larger than 1024, if that gives you some idea of what a colossally large figure we are dealing with.

So that begs the question, exactly how long would it take to put 1043 number of positions into a comprehensive database such as the endgame tablebase that we already have? The endgame tablebases account for about 1014 number of possible positions solved, so we can reduce 1043 to 1029 number of positions we have to account for.

The fastest chess engine can execute about 2 million positions per second. But let’s say for the sake of argument that computers could process 1 billion positions per second.  If we hooked up 1 billion computers that could each compile 1 billion unique positions per second into a database, it would still take 3,170 years to compile into a database that would be about 10,000,000,000,000,000,000,000,000,000,000 terabytes.

This method of solving chess will not be done anytime soon.

Sandwich Method
There is already a 7-piece Nalimov endgame tablebase near completion.  Endgame tablebases are a method of solving chess starting from checkmate going towards the beginning. Chess opening theory, which humans have been doing for over 250 years, is solving chess from the beginning towards the back end.

At some point probably in the next 100 years, these two methods of solving chess will get close enough to be bridged together by computer analysis.

Checkers was solved in a similar fashion. The checkers playing engine Chinook sticks with an opening book that gives it the highest probability of victory when moving first (the fewest moves available to its opponent that leads to a forced draw). Chinook prunes all other opening families when moving first and plays the lines which gives it the shortest path to a draw versus every opening when moving second.

However, you cannot input any checkers position into Chinook and it will spit out a definitive result like an endgame tablebase will. Here is an example in chess terms. Let’s say there was a chess playing machine similar to Chinook called, of course, weaksquare. The sandwich solving of chess determined that 1.e4 and 1.d4 lead to victory for white, and all other moves lead to a draw. Therefore, weaksquare will only play 1.d4 or 1.e4 as white, ignoring all other opening moves as a possibility.

Weaksquare would not be complete without an adequate defense to every opening move by white when playing black. Let’s say whenever someone plays the Bird Opening, the fastest route to a draw is the response 1... g6. Weaksquare ignores all other responses to 1.f4 and only plays 1... g6, even though others may also draw. If weaksquare were playing white and the game were to somehow begin 1.f4 e5!? (From’s Gambit) then the perfect chess playing machine would have absolutely no clue what to do on move 2 because this position is literally not in its database of moves.

Chinook has the same drawback, it is not a brute-force solving of checkers. You cannot input any position into Chinook and it cannot give you a conclusive outcome. But as long as Chinook controls the game from the beginning, it will never be defeated (because checkers is a forced draw with best play).

The creation of weaksquare, the perfect chess-playing machine, is inevitable.  The gap between endgame tablebases and opening theory is astronomically vast. However, with improving computer hardware and improving computer chess analysis, this gap will get exponentially smaller until it disappears completely and chess is solved.