Computers solving chess problems

A computer enthusiast had given his computer this task 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 found 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:

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)?

How long does it take a computer to search three trillion positions (which is what we asking of it in the mate search). Let's assume that a good chess computer on mate search level (where all evaluation functions except the mate are switched off) can generate about 1000 positions per second. That is then about

4 million positions per hour, or
86 million positions per day or
31 billion positions per year. 

The examination of 3 trillion positions should therefore take no less than 95 years!

We were concerned about the extremely large discrepancy between the theoretically determined value and the computing time given in Der SPIEGEL. We tried  letting our chess computers do the calculations, but after 100 hours the experiment was aborted. We then sent the position to Mika Korhonen, our contributor from Finland. Some years ago Mika developed a machine program for the Apple microcomputer to solve chess problems (mate, helpmate, selfmate). His program, called "Mate", is one of the most powerful programs ever written for a micro.

Mika ran the SPIEGEL problem and had the solution after 98 hours, 11 minutes and 30 seconds. Note that the program did not only give the solution, but had also checked the problem for secondary solutions (that's the whole point). So it had searched the tree completely. Mate does about 30,000 (!) position checks per second. In the last half moves it does much more, because it has a lot of problem-chess specific information, and recognizes far in advance that certain variants cannot lead to mate for technical reasons. But even this is not enough to explain the observed performance (even at 40,000 knots/second it should take almost 10,000 hours = 41.6 days).

Are there any mechanisms, which shorten the tree search for chess problems? It would be nice, of course, if you could simply use alpha-beta (how the alpha-beta algorithm exactly works will be described in a later issue). Then the program would only have to check about the square root of 3 x 10^12 = 1.7 million positions instead of 3 x 10^12, and the task would be solved in less than an hour.

Unfortunately the alpha-beta algorithm is not applicable for chess problems. It only concerns relative scores, which do not exist for mating problems: the end positions, which are found during the tree search, cannot be "a bit better" or "a bit worse" than the best ones found so far. Either an end position is mate – then it is good – or it is not, and is completely worthless.

But there are other mechanisms which are especially useful in problem chess. As Mika tells us, for example the so-called "killer heuristic" in chess problems contributes tremendously to saving computing time. With this method, all black moves, which have "disproved" previously examined variants, are stored and examined first in later variations. In this way, the program gradually finds out which is the most effective defence for Black. The same defence usually disproves most other variants immediately, and the program does not examine many nonsensical black moves. Mika appreciates (after careful investigation of the SPIEGEL problem) that his program considers only 1.2 possibilities instead of 3 for each black half move.

This reduces the number of end nodes to 13 billion (24 x 1.2 x 24 x 1.2 ... ), and now, running at 40,000 nodes/second, we get 95 hours of computing time, which is pretty much the observed value. Also, the performance of the regular chess computer becomes obvious. If we assume that a chess computer today can run at 1000 nodes/sec in a pure mate search, and that it applies the killer heuristics optimally, we get a computing time of 158 days. If we further assume that the key move was found after about half of the computing time (chess computers then stop immediately), then at 79 days we already come close to the computing time quoted by Der SPIEGEL. The difference can easily be made up by the use of a very fast computer (more than 1000 knots/sec.), or by the luck of the brave. We sent the position to Ken Thompson for further investigation with his chess machnie Belle.

If you, dear readers, are interested in such questions, we advise you not to use the SPIEGEL position. 48 days is a long time. We have instead devised a simpler seven-mover for you to experiment with:

The solution: 1.Ke6! d4! 2.Bxd4 alQ 3.Bxal b2 4.Bxb2 c3 5.Ba1! c2 6.Kf7 clQ 7.Bxg7 mate. The try 1.Kxd5? does not work: 1...b2 2.Bxb2 c3 3.Bxc3 alQ 4.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 13th ply to recognize the stalemate. With this problem the number of variations can be much better estimated, and initial experiments show us that chess computers only need a few hours to find the solution. 

Of course, our test problem can easily be deepened if you want to continue your 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. But be careful: we do not dare to speculate about possible calculation times for normal chess computers. The special computer Belle sees the checkmate only after 746 minutes. It solved our 7-move problem in just 14.9 seconds!

For all readers who own a simple chess computer we bring you, in closing, a mate in six which, we can assure you, it will have no difficulty with:

This is a humorous chess problem: both sides always have only one legal move! The computer does not have to check billions of moves, but exactly 14 (including under-promotions). Even the simplest chess computers should be able to handle that in a second or two!

The considerations and calculations in the above article, written over 37 years ago, at the dawn of computer chess, are quite theoretical and may contain logical or mathematical errors. We would be very interested in your thoughts and the results of your tests. It would be great to experiment with chess problems that today's engines need more than microseconds to solve.