Game Development Reference
In-Depth Information
chapter 6
Look-Ahead: The First
Step of Planning
If you have not memorized all the possible moves in Tic-Tac-Toe , you probably
play by thinking something like, ''If I move here, he could move there, there, or
there. . . .'' This is the heart of look-ahead. Another way of thinking about it
would be to ask the simple question, ''If I move here, and then each of us takes
our best moves in turn, will I win in the end?'' We will revisit the implications of
each part of this reasonably simple question throughout the chapter.
The method seems simple on the surface, but even simple games such as Tic-Tac-
Toe reveal some hidden complexities. Every part of our seemingly simple
question is an iceberg hiding many complexities, including evaluation functions,
pruning, heuristics, discrete moves, and knowledge representation. By the end of
this chapter, it will be clear that look-ahead lives and dies on how well the
implementation manages computational complexity. We mentioned combina-
torics in passing in Chapter 5, ''Random and Probabilistic Systems.'' We will
lightly brush up against it here as well, mostly hidden as determining the product
of a bunch of numbers multiplied together. Computational complexity will be a
running theme throughout the discussion of other complexities.
After examining look-ahead and its complexities, we will summarize the meth-
od's advantages and disadvantages. This will make it easy to discuss the kinds of
games for which look-ahead is well suited. This chapter then ends with the Fox
and Hounds project, which illustrates in depth many of the challenges to using
Search Nedrilad ::

Custom Search