Ken Thompson, working at the Bell Laboratories, generated one of the world’s first chess endgame databases — king and queen vs king and rook. At the time, he explained to me how this revolutionary new technology worked. He did it in the form of a parable: God calculating the 32-piece endgame and playing chess. It is an amusing thought experiment that has gained interesting relevance at the current time.
In the beginning, the four-piece ending
It was in the early 1980s. Ken Thompson, the man behind Unix and the computer language C, had built a hardware chess machine named Belle, which duly won the World Computer Chess Championship. Ken had also resolved a dispute with IM David Levy on the feasibility of generating endgame databases. He did it by actually building a four-piece database, king and queen vs king and rook, and we had a lot of fun with. At a tournament in New Jersey I challenged top players to win with the queen. "That is quite easy," they would say, only to fail again and again against the optimum defence of the computer. One prominent victim was GM Walter Browne, three times US Champion.
I asked Ken to explain how his "endgame databases" were constructed. He explained: you generate every legal position with the given material — for KQ vs KR there are 1.9 million of them — and store them on a hard disk. Then a program examines each position to see if one side is mated. If that is the case, the position is marked with a zero. Now it retracts one legal move from all positions that are marked zero and marks them with a one. These are positions that allow one side to deliver mate in one move.
Then the program takes all positions marked with a one and retracts all legal moves from each of them. It checks these positions for ones in which every legal move leads to a position that was previously marked. Such positions are marked with a two. They are positions in which the side to move will be mated by force in two ply (half-moves).
In the above schematic, positions with White to move are depicted as circles, Black to move as squares. In the first diagram positions in which Black is mated are marked zero; in the second all positions in which White can mate in one move are marked with a one; and in the third diagram all positions with Black to move that lead only to positions marked one are marked two.
The process is continued until all 1.9 million positions have been processed. With the hardware available at the time (a mainframe in Bell Labs, New Jersey) it took half a day to process the endgame. The result: over 1.7 million positions got a number between 0 and 61, which means that the maximum length of a win in the endgame queen vs rook is 31 moves. Since more than 90% of all positions are marked, this endgame is considered a win for the side with the queen. Especially if you are a computer.
For humans it is different. In the sixth game of the 1983 Candidates Semifinals in London, Garry Kasparov, who had just turned 20, was facing the experienced Viktor Korchnoi. The game reached the following position:
Kasparov played 67...Rxd6+ 68.Rxd6 g1Q. Now everyone knows that queen vs rook wins, but Korchnoi wanted to see if his young opponent could do it. Instead of resigning, he played on: 69.Re6+ Kf5 70.Rd6 Qa7+ 71.Kd8 Ke5 72.Rg6 Qa5+ 73.Kd7 Qa4+ 74.Ke7 Qh4+ 75.Kf8 Qd8+ 76.Kf7 Kf5 77.Rh6 Qd7+ 78.Kf8 Kg5 and 0-1. Clearly Garry could. But Korchnoi was justified in putting him to the test.
The battle Q v R is not completely trivial. André Chéron, the ultimate endgame expert, requires seven full pages in his monumental four-volume Lehr- und Handbuch der Endspiele to describe the winning strategy. In spite of this, most tournament players assume they can win the endgame, grandmasters usually consider it trivial.
It is interesting to note that there are exactly two positions that require the maximum number of moves. This is one of them – it is the position that Walter Browne could not win in 50 moves. The endgame database instantly announces mate.
What about the 10% of unmarked positions in the database? Many are "pathological positions" in which Black can exchange the rook for the queen, e.g. wKb1, Qa1, bKb8, Rh1, which is an immediate draw (1.Kb2/Ka2 Rxa1). In fact Black wins if the white king is on d1, e1 or f1. But there are also more complex draws. The following has been known for over two hundred years:
The rook keeps checking White from h7, g7 and f7. If the white king moves onto the e-file then …Re7 pins the queen and wins it; and if the king moves to f6 or h6 then …Rg6+/Rh7+ Kxg6/h7 forces stalemate.
Before we proceed with the narrative, there are some little stories I need to relate. The first is that, at a tournament in Brussels, I got Anatoly Karpov and Garry Kasparov to sit together in front of my Atari ST computer and try to win queen vs rook. It was a hurried attempt in the press room after a round. They did not succeed, and laughed in amazement over the computer’s defence.
The other is about a 14-year-old chess talent who stayed at my house and whom I asked if he could win with the queen vs the rook. "Of course I can," he said, only to fail against the computer.
The next morning at breakfast the boy announced he had found the strategy to win, and proved it with flawless play against the computer. The lad, whose name was Peter Leko, had actually worked it out in his head, while lying in bed in the dark. Peter went on to become a challenger for the World Championship.
Finally, there was an incident at a chess tournament in the US: I was showing players the K+Q vs K+R endgame database, and had offered anyone who could win one of the long positions against the computer ten dollars. A young man approached and worked out the conditions with me: okay, he had to stake one dollar for the try, and White had to beat the computer in less than 50 moves (as required by the chess rules)? Yes. He put down the dollar but did not start playing. “I’ll be back in a minute,” he said, and returned with grandmaster Artur Yusupov, a world-class super-grandmaster. “You didn’t specify that it was me that had to play,” he said – and was disappointed to see my unshocked face. “That’s fine,” I said, with a smile. Well, Artur could not do it, and I got to keep the dollar.
A short while later Ken had calculated all five-piece endings, which have between 212 and 335 million positions each. They could be fit on four data CDs. Then came the six-piece endings, which at the time could not be delivered on DVDs – the total file size was much too large. But I had access to the remote server that held the data. Of course, the play of these endgame programs is completely incomprehensible. That was demonstrated to me in another incident.
Shortly after the six-piece endings had been calculated I had occasion to visit Garry Kasparov in his training camp. He was preparing for a World Championship with four of the greatest chess analysts in the world. I told them about the six-piece database and how there were six-piece endings in which the attacking side needs to play over 200 accurate moves to mate the opponent, assuming perfect play by both sides. “I want to try an experiment with you guys,” I said.
“Come on, Fred,” said Garry, “we know that humans cannot solve these kinds of endings.”
“I am not going to ask you to do that,” I said. “I am going to show you two positions. White needs to make eight accurate moves to get from one position to the other. Any deviation leads to a draw.”
Garry frowned. “And you want us to find these eight moves?”
“No,” I said, and put down two sheets of paper in front of the Kasparov team. “These are the two positions,” I said, “from somewhere in the middle of a 200-move win. What I want you to do is to tell me which is the earlier position, which is the position that requires the eight accurate moves in order to reach the other position and retain the win?”
After a few minutes of thought the whole team broke into laughter: “Impossible!” they said. “There is no way you can tell which is more advanced, which is the position you must reach with the accurate moves to get to in order to win. They both look exactly equivalent.”
To demonstrate the complexity of six-piece endings here’s a similar problem you can use to stupefy any chess player – even if he is the World Champion:
White to play has only one single move he must find, in order to win. All other moves lead to a position in which Black can draw. What must White play?
The answer is 1.Rh7!! Nobody will find this irrelevant-looking move. Except of course a chess program that has access to the six-piece database. In this case the chess engine Fritz does – it shows the correct move and a huge bonus for White.
Below the Fritz evaluation is a ChessBase service called “Let’s check”, that has direct access to the uncompressed data that is remotely located on a server. It tells you the same, specifying that after 1.Rh7 White has a mate in 254 moves. Any other move would lead to a draw. This analysis comes in practically zero seconds and is extracted from files with a total size 14 Terabytes (14,000 Gigabytes). Now that is huge!
Today, with special compression, the 143 most important six-piece endgames fit on a USB 3.0 flash drive (128 GB) and allow top engines to play these endgames perfectly. In fact, they can access them in the search, which means they have perfect evaluation for any six-piece positions they encounter after trading down from more complex positions in their calculations. Seven-piece endings have also been calculated, but the five hundred trillion positions have to be stored in databases on remote servers.
So how does God play chess?
Already with the advent of the five-piece endgame databases I was very eager to understand what they meant for the game. Whom better to ask than Ken Thompson, who had set the ball rolling. “When computers have calculated the 32-piece ending, they will play 1.e4 and announce mate?” I asked. “No!” answered Ken emphatically, and proceeded to explain why in a parable.
One day, World Champion Garry Kasparov, who towered above all his rivals, reached an Elo of 3000. When the rating list was released, the heavens over Baku opened and an Angel of the Lord descended. He approached Garry and said: “For what you have achieved, you are invited to play a game of chess against God.”
Garry was overwhelmed. He dressed in his finest and got onto the golden escalator that transported him into heaven. There the Angel led him into a small room where God was sitting, drinking coffee and looking at a computer screen. Garry was somewhat surprised that God was wearing jeans and a t-shirt, and had a fairly unkempt white beard. Garry bowed deeply and said:
“Oh Almighty Lord, Creator of the Universe…”
“Just call me God,” God interrupted. “Or G, which is what most of my friends call me.”
“Okay, God, it is a great privilege for me to stand in your presence and to actually play a game of chess against you. Of course, I have absolutely no expectation of winning. I assume you play a perfect game!?”
“Yes,” replied God, “I have done the 32-piece endgame.”
“Ahh,” said Garry, “Of course, that is trivially easy for you.”
“No, no,” said God, “it was really tough. More than 1035 legal positions. But let us play. You can have white.”
So Garry played his favourite 1.e4, expecting an exciting Sicilian. But after a few moves the game had left all known theory and God’s position was in shambles.
"This is divine humour," Garry said, "You want me to have a chance, God?" But He just smiled and said "No." Soon Garry was two pawns up and had an overwhelming position. "I am winning for sure now," he said. "No," said God, "it is a draw. The whole game is a draw. Can’t be won."
Garry was not convinced. He played on with great attacking moves, and even won an additional piece. Surely now he was completely winning. He reached a stage where it was clearly only a matter of technique to mate the opponent. However, try as he might, he was not able to actually deliver mate. There was always some unexpected defence, some bizarre move that prevented it. He tried this and that, but somehow could not succeed.
Then suddenly God interrupted a phone call he was making and stared in disbelief at the board. "My Self" he said, "It’s a win! I haven’t seen one in a billion years." "Yes, but I can’t find it," said Garry, "I cannot seem to convert my advantage to a mate." "Oh, no," God said, "not for you. It is a win for me — for Black. This only happens once in a decillion times."
The game proceeded, and God, now fully concentrated, started making moves that were completely incomprehensible to Garry. But they slowly improved Black’s position. Soon the game was equal, and Black started to take what for Garry seemed to be the "initiative". Then, in a flurry of unexpectedly brilliant moves, he was mated.
"I will be eternally grateful, God, for this demonstration of your omniscience," Garry said in parting. "I thank you for a very interesting game, Garry," God replied. "A one in a gazillion experience."
So what was Ken telling me? First of all, that calculating the 32-piece ending, i.e. comprehensively solving the game of chess, was beyond the scope of the current universe. "Just storing the data requires you to dismantle an entire planet," he said. "Just imagine what Greenpeace would say to that!"
Secondly Ken was predicting that the game of chess was a draw, that probably an overwhelming majority of all legal positions, including the starting position, would lead to a draw with perfect play. Both sides can always find moves that lead to unmarked (drawing) positions.
His prediction is further confirmed by the recent experiment with Google's AlphaZero, the Artificial Intelligence neural network program. The system achieved super-human chess skill after just four hours of "thought", in which it played tens of millions of games against itself. AlphaZero achieved a rating in the range of a 3500.
So the question arises: what happens if you let the system ponder for eight hours, or for eighty, or run on a far larger number of processors? My prediction: it will not be able to rise above Elo 4000 — nothing ever will. The draw in chess will prevent that from happening: a 4000 program will always be able to hold the draw, however strong the opponent.