Extracting winning strategies in update games

Imran Khaliq, Bakhadyr Khoussainov, Jiamou Liu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper investigates algorithms for extracting winning strategies in two-player games played on finite graphs. We focus on a special class of games called update games. We present a procedure for extracting winning strategies in update games by constructing strategies explicitly. This is based on an algorithm that solves update games in quadratic time. We also show that solving update games with a bounded number of nonkdeterministic nodes takes linear time.

Original languageEnglish
Title of host publicationModels of Computation in Context - 7th Conference on Computability in Europe, CiE 2011, Proceedings
Pages142-151
Number of pages10
DOIs
Publication statusPublished - 26 Sep 2011
Externally publishedYes
Event7th Conference on Computability in Europe, CiE 2011 - Sofia, Bulgaria
Duration: 27 Jun 20112 Jul 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6735 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th Conference on Computability in Europe, CiE 2011
CountryBulgaria
CitySofia
Period27/06/112/07/11

    Fingerprint

Cite this

Khaliq, I., Khoussainov, B., & Liu, J. (2011). Extracting winning strategies in update games. In Models of Computation in Context - 7th Conference on Computability in Europe, CiE 2011, Proceedings (pp. 142-151). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6735 LNCS). https://doi.org/10.1007/978-3-642-21875-0_15