Documentation

CombinatorialGames.Misere.PFreeBlockingEnds

Ends of $\operatorname{pf}(\mathcal{U})$ are integers #

For a universe U carrying the hypotheses of misereGE_iff_promain (in particular ShortBlocking and ShortDeadEnding), every end of $\operatorname{pf}(\mathcal{U})$ is equivalent modulo $\operatorname{pf}(\mathcal{U})$ to an integer. This is the blocking analogue of isEnd_exists_intCast_misereEQ.

Throughout, larger integers are smaller games: a ≤ b in ℤ gives b ≥m pf(U) a.

The key step is misereGE_intCast_or_exists_leftMove_of_not_succ_misereGE: for every g ∈ pf(U) and every integer n ≤ 0, if n + 1 ≱ g then g ≥ n or some Left option of g is ≥ n - 1. Applied to a Left end g at the largest n ≤ 0 with n ≥ g, it gives g = n.

The main results are

theorem PFree.misereGE_intCast_of_forall_rightMoves {U : GameForm → Prop} [ShortUniverse U] [Form.HasInt U] [Form.Blocking U] {g : GameForm} {n : ℤ} (h_n : n ≤ -1) (h_g : PFreeSubset U g) (h_not_isEnd : ¬Form.IsEnd Player.right g) (h_out : Form.Misere.Outcome.MisereOutcome g ≠ Outcome.R) (h_moves : ∀ gr ∈ Moves.moves Player.right g, gr ≥m (PFreeSubset U)↑(n + 1) ∨ ∃ grl ∈ Moves.moves Player.left gr, grl ≥m (PFreeSubset U)↑n) :
g ≥m (PFreeSubset U)↑n

Sufficiency half of the comparison of g with a negative integer n: it is enough that every Right option of g is ≥ n + 1 or has a Left option ≥ n.

@[irreducible]

If $\operatorname{o}(G) = \mathscr{L}$ then $G \ge \overline{1}$.

theorem PFree.exists_rightMove_of_intCast_misereGE {U : GameForm → Prop} [OutcomeStable U] [Form.Short U] [ShortUniverse U] [Form.HasInt U] [Form.ClosedUnderAddNat U] [IntegerInvertible U] [Form.Blocking U] {g : GameForm} {n : ℤ} (h_n : n ≤ -1) (h_g : PFreeSubset U g) (h_not_isEnd : ¬Form.IsEnd Player.right g) (h_ge : ↑n ≥m (PFreeSubset U)g) :
∃ gr ∈ Moves.moves Player.right g, ↑(n + 1) ≥m (PFreeSubset U)gr

Necessity half of the comparison of a negative integer n with g: if n ≥ g and g is not a Right end, then some Right option of g is ≤ n + 1.

theorem PFree.not_intCast_misereGE_cases {U : GameForm → Prop} [OutcomeStable U] [Form.Short U] [ShortUniverse U] [Form.HasInt U] [Form.ClosedUnderAddNat U] [IntegerInvertible U] [Form.Blocking U] {g : GameForm} {n : ℤ} (h_n : n ≤ 0) (h_g : PFreeSubset U g) (h_not_ge : ¬↑n ≥m (PFreeSubset U)g) :
(∀ gr ∈ Moves.moves Player.right g, ¬↑(n + 1) ≥m (PFreeSubset U)gr) ∨ ∃ gl ∈ Moves.moves Player.left g, ¬↑(-1) ≥m (PFreeSubset U)gl ∧ ∀ glr ∈ Moves.moves Player.right gl, ¬↑n ≥m (PFreeSubset U)glr

Unwinding n ≱ g for an integer n ≤ 0: either no Right option of g is ≤ n + 1, or some Left option gl of g is not ≤ -1 and has no Right option ≤ n.

Unwinding 1 ≱ g when $\operatorname{o}(G) = \mathscr{R}$: some Left option gl of g is not ≤ 0 and has no Right option ≤ 1.

@[irreducible]
theorem PFree.misereGE_intCast_or_exists_leftMove_of_not_succ_misereGE {U : GameForm → Prop} [OutcomeStable U] [Form.Short U] [ShortUniverse U] [Form.HasInt U] [Form.ClosedUnderAddNat U] [IntegerInvertible U] [Form.Blocking U] {g : GameForm} (h_g : PFreeSubset U g) {n : ℤ} (h_n : n ≤ 0) (h_not_ge : ¬↑(n + 1) ≥m (PFreeSubset U)g) :
g ≥m (PFreeSubset U)↑n ∨ ∃ gl ∈ Moves.moves Player.left g, gl ≥m (PFreeSubset U)↑(n - 1)

For n ≤ 0: if n + 1 ≱ g then g ≥ n, or some Left option of g is ≥ n - 1.

If $G \in \operatorname{pf}(\mathcal{U})$ is a Left end, then it is equivalent to some non-positive integer.

If $G \in \operatorname{pf}(\mathcal{U})$ is a Right end, then it is equivalent to some non-negative integer.

If $G \in \operatorname{pf}(\mathcal{U})$ is an end, then it is equivalent to some integer.

Every end of $\operatorname{pf}(\mathcal{B})$ is equivalent to an integer.