Changing the rules¶
This chapter changes Alba's real rules in Games/Alba/Rules.lean, three
times, and each time asks the tests and the proofs what they think. The
interesting question is not only what breaks, but why: some guarantees
follow a change by themselves, because of how they are stated, and some
break, for one of two quite different reasons.
Before you start, make sure your copy is clean:
After each change, run:
And to undo a change:
Change one: fewer rejections¶
Here is the limit on rejected proposals:
/-- Rejected proposals in a row that lose the game for the servants. -/
def rejectionLimit : Nat := 5
Make it 4. Nothing else in the rules says 5: tally compares with
rejectionLimit, so the game now ends on the fourth rejection in a row.
What follows by itself. Everything that uses the name. The rules text
every player is given is built from rejectionLimit, so it now says "4
rejections in a row and the Mirk win". The catalogue sends the number to the
browser, which draws the rejection track from it, and the ending text uses
it too. None of these needed editing.
The tests fail, two of them. One plays four rounds of rejections and expects the game to go on. The other plays five, and its fifth proposal is now refused, since the game is already over. Both were written for a limit of five, and both are right to complain: tests pin down the rules as they were.
The proofs all pass. Here is the guarantee about rejections:
/-- **Too many rejections in a row: the minions win.**
The rejection that brings the track to `rejectionLimit` ends the game. -/
theorem the_rejection_limit_loses_the_game (s : State) (minority : ¬ 2 * approvals s > s.players)
(atLimit : rejectionLimit ≤ s.rejections + 1) : (tally s).1.phase = .finished true :=
tally_at_rejection_limit s minority atLimit
and the lemma behind it:
/-- The rejection that reaches the limit ends the game, with the minions winning. -/
theorem tally_at_rejection_limit (s : State) (minority : ¬ 2 * approvals s > s.players)
(atLimit : rejectionLimit ≤ s.rejections + 1) : (tally s).1.phase = .finished true := by
unfold tally approvals finish at *
simp [minority, atLimit]
Neither says 5. They say rejectionLimit, so they make the same promise
about whatever the limit is, and the proof, which only matches the hypothesis
atLimit against the test in tally, works for any number. Try 6 as well:
one test fails (it expects five rejections to end the game), and the proofs
still pass.
This is the most useful habit in stating guarantees: say them with the rules'
own names, not with the numbers those names happen to have today. A
guarantee written with 5 would have broken here, and with a limit of six it
would have become false.
Change two: more of the Mirk¶
How many minions a table has:
Give tables of five and six three minions: change the first line to
| 5 | 6 => 3.
Everything passes, tests and proofs alike, and that's no accident. Look again at how the dealing guarantee is stated:
/-- **Every seat is dealt exactly one role, in the right numbers.**
For any number of players the game allows (5 to 10, which the configuration
enforces), a new game's roles are a shuffle of the role deck, which has one
role per seat, exactly one oracle, exactly one assassin, and the right number
on the minions' side. -/
theorem roles_are_dealt_correctly (n seed : Nat) (atLeast : 5 ≤ n) (atMost : n ≤ 10) :
(init n seed).roles.length = n ∧ (init n seed).roles.count .oracle = 1 ∧
(init n seed).roles.count .assassin = 1 ∧ (init n seed).roles.countP (·.minionSide) = minionCount n := by
-- The dealt roles are a rearrangement of the deck...
have dealt := init_roles n seed
-- ...and the deck has the right numbers.
obtain ⟨len, oracle, assassin, minions⟩ := roleDeck_numbers n atLeast atMost
exact ⟨dealt.length_eq.trans len, (dealt.count_eq _).trans oracle, (dealt.count_eq _).trans assassin,
(dealt.countP_eq _).trans minions⟩
It says the dealt roles have minionCount n on the minions' side, whatever
minionCount says. Its proof checks each table size with decide, which
works the new deck out and finds it right. The test of the deal compares
with minionCount n too. And the rules text players are given now says "5
players: 2 of the Licht, 3 of the Mirk", because it is built from the same
function. One edit, and every part of the game that depends on it moved
together.
Now go too far: | 5 | 6 => 5. The proof fails, at the decide for five
players, with Lean's message that decide proved the statement false. Work
out the deck: an oracle, an assassin, four more minions, and
5 - 5 - 1 = 0 servants. That's six roles for five seats. The statement is
false, so no proof could pass; the deck needs room for the oracle, so a table
of n can have at most n - 1 minions. The tests fail too, all over:
the deal test finds the wrong number of roles, and random games at five
players go wrong, because the game now thinks it has a sixth seat.
Change three: servants may fail¶
The rule that a servant can't fail a quest is in two places, as every rule
is: in Legal, as the last condition for .play, and in check, as the
last test for .play, the one that gives the reason "you may only play
success":
/-- Is this move legal? Returns the reason if not. -/
def check (s : State) (actor : Nat) : Move → Option String
| .propose team =>
if s.phase != .proposing then some "not the time to propose"
else if actor != s.leader then some "only the leader proposes"
else if team.length != teamSize s.players s.quest then some "wrong team size"
else if !team.Nodup then some "each player at most once"
else if !team.all (· < s.players) then some "no such player"
else none
| .ready =>
if s.phase != .discussing && s.phase != .deliberating then some "not the time to discuss"
else if actor ≥ s.players then some "no such player"
else if s.ready.contains actor then some "you are already ready"
else none
| .vote _ =>
if s.phase != .voting then some "not the time to vote"
else if actor ≥ s.players then some "no such player"
else if s.voters.contains actor then some "you have already voted"
else none
| .play success =>
if s.phase != .questing then some "not the time to play a card"
else if !s.team.contains actor then some "you are not on the team"
else if s.playedBy.contains actor then some "you have already played"
else if !success && !(s.role actor).minionSide then some "you may only play success"
else none
| .accuse target =>
if s.phase != .assassinating then some "not the time to accuse"
else if s.role actor != .assassin then some "only the assassin accuses"
else if actor ≥ s.players then some "no such player"
else if target ≥ s.players then some "no such player"
else if target == actor then some "accuse someone else"
else none
First, delete only that line (else if !success && …) from check, and
leave Legal alone.
The proof that fails is check_none_iff_legal, the bookkeeping lemma
that says check accepts exactly the Legal moves. Lean is left with the
goal (s.role a).minionSide = true, for a fail played by someone on the team
who hasn't played yet: check now accepts it, Legal still requires it to
come from the minions' side, and nothing proves they agree. That is what
stating a rule twice is for: if the two ever say different things, the
build stops.
Now also delete the condition from Legal, so the .play case ends at
actor ∉ s.playedBy. check and Legal agree again, and
check_none_iff_legal passes. Two guarantees fail:
quest_cards_follow_the_rulespromises "a fail only from the minions' side". Its proof was just "an accepted move isLegal", andLegalno longer says it.a_servant_never_failsis now false, and its proof stops where it used the condition that's gone.
Both are statements of exactly the rule you removed, so they should fail.
The honest repair is to delete a_servant_never_fails (it is no longer a
promise the game makes) and take the last part out of
quest_cards_follow_the_rules.
What follows by itself. The moves the engine offers: in Game.lean, the
Fail button is enabled exactly when check accepts a fail, so servants are
now offered it without anyone touching the interface. The test that a
servant may only play success fails, as it should.
Exercises¶
- Make two quests decide the game: change
questsToWinto2. Before running anything, predict: will the tests fail? The proofs? What will players be told? - Make the fourth quest need two Fails from six players up, not seven: in
failsNeeded, change7 ≤ nto6 ≤ n. Predict the same three things. - Make quest cards public: give the event
cardPlayeda second field,(success : Bool), pass the card inapply, and show it inGame.lean'sEvent.toJson. Does any test fail? Does any proof?
Answers
- Everything passes, tests and proofs. The guarantees about the end of
the game are stated with
questsToWin, like the rejection limit, and the rules text every player is given says "2 failed Quests" because it is built from the same name. -
Everything passes again, and the rules text for six players now gives the second Fail on the fourth quest, because it is built from
failsNeededitself, quest by quest:/-- The rules in plain words, for this many players: what every client is told. -/ def rulesText (n : Nat) : String := s!"{n} players: {n - minionCount n} of the {sideTitle false}, {minionCount n} of the {sideTitle true}. " ++ s!"Everyone knows their own role. The {sideTitle true} know each other; the {Role.oracle.title} knows who the {sideTitle true} are. " ++ s!"There are {(teamSizes n).length} {term "quest"}s. For each, the {term "leader"} proposes a {term "team"} " ++ s!"(sizes: {listNats (teamSizes n)}). The table discusses; when everyone has said " ++ s!"'{term "ready"}', everyone votes {term "approve"} or {term "reject"}, and the votes are revealed together. " ++ s!"A strict majority approves. If rejected, the next player becomes {term "leader"}; {rejectionLimit} rejections " ++ s!"in a row and the {sideTitle true} win. If approved, each {term "team"} member secretly plays {term "success"} or " ++ s!"{term "fail"}; the {sideTitle false} may only play {term "success"}. Only the number of {term "fail"}s is " ++ s!"revealed. A {term "quest"} fails if it gets enough {term "fail"}s (needed, {term "quest"} by {term "quest"}: " ++ s!"{listNats ((List.range (teamSizes n).length).map (failsNeeded n))}). {questsToWin} failed {term "quest"}s: the {sideTitle true} win. {questsToWin} successful {term "quest"}s: the " ++ s!"table talks it over, and once everyone has said '{term "readyToChoose"}', the " ++ s!"{Role.assassin.title} names one player; if that is the {Role.oracle.title}, the {sideTitle true} win, " ++ s!"otherwise the {sideTitle false} win. When the game is over, everyone's role is revealed."A rules text with its own copy of the rule (say, its own
7 ≤ n) would have gone on telling players and bots the old rule, and nothing would have noticed. -
No test fails, but a proof does: the lemma behind this guarantee.
/-- **Playing a quest card announces that it was played, never which card it was.** Take two plays by the same player, on two tables that are the same except for which player played which of the quest cards: the same players have played, and the same cards are on the table once this one is down, whichever card this player and each of the others played. If both are accepted, they announce exactly the same events: that the card was played, and, when it is the last, the quest's result with only its number of fails. -/ theorem playing_a_quest_card_reveals_no_card (u : State) (cs ct : List (Nat × Bool)) (a : Nat) (b b' : Bool) (samePlayers : cs.map (·.1) = ct.map (·.1)) (sameCards : (((a, b) :: cs).map (·.2)).Perm (((a, b') :: ct).map (·.2))) {s t : State} {e f : List Event} (first : step { u with cards := cs } a (.play b) = .ok (s, e)) (second : step { u with cards := ct } a (.play b') = .ok (t, f)) : e = f := by -- What each play announces is the same... have announced := apply_play_events_ignore_which_card u cs ct a b b' samePlayers sameCards -- ...and an accepted play announces exactly that. rw [(accepted_step first).2.2.2, (accepted_step second).2.2.2] exact announcedIt compares two plays that leave the same cards on the table, played by the same players, whichever card each one played, and promises the same events. With the card in the event, two such plays announce different events, so the promise is false and no proof could pass. This is the guarantee that keeps who played which card secret in the events;
whole_views_reveal_nothing_hiddencovers the rest of a player's view, but takes the events as given.