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

摘要

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 pursuitevasion 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.