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

Bosansky, Branislav (Czech Technical University in Prague) | Lisy, Viliam (Czech Technical University in Prague) | Cermak, Jiri (Czech Technical University in Prague) | Vitek, Roman (Czech Technical University in Prague) | Pechoucek, Michal (Czech Technical University in Prague)

AAAI Conferences 

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.

Duplicate Docs Excel Report

Title
None found

Similar Docs  Excel Report  more

TitleSimilarity
None found