Computers solving chess problems

by Frederic Friedel
9/8/2020 – In the prestigious 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 7-mover and the computer required more than 48 days to solve it. In an article at the time Frederic Friedel 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.

ChessBase 15 - Mega package ChessBase 15 - Mega package

Find the right combination! ChessBase 15 program + new Mega Database 2020 with 8 million games and more than 80,000 master analyses. Plus ChessBase Magazine (DVD + magazine) and CB Premium membership for 1 year!

More...

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:

white move black replies
a6 1
h4 1
Ba6 1
h3 2
B- (5x) 2
Nd8 5
N- (6x) 6
K- (8x) 2

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

Half-moves (ply) Positions
1 24
2 72
3 1728
4 5184
5 124,000
6 373,000
7 9 million
8 26 million
9 650 million
10 2 billion
11 46 billion
12 140 billion
13 3 trillion

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.




Editor-in-Chief emeritus of the ChessBase News page. Studied Philosophy and Linguistics at the University of Hamburg and Oxford, graduating with a thesis on speech act theory and moral language. He started a university career but switched to science journalism, producing documentaries for German TV. In 1986 he co-founded ChessBase.
Discussion and Feedback Join the public discussion or submit your feedback to the editors


Discuss

Rules for reader comments

 
 

Not registered yet? Register

albitex albitex 9/11/2020 11:15
Stockfish 11 on my smartphone takes 24s to find the mate in 7.
Paris Beau Paris Beau 9/9/2020 09:37
SF 11 solve it in 30 sec.
adam7212 adam7212 9/9/2020 02:02
1.Bf1 h4 2.Bh3 Kb7 3.Kd5 Ka6 4.Kc5 Kb7 5.a6+ Ka8 6.Bc8 h3 7.Bb7 mate

Stockfish 20200908 found it instantly > http://prntscr.com/udyalg
wok wok 9/8/2020 10:53
Very nice article. Obviously it requires extraordinary deep solutions to trick today's silicon monsters. The following position I managed to solve faster than Stockfish 11 which takes about 20 minutes on my machine with around 35 MNodes/sec until it comes up with a convincing mainline:
White: Kg1, Qc1, Pawns on f2,g3,h2
Black: Kh8, Bh3, Pawns on g2, f3, g4
White to move and win - so it's not a "mate in n" position and therefore maybe doesn't qualify
The winning idea is quite easy to spot for a human, then it takes some effort to figure out the proper way to implement it which is the punch line of the study.
brian8871 brian8871 9/8/2020 05:52
It used to take a month and a half to solve a problem that programs now can eat for breakfast. That reminds me of a time in the 90's when the only shows you could watch online were South Park and Powerpuff Girls, and that was because the animation was so primitive that it didn't take much bandwidth. There was no such thing as streaming a live-action show.
Thomas Beuman Thomas Beuman 9/8/2020 02:24
I wrote my own mate-finding program many years ago. Like Mika's program, it can also do help- and selfmates, and also does brute-force searching without any pruning (except when an effective defensive move is found, it then doesn't check other moves). It doesn't use the trick of "learning" good defensive moves though, that's a nice touch.
It does use hashing to store evaluations of positions to avoid reexamination of positions that can be reached via multiple move orders. Unfortunately, this storage is such an integral part of my program and it outputting the solution(s), that I can't (easily) turn it off and compare with Mika's program.
For the moment, I can report that my program (running on my 2.5 GHz laptop) solved the Zucker problem in about 10 seconds, encountering 2211305 unique positions along the way. The first test problem was solved in about 3 seconds, with 623992 unique positions. Test problem 2 would undoubtedly take hours.
1