Strategy Games - Fundamentals of Game Design - page 448

games, it's fun to think of pitting one's wits against an enemy general. The old
Electronic Arts war game Patton vs. Rommel explicitly encourages this fantasy; the
player takes the role of one general and the computer takes the other. However, it is
only a fantasy, of course; the opponent it provides is artificial, implemented by AI
techniques. This section includes a brief introduction to some of the AI used to cre-
ate artificial opponents in strategy games. As the designer, you won't have to write
the software, but you should be aware of the strengths and weaknesses of several
approaches.
Game Tree Search
In turn-based games such as checkers, chess, or Go, each player has a number of
choices—possible moves that he can make—at each turn. You choose your move,
then your opponent makes his move from the choices available to him, and then
it's back to you with a new set of possible moves, and so on. If you draw a graph of
this, showing how the options branch out at every turn, it looks like a tree, so the
set of all possible future moves is called the game tree .
With simple games, artificial opponents search through the game tree, looking
for the moves that produce the most advantageous result. The fewer choices there
are, the easier this is. With tic-tac-toe, the problem is trivial; with checkers, it is
comparatively easy; with chess, it is quite difficult; and with Go, no one has yet
managed to build a computer game that can play as well as a master human player.
In Go, the board is large and the player can play nearly anywhere, so the number of
possible future moves is simply astronomical. In addition, unlike in chess, it is very
difficult to evaluate whether a potential move is good or bad; it depends too much
on other moves.
As a designer, do not expect to use game-tree search in any but the simplest of
games. The length of time it will take for the computer to compute a good move
increases exponentially with the number of possible moves available.
Neural Nets
A neural net is a program that simulates, in a simplified form, the behavior of brain
cells, or neurons. The details are too complex to discuss here, but put simply, a neu-
ral net mimics the brain's ability to recognize and correctly identify patterns of
data. This is how we learn to tell an apple from an orange, for example: Our brains
learn the visual patterns that apples and oranges fall into. Like the brain, a neural
network has to be taught to recognize the pattern; after that, and with repeated
exposure, the brain or the neural network identifies the pattern correctly.
Some efforts have been made to teach neural nets to learn to play strategy games by
recognizing patterns of play that lead to success. Although this technique is worthy
of further research, you shouldn't count on it. Neural nets take a long time to learn,
and the process doesn't work well for complex patterns of information, such as the