Darkness on the Horizon (1)

This historical article appeared in the magazine Computerschach International in 1983. It was in German and has been translated and edited for republication on our news page.

Imagine that you are travelling by car and have a breakdown. It's the middle of the night and it's completely dark. You are in a rural area, but fortunately you can see a light in the distance. Obviously a house where you can get help or at least make a phone call.

You take the small flashlight that you always have in your car and set off. But you don't get very far, because soon you see a nasty-looking fence in the beam of your torch, two meters high and covered with barbed wire. It blocks your way to the house. Of course you could try to climb over the fence, but you'll probably tear your expensive suit and break your neck. On the other hand, you can't possibly spend the whole night outdoors.

So what do you do? You shine your flashlight to the left and to the right, but everywhere the fence seems to continue. In front of you, you suddenly see a gap in the fence, obviously a passageway through which you can easily get to the house. At least almost without problems. Because directly in front of the gap you can see a big mud puddle in which a pig is wallowing. You have to wade through this puddle if you want to get to the house. That will certainly not do your suit any good, and you will certainly not smell like a rose when you reach the house. But at least it's better than having to climb over the fence.

So hold your nose closed and walk bravely through the mud. You get to the other side and breathe a sigh of relief. That's all over, you can get to the house that will save you. But now you can see in the light of your flashlight that the fence had no passage but only a small indentation.

Unfortunately the passage through the puddle did not help, you have to climb over the fence. Beside the torn suit and possible injuries you have also dirtied yourself with mud, which was completely unnecessary. If you had a better flashlight, this wouldn't have happened. You would have seen for sure that crossing the puddle was useless. And you might have discovered that there's a gate to the left through which you could have simply walked...

I found this nice little story in a book about chess computers (Julio Kaplan: "How to get the most from your chess computer", R.H.M. Press/Pitman, 1980). The author belongs to one of the best connoisseurs of the matter, because he himself has written quite a few programs for chess computers, and he is also an excellent chess player. Born in Argentina, Julio Argentino Kaplan Pera became junior world champion in 1967 (ahead of Hübner and Timman!) and has lived for many years in Oakland, California, where he is part of a software company, Autodesk, that makes software services for the architecture, engineering, construction, manufacturing, media, education, and entertainment industries.

Kaplan’s book belongs in the collection of every computer chess friend. Besides a very well-founded introduction to chess programming you will find many excellent and knowledgeable hints that increase the fun of playing against the computer.
But what does the story about the fence and the puddle have to do with computer chess? Well, it illustrates in a catchy way the phenomenon known as the "horizon effect." Even computers get into situations not unlike the one described above.

We want to illustrate the horizon effect with the help of a classic example from the doctoral thesis of Hans Berliner, former correspondence chess world champion and now computer scientist at the Carnegie Mellon University in Pittsburgh.

[Diagram from the time: White to move]

Any human chess player can immediately see that the white bishop on a4 will be captured by the black pawns on the queenside. But for a chess program that could, in pioneer days, only process a few thousand positions, and look around three half-moves ahead, there were some traps.

Among many other move sequences the computer would find 1.Bb3 c4 2.Bxc4. A static evaluation of the position would give an advantage of one pawn, which would of course be a fatal misjudgement. Most programs therefore performed a so-called "quiescence search” at this point, evaluating all capture sequences until the position became "quiet."

During this quiescence search, the computer discovers that further moves will bring an advantage for the opponent (2...bxa4 etc.). But instead of accepting this as inevitable, it develops a foolish plan to "save" the bishop. The computer plays 1.e5? A human being would see at a glance that this does not change the bishop's situation. But for the program, the bishop is effectively saved.

Let us reconstruct the reasoning of a three-ply search. After 1.e5 bxa4 2.exf6, the original material balance is preserved. But what is the situation after 1.e5 dxe5 2.Bb3 for the program? Perfect, because no subsequent capture loses a piece. 2...c4 is not a conspicuous move and is not considered in the quiescence search. For the program, the sacrifice of a pawn to save the bishop is fully justified. After 1.e5 dxe5, it naturally discovers that the threat has not disappeared, and it must again develop a clever plan to save the bishop: 2.Rxd7 Nxd7 3.Bb3. This loses the exchange, but again that apparently saves an entire piece.

As you can see, computers at the time could give away a lot of material to delay the inevitable. It was a problem that every chess program that worked with a search tree (i.e. practically all of them) had to face. Beyond the terminal positions there was complete darkness for the program, just like for the person seeking help in our example above. He can only see as far as the cone of light of his flashlight reaches.

The example of Prof. Berliner was for computers in the very early days of chess programming. Soon they were equipped with more sophisticated search algorithms that made them less short-sighted. But we could easily find examples where even more advanced chess computers fell victim to the horizon effect. Take the following drastic position:

Master Class Vol.11: Vladimir Kramnik

This DVD allows you to learn from the example of one of the best players in the history of chess and from the explanations of the authors (Pelletier, Marin, Müller and Reeh) how to successfully organise your games strategically, consequently how to keep y

Black, as you can easily see, wins easily by simply giving up the rook. Today’s programs will tell you in a second or two that e.g. 1...f5 results in a mate in 14, and 1...e5 mate in 15. But with the programs at the time you could experience strange things. Many would give away the win in the foolish attempt to save the rook: 1...f6 2.Bxf6 e5 3.Bxe5 d4 4.Bxd4 c3 5.Bxc3 and now the position is a draw.

You know that on the diagram boards on our web page you can move pieces, and in fact I can add an engine to play countermoves. So I had this idea to provide you with the experience of what it was like to play a 1983 chess program. Unfortunately, though, even if I set our JavaScript engine to work for a thousandth of a second per move, it will still win the position easily for Black. So you are going to have to simply imagine what it was like back then.

Now let us look at another position I used to test the ability of 1980s computers to avoid the horizon trap:

In 1983 I used the position on commercial chess computers and commented my results, ironically:

1.Kxhl is a clear mistake. It leaves the computer no other option but to destroy you: 1...Ke5 2.Kg2 Kd4 3.Bg8 c4 etc. But can you achieve a better result? Not against a human opponent, of course, but against a computer on the lower levels. We have to simply take advantage of the horizon effect and subtly deceive our electronic friend. For example we play against the CC Sensory 9 [one of the most popular computers in 1983] on level 3 and start with 1.Kf3!! You probably won't believe it, but only with this nonsensical move do we have a chance to draw.

The computer starts to calculate and first considers 1...Ke5, with which it would win without further ado. But soon it realizes that the opponent can then capture the black knight with 2.Kg2. But it doesn't want to give that up (the fact that we spurned the knight one move before has of course no meaning for the computer) and so it quickly hatches a clever plan to "save" the knight: 1...c4? With this move it has pushed the loss of the knight beyond its calculation horizon. For it the knight remains in play, and for that it gladly gives up a pawn.

Now you can also see why 1.Kf3 was important. Had we captured the knight, 1...Ke5 would have come, of course. And if the king had stayed at g2, the computer would have realized too quickly that it would lose the knight anyway. It wouldn't have bothered about it at all and would have won the game ice cold.

But we have not yet solved all problems: 2.Bxc4 Ke5! Obviously the computer wants to attack the bishop after 3.Kg2 with 3...Kd4 and thus "save" the knight again. Since this also happens to win, we have to play carefully and once again lead the opponent away from the right path: 3.Bg8! Again it wants to continue correctly with 3.Kd4, but then discovers that we are threatening the knight and tries to save it again: 3...b3? The trick worked, we have a draw: 4.Bxb3 Kd4 5.Kg2 etc.

This time I have set the JavaScript engine in the diagram above to a tenth of a second per move for you to experiment with. See if you can trick the computer. I cannot guarantee anything – your computer may be too fast for the engine to go astray.

In the next historical installment I will discuss further dirty tricks we were able to use against computers in 1983 – and some positions that even today are fairly simple for humans but extremely difficult for chess engines. Interested?