The Early Days
The early days include the time before computers, where philosophy of mind occasionally made forays into AI with such questions as: “What produces thought?” “Could you give life to an inanimate object?” “What is the difference between a cadaver and the human it previously was?” Tangential to this was the popular taste in mechanical robots, particularly in Victorian Europe. By the turn of the century, mechanical models were created that displayed the kind of animated, animal-like behaviors that we now employ game artists to create in a modeling package.
In the war effort of the 1940s, the need to break enemy codes and to perform the calculations required for atomic warfare motivated the development of the first programmable computers. Given that these machines were being used to perform calculations that would otherwise be done by a person, it was natural for programmers to be interested in AI. Several computing pioneers (such as Turing, vonNeumann, and Shannon) were also pioneers in early AI. Turing, in particular, has become an adopted father to the field, as a result of a philosophical paper he published in 1950 [Turing, 1950].
The Symbolic Era
From the late 1950s through to the early 1980s the main thrust of AI research was “symbolic” systems. A symbolic system is one in which the algorithm is divided into two components: a set of knowledge (represented as symbols such as words, numbers, sentences, or pictures) and a reasoning algorithm that manipulates those symbols to create new combinations of symbols that hopefully represent problem solutions or new knowledge.
An expert system, one of the purest expressions of this approach, is the most famous AI technique. It has a large database of knowledge and applies rules to the knowledge to discover new things. Other symbolic approaches applicable to games include blackboard architectures, pathfinding, decision trees, state machines, and steering algorithms. All of these and many more are described in this article.
A common feature of symbolic systems is a trade-off: when solving a problem the more knowledge you have, the less work you need to do in reasoning. Often, reasoning algorithms consist of searching: trying different possibilities to get the best result. This leads us to the golden rule of AI: search and knowledge are intrinsically linked. The more knowledge you have, the less searching for an answer you need; the more search you can do (i.e., the faster you can search), the less knowledge you need.
It was suggested by researchers Newell and Simon in 1976 that this is the way all intelligent behavior arises. Unfortunately, despite its having several solid and important features, this theoryhas been largely discredited. Many people with a recent education in AI are not aware that, as an engineering trade-off, knowledge versus search is unavoidable. Recent work on the mathematics of problem solving has proved this theoretically [Wolpert andMacready, 1997], and AI engineers have always known it.
TheModern Era
Gradually through the 1980s and into the early 1990s, there was an increasing frustration with symbolic approaches. The frustration came from various directions. From an engineering point of view, the early successes on simple problems didn’t seem to scale to more difficult problems or handle the uncertainty and complexity of the real world. It seemed easy to develop AI that understood (or appeared to understand) simple sentences, but developing an understanding of a full human language seemed no nearer.
There was also an influential philosophical argument made that symbolic approaches weren’t biologically plausible. The proponents argued that you can’t understand how a human being plans a route by using a symbolic route planning algorithm any more than you can understand how human muscles work by studying a forklift truck. The effect was a move toward natural computing: techniques inspired by biology or other natural systems. These techniques include neural networks, genetic algorithms, and simulated annealing. It is worth noting, however, that some of the techniques that became fashionable in the 1980s and 1990s were invented much earlier. Neural networks, for example, predate the symbolic era; they were first suggested in 1943 [McCulloch and Pitts, 1943]. Unfortunately, the objective performance of some of these techniques never matched the evangelising rhetoric of their most ardent proponents.
Gradually, mainstream AI researchers realized that the key ingredient of this new approach was not so much the connection to the natural world, but the ability to handle uncertainity and the importance it placed on solving real-world problems. They understood that techniques such as neural networks could be explained mathematically in terms of a rigorous probablistic and statistical framework. Free from the necessity for any natural interpretation, the probablistic framework could be extended to found the core of modern statistical AI that includes Bayes nets, support-vector machines (SVMs), and Gaussian processes.
Engineering
The sea change in academic AI is more than a fashion preference. It has made AI a key technology that is relevant to solving real-world problems. Google’s search technology, for example, is underpinned by this new approach to AI. It is no coincidence that Peter Norvig is both Google’s Director of Research and the co-author (along with his former graduate advisor, professor Stuart Russell) of the canonical reference for modern academic AI [Russell and Norvig, 2002].
Unfortunately, there was a tendency for a while to throw the baby out with the bath water and many people bought the hype that symbolic approaches were dead. The reality for the practical application of AI is that there is no free lunch, and subsequent work has shown that no singleapproach is better than any other. The only way any algorithm can outperformanother is to focus on a specific set of problems. The narrower the problem domain you focus on, the easier it will be for the algorithm to shine—which, in a roundabout way, brings us back to the golden rule of AI: search (trying possible solutions) is the other side of the coin to knowledge (knowledge about the problem is equivalent to narrowing the number of problems your approach is applicable to).
There is now a concerted effort among some of the top statistical AI researchers to create a unified framework for symbolic and probabilistic computation. It is also important to realize that engineering applications of statistical computing always use symbolic technology. A voice recognition program, for example, converts the input signals using known formulae into a format where the neural network can decode it. The results are then fed through a series of symbolic algorithms that look at words froma dictionary and the way words are combined in the language.
A stochastic algorithm optimizing the order of a production line will have the rules about production encoded into its structure, so it can’t possibly suggest an illegal timetable: the knowledge is used to reduce the amount of search required.
We’ll look at several statistical computing techniques in this book, useful for specific problems. We have enough experience to know that for games they are often unnecessary: the same effect can often be achieved better, faster, and with more control using a simpler approach. Although it’s changing, overwhelmingly the AI used in games is still symbolic technology.
