Aarhus University Seal / Aarhus Universitets segl

Deterministic Graphical Games Revisited

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

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 languageEnglish
JournalJournal of Logic and Computation
Volume22
Issue2
Pages (from-to)165-178
Number of pages14
ISSN0955-792X
DOIs
Publication statusPublished - 2012

See relations at Aarhus University Citationformats

ID: 44912901