AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it