catch_up_search
def
Pruned 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 whether they can avoid losing; at their own moves it stops at the first good move.
Statement
def catch_up_search : ℕ → List ℕ → ℕ → ℕ → Bool → Bool → Bool- 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
- none listed
- Used by 2
- 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…
- 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
/-- Pruned search: `true` asks whether the mover can force a win, `false` whether they can avoid losing. -/ def catch_up_search : ℕ → List ℕ → ℕ → ℕ → Bool → Bool → Bool := fun | 0, _, s_me, s_opp, _, w => if w then decide (s_opp < s_me) else decide (s_opp ≤ s_me) | n + 1, l, s_me, s_opp, first, w => match l with | [] => if w then decide (s_opp < s_me) else decide (s_opp ≤ s_me) | _ :: _ => if s_me + l.sum < s_opp then false else l.any fun x => if first || decide (s_opp ≤ s_me + x) then !(catch_up_search n (l.erase x) s_opp (s_me + x) false (!w)) else catch_up_search n (l.erase x) (s_me + x) s_opp false w