The multi-player version of minimax displays game-tree pathology
✍ Scribed by David Mutchler
- Publisher
- Elsevier Science
- Year
- 1993
- Tongue
- English
- Weight
- 724 KB
- Volume
- 64
- Category
- Article
- ISSN
- 0004-3702
No coin nor oath required. For personal study only.
✦ Synopsis
Mutehler, D., The multi-player version of minimax displays game-tree pathology (Research Note), Artificial Intelligence 64 (1993) 323-336.
It is widely believed that by searching deeper in the game tree, the decision-maker is more likely to make a better decision. Dana Nau and others have discovered pathology theorems that show the opposite: searching deeper in the game tree causes the quality of the ultimate decision to become worse, not better. The models for these theorems assume that the search procedure is minimax and the games are two-player zero-sum. This report extends Nau's pathology theorem to multi-player game trees searched with maxn, the multi-player version of minimax. Thus two-player zero-sum game trees and multi-player game trees are shown to have an important feature in common.
1. Introduction
Games played by more than two players have important characteristics that mark them as altogether different from two-player zero-sum games.