This is a memoir of Kasparov’s interactions with computer chess programs, culminating most famously with his two battles with IBM’s Deep Blue. In relating the tale, however, Kasparov also covers the history of the decades long effort to make an adequate chess playing computer program in general, as well as the history of artificial intelligence more broadly. For chess fans to hear the thoughts and recollections of one of history’s greatest players is invaluable and utterly enjoyable. Kasparov sprinkles insights and tips throughout the way. He points out that computer chess programs, from their inception, have played a distinctly “computer-style” of the game. That is not a bad thing, necessarily. “We confuse performance- the ability of a machine to replicate or surpass the results of a human- with method, how those results are achieved…. Machines don’t need to do things the same way the natural world does in order to be useful, or to surpass nature.” Chess computers eventually became successful not by trying to replicate the human mind, but through brute strength and blazing speed. One breakthrough was “the “minimax” algorithm, which originated in game theory and has been applied to logical decision making in many fields. Very simply put, a minimax system evaluates possibilities and sorts them from best to worst.” It evaluates every single possible move anew with each turn and ranks them in order. A huge advance then came with “the “alpha-beta” algorithm [that] allowed the programs to rapidly prune out weak moves and thus to see further ahead, faster.” All modern chess programs use alpha-beta pruning, combined with minimax concepts. Humans play chess very differently. “Outside of the opening sequences that are indeed memorized, strong human players don’t rely on recall as much as on a super-fast analogy engine…. Disregarding forced moves, each position will have three or four plausible moves, sometimes as many as ten or so. Again, before any real search begins in my mind, I have selected several to analyze more deeply, what we call candidate moves.” A machine does none of this pre-sorting. It looks at every single possible move and chooses the best one through the brute force of its algorithm. “The total number of legal positions in a game of chess are comparable to the number of atoms in our solar system.” Chess programs are very good at tactics based on the inputs of the value of pieces. “The basic set of values was established two centuries ago: pawns are worth one; knights and bishops are worth three; rooks are worth five; the queen is worth nine…. One trick is to assign the king a value of one million so the program knows not to put it in danger.” Computers are not good at deeper strategy beyond that. They cannot create plans because they reevaluate the board fresh with every move. “After the material value of the pieces and pawns, you have more abstract knowledge such as which player controls more space on the board, the structure of the pawns, and king safety…. Computers are very good as chess calculation, which is the part humans have the most trouble with. Computers are poor at recognizing patterns and making analogical evaluations, a human strength…. Computers are very good at sharp tactics in complex positions while that is a human’s greatest weakness. Humans are very good at planning and what we call “positional play,” the strategic and structural considerations and quiet maneuvering.” Kasparov would first beat Deep Blue, only to lose the more remembered rematch in 1997, the first time a computer had beaten a current world champion in match play. It was also the first chess match Kasparov had lost playing with standard rules to anyone. In creating Deep Blue, however, IBM had created a machine specifically designed to play chess (and some would say specifically to beat Gary Kasparov). It had inputed every single game he had ever played, every opening, every defense, and then recruited the world’s best current grand masters to input their best countermeasures to all of Kasparov’s favorite plays. They had inputed every “opening book” move for beyond fifteen moves for all of the known chess game beginnings in the history of chess. Then they had worked backwards from mate to create inputs that memorized end of game scenarios for up to six pieces on the board. Computers were already considered superior to humans in the so-called middle game and so IBM has sought to fix its most glaring weaknesses through sheer memory. Deep Blue was not a thinking machine, but an extremely impressive databank of all of the greatest games and individual moves in the history of chess. In the end, chess programs were of relatively little use to furthering the development of AI. It is not clear what, if any, intelligence they actually exhibited. It would take the deep learning methods of AlphaGo to stretch the boundaries of machine thought. The key was the explosion of data, along with exponential processing speed improvements. “Instead of telling it a process, you provide it with lots of examples of that process and let the machine figure out the rules, so to speak…. Errors are reduced by quantity leading to quality, keeping the good examples and discarding the bad a billion times per second…. It uses machine learning and neural networks to teach itself how to play better, as well as other sophisticated techniques beyond the usual alpha-beta search. Deep Blue was the end; AlphaGo is a beginning.”
No comments:
Post a Comment