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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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