Computers, Chess, and A.I.

by Albert Frank

More than sixty years ago chess began to be programmed into computers, with the help of Engineer Michael Botvinnik who was World chess champion. Around 1985, some computer programs reached a master level. Among the specialists in this field was American Grand Master Hans Berliner, World chess champion by correspondence.

Slowly, the question arose: Will a computer ever be better than any human being?

Of course a computer is incredibly fast. Nevertheless, the number of possibilities in chess is huge, much greater than any computer could possibly manage for long terms planning. Assume we have 20 "half-move" (a move for one player) possibilities. For 10 moves, there are 20^20 possibilities! So the computer specialists had to cut some parts of this tree of possibilities, and often they cut the best branch -- either a winning branch or an excellent defensive branch. So an optimal compromise had to be found. Every year computer entries became stronger and stronger, and the question changed into, "WHEN will a computer be better than any human being?"

In 1997, the IBM program Deep Blue won a match against World champion Garry Kasparov. There was a "problem" however: The quality of the games in that match was incredibly low"¦ so the top chess players don't consider this match very interesting…

Up to about 2001, several GMs (chess Grand Masters) specialized in beating computers. They were not playing very good chess, they were playing against the weakness they had found in the programs.

Then everything changed. Several top programs where "learning": If they had a difficult position in a game, their approach to similar positions in subsequent games changed (exactly like a human's would). I would say this is a form of artificial intelligence (AI). I remember that twice I gave some difficulties (I mean by this that I had a normal human type chess interaction) playing against the computer "Fritz 6" using a very rare opening, the Feustel System. However, when I tried a third time, I was completely and quickly destroyed. And at a much higher level, the "anti computer specialists" had more and more difficulty.

The question finally had a definitive answer on June 27^th 2005: After a match of six long games between the huge computer Hydra (500 kilograms!) and the top player (number 5 in the World) British GM Michael Adams, the score was 5.5 / 6 for the computer. The computer made new plans, some requiring a "forecast" of more than 20 moves, with nothing forced. Certainly there was something other than mere calculation, something not so far from what some would call "human intuition". I followed all the games on the Internet, move by move. I had a strange feeling, for I had written in several articles, "Chess is an art!" (Sadly, to experience this about two years of practice are needed.) And my feeling now was that Michael was playing against a great artist, not just against a machine.

Hydra's score against top human players is about 80% (Hydra never lost a game against a human). Hydra's website: http://www.hydrachess.com/

That was a year and a half ago. Now, a few other programs are nearly as strong as hydra, and can be bought for as little as $50. Their "brain" requires less than 4 megabytes of memory! This means that if you know how to use it (and the settings are important), you have the world champion on your own "normal" computer.

From November 25th to December 5^th 2006, World champion Vladimir Kramnik played in Bonn (Germany) a six game match against the computer Fritz 10 (in strength, about 3rd in the World, after Hydra and Rybka). The Computer won by the score 4 — 2. (The computer won two games, four where drawn).

Several things need to be said:

• All the games were of a very high level, on both sides.
• When the computer was using its memory (millions of games and positions), GM Kramnik could see the same screen -- an excellent idea by the organizers.
• There was commentary on the games by several top experts, including Garry Kasparov (who has retired from playing chess) and American GM Yasser Seirawan.
• Except in the last game, there was absolutely no domination by the computer. When Kramnik got a very small advantage, the computer defended extremely well.
• In games 1 and 2, Kramnik could have forced victory (this was identified very quickly, during the games, by the two commentators). Of course, it was extremely complicated, and it's emotionally very difficult for a human to play against such a machine.
• Something incredible happened (for this level, although it sometimes happens just because humans are humans): In game two, Kramnik lost (from a position in which neither had an advantage), because he did not see, after 5 minutes of thinking about his move that he could have had a mate in ONE move.

Here is game six, of which nothing else can be said than that "Fritz found new ideas and played like a great artist!"

Deep Fritz 10 — Vladimir Kramnik Bonn, December 5^th 2006

1.e4 c5 2.Nf3 d6 3.d4 cxd4 4.Nxd4 Nf6 5.Nc3 a6 6.Bc4 e6 7.0-0 Be7 8.Bb3 Qc7 9.Re1 Nc6

Nothing new: We have the following position, which has occurred a lot of times at any level of strength, with the following continuations: 10. Bg5 or Be3 or Nxc6 or Qd3 or a3 or f4:

And here, Fritz had a new idea: 10.Re3. This move looks like a beginner move — what's that? The commentators (GM!) first reaction was to laugh, "How is that possible; it's not deep; nothing can come out this move…"

Here is how it appeared in the playing hall in Bonn:

10…0-0 11.Rg3 Kh8 12.Nxc6 bxc6 13.Qe2 a5 14.Bg5 Ba6 15.Qf3 Rab8 16.Re1 c5 17.Bf4 Qb7 18.Bc1.

The dancing white bishop move c1 — g5 — f4 — c1 (with Re1 inserted) is like surrealistic art. 18…Ng8 19.Nb1. Another "fascinating symmetry": Both knights go back home. But Kramniks 18…Ng8 has a deep goal: defence and stabilization of the king side, preparing an attack on the queen side. The commentators had the impression that black's position was better. The computer's answer 19. Nb1 is incredibly deep: It prepares a perfect defence of the queen side and also prepares a fatal attack on the king side. The commentators started to realize that "the computer was not so mad"! 19…Bf6 20.c3 g6. 21.Na3! This was not foreseen by the GMs. Deep Fritz is still playing moves that are very hard to understand for humans. 21…Qc6 22.Rh3 Bg7 23.Qg3 a4 Is this move "good" or "bad"? Very long analyses are required before giving an answer. 24.Bc2 Rb6? This move is not very good — but black's position is already so difficult to defend (if it is even possible):

Now the killing calculation power of the computer becomes efficient: 25.e5! (An exchange sacrifice leading to the winning of a full pawn) dxe5 26.Rxe5 Nf6 27.Qh4 Qb7 28.Re1 h5 29.Rf3 Nh7 30.Qxa4 Qc6. White is now a pawn up without compensation — nothing to do at this level. 31.Qxc6 Rxc6 32.Ba4 Rb6 33.b3 Kg8 34.c4 Rd8 35.Nb5 Bb7 36.Rfe3 Bh6 37.Re5 Bxc1 38.Rxc1 Rc6 39.Nc3 Rc7 40.Bb5 Nf8 41.Na4 Rdc8 42.Rd1 Kg7 43.Rd6 f6 44.Re2 e5 45.Red2 g5 46.Nb6 Rb8 47.a4 1-0 There is nothing to do, black can't move any more.

The final position:

A great game! And, without knowing who or what is playing, anyone would think it's a top class game played between two humans. Isn't that (at least a little) what we can call A.I.?