A Theory of Heuristic Information in Game-Tree Search

Searching is an important process in most AI systems, especially in those AI production systems consisting of a global database, a set of production rules, and a control system. Because of the intractability of uninformed search procedures, the use of heuristic information is necessary in most searching processes of AI systems. This important concept of heuristic information is the central topic of this book. We first use the 8-puzzle and the game tic-tac-toe (noughts and crosses) as examples to help our discussion.

This chapter introduces some basic concepts of games. Finite zero-sum two-person perfect information games, for which our theory is to be developed, are introduced first. These games are represented by special graphs, called game graphs. If nodes representing the same game position in a conventional game tree are merged into only one node, then the merged graph is called a game graph. Two examples are used to clarify the discussion.

In the last chapter, we discussed zero-sum two-person perfect information games. If both players playing such a game can find at each step the minimax values of all possible next moves, then the corresponding game-playing problem is completely solved. MAX chooses a move of the highest minimax value at each step, and MIN chooses a move of the lowest minimax value at each step. The moves chosen have identical minimax values; this value is exactly the same as the final payoff of the game. It is because this use of minimax values solves game problems that finding minimax values is a central issue in the theory of zero-sum two-person perfect information games.

In this book, a game space on which a heuristic-search model is constructed is always a probability space. All notions in the model, such as heuristic information, strength of nodes, and so on, are formulated in the terminology of probability theory. We use the concept of martingales to represent relationships among various node estimates that are based on heuristic information.

In this chapter we introduce a formal definition of a probabilistic game model for further theoretical study. The P₂- and G₁-games introduced in Chap. 2 are two probabilistic game models. A probabilistic game model is a space of zero-sum two-person perfect information games such that all of the games in the space have the same fixed game graph (or tree) and the values on leaves are assigned according to a fixed distribution. Because of this probabilistic assignment of the values at leaves, a game in a probabilistic game model can be treated as a random event in a probabilistic space.

In this chapter we formulate a concept of heuristic information. In a conventional heuristic game-tree search, heuristic information is a set of values returned by a static evaluation function at search-tip nodes. A static evaluation function is primarily used to estimate the strength of a node. However, the notion of node strength relies mostly on heuristic and intuition and usually does not have a precise formulation. Since the minimax value is the value most used to characterize a node in a game tree, the strength of a node is often seen as the minimax value of the node. But, a static evaluation function, such as the one-counter in P _b - and G _d -game models, usually does not directly estimate minimax values. In a P _b - or G _d -game, the minimax value of a node is correlated with the number of ones in the corresponding game position (that is, the value of the one-counter), but this number is definitely not a direct estimate of the minimax value. A transformation from this search information, the number of ones, to an estimate of the minimax value is necessary. Here we first study such search information, called heuristic information, as a mathematical object, and then consider node estimation based on heuristic information in the next chapter.

The primary purpose of a heuristic search is to gather heuristic information for making a move. In a conventional approach, the decision making is based on estimates of possible next moves. These estimates are derived by backing up original estimates at search-tip nodes returned by a static evaluation function. From this conventional approach, we develop in this chapter a general theory of decision making based on heuristic information.

Both the game models and the heuristic information introduced in the previous chapters are purely theoretical. Although estimates of the strength of nodes, given a piece of heuristic information, exist and have the monotone property (Theorem 7.1), no practical process of finding such estimates can be generally derived for all game models. Since these estimates have been formulated into mathematical terms, developing any practical process of determining them becomes a mathematical problem. Hence an actual process can only be created for each particular case.

A P _b -game model (Sect. 5.3) is characterized by its complete, uniform game tree with branching factor b and by the distribution of the payoffs at terminal nodes. The value 1 or 0 is independently assigned to all leaves with a probability of p or 1 - p, respectively, where 1 denotes a win for MAX and 0 a win for MIN.

Since the structures of G _d -games are different from the structures of P _b -games, a G _d -game model has a different process for estimating minimax values based on the one-counter. In this chapter, we study the estimation of minimax values in G _d -game models.

The mathematical theory of heuristic information introduced in this book demonstrates the fact that concepts in heuristic game-tree searches, such as heuristic information, node strength, node estimation, and decision making, can be formulated in mathematical terms. In a heuristic game-tree search, if the information is accumulated at all of the nodes in the search tree and if the node strength of each possible next move is precisely estimated, then the decision quality is improved with a larger search tree. Accumulating information at all nodes in the search tree guarantees the increase of heuristic information in a deeper search. The increased information then upgrades node-strength estimates and hence improves decision quality.