Different Approaches to Finding a Solution

Given the representation, we need to find the right instance of the internal values to provide a valid solution. The existence of a brute-force solution (revealed by information theory from the first section of this chapter) and the smoothness of the search space (analysis of the representation in the second section) provide little benefit if we can't solve the problem!

It's the job of the developer to pick the AI technique so that the internal variables of the solution are set correctly. Assuming it's possible for this type of representation to express the solution, there are different approaches to find the right values for each of these internal variables.

Expert Solution

Some AI techniques rely on the engineer to create the internal knowledge of the solution. This is the case for rule-based systems, where the developer crafts the rules (for instance, for wall following). An expert could also create a decision tree manually in the same fashion for weapon selection.

In this approach, the AI developer uses all his experience and wisdom to find the best possible instance. The developer is also responsible for updating the solution if it doesn't work immediately (common in the experimentation phase).

Expert Guidance

Taking a broader view of this approach, the developer can get involved on several levels to help find the solution. Instead of finding the solution directly (level 0 contribution), the expert can devise algorithms to find the right configuration (level 1). This is the case of multilayer perceptrons, where the gradient descent technique allows the adjustment of the weight to a near-optimal configuration.

With even less involvement, the expert can develop technology that helps general algorithms find the right solution (level 2). This is the case with decision trees; the statistical heuristic used to determine the best attribute helps the generic recursive partitioning algorithm find a solution.

The higher the involvement of the expert (level n), the less work needs to be done to have an effect on finding the solution. The understanding of the algorithms becomes more and more abstract, however, so it can be difficult to understand the consequences of high-level policies. In games, low-level involvement allows explicit control but can be time-consuming. Higher-level involvement results in less work but can suffer from the indirect nature control.

Exhaustive

A less sophisticated—but fully automated—approach relies on brute force to find the solution. All the configurations are tested until one of them matches the criteria laid out by the design. Each of the values is searched methodically, often in the form of nested "for" loops. All the instances are therefore searched exhaustively (hence the term "search space").

The major advantage of this approach is thoroughness. If there is a solution using the representation, it will be found! The cost of this guarantee is computation power—lots of it. This can be suitable for preprocessing in game AI, but nothing else.

Random

A random approach to finding a solution essentially chooses the instance stochastically. It is evaluated by a third-party component, and the process is repeated until the solution is acceptable.

The advantage of this approach is that there is no particular bias toward any type of solution. This means that we'll get a representative distribution of the possible instances of the solution before a satisfactory one is found. This approach is very unpredictable by nature, however, and no guarantees on a time scale to find a solution can be made.

Hybrid Approaches

Most AI techniques use a blend of these approaches. All the previous paradigms have tremendous advantages; often, they can be combined successfully. In many cases, particular solutions are better suited to different kinds of approaches, so we have the freedom of choosing the best technique for the job. In many cases, the choice is made among the techniques presented in this book, which provides a diversity of approaches.