Operations Performed during Game Playing | Artificial Intelligence

The three basic operations which can be performed on game trees in the process of designing a game playing program are: 1. Generation 2. Evaluation 3. Pruning.

Operation # 1. Generation:

The two methods available for generation of a game tree are variations of the breadth- first and depth-first searches. In breadth first generation, all possible states at level 1 are generated before proceeding to level 2, at which point all possible game states are generated before proceeding to level 3, and so on.

In depth first generation, the game rules are applied to generate all states along the left side of the graph, for instance, until a terminal node or predetermined number of ply is reached. Then the generator backs up until it reaches the next left-most branch and follows that to its terminal node or ply limit, and so on.

Both of these methods are applicable in practice to only the simplest possible games and totally impractical for complex games such as chess unless restrictions are placed on the number of plies searched. For such complex games, the generator runs ahead to some predetermined level or follows certain branches to various levels depending on the particular heuristic in effect.

The game tree terminates in one of three states- A wins, B wins, or draw for most board games, and these terminal nodes are sometimes called leaves of the game tree.

Such terminal nodes or leaves occur throughout the game tree and may be reached early if one of the players is much more skillful than the other.

Operation # 2. Evaluation:

The generation operation is strictly determined by the “rules of the game” and hence may be algorithmic in nature. However the evaluation operation is much more subjective and becomes the point at which the game program author tries in incorporating the skill and tricks of clever play into the program, generally in heuristic form.

If the game is sufficiently simple that all nodes can be generated then the optimum strategy for player A, for example, is to examine which terminal nodes lead to a win and make those forward moves from level 0 which maximise his chances of reaching a winning node. However, for complex game it is simply impossible to generate, much less evaluate, all possible nodes.

This leads, then to the concept of the heuristic, static evaluation function, the game tree equivalent of the evaluation function for the search tree nodes.

A lot of work in game-playing programs has gone into the development of good static evaluation functions. A very simple static evaluation function for chess based on piece advantage was proposed by Turning-simply add the value of black’s pieces (B), the values white’s pieces (W) and the compute the quotient W/B.

A more sophisticated approach was by Samuel’s checkers program in which the static evaluation function was a linear combination of several simple, functions, each of which appeared as though it might be significant. Samuel’s functions included, the obvious piece advantage, capability for advancement, control of the centre, threat of a fork, mobility etc. These factors were then combined by attaching to each an appropriate weight and then adding the terms together.

Thus, the static evaluation function had the form:

f = C₁ x piece advantage + C₂ x advancement + C₃ x centre control…

There were also some non-linear terms reflecting combinations of these factors. Samuel did not know the correct weights to assign to each of the components. So he employed a learning mechanism in which components which had suggested moves leading to wins were given an increased weight, while the weights of those which had led to losses were decreased. Deciding which moves have contributed to wins and which to losses is not easy. The problem of deciding which of a series of action is actually responsible for particular outcome is called the credit assignment problem.

A statistical static evaluation function, was proposed by Firebaugh (1995) in the case of Chess-playing. This function estimates the present value to chess player A of the particular node in question, say node j, in terms of such parameters as ‘material’ (a numerical value assigned to each piece on the board), king safety, center control, and pawn structure.

Generally, the function is a linear polynomial of the form:

where,

C_j = 1 x N weight vector for position j,

Y_j = Column vector associated with system parameters,

N = Number of parameters used for evaluation.

This evaluation function could serve as a useful parameter for heuristics to guide machine learning. Techniques like suggested by Samuel are also useful in studying correlations between parameters which may be represented by quadratic terms in the weighing polynomial. By such cross terms, the interactions between various parameters are taken into account.

The program adapts to a player’s style and improves the quality of its game as time goes on. These characteristics suggest human abilities in “learning” since games provide a structured task in which it is quite easy to measure success or failure in Machine Learning σ. 

Operation # 3. Pruning:

The expansion of game tree is very cumbersome due to adversial nature of games.

Two hunches can be drawn from the complexity of the game tree:

1. Heuristics are important in game-playing to judge whether a move is good or bad. This is so as one cannot search the game tree as far as actual winning or losing state.

2. Choice of which nodes to expand is critical. A human chess player only examines a small number of the many possible moves, but is able to identify those moves which are interesting. This process of choosing directions to search is knowledge rich and therefore expensive.

More time spent on examining each node means fewer nodes examined—in fact the most successful chess programs have relatively simple heuristic but examine vast number of moves. They attain master level aim and are clearly ‘intelligent’, but the intelligence is certainly artificial.

The evaluation function can be interpreted as one of the most efficient ways of adding knowledge of game strategy to the program in order to prune the game tree to a manageable size. The adversarial nature of games also supplies constraints which significantly prune the game tree.