catch_up_search_eq
theoremverified
For every fuel n, list l, scores and opening flag, the pruned search with flag true returns true exactly when the computable mirror's value is a win, and with flag false exactly when that value is not a loss.
Statement
theorem catch_up_search_eq (n : ℕ) : ∀ (l : List ℕ) (s_me s_opp : ℕ) (first : Bool),
(catch_up_search n l s_me s_opp first true = true ↔
catch_up_eval_list n l s_me s_opp first = .win) ∧
(catch_up_search n l s_me s_opp first false = true ↔
catch_up_eval_list n l s_me s_opp first ≠ .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
Classical.choiceQuot.soundpropext- Built on 5
- catch_up_searchPruned search over the Catch-Up game tree. With the last flag true it decides whether the player to move can force a win, with it false…
- catch_up_eval_listA computable mirror of catch_up_value_aux: the same Catch-Up recursion on a list of the remaining numbers, by structural recursion on a…
- catch_up_best_map_eq_win_iffThe best outcome over a mapped list is a win if and only if some element maps to a win.
- catch_up_best_map_ne_loss_iffThe best outcome over a mapped list is not a loss if and only if some element maps to something other than a loss.
- catch_up_search_childOne move of the search: if two pairs of Booleans decide 'win' and 'not loss' for outcomes E1 and E2, then choosing between the negated…
- Used by 1
- catch_up_value_icc_eq_draw_of_searchIf the pruned search on [1, ..., N] from scores 0, 0 at the opening move finds no forced win for the first player but finds that the first…
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.
/-- The pruned search decides 'win' and 'not loss' for the computable mirror. -/theorem catch_up_search_eq (n : ℕ) : ∀ (l : List ℕ) (s_me s_opp : ℕ) (first : Bool), (catch_up_search n l s_me s_opp first true = true ↔ catch_up_eval_list n l s_me s_opp first = .win) ∧ (catch_up_search n l s_me s_opp first false = true ↔ catch_up_eval_list n l s_me s_opp first ≠ .loss) := by induction n with | zero => intro l s_me s_opp first simp only [catch_up_search, catch_up_eval_list, if_true, Bool.false_eq_true, if_false, decide_eq_true_eq] refine ⟨?_, ?_⟩ <;> split_ifs <;> simp <;> omega | succ n ih => intro l s_me s_opp first cases l with | nil => simp only [catch_up_search, catch_up_eval_list, if_true, Bool.false_eq_true, if_false, decide_eq_true_eq] refine ⟨?_, ?_⟩ <;> split_ifs <;> simp <;> omega | cons h t => simp only [catch_up_search, catch_up_eval_list] by_cases hlt : s_me + (h :: t).sum < s_opp · simp only [hlt, if_true]; simp · simp only [hlt, if_false, Bool.not_true, Bool.not_false] have hc : ∀ x, (if first then (catch_up_eval_list n ((h :: t).erase x) s_opp (s_me + x) false).neg else if s_me + x ≥ s_opp then (catch_up_eval_list n ((h :: t).erase x) s_opp (s_me + x) false).neg else catch_up_eval_list n ((h :: t).erase x) (s_me + x) s_opp false) = (if (first || decide (s_opp ≤ s_me + x)) = true then (catch_up_eval_list n ((h :: t).erase x) s_opp (s_me + x) false).neg else catch_up_eval_list n ((h :: t).erase x) (s_me + x) s_opp false) := by intro x cases first <;> simp [ge_iff_le] simp only [hc, List.any_eq_true, catch_up_best_map_eq_win_iff, catch_up_best_map_ne_loss_iff] have child := fun x => catch_up_search_child ((first || decide (s_opp ≤ s_me + x)) = true) (catch_up_eval_list n ((h :: t).erase x) s_opp (s_me + x) false) (catch_up_eval_list n ((h :: t).erase x) (s_me + x) s_opp false) _ _ _ _ (ih _ _ _ _) (ih _ _ _ _) constructor · exact ⟨fun ⟨x, hx, hp⟩ => ⟨x, hx, (child x).1.1 hp⟩, fun ⟨x, hx, hp⟩ => ⟨x, hx, (child x).1.2 hp⟩⟩ · exact ⟨fun ⟨x, hx, hp⟩ => ⟨x, hx, (child x).2.1 hp⟩, fun ⟨x, hx, hp⟩ => ⟨x, hx, (child x).2.2 hp⟩⟩