In the prestigious German news magazine Der SPIEGEL, edition 49/1982, we found the following chess problem, which a reader had solved on his chess computer. It was a seven-mover, and the computer required more than 48 days to solve it.
In an article at the time I tried to explain not why it took so long, but how it could manage to process theoretically three trillion positions so quickly? In the meantime things have changed and regular chess engines have become much, much faster. You can find out how much faster yourself.
This is the problem the computer enthusiast had given his computer on September 18, 1982. The solution (1.Bf1 h4 2.Bh3 Kb7 3.Kd5 Ka6 4.Kc5 Kb7 5.a6+ Ka8 6.Bc8 h3 7.Bb7 mate) was displayed on November 6. Calculation time: 48 days, 9 hours, 46 minutes and 53 seconds. This formed the amusing conclusion to the SPIEGEL story.
Computer chess experts could, we wrote at the time, indeed be astonished by this calculation time, but not in the sense of Der SPIEGEL. For us a completely different question arose: how on earth could the computer solve the problem so quickly? How can a computer solve a seven-mover in only 48 days? The question was by no means trivial. But before we try to answer it, let's take a closer look at the math.
White has exactly 24 possible first moves (of which only one is the key move). How many counter-moves does Black have? Let us count them exactly: after 1.a6, 1.h4 and 1.Ba6 Black has just one reply. After any other bishop move, after 1.h3 or any king move, he has two.
So a total of 72 different positions can be created after the first black move. After the first white move, black has between 1 and 6 possible moves, on average exactly 3 (72/24). We want to keep these values for the further calculation: after white moves, there are on average 24 possible moves, after black moves 3. How many positions are there then at the end of a search tree of 13 half moves (= mate in 7)? Turns out there are three trillion positions.
Today's computers are of course much faster – they search many millions of positions per second and, more relevantly, use a large number of algorithms to find strategies that optimize the search. So, the solving time has decreased dramatically.
Take the JavaScript engine we use to help our readers analyse positions we show in our diagrams. It is not the most powerful engine in the world – after all, it must be thrifty with processor resources, and run in any browser. So how long will it take to solve Manfred Zucker's problem? You can check that out. Go to the diagram above and click on the fan button to start the engine. Watch how it starts to compute and come up with the solution – in eight seconds.
Now that is a big difference to forty years ago, you have to admit! To make it perfectly clear, here's an experiment I set up:
The solution: 1.Ke6! d4! 2.Bxd4 alQ 3.Bxal b2 4.Bxb2 c3 5.Ba1! c2 6.Kf7 c1Q 7.Bxg7 mate. The try 1.Kxd5? does not work: 1...b2 2.Bxb2 d4 3.Bxd4 c3 4.Bxc3 alQ 5.Bxal is simply stalemate. Even in a regular playing level a computer should soon see it and play 1.Ke6. But it must actually see all the way to the ninth ply, at least, to recognize the stalemate. A couple of decades ago we saw that chess computers only needed a few hours to find the solution. And today? Just click on the engine button below the above diagram.
Of course, our test problem can easily be deepened to continue our experiments. For example, we can easily make an 11-mover out of it: to do so, move the white king to a8 and place additional black pawns on e6 and h6.
Again, the white king must move to f7 and the bishop checkmates by taking on g7. The solution starts with 1.Kb8 or 1.Kb7. In the 1980s the world champion computer Belle saw a checkmate in my eleven-mover after twelve hours and 16 minutes. Once again, click on the engine button to see how far we have come.
Here's a replay app in which you can experiment with the above positions: