Deterministic Graphical Games Revisited

Klas Olof Daniel Andersson; Kristoffer Arnsfelt Hansen; Peter Bro Miltersen; Troels Bjerre Sørensen

doi:10.1093/logcom/exq001

Deterministic Graphical Games Revisited

Klas Olof Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Department of Computer Science

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

Abstract

Starting from Zermelo’s classical formal treatment of chess, we trace through history the analysis of two-player win/lose/draw games with perfect information and potentially infinite play. Such chess-like games have appeared in many different research communities, and methods for solving them, such as retrograde analysis, have been rediscovered independently. We then revisit Washburn’s deterministic graphical games (DGGs), a natural generalization of chess-like games to arbitrary zero-sum payoffs. We study the complexity of solving DGGs and obtain an almost-linear time comparison-based algorithm for finding optimal strategies in such games. The existence of a linear time comparison-based algorithm remains an open problem.

Original language	English
Journal	Journal of Logic and Computation
Volume	22
Issue	2
Pages (from-to)	165-178
Number of pages	14
ISSN	0955-792X
DOIs	https://doi.org/10.1093/logcom/exq001
Publication status	Published - 2012

Access to Document

10.1093/logcom/exq001

http://logcom.oxfordjournals.org/content/22/2/165.abstract

Cite this

@article{577e8c7f82f14610995f418cd1115131,

title = "Deterministic Graphical Games Revisited",

abstract = "Starting from Zermelo{\textquoteright}s classical formal treatment of chess, we trace through history the analysis of two-player win/lose/draw games with perfect information and potentially infinite play. Such chess-like games have appeared in many different research communities, and methods for solving them, such as retrograde analysis, have been rediscovered independently. We then revisit Washburn{\textquoteright}s deterministic graphical games (DGGs), a natural generalization of chess-like games to arbitrary zero-sum payoffs. We study the complexity of solving DGGs and obtain an almost-linear time comparison-based algorithm for finding optimal strategies in such games. The existence of a linear time comparison-based algorithm remains an open problem. ",

author = "Andersson, {Klas Olof Daniel} and Hansen, {Kristoffer Arnsfelt} and Miltersen, {Peter Bro} and S{\o}rensen, {Troels Bjerre}",

year = "2012",

doi = "10.1093/logcom/exq001",

language = "English",

volume = "22",

pages = "165--178",

journal = "Journal of Logic and Computation",

issn = "0955-792X",

publisher = "Oxford University Press",

number = "2",

}

TY - JOUR

T1 - Deterministic Graphical Games Revisited

AU - Andersson, Klas Olof Daniel

AU - Hansen, Kristoffer Arnsfelt

AU - Miltersen, Peter Bro

AU - Sørensen, Troels Bjerre

PY - 2012

Y1 - 2012

N2 - Starting from Zermelo’s classical formal treatment of chess, we trace through history the analysis of two-player win/lose/draw games with perfect information and potentially infinite play. Such chess-like games have appeared in many different research communities, and methods for solving them, such as retrograde analysis, have been rediscovered independently. We then revisit Washburn’s deterministic graphical games (DGGs), a natural generalization of chess-like games to arbitrary zero-sum payoffs. We study the complexity of solving DGGs and obtain an almost-linear time comparison-based algorithm for finding optimal strategies in such games. The existence of a linear time comparison-based algorithm remains an open problem.

AB - Starting from Zermelo’s classical formal treatment of chess, we trace through history the analysis of two-player win/lose/draw games with perfect information and potentially infinite play. Such chess-like games have appeared in many different research communities, and methods for solving them, such as retrograde analysis, have been rediscovered independently. We then revisit Washburn’s deterministic graphical games (DGGs), a natural generalization of chess-like games to arbitrary zero-sum payoffs. We study the complexity of solving DGGs and obtain an almost-linear time comparison-based algorithm for finding optimal strategies in such games. The existence of a linear time comparison-based algorithm remains an open problem.

U2 - 10.1093/logcom/exq001

DO - 10.1093/logcom/exq001

M3 - Journal article

SN - 0955-792X

VL - 22

SP - 165

EP - 178

JO - Journal of Logic and Computation

JF - Journal of Logic and Computation

IS - 2

ER -

Deterministic Graphical Games Revisited

Abstract

Access to Document

Fingerprint

Cite this