N-person game playing and artificial intelligence.

Abstract

Game playing in artificial intelligence (AI) has produced effective algorithms enabling a computer to play two-person, non-cooperative, zero-sum and perfect information games such as checkers and chess. Game theory suggests solution sets for games, but does not shed much light on how to make moves in a game. This dissertation couples AI with game theory and determines ways for a computer to play multi-player games. The max$\\sp{\\rm n}$ algorithm is defined and analyzed for playing non-cooperative, n-person games. The max$\\sp{\\rm n}$ procedure finds an equilibrium point for a game and allows some pruning of calculated payoff values but not pruning of subtrees. An evaluation for representing a cooperative game is defined using the max$\\sp{\\rm n}$ procedure on all possible coalitions. This evaluation is used along with an earnings function in order to define the stability of a coalition and coalition structure. Finally, a solution algorithm is developed that is based on coalition stability for a computer to use in playing cooperative n-person games using look ahead, heuristic evaluation function, and back-up techniques. The solution algorithm gives a result that is sometimes in game-theoretic solution sets such as the core, stable set, kernel, and bargaining set. Potential applications for this work are in AI, conflict resolution, economics, mathematics, and social psychology.