To begin our discussion of artificial intelligence in game playing, we will use the following puzzle described by Brookshear:
"Imagine that you have a puzzle consisting of eight square tiles labeled 1 through 8 mounted in a frame capable of holding a total of nine such tiles in three rows and three columns. Among the tiles in the frame then is a vacancy into which any of the adjacent tiles can be pushed" [Brookshear 1997].
The applet below [Opdorp 1997] shows an example of the puzzle previously described. Note that the numbered tiles have been replaced by images in this version. You can move the tiles by clicking on an image adjacent to the empty tile. Try solving the puzzle and see how many steps you need. Then click the button "Same Shuffle" followed by "Solve" to restore the original shuffle and watch the computer solve the puzzle.
You are probably wondering how the computer is able to solve this puzzle so efficiently. Of course one possibility is that the computer is already programmed with all the possible configurations for this puzzle. However, considering that there are over 180,000 possible configurations for a simple puzzle like this, such a solution is clearly not feasible.
Instead of explicitly storing all the possible solutions, the computer constructs a search tree which holds possible configurations for the 8-puzzle. If we imagine our tiles being numbered, a very simple search tree would look like this:
Notice that moving from one node to the next is equivalent to moving a single tile of the puzzle. In this case, we only need two moves to reach the goal state (the solution configuration). However, if we had started with a more difficult configuration, our search tree would be much larger. By constructing a search tree, the computer can examine the possible configurations of the puzzle systematically until it reaches the goal state. Then by following the path from the goal state back to the start state, the computer can determine the correct steps to solve the puzzle.
The search tree for a particular problem can grow in size quite rapidly if the goal state is not found quickly. To reduce the amount of searching the computer must do, the tree can be constructed in a depth-first manner rather than a breadth-first manner. In this way a single branch of the tree is considered first before examining other branches. The advantage of this approach is that more promising branches can be considered first.
Another technique for reducing the size of the search tree is by using heuristics. Heuristics are like "rules-of-thumb" that tell the computer whether a given branch of the tree is worth exploring or not. These rules guide the computer by telling it how close a given configuration is to the goal state. Configurations which are closer can be given more attention than less promising configurations. To see the effect of using a heuristic, try running the eight-puzzle applet but change the value in the "Heuristic" list to "None". You may need to shuffle the board a couple of times to find a difficult configuration. You should notice that the computer takes quite a while to find the solution. Then try asking the computer to solve the same configuration (use the "Same Shuffle" button) using the "Manhattan" heuristic. The time required to find the solution is noticeably shorter.
In recent years, researchers have combined sophisticated heuristics and increased computing capability to create formidable computer opponents in the games of chess and checkers. As mentioned before, a computer program now officially holds the world title for checkers. In 1997, a chess program designed by IBM researchers played against world champion Garry Kasparov in a six game match and defeated him. Details of the match can be found at a special IBM web site. Both checkers and chess programs construct search trees similar to the example we saw with the 8-puzzle. Then the programs search through the tree for the most advantageous move. Since computers can perform calculations so quickly, these programs can analyze a tremendous number of moves in a single second. For example, the computer which Kasparov played against could examine and evaluate up to 200,000,000 chess positions per second while Kasparov himself could only examine and evaluate up to three chess positions per second [IBM 1997]. While it might seem that Kasparov's odds against such computing power are hopeless, the reality is that most of the moves the computer examines are useless. Since the computer lacks experience and intuition, it must examine each possible move at every step of the game. On the other hand, chess masters like Kasparov have the ability to immediately recognize that some moves are useless. This allows them to think more efficiently and focus their attention on certain strategies that have the most potential.
- Brookshear, J. G. (1997), Computer Science: An Overview, Fifth Edition, Addison-Wesley, Reading, MA, pp. 361.
- Opdorp, G. (1997), "Eight-puzzle applet," http://www.aie.nl/~geert/java/public/EightPuzzle.html.
- IBM (1997), "Kasparov Versus Deep Blue," http://www.research.ibm.com/deepblue/meet/html/d.2.html.