Chess is solved?
oversimplification of alpha-beta search algorithm but I am afraid it will have to do.
The DeepMind team wrote a paper on their AlphaZero project: https://arxiv.org/pdf/1712.01815.pdf It explains that AlphaZero uses the Type B search strategy described above. It uses its “deep neural network to focus much more selectively on the most promising variations.” And how does it figure out the “most promising variations?” Through self- play! Incredible.
The paper also reveals that AlphaZero played a match of 100 games against Stockfish 8. This is one of the top 3 chess programs in the world (the other two being Houdini and Komodo) and it was last year’s computer chess champion.
The result of the match was almost unbelievable: The total score was 64-36. AlphaZero won 25 games with White and three games with Black and drew the rest. They also published 10 of the games of that match. Let us look at two of them.
The usual continuation here is 7.Nc3 Ne4. AlphaZero has shown a knack for pawn and even piece sacrifices for longterm compensation. It makes a sacrifice — you don’t get it, but after several moves down the line you start to see why. I got this same feeling in the 1980s when Garry Kasparov was at his peak. In fact he used this line in the 1980 Olympiad to win a brilliancy vs Marjanovic. You should take a look at it — I give it in the notes to this game.
People used to play 8.Nd4 here, but Polugaevsky introduced Nh4 in the 12th game of his Candidates’ Semifinals match with Viktor Korchnoi and scored a big win. “Lev the Lion” deserves full credit for this novelty.
White’s attacking attempt does not look too serious, but Black can easily fall under. Here is a horror story: 9...cxd5 10.Nc3 Re8? (Would you believe that this is a mistake? Black should play 10...Na6! followed by ...Nc7 to bolster his pawn on d5) 11.Nf5 Bb4 (Here is the reason why Black’s rook should not be on e8, for if now 11...Na6 then 12.Bg5! Nc7 13.Bxf6 Bxf6 14.Nd6 attacking e8 and b7) 12.Bg5 Re5? 13.Nxd5! Bxd5 (13...Rxf5? 14.Nxf6+ gxf6 15.Bxb7 fxg5 16.Bxa8 now it is White who has the material advantage) 14.Bxd5 Nc6 15.e4 h6 16.Bf4 Re6 17.Rc1! Nxe4 18.Qg4! Bf8 19.Bxe4 1–0 Adly,A (2603)-Almedina Ortiz,E (2215) Egypt vs Puerto Rico Baku Olym AZE 2016. You see why Black resigned after 19.Bxe4 right? If 19...Rxe4 20.Nxh6+ Kh7 21.Nxf7 Qe7 22.Ng5+ Kg8 23.Qf5! all is lost.
[10...Bc5 11.e4 Ne7 12.Nxg7! Kxg7 is the Polugaevsky vs Korchnoi game I mentioned earlier. White won back the piece after 13.b4 Bxb4 14.Qd4+ f6 15.Qxb4 after which Black’s king was hopelessly exposed and White had all the open lines to get to it. “Viktor the Terrible” fought very hard but was unable to save the game. 1–0 (73) Polugaevsky,L (2635)-Kortschnoj,V (2695) Buenos Aires 1980.
Kasparov deviated here with 11.Nc3 d5 12.e4 Bf6 13.exd5! cxd5 14.Bf4 Nba6 15.Re1 Qd7?! (A mistake. Black should have played 15... Bc8) 16. Bh3 ( 16. Qg4 Bc8 17.Ne7+ Qxe7) 16...Kh8? played to avoid any discovered check, but now Black is crushed: 17.Ne4 Bxb2 18.Ng5 Qc6 19.Ne7 Qf6 20.Nxh7! Qd4 21.Qh5 g6 22.Qh4 Bxa1 23.Nf6+ 1–0 (23) Kasparov,G ( 2595)- Marjanovic, S ( 2505) URS vs YUG Malta Olym 1980 The finish will be 23.Nf6+ Kg7 24.Qh6+ Kxf6 25.Bg5#.
POSITION AFTER 13...NXC3
This position occurred in a game from the 2016 German Bundesliga between Norbert Schumacher and Sebastian Hanisch. White made the most obvious move on the board — he recaptured 14.bxc3 and there followed a back-and-forth battle which was drawn on the 50th move. There is no such thing as an automatic move for AlphaZero and here he sees a deadly attack.
Forces the knight back, and after 19.Ng4 f5 20.Ne3 b5 Black has survived the first wave. Nobody expected White’s next move.
[19...Qxh6?? 20.Rxe7]
White is not in a hurry at all. The point of this bishop move is simply to make way for his a1–rook to go to d1.
On a3 Black’s queen is cut-off from the action on the kingside, but the attack is coming anyway. If Black had retreated his queen then the offensive would have proceeded without delay 22...Qc7 23.Be4 Qc8 24.hxg5+ fxg5 25.Bf3 and the white queen switches back to the kingside.
This is really chess on a very high level. White’s threat is not 27.Bxc6, it is 27.Be4! h5 28.Bxf5+ Rxf5 29.Qe4 White is clearly winning.
The deadly threat is Qe5+ and the Black king will be mated soon.
36...Nd7 37.Rd1 Nc5 38.Rxd8 Nxe6 39. Rxa8 Kf6 40. cxb5 cxb5 41. Kf3 Nd4+ 42.Ke4 Nc6 43.Rc8 Ne7 44.Rb8 Nf5 45.g4 Nh6 46.f3 Nf7 47.Ra8 Nd6+ 48.Kd5 Nc4 49.Rxa7 Ne3+ 50.Ke4 Nc4 51.Ra6+ Kg7 52.Rc6 Kf7 53.Rc5 Ke6 54.Rxg5
[54.Rxb5?? Nd6+]
Really impressive stuff, right? Some people say that machine learning is overhyped: “effective machine learning is difficult because finding patterns is hard and often not enough training data is available; as a result, machine-learning programs often fail to deliver.”
It looks like we have reached the stage where the opposite is happening — advances are going so fast that it is already a bit scary.
Remember the story a few months ago about computers communicating with each other in Google? Well, they talk to each other in English but somewhere along the line they decided that English is inefficient and decided to create their own language. Pretty soon the Google developers couldn’t understand what the machines were saying to each other, so they panicked and shut everything down.
We are at that stage. Let us continue the discussion on Tuesday.