State Space Searching

Touretzky Reading: None

Almost all of this material is lifted from Kurt Eiselt's notes on this subject.

For example, a compiler has a component called a parser which decomposes a high-level instruction into its component parts. But these instructions can be ambiguous, so the parser must make decisions about how various symbols (known as "tokens" in compiler world) are being used. How that decision is made depends on what the parser has already seen; in other words, the next possible state of the parsing process depends on the history of the previous states.

The parser reads the input from left to right, making "guesses" as it goes. If the sequence of guesses leads to a structure for an instruction that's not legal, the parser will backtrack and systematically try new guesses, just like a depth-first search algorithm. If no combination of guesses works for the parser, you'll get a "syntax error" message. These things are sometimes called "recursive descent parsers."

Parsers are something that are a generally useful tool in a variety of contexts, so lets look at them in a little more detail. Consider a parser for a Pascal like language which gets a string of tokens to parse like this:

What if you were interested in parsing this? Suppose you had a rule that said two objects with the same center point move together? What about rules for scaling and rotation?

The same sorts of ideas are used to get computers to understand English and other natural languages. In fact, an entire company was founded on this idea. A guy named Gary Hendrix at the University of Texas wrote a PhD thesis on parsing English back in the late 60's or early 70's. He later took some of those same ideas and build an interface to a simple database system -- an interface that could accept data base queries in English (or at least a subset of English). He called the whole thing "Q&A", it runs on PC compatibles, and it sells off the shelf at computer stores for about $300 a copy. This product was one of the first, if not the first, offered by the company Hendrix co-founded, which is called "Symantec" -- a company which most of you Mac or PC owners know about, since it's swallowing up all sorts of other software vendors. Hendrix is now a zillionaire, and the moral to this story is that state-space search can make you rich.

As we mentioned in class, evolutionary biologists think of all of us (and I mean *all* of us) as the bottom layers of nodes on a very big state space. Those of us who don't have any children are the leaves on a very very big tree (well, it's not exactly a tree, but you get the idea). Some of us will generate new states (our kids) and others of us won't. Each state presumably brings humanity slightly closer to some lifeform that is perfectly adapted to the environment. (If only we could get the environment to stop changing....)

Finally, a state-space search is a nice little metaphor for how we lead our lives: every decision we make is based on the chain of decisions leading up to that point. However, in life, unlike in your computer, there's often no backtracking possible when you make a bad decision.

A state-space search algorithm (depth-first)

state-space (initial-states, goal-state, operators)

1. look at the first (leftmost) initial-state
2. if that state is the goal-state, then return success
3. if that state isn't the goal-state, then generate all possible new states from that state by applying the set of operators to that state
4. if there aren't any new states generated by applying those operators, then return failure
5. call state-space with this new list of states passed as the initial-states argument, and if that succeeds then return success else...
6. return failure

Making your search smarter

Usually, however, we don't have time to burn. We'd like to strive to find the goal state in as few steps as we can. That is, we'd like to try to find the "optimal path" from the initial state to the goal state, and we can help ourselves out here if we can put a little more "intelligence" into our search.

One time-honored way of doing this is to find a method to measure the "goodness" of a state -- that is, to determine how close a given state is to the goal state. If we could make that evaluation consistently and correctly, then when we look at a list of states in trying to decide which to use next to generate new states, we could pick the state closest to the goal, instead of just picking the first one we see or picking one at random.

Most of the time, though, such measurements of a state's goodness are just estimates. If the estimate is wrong, you could spend a lot of time and effort searching paths that will never get you to the goal, or at least that will give you less optimal solutions. The better the ability to estimate goodness, the better is the chance for optimality. But unless the estimate is always right, there's no guarantee of success. These measures of goodness are one example of something called "heuristics": techniques that aid in the discovery of solutions to problems most of the time, but don't guarantee that they'll lead to solutions all of the time.

A note to be aware of about the term "heuristics:" In general heuristics have the property that they do not make guarantees of success. If they did, they would be an "algorithm." Hueristics are approaches that trade certainty for certain optimizations, generally these are optimizations of speed or space. Consider a compiler that used hueristics to parse. Would you want to use a compiler that claimed that "most of the time, we compile a lot faster than our competitors?" Consider various "precompilation" techniques. The hueristic here is that "people compile the same things lots of times, so lets give up some space to have an already compiled version laying around." Note: If you end up not really compiling the same file often, you lose! All the space that is dedicated to the "precompiled" parts of the system go to waste.

Heuristics and the 8-tile puzzle

                  1 2 3
                  8   4
                  7 6 5

                  2 8 3
                  1 6 4
                  7   5
                   /|\
                  / | \
                 /  |  \
                /   |   \
               /    |    \
              /     |     \
             /      |      \
            /       |       \
          2 8 3   2 8 3   2 8 3
          1 6 4   1   4   1 6 4
            7 5   7 6 5   7 5

          score   score   score
            3       5       3

Adversarial or game search -- the sneak preview

The fundamental change in the nature of that question results in a fundamental change to the way we do state-space search in adversarial situations, thus giving rise to something called "adversarial search". And since we frequently use this kind of search when we build intelligent game-playing programs, this kind of search is frequently called "game search".

The principle of game search is to first generate the state space (or "game tree") some number of levels deep, where each level corresponds to one player's move (or, more accurately, the set of all moves that the player could possibly make at that point). After generating the state space for that number of levels, the nodes at the bottom level are evaluated for goodness. (In the context of game playing, those nodes are often called "boards", each one representing one possible legal arrangement of game pieces on the game board.)

The estimate of the goodness of a board is a little bit different than before, but not much. Since we have to worry about the opponent, we set up our estimation function so that it returns a spectrum of values, just like before, but now the two extremes are boards that are great for us (i.e., we win) and boards that are great for our opponent (i.e., we lose). We apply our estimation function to those lowest level boards, and propagate the numerical values upward to help us determine which is the best move to make.

But this is perhaps a bit sketchy. In the next lecture, we'll go into game search in great detail, and we'll introduce a simple game that is sure to drive you bonkers over the next couple of weeks.

Last Modified 8 Feb 95 by Ian Smith (iansmith@cc.gatech.edu)