AFTD Auto-Formalizing Theoretical Domains

catch_up_search_child

theoremverified

One move of the search: if two pairs of Booleans decide 'win' and 'not loss' for outcomes E1 and E2, then choosing between the negated searches of E1 (when the turn passes) and the searches of E2 decides 'win' and 'not loss' for the corresponding outcome, E1 negated or E2.

Statement

theorem catch_up_search_child (P : Prop) [Decidable P] (E1 E2 : CatchUpOutcome)
    (s1t s1f s2t s2f : Bool)
    (h1 : (s1t = true ↔ E1 = .win) ∧ (s1f = true ↔ E1 ≠ .loss))
    (h2 : (s2t = true ↔ E2 = .win) ∧ (s2f = true ↔ E2 ≠ .loss)) :
    ((if P then !s1f else s2t) = true ↔ (if P then E1.neg else E2) = .win) ∧
    ((if P then !s1t else s2f) = true ↔ (if P then E1.neg else E2) ≠ .loss)
Source
step towards the kernel checks catch_up_value_icc_four/seven/eight/eleven (Catch-Up: A Game in Which the Lead Alternates (Game & Puzzle Design 1(2), 2015), Table 2; computable mirror and pruned search of catch_up_value_aux)
Verified
06 Oct 2026
Axioms
propext
Built on 2
  • CatchUpOutcomeThe three possible outcomes of a game of Catch-Up, from the point of view of a fixed player: win, loss, draw.
  • CatchUpOutcome.negNegation of an outcome: win and loss are exchanged, draw is fixed. Used when the turn passes to the other player.
Used by 1
  • catch_up_search_eqFor every fuel n, list l, scores and opening flag, the pruned search with flag true returns true exactly when the computable mirror's…

Lean source view module on GitHub

/-- One child of a search node agrees with the outcome, through `neg` when the turn passes. -/theorem catch_up_search_child (P : Prop) [Decidable P] (E1 E2 : CatchUpOutcome)    (s1t s1f s2t s2f : Bool)    (h1 : (s1t = true ↔ E1 = .win) ∧ (s1f = true ↔ E1 ≠ .loss))    (h2 : (s2t = true ↔ E2 = .win) ∧ (s2f = true ↔ E2 ≠ .loss)) :    ((if P then !s1f else s2t) = true ↔ (if P then E1.neg else E2) = .win) ∧    ((if P then !s1t else s2f) = true ↔ (if P then E1.neg else E2) ≠ .loss) := by  split_ifs  · constructor    · rw [Bool.not_eq_true', ← Bool.not_eq_true, h1.2]; cases E1 <;> simp [CatchUpOutcome.neg]    · rw [Bool.not_eq_true', ← Bool.not_eq_true, h1.1]; cases E1 <;> simp [CatchUpOutcome.neg]  · exact h2
See it in the graphDiscuss this resultChallenge it