AFTD Auto-Formalizing Theoretical Domains

catch_up_value_aux

def

The game value of a Catch-Up position for the player about to move. If nothing remains, compare scores. If even all remaining numbers cannot bring the mover level with the opponent, the mover loses. Otherwise the mover picks a number x; on the opening move, or if the mover's score reaches at least the opponent's, the turn passes (value negated); if still strictly behind, the same player picks again. The mover takes the best outcome over all choices.

Statement

noncomputable def catch_up_value_aux (remaining : Finset ℕ) (s_me s_opp : ℕ) (isFirstMove : Bool) : CatchUpOutcome
Defined in
google-deepmind/formal-conjectures, FormalConjectures/Paper/CatchUpConjecture.lean (definitions copied verbatim, renamed to top-level AFTD names)
Verified
01 Oct 2026
Axioms
none listed
Built on 3
  • 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.
  • CatchUpOutcome.bestGiven a list of outcomes, the best one for the player who chooses, under the order win > draw > loss (and loss if the list is empty).
Used by 27

Lean source view module on GitHub

/-- Value of a Catch-Up position under optimal play, for the player about to act: `remaining` numbers are untaken, `s_me`/`s_opp` are the scores, `isFirstMove` marks the opening move, where exactly one number is taken. Otherwise the mover keeps taking numbers while strictly behind and the turn passes once they reach at least the opponent's score; a mover who cannot catch up even with everything left loses. -/
noncomputable def catch_up_value_aux (remaining : Finset ℕ) (s_me s_opp : ℕ) (isFirstMove : Bool) : CatchUpOutcome :=
  if remaining = ∅ then
    if s_me > s_opp then .win
    else if s_opp > s_me then .loss
    else .draw
  else
    if s_me + remaining.sum (fun x => x) < s_opp then
      .loss
    else
      let moves := remaining.attach.toList
      let outcomes := moves.map (fun ⟨x, _⟩ =>
        let s_me' := s_me + x
        let remaining' := remaining.erase x
        if isFirstMove then
          (catch_up_value_aux remaining' s_opp s_me' false).neg
        else
          if s_me' ≥ s_opp then
            (catch_up_value_aux remaining' s_opp s_me' false).neg
          else
            catch_up_value_aux remaining' s_me' s_opp false)
      CatchUpOutcome.best outcomes
termination_by remaining.card
decreasing_by
  all_goals
    simpa using Finset.card_erase_lt_of_mem ‹_›
See it in the graphDiscuss this resultChallenge it