Computer Chess Program Shredder

After I have managed to win last year's open computer chess world championships in Paderborn, even though my program Shredder was the only program at the top not running on very fast and also very expensive multi cpu computer systems, many people asked how it could have been possible to win this uneven fight. I will try to answer this question in the following article and will also explain some background about computer chess in general understandable for everybody. You don't have to be an expert in this topic to be able to follow this article.

First of all I would like to explain how computers can play chess without using too much technical vocabulary. A chess program consists of two major parts: an evaluation function and a tree searching algorithm. The latter is needed to search almost all possible moves sequences to find and play the best line for the program, whereas the program needs an evaluation function to tell which positions are good and which are bad for one side.

The number of all possible variations in chess is very, very big as there are on average 35 legal moves in every position. If you want to consider only one move for yourself and one for your opponent, we call this two plies, you already get 35*35 = 35 2 = 1225 different variations. With just one move or another two plies more you already have 35*35*35*35 = 35 4 = 1500625 possibilities. As you can see the number of all the possible variations growths exponentially, which means that they grow very, very fast. Even for the fastest chess program it is getting impossible to examine ALL possible moves and variations and if you want to look only 5 or 6 moves ahead, even the fastest computer will need months to complete this task. What can be done? Well, the trick is that a computer should discard variations that are obviously bad as soon as possible and save his time for more important tasks. Sounding so easy in theory there are still some problems in practice, as the stupid queen move can turn out to be a genial winning sacrifice in the end.

While trying almost all variations, the program also has to evaluate them or better their final positions because after all the program should play the possibly best move. The first criteria is material. You tell the program that a queen is usually better than a rook, which is most of the time superior to a bishop or knight and every piece is better than a pawn. The king gets no value attached to because once he is gone the game is already over. But there are much more things in chess a program should know about. For example a double pawn or an unprotected king in the middlegame is usually bad. In the endgame an advanced passed pawn is often very strong and with two knights alone one can't mate. But some points are not so easy to evaluate, like weather the isolated pawn on d4 is strong or weak. As you can see there is much a program can be taught about but you should keep in mind that there is an exception to almost every rule. The double pawn in the above example can also be very strong.

To my knowledge today all strong and successful chess programs are working that way. But don't worry, there is still enough room for authors to bring in their own ideas and algorithms so that all programs are nevertheless significantly different to each other. I was only talking about the basic concepts used in chess programming today.

It should be clear by now that there are two major ways to improve your chess program. First you can try to make it faster, so that it can examine more positions in a given time and can look further ahead in the game tree. The alternative is to make the program more intelligent or smarter, so it knows more about chess and can evaluate the positions in its search tree more accurate and with a smaller margin of error. To do both would certainly be the optimum, but unfortunately that's not possible, because adding more knowledge will make the program slower and a higher speed can only be achieved by deleting some knowledge. If you are starting with chess programming this must not necessarily be true, as you can often gain speed by optimizing your code or your algorithms, but I think that this was already done by all of the authors of today's high level chess programs. What always helps in computer chess is a very fast computer, because every program plays better on a fast state of the art computer than on yesterday's hardware. The program can go faster without the need to delete some of its internal chess knowledge. That's the reason why important computer chess events and tournaments always remind me of a hardware fair where all the latest and greatest hardware improvements show up. Last year's computer chess world championship was no exception to that rule.

There has always been a big discussion among the programmers and users about what to do to get optimal playing strength for chess programs: fast and stupid or slow and intelligent. I am not quite sure weather there is an optimal solution for that problem, but I will try to show you the way I did it in Shredder and to explain my decisions.

In my opinion it is only possible to increase the playing strength of a chess program by a small amount if you just try to increase its speed. Today's top programs have reached a level where not many people are still able to compete. At this level games are not decided because one side has overlooked a tactical threat and lost a piece, but if you have lost you got most of the time strategically outplayed before. To play strategically you need to know about chess. It is not enough for a chess program to see 5 or 6 moves ahead, make no tactical blunder within this horizon and wait for the opponent to make a mistake. I agree that this works pretty well against humans in speed chess, but with longer time controls it can be seen that you can't go very far in chess without strategic knowledge. Just as one expert has put it: “I don't know where I am going but I am going very fast.”

Another problem of that strategy is that you can increase the number of moves you can look ahead only very slowly. As the search tree growths exponentially, one need about three times more time for every single ply deeper in the tree. So unfortunately it is not that you need twice more time to look 10 moves ahead than to look 5 moves ahead, you need 59049 times more time! In some positions, especially in the endgame, you won't find the right move even if you can see 20 moves ahead. You simple have to “know” what to do, you can't calculate it.

But there is also another thing you have to keep in mind. Chess programs do not exist just because they are chess programs. They are also made for users to play against them, to help them analyze or to support them. Playing against today's programs himself, the user will certainly lose most of the games. But in my opinion there is a significant difference how the games are lost. Against an “intelligent” program you lose because you got outplayed strategically, against a “stupid” program you lose because you overlooked a tactical trick in a promising position. Some will say, “well, anyway, lost is lost”, but there is a difference: What did you learn as a chess player in these examples? In the latter case only that you have to be more careful in the future, but in the other game you learn about your weaknesses in chess. For that you need a program that is able to detect and exploit those weaknesses. Unfortunately it also happens against an “intelligent” program that you overlook a simple tactical threat or just lose a piece for nothing.

For home analysis it is even more obvious that you need a program with chess knowledge, otherwise the programs analysis in a quiet position won't help you much. Maybe you will say that you only want to check your own analysis for tactical blunders and for that purpose the program don't need much knowledge. There is certainly some truth in that, but today the tactical strength of ALL programs is so high, that every player, no matter of which class, can benefit from them and all of the programs are able to discover hidden tactics.

I certainly don't want to question the whole concept of tree searching, but with today's computing power we got to a point where we have to think about how to advance in computer chess.

After all that being said it should be clear which way I chose with Shredder. Of course I didn't do without tree search but I tried to add so much knowledge to Shredder it is able to play nice and successful chess. I would like to show you some games Shredder played last year at the world championship in Paderborn, where it played some very nice moves. I am not saying that other programs won't be able to play those moves, maybe one or the other move will also be played be program X or program Y. The point is that in most of the games my ways will lead to better and more interesting chess.

(20) Fritz - Shredder [C88]

WCCC99 Paderborn (2), 15.06.1999

1.e4 e5 2.Sf3 Sc6 3.Lb5 a6 4.La4 Sf6 5.0–0 Le7 6.Te1 b5 7.Lb3 0–0 8.a4 b4 9.d3 d6 10.a5 Le6 11.Sbd2 Tb8 12.Lc4 Dc8 13.Sf1 Sd4 14.Sxd4 exd4 15.Lf4 Sd7 16.Sd2 Lxc4 17.Sxc4

Shredder opens the opponent's queenside. That for he temporarily sacrifices a pawn.

17...b318.cxb3 Sc5 19.b4 Txb4 20.Ta3 De6 21.Ld2 Sxd3 22.Txd3 Txc4 23.b3 Tc5 24.Txd4 Lf6 25.Td3 Tb8 26.h3 Lb2 27.De2 Tcb5 28.Td5 Le5 29.Dc4 c5 30.b4 cxb4 31.Txb5 Txb5 32.Dc6 h6 33.Dxa6

Shredder eliminates all threats and prepares the support for his own passed pawns.

33...Dd7 34.Tc1 b3 35.Dc8+ Dxc8 36.Txc8+ Kh7 37.Tc1 b2 38.Tb1 Tb3 39.Lc1 bxc1D+ 40.Txc1 Kg6 41.g3 f5 42.exf5+ Kxf5 43.Tc6 Ta3 44.Kg2 Ta2 45.Ta6 Ke4 46.Ta8 d5 47.Tc8 d4 48.Tc4 Txa5 49.Tb4 g5 50.Tc4 Ta1 51.Tb4 Ld6 52.Tb6 Kd5 53.Kf3 d3 54.Txd6+ Kxd6 55.Ke3 0–1

(42) Shredder - Rebel [D23]

WCCC99 Paderborn (3), 15.06.1999

1.d4 d5 2.c4 c6 3.Sf3 Sf6 4.Dc2 dxc4 5.Dxc4 Lf5 6.g3 e6 7.Lg2 Sbd7 8.Sc3 Le7 9.0–0 0–0 10.Te1 Se4 11.e3 Te8 12.Sd2 Sd6 13.De2 e5 14.d5 cxd5 15.Sxd5 Tc8 16.e4 Le6 17.Sxe7+ Dxe7 18.b3 Tc2 19.La3 Tec8 20.Tec1 Txc1+ 21.Txc1 Txc1+ 22.Lxc1 Dd8 23.La3 Db6 24.Lf1 Sc5 25.Lb2 f6 26.De3 Scxe4 27.Sxe4 Dxe3 28.Sxf6+ gxf6 29.fxe3 Se4 30.Le2 Kf7 31.Ld3 Ld5 32.g4 Kg6 33.h4 f5 34.Le2 Kf6 35.g5+ Ke6 36.Kh2 a5 37.Kg1 a4 38.bxa4 Lxa2 39.a5 Ld5 40.La3 Sc3 41.Lh5 Lc6 42.g6 hxg6 43.Lxg6 Sd5 44.h5 Kf6 45.Lc5 Sc3 46.Kf1 Lf3 47.Lb6 Lg4 48.Ld8+ Kg7 49.Lc7 Kf6 50.Kg2 Sd5 51.Ld8+ Kg7

An endgame with only few pieces left. Shredder sacrifices a pawn to activate its king. This is only very hard to calculate as it takes quite a while for white to get obvious compensation for the pawn. Additionally the opponent gets two connected passed pawns which will be evaluated much higher than the active king if you evaluate this too statically.

52.Kg3 Sxe3 53.Kh4 Sd5 54.Kg5 Lh3 55.h6+ Kg8 56.Le8 Sf4 57.Ld7 Lg4 58.Lc8 Kh7 59.Lc7 Sh3+ 60.Kf6 Sf2 61.Lxb7 Se4+ 62.Kxe5 Le2 63.a6 Lxa6 64.Lxa6 Kg6 65.h7 Kxh7 66.Kxf5 Sc5 67.Lc4 Sd7 68.Lb5 Sc5 69.Lb6 1–0

(106) Shredder - Ferret [A29]

WCCC99 Paderborn - Playoff, 19.06.1999

1.c4 e5 2.Sc3 Sf6 3.Sf3 Sc6 4.g3 d5 5.cxd5 Sxd5 6.Lg2 Sb6 7.0–0 Le7 8.d3 0–0 9.a4 a5 10.Le3 Ta6 11.Tc1 Lb4 12.Te1 f6 13.Ld2 Le6 14.Se4 Sd7 15.Lxb4 axb4 16.e3 Ld5 17.Sed2 De7 18.b3 Taa8 19.d4 e4 20.Sh4 f5 21.Lh3 g6 22.Tf1 De6 23.Sg2 g5 24.Dh5 De7 25.Se1 Dg7 26.De2 Sb6 27.Sc2 Le6 28.Lg2 Sa5 29.Sa1 Sd5 30.Tfe1 Sc3 31.Df1 c6 32.Tc2 Kh8 33.Sb1 Sxb3 34.Sxc3 bxc3 35.Txc3 Df7

I agree that Shredder has moved itself into a very bad position. But now he plays a very active move that leads to counterplay in compensation for the sacrificed pawn.

36.g4 fxg4 37.Sxb3 Lxb3 38.Lxe4 Txa4 39.Tc5 Le6 40.Tec1 h6 41.T1c2 Tfa8 42.Tb2 Lc4 43.Dc1 Le6 44.Df1 Lc4 45.Dc1 Ta1 46.Tb1 Txb1 47.Dxb1 Le6 48.Te5 Tf8 49.Db2 Df6 50.Ta5 Kg8 51.Ta7 Lc8 52.Ta8 De7 53.Lb1 Le6 54.Ta7 Tb8 55.Ld3 Dc7 56.Db1 Lf7 57.Le2 Kg7 58.Lxg4 Lg6 59.Db3 Lf7 60.Db4 Kh8 61.Lf5 Kg8 62.e4 Kg7 63.Db2 Kg8 64.Da3 Kg7 65.Da1 Kg8 66.Da4 Dd6 67.e5 Dd8 68.e6 Lh5 69.Dc4 Df6 70.e7+ Kg7 71.Dc5 Le8 72.Lg4 Df4 73.Lf3 Kf6 74.Le2 Ld7 75.Lh5 Le8 76.Lf3 h5 77.Le2 g4 78.Ld1 h4 79.Db4 Ld7 80.Ta3 Te8 81.Te3 Kg7 82.Le2 Df6 83.Ld3 Tb8 84.Te5 b5 85.Lf5 Lxf5 86.e8S+ Txe8 87.Txe8 Lg6 88.Te7+ Kg8 89.Td7 Le8 90.De7 Dg6 91.Tb7 Db1+ 92.Kg2 h3+ 93.Kg3 Dg1+ 94.Kf4 Dxf2+ 95.Kxg4 Dg2+ 96.Kh4 Df2+ 97.Kxh3 Df3+ 98.Kh4 Df4+ 99.Kh3 Df3+ 100.Kh4 Df4+ 101.Kh3 Df3+ ½–½

Because of Shredder's huge amount of built in knowledge, he likes to sacrifice pawns for active play or getting the initiative. Very often this leads to nice and active play, but I have to admit, that sometimes Shredder's positional advantage will fade away and that he is down a pawn for nothing after all. Luckily those cases are getting rarer and rarer but I take this into account because in general Shredder's play gets better and more active and also successful this way. In addition this is more like modern chess is played today. The old disease of computer chess, that computers are just counting material is no longer true, there are ways to cure this.

I have much more ideas about how to make progress in computer chess. Right now I am working on an automatic combination of two different chess programs. In theory the move of the program which understands the given position better should be chosen, as it is able to produce a stronger move then. The strengths of both programs are combined and their weaknesses are avoided. Soon we will see if this is another way to improve computer chess.

I know that many people watch the progress in computer chess with great concern, maybe even more after reading this article. They fear that this is another field where computers will be superior to mankind and chess will be meaningless after we have the first nonhuman world champion. I certainly don't agree with them since I am working to improve computer chess in the first line. Every chess player should see that there are also many advantages to have an electronic grandmaster at home. You have a chess partner or analyzing tool of any strength available at any time. Not very long ago it wasn't easy for an average chess player to get a solid analysis of a complicated position. I don't even want to start talking about all the advantages of electronic databases here.

In our daily life there are many electronic or mechanical things that do their job much better than any human can ever do. We got used to them and consider them as useful tools that make life easier. Beside of this we don't pay much attention to it. I am sure that everyone can name a few such things after only a short thought. Probably we first have to get used to it, if the time has come for computers to play better chess than all human, but after a while we will certainly get used to it and take advantage of it. If there is still somebody out there thinking that his will be just another step for computers on their way to rule mankind with intelligent robots, I have to tell him, that even after long thinking I can't think of anything in computer chess which can be transferred directly to our daily life.

In the last paragraph I have mentioned that one day computers will play stronger chess that any human. Well, I agree that you can argue about that and that there are many people around having a totally different opinion, but if you take a closer look at the development of the playing strength of both humans and computers in recent years, you have to admit, that computers have made without any doubt the much bigger step. If you also know that computer programs are getting better with a faster computer and that one cannot see the end of the development of computer hardware, you can only draw this one conclusion. But as I have mentioned earlier, one can argue about that. I am not saying that it will happen within two or three years, the exact time is very hard to predict, but I am sure that it will happen sooner or later.

I am not sure weather all of my theories stated in this article are true, but the success of my program Shredder at the computer world chess championships on inferior hardware gives some proof to this. I am not sure weather my way is the only way to go, but at least it seems that it is not completely wrong :-)

Chess Download Schach Download Schach Chess