Skip to content

The numbers

Much of Alba depends on how many sit at the table: how many are of the Mirk, how big each Band is, how many Fails sink a Quest. This chapter reads those numbers in Games/Alba/Rules.lean, and the proof that every game is dealt the right roles.

Roles and sides

inductive Role where
  | servant | oracle | minion | assassin
  deriving DecidableEq, Repr, Inhabited

Four roles, and two sides. Which side a role is on is a function:

/-- The assassin and the minions are on the minions' side. -/
def Role.minionSide : Role → Bool
  | .minion | .assassin => true
  | _ => false

The first line matches two alternatives at once: .minion | .assassin means either of these. The _ catches everything else. Because the side is worked out from the role, rather than stored beside it, a player can never be an assassin on the servants' side: there is no way to write that down.

/-- info: Games.Alba.Role.oracle -/
#guard_msgs in
#eval Role.oracle

/-- info: [false, false, true, true] -/
#guard_msgs in
#eval [Role.servant, .oracle, .minion, .assassin].map (·.minionSide)

(·.minionSide) is short for fun r => r.minionSide: the · (type \.) stands for the argument.

Matching on numbers

How many minions a table has:

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

This is the same pattern matching you met with alternatives, but on numbers. Each line lists the numbers it handles, and the last line, _, catches every number not listed. Lean requires the lines to cover every Nat, and there are infinitely many, so a catch-all is needed.

/-- info: [2, 2, 3, 3, 3, 4] -/
#guard_msgs in
#eval [5, 6, 7, 8, 9, 10].map minionCount

The catch-all has a cost: it answers for numbers that make no sense too.

/-- info: [4, 4, 4] -/
#guard_msgs in
#eval [0, 4, 100].map minionCount

A table of 100 is told it has 4 minions. Nothing in minionCount stops it. What stops it is the game's configuration, in Game.lean, which refuses any number of players outside five to ten. So every proof about dealing has to say "for five to ten players", as you'll see below.

The sizes of the Bands work the same way, giving a list of five sizes, one per quest:

def teamSizes : Nat → List Nat
  | 5 => [2, 3, 2, 3, 3]
  | 6 => [2, 3, 4, 3, 4]
  | 7 => [2, 3, 3, 4, 4]
  | _ => [3, 4, 4, 5, 5]
/-- How many players quest `q` needs. -/
def teamSize (n q : Nat) : Nat := (teamSizes n).getD q 0

getD q 0 is the qth element of the list, counting from 0, or 0 if there isn't one (the D is for default):

/-- info: [2, 3, 2, 3, 3] -/
#guard_msgs in
#eval teamSizes 5

/-- info: 4 -/
#guard_msgs in
#eval teamSize 7 3

/-- info: 0 -/
#guard_msgs in
#eval teamSize 7 5

And how many Fails it takes to fail a quest:

/-- How many fails make quest `q` fail. -/
def failsNeeded (n q : Nat) : Nat := if 7 ≤ n ∧ q = 3 then 2 else 1

This one isn't a match, but an if with a condition: ∧ is and (type \and), and ≤ is at most (type \le). Quests count from 0, so q = 3 is the fourth quest. Here is every table's row:

/-- info: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 2, 1], [1, 1, 1, 2, 1], [1, 1, 1, 2, 1], [1, 1, 1, 2, 1]] -/
#guard_msgs in
#eval [5, 6, 7, 8, 9, 10].map fun n => [0, 1, 2, 3, 4].map (failsNeeded n)

From seven players up, the fourth quest needs two Fails.

Named numbers

Two numbers in the rules get names of their own:

/-- Rejected proposals in a row that lose the game for the servants. -/
def rejectionLimit : Nat := 5
/-- Successful (or failed) quests that decide the game. -/
def questsToWin : Nat := 3

A def with no arguments is a constant. Naming them means the rules say rejectionLimit rather than 5 wherever the number is used, and so does everything else that needs it: the rules text players read, the track the browser draws, the ending text. Change the definition and they all change with it. The last chapter does exactly that.

Dealing the roles

The roles dealt to a table, before shuffling:

/-- The roles dealt, before shuffling. -/
def roleDeck (n : Nat) : List Role :=
  [.oracle, .assassin] ++ List.replicate (minionCount n - 1) .minion ++
    List.replicate (n - minionCount n - 1) .servant

One oracle and one assassin, then the rest of the minions, then the servants. List.replicate k x is a list of k copies of x, and ++ joins lists:

/-- info: [Games.Alba.Role.servant, Games.Alba.Role.servant, Games.Alba.Role.servant] -/
#guard_msgs in
#eval List.replicate 3 Role.servant

/--
info: [Games.Alba.Role.oracle,
 Games.Alba.Role.assassin,
 Games.Alba.Role.minion,
 Games.Alba.Role.servant,
 Games.Alba.Role.servant,
 Games.Alba.Role.servant]
-/
#guard_msgs in
#eval roleDeck 6

Look at n - minionCount n - 1, the number of servants: the players, less the minions (the assassin among them), less the oracle. Subtraction on Nat never goes below zero: when the answer would be negative, it is 0. That is fine for five to ten players, but for four, the deck has a card too many:

/-- info: 0 -/
#guard_msgs in
#eval 4 - 4 - 1

/-- info: 5 -/
#guard_msgs in
#eval (roleDeck 4).length

Another reason the guarantee below is only for five to ten players.

A new game shuffles the deck and picks a first leader at random:

/-- A new game for `n` players: roles dealt from a shuffle, a random first leader. -/
def init (n seed : Nat) : State :=
  let g := Rng.ofSeed seed
  let dealt := g.shuffle (roleDeck n).toArray
  { roles := dealt.1.toList, leader := (dealt.2.below n).1 }

Every seat gets one role

Here is the guarantee:

/-- **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⟩

Read the statement first. For any number of players n from five to ten, and any seed: there are n roles; count finds exactly one oracle and one assassin; and countP, which counts the elements with a property, finds minionCount n on the minions' side.

The proof has the same two steps as any proof about a shuffled deal: the dealt roles are a permutation of the deck (init_roles, built on the engine's shuffle_perm), and the deck has the right numbers. A permutation keeps the length (length_eq) and every count (count_eq, countP_eq), and .trans chains the two equalities together.

The deck's numbers are checked by computation, one table size at a time:

/-- The role deck has one role per seat, one oracle, one assassin, and the
right number on the minions' side: checked by computation for each count. -/
theorem roleDeck_numbers (n : Nat) (atLeast : 5 ≤ n) (atMost : n ≤ 10) :
    (roleDeck n).length = n ∧ (roleDeck n).count .oracle = 1 ∧ (roleDeck n).count .assassin = 1 ∧
      (roleDeck n).countP (·.minionSide) = minionCount n := by
  match n, atLeast, atMost with
  | 5, _, _ => decide
  | 6, _, _ => decide
  | 7, _, _ => decide
  | 8, _, _ => decide
  | 9, _, _ => decide
  | 10, _, _ => decide
  | 0, h, _ | 1, h, _ | 2, h, _ | 3, h, _ | 4, h, _ => exact absurd h (by decide)
  | _ + 11, _, h => exact absurd h (by omega)

match n, atLeast, atMost with splits on the number of players, carrying the two hypotheses along. For each of 5 to 10, decide works the deck out and checks it. The other two lines deal with the numbers that can't happen:

  • For 0 to 4, h says 5 ≤ n, which is false. by decide proves it false, and absurd turns a fact and a proof of its opposite into anything at all: this case can't happen, so it needs no further proof.
  • _ + 11 matches every number from 11 up, and omega sees that h, which says it is at most 10, is false.

Because the statement uses minionCount n rather than the numbers themselves, the proof checks the deck against whatever minionCount says. Change the count for a table size, and the guarantee is about the new count, without anyone editing it. Whether its proof still goes through is another matter, which the last chapter finds out.

You can do the same check over every table size at once, without splitting by hand. Fin 6 has six values, 0 to 5, so k + 5 runs over five to ten, and decide checks every one:

example : ∀ k : Fin 6, (roleDeck (k + 5)).length = k + 5 := by decide

Exercises

  1. Define servantCount n, the number of players on the servants' side, and check it for every table size with #eval.
  2. Prove, with decide, that at every table of five to ten the servants outnumber the minions.
  3. Prove that failsNeeded n q is always 1 or 2. (∨ is or, typed \or. To prove A ∨ B, the tactic left chooses to prove A, and right chooses B.)
  4. Prove that at a table of fewer than seven, one Fail is always enough.

As before, put definitions you'll call with a dot inside the rules' namespace, here namespace Games.Alba.

Solution
namespace Games.Alba

/-- How many players are on the servants' side. -/
def servantCount (n : Nat) : Nat := n - minionCount n

/-- info: [3, 4, 4, 5, 6, 6] -/
#guard_msgs in
#eval [5, 6, 7, 8, 9, 10].map servantCount

/-- The servants always outnumber the minions. -/
example : ∀ k : Fin 6, minionCount (k + 5) < servantCount (k + 5) := by decide

/-- A quest needs one fail or two, never anything else. -/
theorem failsNeeded_one_or_two (n q : Nat) : failsNeeded n q = 1 ∨ failsNeeded n q = 2 := by
  unfold failsNeeded
  split
  · right; rfl
  · left; rfl

/-- At a table of fewer than seven, one fail is always enough. -/
theorem small_tables_need_one_fail (n q : Nat) (small : n < 7) : failsNeeded n q = 1 := by
  unfold failsNeeded
  split
  · omega
  · rfl

end Games.Alba

In both proofs about failsNeeded, split gives one goal per branch of the if, with the condition (or its opposite) as a new hypothesis. In the last one, the first branch assumes 7 ≤ n ∧ q = 3 while small says n < 7, and omega sees that both can't be true.