Algorithms for computing strategies in two-player simultaneous move games

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00300256" target="_blank" >RIV/68407700:21230/16:00300256 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1016/j.artint.2016.03.005" target="_blank" >http://dx.doi.org/10.1016/j.artint.2016.03.005</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.artint.2016.03.005" target="_blank" >10.1016/j.artint.2016.03.005</a>

Result language

angličtina

Original language name

Algorithms for computing strategies in two-player simultaneous move games

Original language description

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. (C) 2016 Elsevier B.V. All rights reserved.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2016

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Artificial Intelligence

ISSN

0004-3702

e-ISSN

—

Volume of the periodical

237

Issue of the periodical within the volume

August

Country of publishing house

GB - UNITED KINGDOM

Number of pages

40

Pages from-to

1-40

UT code for WoS article

000377828500001

EID of the result in the Scopus database

—