Beyond Minimax: Nonzero-Sum Game Tree Search with Knowledge Oriented Players

Contents

The classic minimax search for two-player zero-sum games such as chess has been thoroughly studied since the early years of AI; however for more general nonzero-sum games, minimax is non-optimal, given a player’s knowledge about the opponent. Previously, a few opponent models and algorithms such as M* were introduced to improve minimax by simulating the opponent’s search, given the opponent’s strategy. Unfortunately, they all assume that one player knows the other’s strategy but not vice versa, which is a very special relationship between knowledge and strategies. In this paper, we characterize minimax and M* and show examples where they can be non-optimal. We propose a new theoretical framework of Knowledge Oriented Players (KOP), using the powerful S5 axiom system to model and reason about players’ knowledge. With KOP, the general relationship between knowledge and strategies can be analyzed, which is not handled by the traditional game theory. We show how strategies are constrained by knowledge and present new strategies for various problem settings. We also show how to achieve desired knowledge update via communication so that players can achieve the best possible outcome. With respect to players’ knowledge, our strategies always dominate minimax and work well for the general knowledge cases where previous algorithms do not apply.