1. Algorithms for computing strategies in two-player simultaneous move games
- Author
-
Marc Lanctot, Viliam Lisý, Branislav Bošanský, Jiří Čermák, Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Computer Science::Computer Science and Game Theory ,Linguistics and Language ,Mathematical optimization ,Sequential game ,Monte Carlo Tree Search ,Monte Carlo tree search ,02 engineering and technology ,010501 environmental sciences ,computer.software_genre ,01 natural sciences ,Nash equilibrium ,Language and Linguistics ,General game playing ,symbols.namesake ,Markov games ,Artificial Intelligence ,Online search ,Game playing ,0202 electrical engineering, electronic engineering, information engineering ,Simultaneous move games ,Alpha-beta pruning ,0105 earth and related environmental sciences ,Mathematics ,Counterfactual regret minimization ,Regret matching ,Double-oracle algorithm ,Alpha–beta pruning ,Backward induction ,symbols ,020201 artificial intelligence & image processing ,Algorithm ,computer ,Gibbs sampling - Abstract
Simultaneous move games model discrete, multistage interactions where at each stage players simultaneously choose their actions. At each stage, a player does not know what action the other player will take, but otherwise knows the full state of the game. This formalism has been used to express games in general game playing and can also model many discrete approximations of real-world scenarios. In this paper, we describe both novel and existing algorithms that compute strategies for the class of two-player zero-sum simultaneous move games. The algorithms include exact backward induction methods with efficient pruning, as well as Monte Carlo sampling algorithms. We evaluate the algorithms in two different settings: the offline case, where computational resources are abundant and closely approximating the optimal strategy is a priority, and the online search case, where computational resources are limited and acting quickly is necessary. We perform a thorough experimental evaluation on six substantially different games for both settings. For the exact algorithms, the results show that our pruning techniques for backward induction dramatically improve the computation time required by the previous exact algorithms. For the sampling algorithms, the results provide unique insights into their performance and identify favorable settings and domains for different sampling algorithms.
- Published
- 2016