Proceedings

Using Double-Oracle Method and Serialized Alpha-Beta Search for Pruning in Simultaneous Move Games

Branislav Bosanský, Viliam Lisý, Jiri Cermak, Roman Vitek, Michal Pechoucek

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 48-53.

Abstract

We focus on solving two-player zero-sum extensive-form games with perfect information and simultaneous moves. In these games, both players fully observe the current state of the game where they simultaneously make a move determining the next state of the game. We solve these games by a novel algorithm that relies on two components: (1) it iteratively solves the games that correspond to a single simultaneous move using a double-oracle method, and (2) it prunes the states of the game using bounds on the sub-game values obtained by the classical Alpha-Beta search on a serialized variant of the game. We experimentally evaluate our algorithm on the Goofspiel card game, a pursuit-evasion game, and randomly generated games. The results show that our novel algorithm typically provides significant running-time improvements and reduction in the number of evaluated nodes compared to the full search algorithm.

Branislav Bošanský, Viliam Lisý, Jiri Cermak, Roman Vitek, and Michal Pechoucek. 2013. Using Double-Oracle Method and Serialized Alpha-Beta Search for Pruning in Simultaneous Move Games. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 48–53. https://ijcai.org/proceedings/2013/19
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards