Abstract
For two-player games of perfect information such as Checkers, Chess, and Go we introduce “uniqueness” properties. A game position has a uniqueness property if a winning strategy—should one exist—is forced to be unique. Depending on the way that winning strategy is forced, a uniqueness property is classified as weak, strong, or global. We prove that any reasonable two-player game G is extendable to a game G * with the strong uniqueness property for both players, so that, e.g., QBF remains PSPACE-complete under this reduction. For global uniqueness, we introduce a simple game over Boolean formulas with this property, and prove that any reasonable two-player game with the global uniqueness property is reducible to it. We show that the class of languages that reduce to globally unique games equals Niedermeier and Rossmanith’s unambiguous alternation class UAP, which is in an interesting region between FewP and SPP.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Aida, S., Crasmaru, M., Regan, K. et al. Games with Uniqueness Properties. Theory Comput Systems 37, 29–47 (2004). https://doi.org/10.1007/s00224-003-1105-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-003-1105-7