The history of chess AI

Nowadays, in 100 matches, the reigning world chess champion Magnus Carlsen would not score a single victory against the world's best chess program. Carlsen currently has an Elo rating of 2845 (February 2019), while Stockfish 9 has a rating of 3438 (the engine ratings are not FIDE ratings, but the player pool for engines is much stronger than for humans, so theoretically an FIDE rating for Stockfish 9 would be even higher). In chess, if two players are separated by 600 Elo points or more, then a comparison between the two resembles a comparison of Portland Pickles and Red Sox, Justin Bieber and Bob Dylan, Windows Phone and literally any other phone. It's obvious who the boss is.

As a chess player, I asked myself how chess programs could become this powerful and what the milestones of chess AI were. What had to happen before Kasparov was defeated? Also, how stressful is it to write a chess program today?

Teaching an AI the basics of chess

At the beginning of every conception of a chess program lie the basics of chess: first and foremost the information on how each piece can move, how castling works, and how to set the king in checkmate. Special moves, such as en passant and promotion, and the basic value of all pieces must not be forgotten. If, while reading, you feel like writing a simple chess program yourself, I recommend Lauri Hartikka’s tutorial A step-by-step guide to building a simple chess AI. Just like Lauri, I’d advise using the chess.js library for move generation and chessboard.js for visualizing the board.

When Kasparov realized that Deep Blue had played better chess than him, he declared:

Obviously, that statement was complete nonsense. The very first concepts of a chess programs, however, actually resembled relatively easy-to-understand machines.

Alan Turing began around 1946 with the first investigations into a chess computer, but limited his concept only to handwritten records, which were further developed by Claude Shannon. Turing's conception was based on the following principles:

• Each piece had a certain value: pawn = 1; knight = 3; bishop = 3.5; rook = 5; queen = 10 and king = 1000 (simply so that a king's sacrifice does not represent a mathematical option). With his assessment of the strengths of knight and bishop, Turin was interestingly close to Bobby Fischer (who estimated 3 and 3.25) as well as to the evaluations of thousands of chess program matches that confirm the bishop as more valuable than the knight.
• All white moves and all black counter moves were examined. If white could make one move, then all the opponent's moves and all subsequent white moves were examined until the position was “dead” (until there were no more moves to play).
• In the resulting positions, a figure count was performed and the move that won the most material was selected. However, since, especially in the opening phase, most of the moves available for selection produced the same result, Turing also introduced some positional evaluation criteria.

In 1951, the University of Manchester developed a program for the Ferranti Mark 1 computer that solved predefined problems in 15 minutes. The program is regarded as the first solving program in chess history.

John von Neumann classified chess in his game theory as a two-person zero-sum game with complete information. This class of problems can be solved with the Minimax algorithm. However, chess is too complex to work through the search tree completely. There are more moves in a game of chess than there are grains of sand on all the beaches in the world (it is a popular assumption that the number of all possible chess games exceeds the number of atoms in the visible universe; but it is not that simple).

John von Neumann's chess program was completed in the mid-1950s and ran on the MANIAC I tube computer. For simplification, however, only a 6x6 (instead of 8x8) board was used. The program played a total of three games and won one of them, against a young woman who had only been playing chess for one week and had trained especially for this game. That was progress for that time. 

The problem was not a lack of conception, but a lack of computer power and at the same time a need for larger databases. The average programmer of today also faces this problem when trying to write their own chess program. Even after considering all the basics of chess, one will notice that the moves of a simple chess AI suck in conspicuous intensity.

Every game ever played

Former world champion Mikhail Tal once wrote:

If you create a chess program, you might want to check your math. However, human experience, creativity and intuition from previous games were indeed the key factors in taking chess programs to the next level.

Imagine a single chess program has a huge library of all the games ever played in chess history.

Yeah, that was just not possible in the 1960s.

But now think a bit smaller and imagine a chess program that doesn’t need to play every game from scratch, but can handle the 20 most played openings and, with the knowledge from more than 1000 GM games, knows exactly how they went until the 5th move. Such an opening library would make an early chess program much stronger in calculating “good moves”.

The first program to participate in human tournaments was Mac Hack (no, it wasn't an Apple product), developed by Richard Greenblatt from 1965 to 1967. And it was the first program to defeat a (comparatively intelligent) human. This eternal honor went to the American philosopher Hubert Dreyfus, who was checkmated by Mac Hack in the 37th move in 1967. Here are the moves of this game:

You can see from the moves that Dreyfus (playing white) wasn't a very talented chess player, but when you're a chess engine in the 60s, you take whatever you get. 

In 1979 Ken Thompson developed the famous chess machine Belle, which worked with an opening library and a hash map. That was a pretty big deal. Belle was a hard-wired machine; it could generate up to 180,000 positions per second and reached a search depth of up to nine and a half moves. Belle dominated the computer chess scene until 1983, when it was awarded the title of National Champion by the US Chess Federation. This was the first award of this kind for a chess computer.

Belle was, as long as the computational power was able to keep up, expandable by increasingly detailed opening libraries. And nothing better came after Belle for a long time.

Then a computer science genius (Crazy Bird) entered the stage to make the chess genius (Kasparov) weep.

In school Feng-hsiung Hsu got the nickname Crazy Bird because his classmates thought he was weird and eccentric. In 1989, he joined the IBM team and researched parallel computing with Murray Campbell. From this work, the new chess supercomputer Deep Blue came into being (the naming is explained as a homage to IBM, whose company color is blue). With Deep Blue, Crazy Bird and his team succeeded in winning the historic match against the world chess champion in 1997.

It’s all over

The last game in the 1997 match, game 6, had only 19 moves and became chess legend. It looked liked this:

Deep Blue played white and Kasparov tried the Caro-Kann Defence. So Deep Blue answered with a knight sacrifice and that was the end of the game. Kasparov told chess reporters that he chose to play a dubious opening, trying to put Deep Blue out of its comfort zone. Although the knight sacrifice is a good refutation, he thought that Deep Blue wouldn't play the move without a concrete gain. Kasparov didn’t know that on the very same day, the Deep Blue creators had added the variation to the opening library. That’s what happens when you try to fool Crazy Bird.

After Deep Blue, chess programs became rapidly stronger and every chess engine I can load onto my phone today would be at least an equal opponent for every chess grandmaster. And advanced chess engines on my laptop play a game that GMs and world champions might just understand but can never defeat.

After 2015 there was something of a retro hype, a return to the game without opening libraries and databases. And this time the idea worked because the computing power was no longer comparable to that of the 50s and early 60s.

AlphaZero, for example, is a self-taught computer program by DeepMind, whose algorithm can learn the game of chess only on the basis of the game rules and victory conditions as well as through intensive playing against itself. Since 2016 it has been known that AlphaZero is extremely strong in the self-learning process without any opening libraries; this image solidified in December 2018.

An updated version of AlphaZero scored 155 wins against Stockfish 8, with only 6 defeats and 839 draws. AlphaZero even defeated Stockfish 9 with almost the same results as the match against its predecessor. According to DeepMind, the self-learning machine also won a comparison against “a version of Stockfish that uses a strong opening file”. The opening library seemed to have helped Stockfish, as it won a considerable number of white games, but not enough to win the whole duel.

And now for the most amazing thing: In 2016, prior to the first games against Stockfish 8, AlphaZero trained only 4 hours with itself to build up its impressive skills. And with every game, its play became more superior.

In his defense, it must be concluded that Kasparov has now become an admirer of artificial intelligence, inside and outside the chessboard. And he has become more realistic and calmer, by Kasparov's standards. As for the game, it is chess engines that play the ultimate moves; at best, we humans may learn something by watching them. Sad. Or to put it in the words of my favorite GM, the legendary Ben Finegold:

If you enjoyed this, then look forward to new articles about AI, Deep Learning and IoT on our blog soon.