Documentation

CombinatorialGames.Game.Loopy.Outcome

Outcomes of loopy games #

We define when a loopy game is a win, a draw, or a loss with each player going first (under the normal play convention).

In particular, this proves the correctness of the characterization of the order in IGame. See the theorems:

inductive LGame.IsWin :
Player → LGame → Prop

IsWin p x means that player p wins x going first.

Instances For
    inductive LGame.IsLoss :
    Player → LGame → Prop

    IsLoss p x means that player p loses x going first.

    Instances For
      theorem LGame.isWin_iff_exists {p : Player} {x : LGame} :
      IsWin p x ↔ ∃ y ∈ moves p x, IsLoss (-p) y
      theorem LGame.isLoss_iff_forall {p : Player} {x : LGame} :
      IsLoss p x ↔ ∀ y ∈ moves p x, IsWin (-p) y
      theorem LGame.IsLoss.isWin_of_mem_moves {p : Player} {x y : LGame} (h : IsLoss p x) (hy : y ∈ moves p x) :
      IsWin (-p) y
      theorem LGame.not_isWin_iff_forall {p : Player} {x : LGame} :
      ¬IsWin p x ↔ ∀ y ∈ moves p x, ¬IsLoss (-p) y
      theorem LGame.not_isLoss_iff_exists {p : Player} {x : LGame} :
      ¬IsLoss p x ↔ ∃ y ∈ moves p x, ¬IsWin (-p) y

      A surviving strategy for player p, going second.

      This is a set of states, such that for every move the opposite player makes, p can bring it back to the set.

      You can think of this as a nonconstructive version of the more common definition of a strategy, which gives an explicit answer for every reachable state.

      Equations
      Instances For
        theorem LGame.IsStrategy.neg {p : Player} {s : Set LGame} (h : IsStrategy p s) :
        IsStrategy (-p) (-s)
        @[simp]
        theorem LGame.IsStrategy.iUnion {p : Player} {ι : Sort u_1} {s : ι → Set LGame} (h : ∀ (i : ι), IsStrategy p (s i)) :
        IsStrategy p (⋃ (i : ι), s i)
        theorem LGame.IsStrategy.sUnion {p : Player} {S : Set (Set LGame)} (h : ∀ s ∈ S, IsStrategy p s) :
        theorem LGame.IsStrategy.not_isWin' {p : Player} {x : LGame} {s : Set LGame} (h : IsStrategy (-p) s) (hx : x ∈ s) :
        theorem LGame.IsStrategy.not_isWin {p : Player} {x : LGame} {s : Set LGame} (h : IsStrategy p s) (hx : x ∈ s) :
        ¬IsWin (-p) x
        @[simp]
        theorem LGame.not_isLoss_of_isWin {p : Player} {x : LGame} (h : IsWin p x) :
        @[simp]
        theorem LGame.not_isWin_of_isLoss {p : Player} {x : LGame} (h : IsLoss p x) :
        @[simp]
        theorem LGame.isWin_neg {p : Player} {x : LGame} :
        IsWin p (-x) ↔ IsWin (-p) x
        theorem LGame.IsWin.neg {p : Player} {x : LGame} (h : IsWin p x) :
        IsWin (-p) (-x)
        @[simp]
        theorem LGame.isLoss_neg {p : Player} {x : LGame} :
        IsLoss p (-x) ↔ IsLoss (-p) x
        theorem LGame.IsLoss.neg {p : Player} {x : LGame} (h : IsLoss p x) :
        IsLoss (-p) (-x)
        def LGame.IsDraw (p : Player) (x : LGame) :

        IsDraw p x means that p draws x going first.

        Equations
        Instances For
          @[simp]
          theorem LGame.IsDraw.not_isWin {p : Player} {x : LGame} (h : IsDraw p x) :
          @[simp]
          theorem LGame.IsDraw.not_isLoss {p : Player} {x : LGame} (h : IsDraw p x) :
          @[simp]
          theorem LGame.isDraw_neg {p : Player} {x : LGame} :
          IsDraw p (-x) ↔ IsDraw (-p) x
          theorem LGame.IsDraw.neg {p : Player} {x : LGame} (h : IsDraw p x) :
          IsDraw (-p) (-x)
          noncomputable def LGame.outcomeFor (p : Player) (x : LGame) :

          outcomeFor p x is the outcome of x with p going first.

          Equations
          Instances For
            @[simp]
            theorem LGame.outcomeFor_neg {p : Player} {x : LGame} :

            Outcome calculations #

            dud #

            @[simp]

            on #

            off #

            tis and tisn #

            Outcomes of well-founded games #

            @[simp]

            Well-founded games can never be tied; they must end eventually.

            theorem IGame.fuzzy_zero_iff_isWin {x : IGame} :
            x ‖ 0 ↔ ∀ (p : Player), LGame.IsWin p (toLGame x)
            theorem IGame.equiv_zero_iff_isLoss {x : IGame} :
            x ≈ 0 ↔ ∀ (p : Player), LGame.IsLoss p (toLGame x)