What always holds¶
Some facts about a game are true at every moment: in Snap, there are always exactly 52 cards in play, and a game in progress is always below its flip limit. Facts like these are called invariants, and they are the most useful kind of guarantee: a bug that breaks one shows up in every game, not just in the cases a test thought of.
You prove an invariant in two parts:
- It holds at the start: every new game has it.
- Every move keeps it: if it holds before an accepted move, it holds after.
Together, these mean it holds after any number of moves, in any game.
No card is created or lost¶
What does "the same cards" mean, exactly? Not the same list: cards move
between piles, and piles are in different orders. It means the same cards,
counted with how many times each appears, in any order. That is a
permutation, List.Perm:
(¬ is not.) The rules gather every card in play into one list, in a fixed
order:
/-- Every card in play, in a fixed order. Conservation is stated over this. -/
def cards (s : State) : List Card :=
s.hand0.down ++ s.hand0.up ++ s.hand1.down ++ s.hand1.up
It holds at the start. A new game is dealt from the shuffled deck:
/-- **Every new game is dealt exactly the full deck.**
The shuffle only reorders the deck, and dealing hands each card to one
player or the other. -/
theorem new_games_hold_the_full_deck (seed maxFlips : Nat) : (State.deal seed maxFlips).cards.Perm deck := by
-- The two stacks are the shuffled deck's even and odd positions...
unfold State.deal State.cards
simp only [List.append_nil]
-- ...which together are the shuffled deck, and that is the deck reordered.
exact (alternate_deal_perm _ 0).trans (by simpa using Proofs.shuffle_perm _ deck.toArray)
The proof has two steps. First, the shuffle only reorders the deck: that is
shuffle_perm, proved once in the engine for every game. Second, dealing
alternately loses nothing:
/-- Dealing alternately loses nothing: the cards at even positions and the
cards at odd positions are, together, the whole list (positions counted from
`k`). -/
theorem alternate_deal_perm {α : Type} (l : List α) (k : Nat) :
((l.zipIdx k).filterMap fun (c, i) => if i % 2 == 0 then some c else none) ++
((l.zipIdx k).filterMap fun (c, i) => if i % 2 == 1 then some c else none) |>.Perm l := by
induction l generalizing k with
| nil => simp
| cons a l ih =>
have rest := ih (k + 1)
simp only [beq_iff_eq] at rest
by_cases even : k % 2 = 0
· have odd : k % 2 ≠ 1 := by omega
simpa [even, odd] using rest.cons a
· have odd : k % 2 = 1 := by omega
simpa [even, odd] using List.perm_middle.trans (rest.cons a)
This is a proof by induction, the way to prove something about every
list. A list is either empty (nil) or an element in front of a shorter list
(cons a l). So it's enough to prove the empty case, and to prove the
cons a l case while assuming the fact for l, which is called ih (the
induction hypothesis). For an empty list there is nothing to deal. For
a :: l, the first card a goes to one player or the other, depending on
whether its position k is even or odd, and the rest of the deal is ih. In
the odd case, a lands in the middle of the joined list, and
List.perm_middle says that's still a permutation.
Every move keeps it. This is the guarantee:
/-- **No card is ever created or destroyed.**
Whatever action is accepted, the cards in play afterwards are exactly the
cards in play before, just rearranged. -/
theorem accepted_actions_conserve_cards (accepted : step s a act = .ok (s', evs)) :
s'.cards.Perm s.cards := by
-- An accepted action is some player's flip or snap.
obtain ⟨-, p, -, ⟨-, flipped⟩ | ⟨-, snapped⟩⟩ := accepted_step accepted
· -- A flip only moves a card within the flipping player's own hand.
exact flip_conserves flipped
· -- A snap only moves face-up piles between the players.
rw [snapped]
exact snap_conserves s p
A new tactic: obtain takes apart a fact into its pieces. The lemma
accepted_step says that an accepted action was some player's flip or some
player's snap. obtain ⟨-, p, -, ⟨-, flipped⟩ | ⟨-, snapped⟩⟩ names the
pieces it needs (- drops the others) and splits the two cases, each proved
by its own lemma. Here is the one for a snap:
/-- A snap moves face-up piles between the two players: no card is created or lost. -/
theorem snap_conserves (s : State) (p : Fin 2) : (snap s p).1.cards.Perm s.cards := by
apply perm_of_count; intro c
match p with
| 0 => unfold snap; split <;>
simp [State.setHand, State.cards, State.hand, other, List.count_append, List.count_reverse] <;> omega
| 1 => unfold snap; split <;>
simp [State.setHand, State.cards, State.hand, other, List.count_append, List.count_reverse] <;> omega
Rather than track where each card goes, this counts: for every card c, c
appears as often after as before. simp works out the counts of each pile,
and omega, a tactic that solves arithmetic, finishes. match p with checks
both players.
Putting the two halves together:
/-- **A game dealt from the full deck always holds exactly the full deck.**
The previous guarantee, applied one accepted action at a time. -/
theorem full_deck_stays_full (full : s.cards.Perm deck) (accepted : step s a act = .ok (s', evs)) :
s'.cards.Perm deck :=
(accepted_actions_conserve_cards accepted).trans full
.trans chains permutations: if the new cards are a reordering of the old,
and the old are a reordering of the deck, the new are a reordering of the
deck.
Below the flip limit¶
The second invariant is defined as a statement of its own:
/-- A game in progress has used fewer flips than its cap. -/
def BelowCap (s : State) : Prop := s.phase = .playing → s.flips < s.maxFlips
→ is implies: if the game is being played, the flips so far are below the
limit. A finished game can be anywhere. A def whose type is Prop defines
a property, which theorems can then state and prove.
At the start:
/-- **A new game starts below its flip cap.**
The config rejects a cap of zero, so any game that can be created satisfies
this. -/
theorem new_game_below_cap (seed maxFlips : Nat) (positive : 0 < maxFlips) :
BelowCap (State.deal seed maxFlips) := by
-- A fresh deal has made no flips.
intro _
show 0 < maxFlips
exact positive
intro _ takes the hypothesis of the → (that the game is being played,
which isn't needed here), and show restates the goal in a simpler form Lean
agrees is the same. Note the hypothesis positive: with a limit of zero, a
new game would already be at its limit. This is why Snap's configuration
refuses a limit of zero: the proof needed it, and the configuration makes
sure it's always true.
And kept by every move:
/-- **Every accepted action leaves a game in progress below its cap.**
Both kinds of action finish by `settle`, which ends the game as a draw as soon
as the cap is reached. -/
theorem accepted_actions_stay_below_cap (accepted : step s a act = .ok (s', evs)) :
BelowCap s' := by
obtain ⟨-, p, -, ⟨-, flipped⟩ | ⟨-, snapped⟩⟩ := accepted_step accepted
· obtain ⟨t, settled, -, -⟩ := flip_counts flipped
rw [settled]; exact settle_below_cap t
· obtain ⟨t, settled⟩ := snap_settles s p
rw [snapped, settled]; exact settle_below_cap t
Both kinds of move end with settle, and settle ends the game as a draw as
soon as the limit is reached, so a game still in progress after settle is
below the limit.
What isn't proven¶
Notice what these guarantees don't say. They don't say that every game ends: a snap doesn't count as a flip, so a game in which players only ever snap never reaches its limit. That's true of real Snap too. A guarantee says exactly what it says, and no more, and part of reading proofs is noticing what's missing.
Exercises¶
- Prove that after any accepted move in a game holding the full deck,
exactly 52 cards are in play. Hint:
List.Perm.length_eqturns a permutation into equal lengths. - Prove that two accepted moves in a row keep the full deck. Use
full_deck_stays_fulltwice.
Solution
theorem always_52 {s s' : State} {a : Nat} {act : Action} {evs : List Event}
(full : s.cards.Perm deck) (accepted : step s a act = .ok (s', evs)) : s'.cards.length = 52 :=
(Proofs.Snap.full_deck_stays_full full accepted).length_eq
theorem two_moves_keep_the_deck {s s' s'' : State} {a b : Nat} {act act' : Action} {evs evs' : List Event}
(full : s.cards.Perm deck)
(first : step s a act = .ok (s', evs)) (second : step s' b act' = .ok (s'', evs')) :
s''.cards.Perm deck :=
Proofs.Snap.full_deck_stays_full (Proofs.Snap.full_deck_stays_full full first) second
Both proofs are just calls: theorems are functions, and the hypotheses
are their arguments. In the first, Lean works out deck.length to 52
by itself.