A General Theory for Determined Two-player Games #
Nothing here is specific about PDL, but we give a general
definition of games and show that one of the two players
must have a winning strategy: gamedet at the end.
Games #
@[instance_reducible]
Two-player game with
- perfect information
- sequential moves (i.e. only one player moves at each position)
- finitely many moves at each step (aka finitely branching)
- a well-founded relation to ensure that the game ends.
- Pos : Type
Positions in the game.
Whose turn is it?
What are the available moves?
- wf : WellFoundedRelation Pos
A wellfounded relation on positions.
- move_rel (p next : Pos) : next ∈ moves p → WellFoundedRelation.rel next p
Every move goes a step down in the relation.
Instances
@[instance_reducible]
This seems a bit hacky, but makes termination_by (p : g.Pos) work in winner and elsewhere.
If the instance causes trouble, change to termination_by g.wf.2.wrap p via WellFounded.wrap.
Equations
theorem Game.no_moves_of_no_rel {g : Game} {p : Pos} (no_rel : ∀ (q : Pos), ¬WellFoundedRelation.rel q p) :
If the bound bound is zero then there are no more moves.
Strategies #
Equations
Instances For
Good positions #
Equations
- good_strat i p turn nempty = if W : good i p then have E := ⋯; ⟨E.choose, ⋯⟩ else choose_move nempty
Instances For
Cones #
The cone of all positions reachable from p assuming that i plays sI.
- nil {i : Player} {g : Game} {sI : Strategy g i} {p : Game.Pos} : inMyCone sI p p
- myStep {i : Player} {g : Game} {sI : Strategy g i} {p q : Game.Pos} : inMyCone sI p q → ∀ (has_moves : q.moves.Nonempty) (h : Game.turn q = i), inMyCone sI p ↑(sI q h has_moves)
- oStep {i : Player} {g : Game} {sI : Strategy g i} {p q r : Game.Pos} : inMyCone sI p q → Game.turn q = other i → r ∈ Game.moves q → inMyCone sI p r
Instances For
Zermelo's Theorem #
theorem good_strat_winning {g : Game} {i : Player} {p : Game.Pos} (W : good i p) :
winning (good_strat i) p
Additional Helper Theorems #
theorem not_in_cone_of_move {i : Player} {g : Game} {p q : Game.Pos} (q_in : q ∈ Game.moves p) (sI : Strategy g i) :
theorem winning_of_whatever_other_move {i : Player} {g : Game} {sI : Strategy g i} {p : Game.Pos} (h : Game.turn p = other i) (sI_wins_p : winning sI p) (m : ↥(Game.moves p)) :
winning sI ↑m
Helper for gameP_general.