An Algorithmic Solution of N-Person Games

Proceedings of the AAAI Conference on Artificial Intelligence, 5

Volume

Science

Search

Two-person, perfect information, constant sum games have been studied in Artificial Intelligence. This paper opens up the issue of playing n-person games and proposes a procedure for constant sum or non-constant sum games. It is proved that a procedure, maxn, locates an equilibrium point given the entire game tree. The minimax procedure for 2-person games using look ahead finds a saddle point of approximations, while maxn finds an equilibrium point of the values of the evaluation function for n-person games using look ahead. Mazn is further analyzed with respect to some pruning schemes.