Twenty years ago, IBM impressed the world with its specialized chess-playing system that won the match against the best chess player of all times, Garry Kasparov. Last year, Google repeated the same achievement with its Go-winning solutions AlphaGo, AlphaGo Zero and most recently AlphaZero. How did this evolution happen and what are the key success factors of these remarkable events in the history of AI ?
Deep Blue
First, a little bit of history and background theory. The history of chess-playing AI solution goes back to 1957 when IBM research scientist Alex Bernstein wrote the first complete chess-playing program and ran it on IBM 704. But it was only 40 years later, in 1997 that computer-based solution reached such a level to surpass the best human performance. AI-based solutions for game-playing haven’t changed a lot during this period. The best practice was the use of opening books for the first dozen moves, and then use of Minimax algorithm for the search. Chess has up to 35 different moves, and can go to 50 moves deep, which makes it computationally impossible for any computer to identify all possibilities until the end of the game (35^50 is higher than the number of atoms in the universe). Due to the wide search, even nowadays this algorithm would go to the depth of maximum 10 levels within the allotted time for the move decision. Alpha-Beta pruning was developed to discard those subtrees that don’t contribute to the evaluation of the best moves for the Minimax algorithm. This helped to reach deeper levels (up to 18 levels from the current position). Once this depth is reached, an evaluation function must be defined to assess the strength of achieved positions and to grade the selected moves. Evaluation functions are very complex, and this is were humans typically excel. Garry Kasparov had for example extraordinary sophisticated evaluation capabilities, better than any other player. Continue reading “From Deep Blue to AlphaZero”
