Last October, I went to Thailand on a business trip and on a free day went to the Pattaya Crocodile Farm to watch the show. I took some pictures which wound up on the “Google photos” tab of my Google drive.
Now, do you want to know something cool? When I go to my Google drive and search for “crocodile” all those pictures I took that afternoon magically come up. I didn’t tag those pictures as crocodile photos — Google just knew they were.
This is a very basic application of what they call “Machine Learning,” that field of computer science that gives computers the ability to learn without being explicitly programmed. This is the intelligence that seems to have solved chess.
DeepMind, a British artificial intelligence company founded in September 2010 and acquired by Google in 2014 (its founder, Demis Hassabis, aside from being an artificial intelligence guru is also a strong chessplayer — he used to be the second highest rated player under-13, behind no less than Judit Polgar), developed a general program called AlphaZero. This program was fed the basic rules of Go, Chess and Shogi (Japanese Chess) and after a few hours of play against itself managed to teach itself to beat all the strongest human and silicon-based minds in their own game.
This is a complete game-changer. Until now all computer chess programs are specially created to play chess, nothing else. They all use opening books tuned to its strengths and have access to endgame tablebases to guide it during the final stages of the game with a small number of pieces left on the board. AlphaZero is a general program which was fed only the rules of chess — it developed its opening play, middlegame strategies and tactics and endgame technique through self-learning.
(Please pause here a bit and let that sink in.)
You know what is the worst part about this? When computers started beating the likes of Garry Kasparov (vs Deep Blue in 1997) and Vladimir Kramnik (vs Deep Frize 2006) we had the consolation of knowing that at least humans were the ones who taught these monsters how to play. Not so with AlphaZero and its self-learning. Let me explain this a bit.
In 1950 computer chess pioneer Claude Shannon wrote a paper which distinguished between “Type A” and “Type B” search strategies for playing computer chess. Type A search employed what is called a “brute-force” algorithm that searched all positions equally out to a horizon of computability. For example, if there are 30 moves possible in a given position Type A will analyze them all. Type B involves ignoring all moves but those determined to be good (called forward pruning), in other words thinking like a human being.
The 6th world chess champion Mikhail Botvinnik lost his title to Tigran Petrosian in 1963 and after an automatic rematch was not granted by the International Chess Federation (FIDE), he made no other attempt to regain the title. Instead he dedicated the remaining years of his life to developing a computer chess program and to assist in the training of young Soviet players.
Botvinnik was passionate about his computer chess program, even financing it with his own money as he hoped this would be a first step to developing a system to manage the Soviet economy. He was using the “Type B” method and, regrettably, was not able to make any significant headway.
On the other hand the Type A method became the dominant search strategy especially because of the exponential increases in computer power and resources. Then the developers used powerful heuristics (avoid doubled pawns, knight on the rim is dim, etc. etc.) gleaned from expert knowledge coded into modern systems from human players.
In 1956 John McCarthy invented the alpha-beta search algorithm, a method which strongly aided brute-force computers as it eliminated the need to search large portions of the game tree applying a branch-and-bound technique. If one already has found a quite good move and search for alternatives, one refutation is enough to avoid it. This way, the search time can be limited to the “more promising” subtree, and a deeper search can be performed at the same time. This is a gross 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.
AlphaZero — Stockfish 8 [E17]
AlphaZero vs. Stockfish (1.10), 04.12.2017
1.Nf3 Nf6 2.d4 e6 3.c4 b6 4.g3 Bb7 5.Bg2 Be7 6.0–0 0–0 7.d5!
The usual continuation here is 7.Nc3 Ne4. AlphaZero has shown a knack for pawn and even piece sacrifices for long-term 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.
7…exd5 8.Nh4!
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.
8…c6 9.cxd5 Nxd5
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.Nf5 Nc7
[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.
11.e4
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#.
11…d5 12.exd5 Nxd5 13.Nc3 Nxc3 <D>
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.
14.Qg4! g6 15.Nh6+ Kg7 16.bxc3 Bc8 17.Qf4 Qd6 18.Qa4 g5
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.Re1!! Kxh6
[19…Qxh6?? 20.Rxe7]
20.h4 f6 21.Be3
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.
21…Bf5 22.Rad1 Qa3
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.
23.Qc4 b5 24.hxg5+ fxg5 25.Qh4+ Kg6 26.Qh1!
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.
26…Kg7 27.Be4 Bg6 28.Bxg6 hxg6 29.Qh3 Bf6 30.Kg2 Qxa2 31.Rh1 Qg8 32.c4 Re8 33.Bd4 Bxd4 34.Rxd4 Rd8 35.Rxd8 Qxd8 36.Qe6
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+]
54…Kf6 55.Rc5 g5 56.Kd4 1–0
Really impressive stuff, right? Some people say that machine learning is over-hyped: “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.
Bobby Ang is a founding member of the National Chess Federation of the Philippines (NCFP) and its first Executive Director. A Certified Public Accountant (CPA), he taught accounting in the University of Santo Tomas (UST) for 25 years and is currently Chief Audit Executive of the Equicom Group of Companies.
