For years Rybka dominated the computer chess scene. For years, no other program was able to achieve a similar increase in playing strength. For chess analysis Rybka has long become one of the most important analysis tools of professions and amateurs alike. So that this state of affairs will continue in the future, the Rybka-team gathered around programmer Vasik Rajlich has developed a new version which is even better: “Rybka 4 plays more aggressively and more tactically”.
On March 31 the author of the Rybka program, Vasik Rajlich, and his family moved from Warsaw, Poland to a new appartment in Budapest, Hungary. The next day, in spite of the bustle of moving boxes and setting up phone and Internet connections Vas, kindly agreed to the following interview, which had been planned some months ago.
Frederic Friedel: Vas, people have not heard much from you for a while. We know that you were working on an interesting project, and you promised to reveal details in the second quarter of 2012. So now please tell us: what’s been going on?
Vasik Rajlich: Okay, here’s what we have been doing. You know that Lukas Cimiotti has set up a cluster of computers, currently around 300 cores, which has been used by World Champions and World Champion candidates to prepare for their matches. It is arguably the most powerful entity to play chess, ever, anywhere. Well, that was until we hooked it up to a massively parallel cluster of IBM POWER 7 Servers provided by David Slate, senior manager of IBM's Semantic Analysis and Integration department – 2,880 cores at 4.25 GHz, 16 terabytes of RAM, very similar to the hardware used by IBM's Watson in winning the TV show "Jeopardy". The IBM servers ran a port of the latest version of Rybka, and computation was split across the two clusters, with the Cimiotti cluster distributing the search to the IBM hardware.
FF: So now you had an absurdly powerful chess playing system. What does one do with it? Playing against humans would not be sensible, and even other computers would be simply killed by it.
VR: That was not the point, not my intention. I have been using it for purely analytical purposes, to try to solve certain openings.
What does “to solve” in this context mean? And how do you go about it.
We developed an algorithm which attempts to classify chess positions into wins, draws and losses. Using this algorithm, we have just finished classifying the King's Gambit. In other words, the King's Gambit is now solved.
Whoa, that’s quite a lot to digest. First of all what exactly do you mean when you say that the King’s Gambit is “solved”?
It’s solved in the sense that we know the outcome, just as we know the outcome for most five and six piece endings. Except that here we are dealing with a single starting position…
… which is?
1.e4 e5 2.f4 exf4. We now know the exact outcome of this position, assuming perfect play, of course. I know your next question, so I am going to pre-empt it: there is only one move that draws for White, and that is, somewhat surprisingly, 3.Be2. Every other move loses by force.
Rajlich uses three computers in his flat to control the Cimiotti cluster...
... (here with around 50 of 300) cores, which in turn distributes tasks to...
...the IBM POWER 7 with 2,880 cores...
Deep Rybka 4 Multiprocessor Version
For years now Rybka has dominated the computer chess scene. No other program has been able to achieve a similar increase in playing strength. For chess analysis Rybka has long become one of the most important analyis tools of professions and amateurs alike. So that this state of affairs will continue in the future, the Rybka-team gathered around programmer Vasik Rajlich has developed a new version which is even better: “Rybka 4 plays more aggressively and more tactically”.
How can you have worked that out, aren’t there gazillions of possible continuations?
Actually much more than “gazillions” — something in the order of 10^100, which is vastly more than the number of elementary particles in the universe. Obviously we could not go through all of them – nobody and nothing will ever be able to do that. But: you do not have to check every continuation. It’s similar to Alpha-Beta, which looks at a very small subset of possible moves but delivers a result that is identical to what you would get if you looked at every single move, down to the specified depth.
But Alpha-Beta reduces the search to about the square root of the total number of moves. The square root of 10^100, however…
Yes, I know. But think about it: you do not need to search every variation to mate. We only need to search a tiny fraction of the overall space. Whenever Rybka evaluates a position with a score of +/– 5.12 we don't need to search any further, we have our proof that in the continuation there is going to be a win or loss, and there is a forced mate somewhere deep down in the tree. We tested a random sampling of positions of varying levels of difficulty that were evaluated at above 5.12, and we never saw a solution fail. So it is safe to use this assumption generally in the search.
So this means that the result is not 100% certain, it is just a hypothesis.
That is technically correct, similar to the assertion that a position where one side is more than two pieces down, without any compensation, is considered lost, even if you cannot calculate it to a forced mate against any defence. Sure, there theoretically might be a way to save the game, but if Rybka is displaying +5.12 or more the outcome is 99.99999999% secure. That is approximately the confidence number we give to our King's Gambit results: 99.99999999%. It might be that there is a flaw somewhere, but if there is it will not be discovered in the course of this universe – that would require more computational power than could ever be provided. And of course it is possible, and in fact very, very likely, that there is no flaw.
How much processing time went into your project?
Approximately – well actually quite precisely – 10,750,000 hours of single-core CPU time. The King's Gambit run took a little over four months in total, elapsed time, to calculate.
That was on about 3000 cores, right? What was the system doing?
Our algorithm works in an iterative manner – it first forms a hypothesis, and then it confirms or alters that hypothesis over a number of passes using a non-deterministic Turing Machine program running across the clusters. Interesting things happen within the algorithm, such as strategy stealing, which is kind of like null-move where you calculate what happens when you pretend to be the other side. This is coupled with a number of other innovations including advanced zugzwang detection techniques which allow us to establish if a position is a forced win or not. The time needed for each pass varies greatly from position to position. The algorithm never fails and runs in quasi-polynomial rather than exponential time. If it doesn't produce an initial hypothesis for some position in a reasonable amount of time then we have to consider the position as unsolvable with current resources.
What specifically were the results you calculated for the King’s Gambit? And why did you choose this opening?
Well, there were a number of reasons for choosing it. One was that 50 years ago Bobby Fischer published a famous article, "A Bust to the King's Gambit", claiming to have done exactly that. I was curious to see how valid his conclusions were. Turns out they were amazingly accurate. The main line of the King's Gambit, 1.e4 e5 2.f4 exf4 3.Nf3, is indeed winning for Black. Moreover, the only winning move is 3... d6!, just as Fischer claimed. For instance the more popular 3...g5 allows White to draw after 4.h4! In fact, Fischer's main line holds up incredibly well: 3...d6! 4.Bc4 h6! 5.d4 g5! (an exclam denotes any move which gives a better theoretical result than every alternative), although some side-variations from his article do have inaccuracies.
Genius or luck?
Probably mostly luck. Naturally some of his lines are not accurate: they weave in and out of draws. But the main conclusion is correct.
So is the King's Gambit really busted?
No, just if White plays 3.Nf3. Incidentally 3.Bc4 loses as well to 3...Nf6! (incredibly every other move allows White to draw). But this is where the fun begins. It turns out that the weird looking 3.Be2! leads to a draw. In fact we found that 3.Be2! is the only move that avoids a white loss.
Very strange. Can you explain this?
That’s probably a task for a stronger chess player than I am. It's obvious that 3.Nf3 and 3.Bc4 both have some drawbacks which 3.Be2 avoids. The move isn't really a very consistent follow-up to 2.f4, but if we accept, in human terms, that 2.f4 is a mistake and try to make the best of it, then 3.Be2 looks more attractive.
Can the computer explain this in more concrete terms?
The computer's tree isn't especially insightful – it tells you what needs to be played in each position, but does not tell you why. “Because it is in my database of positions” is not an answer a human player is seeking. But you can try out lines to your heart’s content: after 3.Be2, Black has 30 legal replies, and 27 of them lead to a draw. This includes nonsensical moves like 3...h5 and 3...f6. After the most common move, 3...d5, White must play the obvious 4.exd5!, after which Black has 36 legal moves, 29 of which draw, again including nonsensical moves like 4...h5 and so on.
Are there other interesting things in this opening – general conclusions that humans can comprehend?
We've found quite a few hotly debated positions which are in fact winning for one side. Black tends to blunder first far more often than White (in the theoretical sense), and this trend seems to be far stronger in some opening variations than in others. You could say that top players are often irrational in constructing their opening repertoires for Black.
What will human chess players eventually learn from all this?
We'll get a better sense of where the line lies between a theoretical draw and a theoretical win, but this probably isn't that important to a practical player. We'll also probably learn some new principles for practical play. Finally, we'll get some interesting perspectives on the opening debates which the chess elite have conducted over the past decade or so.
Will this take all of the creativity and flexibility out of opening play?
Quite the opposite. I think players will see that many surprising moves are playable, giving them more options to choose from. For example, take the game Topalov-Kramnik from Wijk aan Zee 2008. The genius of Topalov's preparation wasn't that 12.Nxf7 is some sort of great move. It was simply realizing that 12.Nxf7 is playable and doesn't lose by force. Once you establish that, it's not that hard to work out a way to put a ton of pressure on your opponent.
ChessBase CEO Matthias Wüllenweber in Hamburg with Vas and Iweta Rajlich
Will chess professionals, and chess amateurs for that matter, have access to the King’s Gambit “tablebases”, if I may call it that?
There is a problem of size that makes it simply impractical to keep it locally on your computer. However we will make it available online, in the near future, so that everyone can find out which moves win, lose or draw – in practical trial-and-error sessions.
What opening variation do you plan on calculating next? Or was this a one-time shot?
No, of course we are thinking of other openings, and who knows, at some stage we could theoretically cover all the main opening systems. We started with the King’s Gambit because we needed an opening which our algorithm could handle with a reasonable investment of CPU time. It might be a little bit counterintuitive, but sharper positions are actually easier to classify than quiet ones. We ran various experiments on many openings, and the King's Gambit seemed to be one of the easier variations to classify. Second, we wanted a variation which would interest casual chess fans. The King's Gambit has a long and colourful history, and you don't need a deep knowledge of modern opening theory to appreciate its relevance.
Okay, cough it up: what next?
I say this with some apprehension, but we've been looking at the 6.Bg5 Najdorf (10.e5! looks promising as a forced win for White). But if we decide to do the full classification we are going to need much faster hardware. Maybe a factor of a thousand over what we used for the King’s Gambit. There are companies that periodically test that kind of hardware for new server parks, and run very CPU-intensive applications on them to locate faulty processors. We have made contact with the technical director of the Google server farms, who was definitely interested. So maybe in a year or two we will have solved the Najdorf.
Great – and maybe a bit frightening. Thanks for this fascinating insight into your work.
Vasik Rajlich was born 1971 in Cleveland, Ohio, to Czech parents. He grew up in Prague and is a dual Czech-American citizen. He is an International Master in chess and the author of Rybka, one of the strongest chess playing programs in the world. Rajlich married Iweta (née Radziewicz) in 2006. They have one son. Iweta, who is also an International Master, helps him with the development of his chess software as its tester. The couple presently live in Budapest, Hungary.
Order Rybka 4 now in the ChessBase Shop
