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
- catch_up_value_aux_ne_draw_of_odd_sumIn Catch-Up, if the sum of remaining piece values and player scores is odd, the mover cannot achieve a draw.
- catch_up_value_aux_icc_opening_one_ne_win_iffWhen N ≥ 3, Player 2 does not win after Player 1 opens with 1 iff for every response y from {2, ..., N}, Player 1 does not lose from the…
- catch_up_value_aux_first_move_eq_of_eq_scoresIn a Catch-Up position where player scores are equal, every pick ends the mover's turn, so the game value with isFirstMove = true equals…
- catch_up_value_eq_aux_falseThe game value catch_up_value S is equal to catch_up_value_aux S 0 0 false.
- catch_up_value_aux_zero_zeroFor any nonempty set S of pieces, the auxiliary Catch-Up value from scores (0, 0) is the best outcome among all opening moves x ∈ S.
- catch_up_value_aux_ne_loss_iff_exists_ne_winFor any nonempty finite set S of pieces, Player 1 does not get outcome loss from equal scores 0 if and only if there exists an opening…
- catch_up_value_emptyThe value of Catch-Up on an empty set of pieces is a draw.
- catch_up_value_aux_loss_of_sum_ltIn a Catch-Up position, if the mover's score plus the sum of all remaining numbers is strictly less than the opponent's score, then the…
- catch_up_value_aux_singletonIn a Catch-Up position with a single remaining piece x, current score s_me, and opponent score s_opp, the game value for the mover is win…
- catch_up_value_eq_win_iffFor any nonempty finite set S of natural numbers, the game value catch_up_value S is CatchUpOutcome.win if and only if there exists some…
- catch_up_value_aux_eq_eval_listFor every fuel n, every duplicate-free list l of length at most n, and all scores and opening flags, the Catch-Up value of the finset of l…
- catch_up_value_eq_loss_iffFor any nonempty finite set S of natural numbers, the game value catch_up_value S is CatchUpOutcome.loss if and only if for every element…
- catch_up_value_aux_ne_loss_of_ne_winIn Catch-Up from equal scores 0, if an opening move x in S leads to a position where the second player does not win, then the first player…
- catch_up_value_aux_empty_eq_draw_iffIn a Catch-Up position with an empty set of remaining pieces, the game value for the mover is CatchUpOutcome.draw if and only if the…
- catch_up_value_eq_draw_iff_not_lossThe outcome of Catch-Up on a nonempty set S is a draw if and only if Player 1 does not lose from the initial position and Player 2 does…
- catch_up_value_triple_drawFor any natural numbers x < y < z such that x + y = z, the game value of Catch-Up played on the three-element set {x, y, z} is…
- catch_up_value_aux_icc_erase_max_ne_loss_iffAfter Player 1 opens with N in Catch-Up on {1, ..., N} with even triangular sum and N > 0, every response y satisfies y < N, so Player 2…
- catch_up_value_triple_win_of_sum_gtFor any natural numbers x < y < z such that x + y > z, the game value of Catch-Up played on the three-element set {x, y, z} is…
- catch_up_value_aux_icc_erase_ne_loss_iffAfter Player 1 opens with x from {1, ..., N} (with even triangular sum), Player 2 does not lose if and only if there exists a response…
- catch_up_value_aux_emptyIn a Catch-Up position with an empty set of remaining pieces, the game value for the mover is a win if the mover's score is strictly…
- catch_up_valueThe outcome of Catch-Up played on the finite set S of natural numbers, from the first player's point of view, assuming optimal play by…
- catch_up_value_aux_sub_scoresIn Catch-Up, when the mover's score s_me is at most the opponent's score s_opp, the game value equals that from scores 0 and s_opp - s_me.
- catch_up_value_aux_icc_opening_one_ne_win_threeIn Catch-Up on {1, 2, 3}, Player 2 does not win after Player 1 opens with 1.
- catch_up_value_aux_icc_zero_initialIn Catch-Up on the empty interval {1, ..., 0}, the auxiliary game value from scores 0, 0 is draw.
- catch_up_value_aux_ne_loss_iffIn Catch-Up with nonempty remaining pieces and score plus remaining sum at least opponent's score, the mover does not lose if and only if…
- catch_up_value_aux_add_scoresIn Catch-Up, adding a constant c to both the mover's and the opponent's score leaves the game value unchanged, because only score…
- catch_up_value_aux_icc_erase_ne_loss_of_geIn Catch-Up on {1, ..., N} with even triangular sum, if Player 2 has a response y ≥ x such that Player 1 does not win from the resulting…
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 ‹_›