[ CogSci Summaries home | UP | email ]
http://www.jimdavies.org/summaries/

D.H. Ballard (1997), An Introduction to Natural Computation, MIT Press.

Chapter 3: Programs

Author of the summary: Patrawadee Prasangsit, 1999, pp@cc.gatech.edu

Cite this paper for:

Summary:

Abstract

A central facet of natural computation is describing its key elements.  These are programs.  Programs work by searching a state space using operators that govern the transitions from one state to another.  Problem solving can be seen as choosing a good sequence of operators in order to specify a path through sate space.  Heuristic search uses a fitness function to choose between global alternative paths. Minimax, for game playing, uses a fitness function to rate local alternative paths.

Heuristic Search

The key idea is the use of a heuristic function that rates each of the nodes in the search tree.  Then at each point the best node (as rated by heuristic function) is selected for expansion.  The algorithm can be written as follows:
1. Let x be the start node.
2. If x is the goal, return with success; otherwise expand it and put its successors on the list OPEN.
3. If OPEN is empty, then stop with failure; otherwise, let x be the "best" member of OPEN.  Pop x.  Go to 2.
The list OPEN contains the frontier of the tree.  At any moment the best node in the frontier is selected and the frontier is expanded at that point.

It turns out the cost function f(n) of a node n should estimate the cost of the path from the start to the goal.

f(n) = g(n) + h(n)
g(n) is the cost from the start to n
h(n) is the estimated cost from n to the goal
If h(n) overestimates the cost, when the goal node was reached, there might be a better path remaining to be discovered.  With underestimation, this difficulty does not arise.

Two-person Games

Two-person games are characterized by considering an opponent's options (moves) in addition to your own.  The game tree consists of interleaving levels of nodes, corresponding to options of each player.  Since a tree can be huge, it cannot be searched in its entirety.  A typical models for two-person games are checkers, chess, backgammon, and Othello.

The best way is to make a local decision based on limited look-ahead.  The look-ahead strategy will expand the tree a fixed number of plies (a ply consists of two layers, corresponding to each player) and then score the board positions at the leaf nodes.  To do so, an evaluation function must be picked that scores different features of the board.  The scores reflect "your" viewpoint of each leaf node.  The minimax procedure allows the evaluations at the tree extremities to be propagated backward to choose your move.

As it turns out, minimax can be improved by using alpha and beta cutoffs.  The idea is that since the value of a maximizing node can only go up and that of a minimizing node can only go down, some search subtree can be ignored.

Example:
  

                                            o                                            MAX
                                            |
           o---------------------o---------------------o-------------------o             MIN
         /   \             /     |     \             /   \               /   \
       o       o         o       o       o         o       o           o       o
       3       2        -2      -4       6         7       1          -1      -5         MAX


In this example, using alpha-beta cutoffs, -4, 6, and -5 will not be looked at.

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:
JimDavies ( jim@jimdavies.org )

Last modified: August 3, 1999