Abstract
Game Logic is an excellent setting to study proofs-about-programs via the interpretation of those proofs as programs, because constructive proofs for games correspond to effective winning strategies to follow in response to the opponent’s actions. We thus develop Constructive Game Logic, which extends Parikh’s Game Logic (GL) with constructivity and with first-order programs à la Pratt’s first-order dynamic logic (DL). Our major contributions include:
- a novel realizability semantics capturing the adversarial dynamics of games, 2. a natural deduction calculus and operational semantics describing the computational meaning of strategies via proof-terms, and 3. theoretical results including soundness of the proof calculus w.r.t. realizability semantics, progress and preservation of the operational semantics of proofs, and Existential Properties on support of the extraction of computational artifacts from game proofs. Together, these results provide the most general account of a Curry-Howard interpretation for any program logic to date, and the first at all for Game Logic.
Introduction
In the realm of formal methods, program logics such as Hoare logic or Dynamic Logic (DL) are indispensable for verifying software correctness. Game Logic (GL) extends these concepts to model interactions between two competing agents—traditionally termed Angel (the system) and Demon (the environment). While classical GL provides a robust framework for reasoning about these interactions, it suffers from a significant limitation regarding program synthesis: it permits non-constructive proofs. A classical proof may establish the existence of a winning strategy through the law of excluded middle without providing a computable method to execute that strategy.
This paper introduces Constructive Game Logic (CGL), the first framework to apply the "proofs-as-programs" (Curry-Howard) paradigm to Game Logic. By enforcing constructivity, CGL ensures that any proof of a player's ability to win is equivalent to a functional program—a computable, winning strategy.
Methodology
CGL is constructed from the ground up to support first-order programs, allowing for the modeling of complex, state-based games where variables evolve over time. The framework relies on several foundational pillars:
- Realizability Semantics: The logic moves beyond simple truth values. It defines what it means for a program (a realizer) to witness the truth of a formula. In the context of games, a realizer is a higher-order function that computes responses to an opponent's moves.
- Asymmetric Adversarial Dynamics: A novel aspect of CGL's semantics is the interaction between a constructive Angel (who must be computable) and a classical Demon (representing an arbitrary, potentially non-computable environment).
- Natural Deduction Calculus: The authors provide a formal proof system where every logical rule is associated with a specific proof term. These terms function as code in a functional programming language.
- Operational Semantics: The framework defines how proof terms evaluate, ensuring that the extraction of a strategy is computationally sound and type-safe.
Key Insights: Constructivity as Effectiveness
The central insight of this work is that in a game-theoretic setting, the requirement for constructivity is exactly what makes a strategy "effective" or executable by a computer. This leads to the Strategy Property: for any provable game modality ($\langle \alpha \rangle \phi$), there exists an algorithm to extract a computable winning strategy.
CGL effectively bridges logic and type theory by treating "winning a game" as a type. Because the Angel's strategy is a realizer, it acts as a function that accepts any move from the Demon and produces a valid counter-move, maintaining the system's safety or goal state.
Results and Validation
The theoretical robustness of CGL is established through several key results:
- Soundness: The proof calculus is sound with respect to the realizability semantics; a proof guarantees the existence of a realizer.
- Progress and Preservation: Standard type-safety properties are proven for proof terms, ensuring strategy evaluation never stalls and maintains logical consistency.
- Existential and Disjunction Properties: The logic can extract specific witnesses for existential quantifiers and determine which branch of a disjunction leads to a win based on the current state.
The logic was validated using classic benchmarks, including the discrete game of Nim and the continuous-style Cake-cutting problem (using rational values). These examples demonstrate CGL's ability to handle both discrete and fractional game states.
Conclusion and Future Work
Constructive Game Logic provides the most general account to date of a Curry-Howard interpretation for program logics. While the current implementation utilizes rational numbers ($\mathbb{Q}$), future work aims to extend CGL to handle constructive reals, which are necessary for high-precision continuous systems. A primary goal is the development of Hybrid Games, merging CGL with Differential Game Logic (dGL) to synthesize controllers for safety-critical systems like autonomous vehicles.
Summary updated