---
title: "Using Double-Oracle Method and Serialized Alpha-Beta Search for Pruning in Simultaneous Move Games"
authors:
  - "Branislav Bosanský"
  - "Viliam Lisý"
  - "Jiri Cermak"
  - "Roman Vitek"
  - "Michal Pechoucek"
doi: ""
url: "https://ijcai.org/proceedings/2013/19"
pdf: "https://ijcai.org/proceedings/2013/0019.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "48-53"
track: ""
keywords:
---

# 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

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