Skip to content

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:

git status            # nothing changed in Games/

After each change, run:

make test             # what the tests say
make proofs           # what the proofs say

And to undo a change:

git restore Games/Alba/Rules.lean

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:

def minionCount : Nat → Nat
  | 5 | 6 => 2
  | 7 | 8 | 9 => 3
  | _ => 4

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_rules promises "a fail only from the minions' side". Its proof was just "an accepted move is Legal", and Legal no longer says it.
  • a_servant_never_fails is 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

  1. Make two quests decide the game: change questsToWin to 2. Before running anything, predict: will the tests fail? The proofs? What will players be told?
  2. Make the fourth quest need two Fails from six players up, not seven: in failsNeeded, change 7 ≤ n to 6 ≤ n. Predict the same three things.
  3. Make quest cards public: give the event cardPlayed a second field, (success : Bool), pass the card in apply, and show it in Game.lean's Event.toJson. Does any test fail? Does any proof?
Answers
  1. 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.
  2. Everything passes again, and the rules text for six players now gives the second Fail on the fourth quest, because it is built from failsNeeded itself, 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.

  3. 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 announced
    

    It 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_hidden covers the rest of a player's view, but takes the events as given.