2019/07/11 by Stéphane Le Roux, Roux, Stéphane Le
Computer Science · #68N30 #91A02 #Artificial Intelligence in Games #Computability, Logic, AI Algorithms #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.1907.05128
openalex publication_date 2019/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two-player win/lose games of infinite duration are involved in several disciplines including computer science and logic. If such a game has deterministic winning strategies, one may ask how simple such strategies can get. The answer may help with actual implementation, or to win despite imperfect information, or to conceal sensitive information especially if the game is repeated. Given a concurrent two-player win/lose game of infinite duration, this article considers equivalence relations over histories of played actions. A classical restriction used here is that equivalent histories have equal length, hence time awareness. A sufficient condition is given such that if a player has winning strategies, she has one that prescribes the same action at equivalent histories, hence uniformization. The proof is fairly constructive and preserves finiteness of strategy memory, and counterexamples show relative tightness of the result. Several corollaries follow for games with states and colors.