Catalogue of Artificial Intelligence Techniques
Aliases: Game Trees
Keywords: games, zero-sum payoffs
Categories: Game Theory , Inference and Reasoning , Knowledge Representation , Problem Solving , Search , Theorem Proving
Author(s): Toby Walsh , Ian Frank
AND/OR graphs consist of nodes (representing goals and subgoals) connected by directed links--either AND links (representing subgoals that make up their parent goal) or OR links (representing alternative goals that satisfy the parent goal). AND/OR graphs are often used in theorem provers and game-playing programs. In game trees, the OR links from a node become the moves available to the player for whom a decision procedure is to be implemented (since it will be necessary to select exactly one of the alternatives if the game reaches that node). The AND links, on the other hand, represent the moves available to opponents, which cannot be controlled, therefore requiring a response to be considered for each branch. The leaf-nodes are often given a score which represents the payoff for one of the players if the game finishes in the corresponding state. If, as is often the case, the payoffs are zero-sum (i.e., one player's payoff is the negative of the other's) then these two players are called MAX (who tries to maximise his payoff by directing the play towards leaf nodes with high payoffs) and MIN (who tries to minimise MAX's return by directing the play towards leaf nodes with low payoffs), respectively. See also Minimax.
- Nilsson, N.J., Principles of Artificial Intelligence
, Tioga Pub. Co., Palo Alto, California, 1980.