Game Playing, Production Systems

Game Playing and AI

Games are said to be the well-defined problems that are generally interpreted as requiring intelligence to play well. They introduce uncertainty since opponents moves can not be determined in advance. The search spaces can be very large.

For example in chess:
-Branching factor: 35
-Depth: 50 moves each player
-Search tree: 35100 nodes (~1040 legal positions)

Despite this, human players do quite well without doing a much explicit search. They seem to rely on remembering many patterns. Thus game playing is considered to be a good test domain for search methods and development of pruning methods that ignore portions of the search tree which do not affect the outcome.

Game Playing Problem

The game playing problem can be called as an instance of the general search problem. The states where the game has ended are called terminal states. A utility (payoff) function determines the value of terminal states. For example: win=+1, draw=0, lose=-1. In two-player games, assume one is called MAX (tries to maximize utility) and one is called MIN (tries to minimize utility). In the search tree, the first layer is moved by MAX, next layer by MIN and alternate to terminal states. Each layer in the search is called a ply.

Minimax Algorithm

This algorithm is said to be the general method for determining optimal move. It generates the complete game tree down to terminal states. Minimax algorithm computes utility of each node bottom up from leaves toward the root. At each MAX node, pick the move with maximum utility. At each MIN node, pick the move with minimum utility (assumes opponent always acts correctly to minimize utility). When we reach the root, the optimal move is determined.

Production system

It is known as a computer program which consists of a set of rules. These rules which are also termed as production are the representations which are found useful in automated planning, expert system, and action selection. It provides the mechanism which is necessary to execute the production in order to achieve the desired goal. It consists of two parts and they are:

• Detection (Sensory part) and action.

If a production's pre-condition match the current state then it is said to be triggered and if the action is executed then it is called fired. It also contains a database which maintains the information about the current state and rule interpreter.

References:

1. Elaine Rich, Kevin Knight 1991, "Artificial Intelligence".
2. Nilsson, Nils J. Principles of Artificial Intelligence, Narosa Publishing House New Delhi, 1998.
3. Norvig, Peter & Russel, Stuart Artificial Intelligence: A modern Approach, Prentice Hall, NJ, 1995
4. Patterson, Dan W. Introduction to Artificial Intelligence and Expert Systems, Prentice Hall of India Private Limited New Delhi, 1998.