C Kiekintveld, MP Wellman, and S Singh

AAMAS-06 Workshop on Game-Theoretic and Decision-Theoretic Agents, 2006.
Copyright (c) 2006, Kiekintveld et al.


We analyze 4-player chaturanga (an ancient variant of chess) using the methods of empirical game theory. Like chess, this game is computationally challenging due to an extremely large strategy space. From the perspective of game theory, it is more interesting than chess because it has more than 2 players. Removing the 2-player restriction allows multiple equilibria and other complex strategic interactions that require the full tool set of game theory. The major challenge for applying game theoretic methods to such a large game is to identify a tractable subset of the game for detailed analysis that captures the essence of the strategic interactions. We argue that the notion of strategic independence holds significant promise for scaling game theory to large games. We present preliminary results based on data from two sets of strategies for chaturanga. These results suggest that strategic independence is present in chaturanga, and demonstrate some possible ways to exploit it.