When the world champion Garry Kasparov was defeated in 1997 by a Chess playing computer developed by IBM called Deep Blue, it was clear that computers had finally dominated the game of Chess. Millions of people around the world watched and wondered if computers were really getting to be as intelligent as humans.
Garry Kasparov struggles against Deep Blue |
To someone who is not familiar with how computers play Chess, such a victory may give the impression that computers can now think and plan better than the best humans. But have computers really caught up to the intelligence level of humans? Do they now have real intelligence?
In an attempt to show that computers are not even close to matching the kind of real intelligence used by humans in playing strategy games, we have created a new game called Arimaa. Here is a simple game that can be played using the same board and pieces provided in a standard Chess set. However the rules of the game are a bit different and suddenly the computers are left way behind. For humans the rules of Arimaa are very easy to understand and more intuitive than Chess, but to a computer the game is a thousand times more complex. To the best of our knowledge Arimaa is the first game that was designed intentionally to be difficult for computers to play.
When playing strategy games such as Chess, humans use their problem solving capability, experience and intuition to pick what in their judgment is the best move for the current situation. The computer however is actually trying out all the move combinations on an internal board to look ahead as far as possible so that it can pick the move which leads to the most favorable positions. This brute force approach of examining each move as deep as possible is quite different than the way humans play Chess or any other strategy game. The advances in computer hardware have allowed computers to look deeper and deeper to the point where specially designed hardware can now defeat the best human Chess player. Also the accumulation of Chess knowledge in the form of databases for openings and end games have significantly contributed to improving the performance of Chess programs.
We estimate that even with the current rate of advance in computer hardware a system which uses only the look ahead approach will not be able to defeat the best human Arimaa player until at least the year 2020. However, it is possible that advances in the field of Artificial Intelligence that allow computers to more closely match the approach used by humans can reduce this time significantly.
Arimaa was designed so that it could be played with a standard chess set and would not require any special equipment. However the rules of the game are not at all like those of Chess. The rules of Arimaa were chosen to be as simple and intuitive as possible while at the same time making the game interesting to play and yet difficult for computers.
There are several reasons why Arimaa is difficult for computers to play. First the number of new board positions that can arise after a player takes a turn runs into the thousands as compared to an average of about 30 for Chess. With a much bigger range of possibilities at each turn it becomes extremely hard for computers to use the brute force look ahead method to search through all of them to find the better moves. For example at the start of a chess game white has 20 possible moves. In Arimaa a player has about 2,000 to 3,000 moves in the first turn depending on the way they chose to setup the pieces. During the mid-game the number of possible moves can range from about 5,000 to 40,000. If we assume an average of 20,000 possible moves at each turn, looking forward just 2 moves (each player taking 2 turns) means exploring about 160 million billion positions. Even if a computer was 5 times faster than Deep Blue and could evaluate a billion positions per second it would still take it more than 5 years to explore all those positions. However, modern game playing programs use pruning algorithms to significantly reduce the number of positions that need to be explored. Even with such pruning the number of positions that need to be evaluated is still sufficiantly large to make it extreamly difficult for a program to search very deep.
End game databases have also significantly improved the performance of computers in many traditional strategy games. When the number of pieces remaining on the board is reduced to just a few, computers can play a perfect ending by simply looking up the best move for the current postion from a precomputed database of ending postions. However a typical Arimaa game can end with most of the pieces still on the board. It is not uncommon for a game to end without any pieces ever being exchanged. Thus attempting to develop an end game database for Arimaa will not be feasible.
Another important factor is that the starting position of Arimaa is not fixed as it is in Chess. There are more than 64 million different ways in which each player can setup their pieces at the start of the game. This makes it very difficult to develop complete databases of opening moves. One of the difficulties that humans have when playing Chess against computers is that they can easily fall into an opening trap. To avoid this the human player must be extremely familiar with a very large number of Chess openings. This basically boils down to a problem of memorization which computers are extremely good at and humans are not. Even Bobby Fischer, a former World Champion, has proposed allowing different starting positions in Chess to counter the problem of computers having an opening book advantage.
Lastly computers will have difficulty with Arimaa because it is much more of a positional game and has much less tactics than Chess. Computers are great at spotting tactics and taking advantage of them, but they have a much harder time trying to determine if a materially equivalent position is more advantageous for one side or the other. Chess Grand Masters are constantly trying to get their computer opponents into a positional disadvantage while trying to avoid tactical mistakes. After playing Deep Blue, Garry Kasparov wrote that the experience was like walking through a mine field. Arimaa tips the scale in favor of humans, by reducing tactics and giving more importance to position.
In 1968 David Levy, an International Master made a $3,000 bet with John McCarthy, a distinguished researcher in Artificial Intelligence, that no chess computer would beat him in 10 years. He won the bet, but it spurred a lot of interest in developing chess playing programs. In a similar challenge, we are posting a reward of $10,000 USD to the first computer program that can demonstarate before the year 2020 that it is considerably better than the the top human players in an official Arimaa match. It is our hope that Arimaa along with this challenge will promote research in the Artificial Intelligence community to seek new and different approaches to the difficult problem of teaching computers to play strategy games and shift the focus away from the standard look ahead approach such as that used by Deep Blue.
The accomplishment of the Deep Blue team in building a Chess computer that could defeat the world champion is indeed a major achievement. It marks a milestone in the progress of Artificial Intelligence and computer technology. However we should not let this success mislead us into thinking that computers are now as intelligent as humans when it comes to serious game playing. Also we should not think that we have tackled the difficult problem of teaching computers to play strategy games. There is much work that needs to be done in understanding how humans play strategy games and duplicating this in software. Thus far we have relied mostly on advances in computer hardware. Hopefully the creation of Arimaa and the accompanying challenge will help to spur some new and radically different approaches to autonomous strategy game playing and produce some major breakthroughs in the field of Artificial Intelligence, that will have applications in many other fields.
When computers are finally able to defeat even the best human Arimaa players we can then rightfully wonder if they now have real intelligence.
Copyright © 1999-present www.arimaa.com. All Rights Reserved. Contact author for permission. Patent Pending.