First of all, I am no expert in Chess. Am an average player with a strength of approximately 1500 on the Elo rating, unofficially, of course. My best play was in my college days when I finished 9th in Mumbai University and the top 8 qualify to represent Mumbai. That was a massive heartbreak, but compared to other 8 who did qualify I had not prepared at all (competitive chess requires massive preparation just like any other sport). So I got over it quickly and pursued chess only as a hobby. So do not expect any chess advice in this blog. What I am going to write in this blog is advancements in Computer Chess which can be authoritative sources of learning new ideas in chess.
The beauty of chess is that its rules have been unchanged for centuries ( except the introduction of 50-move rule due to advent of computers in chess) and that is according to me the single most important reason why the need for innovation in chess was felt very acutely. The chess playing community across the world responded brilliantly, and took the game forward. After Claude Shannon's seminal paper on building machines to play chess, the computer chess research community joined the bandwagon from 1950s. From being an absolute novice in 1950s to beating the strongest world champion in 1997 (IBM Deep Blue v/s Gary Kasparov) computer chess had its set of innovations. Computers of today routinely beat Grandmasters and there is little doubt that the best of machines has surpassed the best of humans by a huge margin. If they wished, the chess research community could have stopped here and declared the problem as "solved", but they didn't and instead asked themselves the question - "Is there anything that computers can now teach us humans back?" - Indeed. Computer chess advances can achieve phenomenal feats that the humans cant even conceive.Here's an example from Kasparov v/s The World correspondence chess game from 1999.
(The position after 55.Qxb4; tablebases tell us White wins in 82 moves. Source: Wikipedia)
After, 55 Qxb4, tablebases declare that there is a forced win for White another 82-moves away. No human can think this far. Even when the position is fed to Rybka 2.2 32 bit, it looks up about 18-moves ahead and declares that White has a substantial advantage, but still cant predict a checkmate. Curious, what the tablebases are? Read on.
Traditionally and even today, the weakest link in computer chess remains the chess endgames. The board is sparsely populated and humans rely on strategic principles, pattern matching (trying to relate current position to previously played games whose results are known) and absolute calculations. Computers on other hand have to rely only on calculations and hence take long time to play the right moves. Since 1965, researchers have been thinking about building a database of played games in order to teach the computers the "strategic principles" and "pattern recognition". Enter Endgame Tablebases a.k.a EGTB
EGTBs use technique called as retrograde analysis and compute backwards from checkmated position. The computation involves finding the best move that could have avoided a checkmate, followed by the opponents move that would have again tried to enforce a checkmate. Working backwards this way, one gets a series of perfect play (one in which both white and black play optimal moves) . Any sub-optimal play would lead to quicker conversion. Thus the computer now has to only look-up a position in this database and if the position exists then a sequence of move exists which will lead to a perfect result (guaranteed win / loss or a draw) if the optimal moves are played. The look-up tells the computer what to play and in the process saves time and lots of CPU cycles. What fascinates me is that this backward time travel is also able to account for the fact that what is a queen now on the board was a pawn in its previous life (when a queening of a pawn has taken place). So in essence researchers have been able to give a guarantee that a certain position on board is a sure-shot win/loss or a draw given that optimal moves are made. In case, sub-optimal moves are made, computers will always win. So does that mean the game of chess is solved?
Fortunately or unfortunately, whichever way you look at it, the whole game is not solved. EGTBs exist only for 3,4,5 and 6 pieces currently. A N-piece EGTB means any board position with any set of pieces (pawn, knight, bishop, rook and queen) including both Kings does not exceed N. Such positions are coded in the database. So a 3-men tablebase could have any combination of 2 kings plus any side having any other piece on any square on the board. So on and so forth. A 5-men tablebase is 39 GB in size and when compressed comes down to 6.5 GB. 6-men tablebase is 1.2 Terabytes in size. Work on 7-men tablebases is expected to complete by 2015 and that is expected to be in Petabytes.
EGTBs have had a profound impact on advancement in the endgame theory. Go here if you want to know more details of the EGTB technology.
The longest mate with 7-men is an astonishing 524 move long sequence. Try out the 6-men tablebase applet by placing a random legal chess position here and see the results for yourself. If you want to generate up to 5-men tablebases for yourself and make your chess programs use it, download the programs from Miguel Ballicora's website on Gaviota Tablebases. My dual core Lenovo T410 took more than 100 hours with version 0.83 of Gaviota EGTB programs to generate 39 GB tablebase files. Chess GUIs like Arena allow you to configure tablebases for any of your favorite engine that works with Arena.
Even GMs use EGTBs for sharpening their endgame skills. It is especially useful in blitz games where there is less time to think and you just need to play moves by memorizing them. So if you want to improve your endgame skills with under 6-pieces on the board, getting conversant with EGTB is a good idea !
No comments:
Post a Comment