Solving Chess Endgames

In 1950, Claude Shannon calculated an estimate for the lower bound for the number of all possible unique chess games to be . That number came to be known as Shannon's number.

That number is much outdated by today's standards but the fact remains that it is still not currently possible to store that number of chess games in computers even with compression.

Endgame Tablebases

It is possible, though, to search through every possible play for all positions with at most a certain number of pieces. From there, one could "solve" these positions and derive the best play possible and discover the inescapable fate of the game.

Storing a complete table of best plays can be particularly useful: chess endgames have low number of pieces, and so, it is possible to evaluate new positions with absolute certainty. Some people have likened this to consulting an oracle, or quite famously, Ken Thompson called it "playing chess with God".

Demonstration

This demonstration is backed by a 5-men Gaviota tablebase which occupies 7GB of space, compressed. It only works when given valid positions of up to 5 pieces.

You can rearrange the pieces on the board by dragging them around, and also toss pieces away by dragging them off the board.

Relevant Modules in NUS

Interested in making game playing computer programs? You can learn how to do that from the following modules:

  • CS3243 Introduction to Artificial Intelligence

CS3243 can teach you concepts such as minimax search and alpha-beta pruning which are essential to the decision making process.


I hope you've enjoyed this demonstration.

If you have any feedback/questions or if you noticed any mistakes in my article, please contact me at fazli[at]sapuan[dot]org.

Comment section for placebo effect only. Please use email to contact the author