| Man versus Machine |
| Saturday, 01 October 2005 | |
|
Anand Kulkarni and Swanand Gore puzzle out computer chess Britain’s highest ever ranked chess player, Michael Adams, recently suffered an overwhelming defeat by Hydra, the world’s most powerful computer. With this the most recent in a string of computerized triumphs, the chess world is gradually accepting that machines have essentially ‘solved’ the game. Until now, tasks like playing chess required human intelligence, an attribute that has taken millennia to emerge through countless cycles of evolution. In stark contrast, machines designed by us reached their current state within just two human life spans. Does the triumph of machine over man on the chessboard imply that machine intelligence has surpassed human intelligence? Could the successful replication of human intelligence in machines jeopardize our existence on Earth?
What sort of black magic drives these computers? Major reasons for their triumph are both computational and technological. Computer chess programs view a chess game as a tree, with board positions as nodes and moves as branches. The root of the game tree is the starting position and the game tree branches out into nodes,each of which corresponds to a possible move.At the start of the game, the tree can branch out in 20 ways because white can play her first move in 20 different ways (two knight moves and 16 pawn moves). Black can then make a counter-move in 20 ways, leading to a massive 400 combinations for the first round alone. It is easy to imagine the exponential explosion of possibilities as the game proceeds: within 10 moves the number of possible outcomes surpasses the number of atoms in the universe. It is quixotic to take a brute force approach to search the entire game tree for the next best move. This is where theoretical analysis paves the way by cutting down on search space. The basic idea is to avoid unpromising paths in the tree, a process for which search algorithms are critical. Experts have devised some approximate ways to assess the relative merits of moves quantitatively. A simple heuristic is to assign points to pieces, for example, 1 to pawn, 3 to knight, 3 to bishop, 5 to rook, 9 to queen and 200 to king. One can also give a greater weight to centralized pieces, the pawn structure or the phase of the game. The ‘Minimax’ search algorithm makes use of such heuristics and works on the assumption that each contestant plays so as to minimise the possible damage caused by the opponent’s following move.This approach is depicted in Figure 1. Over a span of more than 40 years, various improved algorithms have been devised. These have allowed computers with the same basic speed to play significantly better chess. One such algorithm, the ‘Alpha-beta pruning’ technique reduces the number of terminal evaluations by pruning out parts of the search tree that are so good for one player that the opponent will never allow them to be reached. Along with sophisticated search algorithms and heuristics, hardware development has also had a major role in the remarkable performance of chess-playing computers. Moore’s law states that the number of transistors on an integrated circuit (a rough measure of computer processing power) doubles every 18 months. As processors get cheaper and faster with every generation, it has become possible to harness many of them together to vastly improve overall performance. Chess is also a problem that is easily parallelized. This means that we can give each of several computers a branch of the game tree to evaluate and then check which processor has found the best solution.Versions of the Alpha-beta pruning algorithm for parallel systems were developed throughout the 1980s and by the end of the decade the use of multiple processors within a single program was commonplace.
Recently, an alternative to ASIC that avoids these problems has emerged. Reconfigurable computing allows hardware circuits to be onfigured to suit the particular tasks at hand. Reconfigurable systems make use of Field Programmable Gate Arrays (FPGA), semiconductor devices that process digital information and can be reprogrammed after manufacture without slowing performance. This latest hardware technology forms Hydra’s basic building block. Hydra is a cluster of 32 processors assisted by the same number of FPGA chess cards. It has a processing power of 100 billion calculations — or 200 million chess moves — per second with this configuration and can project the game up to 40 moves ahead. What are the implications of this significant chess achievement for other areas of AI? The public is often intrigued by the idea that intelligent machines could supersede us as the dominant life form on Earth. The triumph of machines over humans on the chessboard tends to be misconstrued as a step towards this idea becoming a reality. Despite the popular impression that Hydra and Deep Blue are masterpieces of AI, they are in fact no more capable of thought than a toaster. Intelligence is much more than just calculating power and should not be confused with computing speed. Hydra and Deep Blue are examples of ‘expert systems’, computers with large and powerful databases that enable them to perform narrowly defined tasks extremely well. The insights gained from designing such machines might tell us how to solve tedious problems quickly with the latest hardware technology, but hardly address large-scale issues in robotics and AI.These challenging problems include replicating a wide spectrum of human intelligence in a machine: knowledge, cognition and learning from experience. Learning is an essential component of intelligence. Many AI researchers have been trying to make chess machines intelligent by including human-like learning processes in their programs, but there has been no great success to date.At present,the way we develop a computer chess machine is by trying to duplicate the knowledge and inference methods of human grandmasters.We have little idea of how to devise a system capable of learning in this way and also of inventing completely new games and negotiating their rules.This is because humanity has yet to unravel the mysteries of the brain. It is hoped that within the next 30 years,we will have a better understanding of how the human brain works, which will give us ‘templates of intelligence’ for developing stronger AI. Herbert Simon and John McCarthy, who are among the co-founders of AI, have both referred to chess as the Drosophila of AI: it is a simple model, a testbed. Hence, it may seem rash to expect fully intelligent machines within a few decades, when computers have barely matched the aptitude of an insect in a half-century of development. Instead, many long-time AI researchers suggest that a few centuries may be a more believable period.We have waited millions of years for the evolution of natural intelligence; we may have to wait centuries for its artificial equivalent. Until then at least, human intelligence rules. http://chess.about.com/od/computerchess Anand Kulkarni is a PhD student in the Institute for Manufacturing. Swanand Gore is a PhD student in the Department of Biochemistry |
Since the emergence of artificial intelligence (AI) in the 1950s, researchers have often used chess as an experimental model. In the early days of computer chess, Claude Shannon, the computer science pioneer, proposed two strategies for designing chess programs.The first is called the ‘brute force’ strategy. In computer science language, brute force refers to trying every possible solution until the best one is found. It does not rely on human-like intelligence but exploits the computer’s ability to examine every possible outcome. A second and much more complicated strategy tries to mimic the learning process of human chess grandmasters using sophisticated programming languages. To date, computer programmers have adopted a brute force approach to play to the strengths (calculating) rather than the shortcomings (learning) of the machine. Today’s computers, Hydra included, lack any real capacity to learn; it is the team of programmers that learns from Hydra’s bad experiences and fine-tunes the chess programs so as to overcome the computer’s weaknesses. In the early days, the brute force approach was of limited value, since the marginal processing power of contemporary computers made investigating every possible solution impractical. More recently, however, the many-fold increase in computing power has allowed the brute force search to become a viable strategy. As a result, the 1980s saw machines taking on the best players and sometimes sharing the honours. In 1997, the computer Deep Blue made history by beating Garry Kasparov, the most successful player in chess history. Although human players fought on bravely, managing a few drawn encounters with machines such as Deep Blue and Deep Fritz, it was clear that the computer’s brute force was dominating over human intelligence; a fact which Hydra finally demonstrated by crushing Adams whilst running at only half of its design capacity. 
Another consequence of the declining cost of hardware is the ability to develop dedicated chess hardware. In 1980, Carnegie Mellon University in the US began developing specialized chips for implementing the Minimax algorithm exclusively for chess moves. Based on this special hardware, their 1988 chess machine HiTech was able to analyse up to one million board positions per second. The version of Deep Blue that defeated Gary Kasparov in 1997 had 256 special purpose chess processors working in parallel, analysing 200 million board positions per second.This hardware, Application Specific Integrated Circuit (ASIC), accelerates specific calculations needed for the Minimax algorithm using dedicated circuits to carry out a particular set of tasks. ASIC can implement a specific algorithm at least 100 times faster than programming the same algorithm in conventional software on a general-purpose computer.ASIC machines are efficient both in performance and power consumption, but lack flexibility in their dedicated hardware circuits, and so perform at a slower rate when the search algorithm is altered or when new chess knowledge is added. | < Prev | Next > |
|---|
News Archives
| News Archives |
