---
title: "Generalized Game Trees"
authors:
  - "Richard E. Korf"
doi: ""
url: "https://ijcai.org/proceedings/1989/52"
pdf: "https://ijcai.org/proceedings/1989/0052.pdf"
venue: "Proceedings of the Eleventh International Joint Conference on Artificial Intelligence"
year: 1989
pages: "328-332"
track: "Search"
keywords:
---

# Generalized Game Trees

Richard E. Korf

*Proceedings of the Eleventh International Joint Conference on Artificial Intelligence*, pages 328-332.

## Abstract

We consider two generalizations of the standard two-player game model: different evaluation functions for the players, and more than two players. Relaxing the assumption that players share the same evaluation function produces a hierarchy of levels of knowledge as deep as the search tree. Alpha-beta pruning is only possible when the different evaluation functions behave identically. In extending the standard model to more than two players, the minimax algorithm is generalized to the maxn algorithm applied to vectors of N-tuples representing the evaluations for each of the players. If we assume an upper bound on the sum of the components for each player, and a lower bound on each individual component, then shallow alphabeta pruning is possible, but not deep pruning. In the best case, the as7ptoti) branching factor is reduced to (1 + 4b- 3 /2. In the average case, however, pruning does not reduce the asymptotic branching factor. Thus, alphabeta pruning is found to be effective only in the special case of two players with a common evaluation function.