Skip to content

What each player knows

Alba is a game about who knows what. A Thane knows only their own role. The Mirk know each other. The Seer knows who the Mirk are, and must not let it show. And no one ever learns who played which quest card. This chapter shows how the rules give each player their knowledge, and how the project proves that nothing else gets out.

Knowledge by role

The rules work out who is on the minions' side:

/-- Seats on the minions' side. -/
def minions (s : State) : List Nat := (List.range s.players).filter fun i => (s.role i).minionSide

It is written inside namespace State in the rules file, so its full name is State.minions, and you call it with a dot: s.minions. List.range n is [0, 1, …, n - 1], every seat, and filter keeps those whose role is on the minions' side. Then each player's knowledge, as a list of seats they know to be minions:

/-- The seats `i` knows to be on the minions' side: all of them for the
oracle, the others for anyone on that side, none for a servant. -/
def knowledge (s : State) (i : Nat) : List Nat :=
  if s.role i = .oracle then s.minions
  else if (s.role i).minionSide then s.minions.filter (· != i)
  else []

The oracle knows them all. A minion knows the others: (· != i) keeps every seat that isn't i (!= is not equal, as a Bool). A servant knows no one. At a table of six:

/-- Six players: the oracle in seat 1, the minion in seat 2, the assassin in seat 3. -/
def six : State := { roles := [.servant, .oracle, .minion, .assassin, .servant, .servant], leader := 0 }

/-- info: [2, 3] -/
#guard_msgs in
#eval six.minions

/-- info: [[], [2, 3], [3], [2], [], []] -/
#guard_msgs in
#eval (List.range 6).map six.knowledge

Two guarantees say the same in general:

/-- **The oracle is shown exactly the minions.** -/
theorem the_oracle_knows_exactly_the_minions {i : Nat} (oracle : s.role i = .oracle) :
    s.knowledge i = s.minions := by
  simp [State.knowledge, oracle]
/-- **A minion is shown exactly the others on the minions' side.** -/
theorem minions_know_each_other {i : Nat} (minion : (s.role i).minionSide = true) :
    s.knowledge i = s.minions.filter (· != i) := by
  have notOracle : s.role i ≠ .oracle := by intro h; rw [h] at minion; simp [Role.minionSide] at minion
  simp [State.knowledge, notOracle, minion]

In the second, the proof first shows that a minion isn't the oracle (notOracle), because knowledge asks about the oracle first. intro h assumes the opposite, rw [h] at minion turns minion into the claim that the oracle is on the minions' side, and simp sees that it's false.

These say what each player is shown. They don't say that players aren't shown more. That needs a guarantee of a different kind.

What a player is sent

A player is sent an observation, built for them:

def observe (s : State) (v : Viewer) : Json :=
  let n := s.players
  let shared := #[
    ("players", Json.ofNat n), ("phase", Json.str (phaseName s.phase)),
    ("leader", Json.ofNat s.leader), ("quest", Json.ofNat s.quest),
    ("teamSizes", Json.ofList Json.ofNat (teamSizes n)),
    ("failsNeeded", Json.ofList Json.ofNat ((List.range (teamSizes n).length).map (failsNeeded n))),
    ("results", Json.ofList Json.bool s.results), ("rejections", Json.ofNat s.rejections),
    ("team", Json.ofList Json.ofNat s.team), ("ready", Json.ofList Json.ofNat s.ready.reverse),
    ("voted", Json.ofList Json.ofNat s.voters.reverse),
    ("played", Json.ofList Json.ofNat s.playedBy.reverse),
    ("revealed", (s.revealed.map (Json.ofList fun r => Json.str r.id)).getD .null),
    ("lastVotes", Json.ofList pairJson s.lastVotes)]
  match v with
  | .player i =>
    .obj (shared ++ #[
      ("role", Json.str (s.role i).id),
      ("knowsMinions", Json.ofList Json.ofNat (s.knowledge i)),
      ("yourVote", ((s.votes.lookup i).map Json.bool).getD .null),
      ("yourCard", ((s.cards.lookup i).map Json.bool).getD .null)])
  | .debug =>
    .obj (shared ++ #[("roles", Json.ofList (fun r => Json.str r.id) s.roles),
                      ("votes", Json.ofList pairJson s.votes.reverse),
                      ("cards", Json.ofList pairJson s.cards.reverse)])

The shared part is the same for everyone: the phase, the leader, the results, who has voted and who has played, but not how. Then each player gets their own role, their knowledge, and their own vote and card. Only the debug viewer, the all-seeing view used for testing, gets everyone's roles, votes and cards.

Here is a quest in progress. Seats 1, 2 and 3 are the Band. The assassin and the minion have played, one Fail and one Success, and seat 3 hasn't played yet. In a second game, the two minions played the other way round. Seat 3's view is the same in both; only the debug view tells them apart:

/-- Five players, on the second quest: seats 1, 2 and 3 are the team. The
assassin (seat 1) and the minion (seat 2) have played; seat 3 has not. -/
def questA : State :=
  { roles := [.oracle, .assassin, .minion, .servant, .servant], leader := 1, quest := 1, results := [true],
    phase := .questing, team := [1, 2, 3], cards := [(2, true), (1, false)] }

/-- The same, except that the two minions played the other way round. -/
def questB : State := { questA with cards := [(2, false), (1, true)] }

#guard toString (observe questA (.player 3)) == toString (observe questB (.player 3))
#guard toString (observe questA .debug) != toString (observe questB .debug)

Looking the same

As with secrecy before, the project states "reveals nothing" as indistinguishability: two games that differ only in what a player may not see give that player exactly the same view. What a player may see depends on who they are, so Alba's LookSame is about one player, i:

/-- Two states agree on everything `i` may see: the public state (including,
once the game is over, every role; whom the assassin named; and the last
revealed votes), `i`'s own
role and knowledge, and `i`'s own vote and card. -/
def LookSame (i : Nat) (s t : State) : Prop :=
  s.players = t.players ∧ s.phase = t.phase ∧ s.leader = t.leader ∧ s.quest = t.quest ∧
  s.results = t.results ∧ s.rejections = t.rejections ∧ s.team = t.team ∧ s.ready = t.ready ∧
  s.voters = t.voters ∧ s.playedBy = t.playedBy ∧ s.revealed = t.revealed ∧ s.accused = t.accused ∧
  s.lastVotes = t.lastVotes ∧
  s.role i = t.role i ∧ s.knowledge i = t.knowledge i ∧
  s.votes.lookup i = t.votes.lookup i ∧ s.cards.lookup i = t.cards.lookup i

The first lines are public: everyone may see them. The last two lines are i's own: their role, their knowledge, and lookup i, which finds i's entry in a list of pairs, so their own vote and their own card, if any. Everything else is missing, and that is what may differ: other players' roles, how others voted, which cards others played.

The two quests above look the same to seat 3, and not to seat 1, who knows which card they played:

example : Proofs.Alba.LookSame 3 questA questB := by
  unfold Proofs.Alba.LookSame; decide
example : ¬ Proofs.Alba.LookSame 1 questA questB := by
  unfold Proofs.Alba.LookSame; decide

LookSame is a def, so decide can't see what it says until unfold replaces it with its body. Then it's a list of facts about two concrete games, and decide checks them all.

The guarantee

/-- **No information leaks: in particular, who played which quest card is never revealed.**

A player's view (their observation and the moves offered to them) depends
only on public information, their own role and what it lets them know, and
their own vote and card. Two games that differ in anything else, such as other
players' roles while the game goes on, how others voted before the reveal, or
which quest cards other team members played, look exactly the same to them. -/
theorem views_reveal_nothing_hidden {i : Nat} {s t : State} (same : LookSame i s t) :
    observe s (.player i) = observe t (.player i) ∧ ∀ who, offers who s (.player i) = offers who t (.player i) := by
  obtain ⟨players, phase, leader, quest, results, rejections, team, ready, voters, playedBy, revealed, accused,
    lastVotes, role, knows, myVote, myCard⟩ := same
  constructor
  · -- The observation is built from the public fields and the player's own.
    simp only [observe, players, phase, leader, quest, results, rejections, team, ready, voters, playedBy,
      revealed, lastVotes, role, knows, myVote, myCard]
  · -- The offers depend on the same, and on `check`, which does too.
    intro who
    have checks := check_same ⟨players, phase, leader, quest, results, rejections, team, ready, voters,
      playedBy, revealed, accused, lastVotes, role, knows, myVote, myCard⟩
    simp only [offers, players, phase, leader, quest, role, checks]

If two games look the same to player i, then i's observation is the same, and so are the moves offered to them. The proof:

  • obtain takes same apart into its facts, one name each.
  • constructor splits the goal, an ∧, into its two halves.
  • simp only [observe, …] unfolds observe and rewrites with exactly the facts listed, and no others. Since observe reads only those fields, both sides become the same.
  • The offered moves also depend on check, so the proof uses check_same, which says check gives the same answer in two games that look the same:
/-- Whether a move by `i` is legal depends only on what `i` may see. -/
theorem check_same {i : Nat} {s t : State} (same : LookSame i s t) (m : Move) : check s i m = check t i m := by
  obtain ⟨players, phase, leader, quest, -, -, team, ready, voters, playedBy, -, -, -, role, -⟩ := same
  cases m <;> simp only [check, players, phase, leader, quest, team, ready, voters, playedBy, role]

A theorem is a function, so you can use it on the two quests above. Give it a proof that they look the same to seat 3, and it gives back a proof that seat 3's observations are equal:

theorem seat3_cannot_tell : observe questA (.player 3) = observe questB (.player 3) :=
  (Proofs.Alba.views_reveal_nothing_hidden (by unfold Proofs.Alba.LookSame; decide)).1

That covers the observation and the moves. A player is sent more than that, and the whole view is covered too:

/-- **Nothing a player is sent reveals what they may not see.**

Everything in a player's view (the observation, the moves offered, what is
happening, who is awaited, the rules, the outcome, and the events they are
admitted to) is the same in any two games at the same table (the same
players' names) that look the same to them. In particular, while the assassin
chooses, no part of the view says who the assassin is. -/
theorem whole_views_reveal_nothing_hidden {i : Nat} {s t : Engine.Session State}
    (same : LookSame i s.state t.state) (names : s.names = t.names)
    (events : Engine.Session.visible s.events (.player i) = Engine.Session.visible t.events (.player i)) :
    s.view (.player i) = t.view (.player i) := by
  obtain ⟨obs, acts⟩ := views_reveal_nothing_hidden same
  exact Proofs.view_is_built_from_its_parts (by simp [Engine.Game.seats, same.1]) names
    (fun who => (public_parts_same same who).1) (public_parts_same same Engine.seatName).2.1
    (public_parts_same same Engine.seatName).2.2.1 obs acts events (fun who => (public_parts_same same who).2.2.2)

The phase text, who the table is waiting for, the rules and the outcome are shown to depend only on public facts (public_parts_same). One of them deserves a look: who the table is waiting for.

/-- Who the table openly waits on. While the assassin chooses, no one is
named: who the assassin is stays secret until they have chosen. -/
def waitingFor (s : State) : List Nat :=
  let all := List.range s.players
  match s.phase with
  | .proposing => [s.leader]
  | .discussing | .deliberating => all.filter (· ∉ s.ready)
  | .voting => all.filter (· ∉ s.voters)
  | .questing => s.team.filter (· ∉ s.playedBy)
  | .assassinating | .finished _ => []

While the assassin chooses, the table waits for no one, because naming the player it waited for would name the assassin. Try changing that line so the table waits for the assassin's seat while they choose: make test still passes, but make proofs fails in public_parts_same, the lemma whole_views_reveal_nothing_hidden is built on. Two games that look the same to a servant can have their assassins in different seats, so their views would differ.

Who played which card

The guarantee's doc comment singles out quest cards, and for good reason. Without that secret, Alba wouldn't be a game: a Fail would point straight at a Conspirator. Look at what happens to the two quests above when seat 3 plays the last card:

def finishQuest (s : State) : State × List Event :=
  match step s 3 (.play true) with
  | .ok r => r
  | .error _ => (s, [])

/-- info: [Games.Alba.Event.cardPlayed 3, Games.Alba.Event.questDone 1 1 false] -/
#guard_msgs in
#eval (finishQuest questA).2

#guard finishQuest questA == finishQuest questB

The events are the same: seat 3 played, and the quest failed with one Fail. And the two whole games are now equal: resolveQuest records only the result, and starting the next proposal empties cards. Once a quest is over, not even the game remembers who played what.

That is one table. Two guarantees prove it for every table. The first is about the play itself: two plays that leave the same cards on the table, played by the same players, announce exactly the same events, whichever card each player played, including the card being played now.

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

The second is about every move after it: in two games that differ only in who played which card, any move is accepted or refused alike, and announces the same events.

/-- **Later moves never reveal who played which quest card either.**

In two games that are the same except for which player played which of the
quest cards on the table (the same players have played, and the same cards
are there), every move is accepted or refused alike, and announces exactly the
same events. With `playing_a_quest_card_reveals_no_card` for the plays
themselves, and `views_reveal_nothing_hidden` for the rest of a player's view,
who played which card is never revealed. -/
theorem later_moves_reveal_no_card (u : State) (cs ct : List (Nat × Bool))
    (samePlayers : cs.map (·.1) = ct.map (·.1)) (sameCards : (cs.map (·.2)).Perm (ct.map (·.2)))
    (a : Nat) (m : Move) :
    (step { u with cards := cs } a m).map (·.2) = (step { u with cards := ct } a m).map (·.2) := by
  -- Whether the move is allowed never looks at which card anyone played...
  have allowed := check_ignores_which_card u samePlayers a m
  -- ...and what it announces never does either.
  have announced := apply_events_ignore_which_card u cs ct samePlayers sameCards a m
  -- Both games are in the same phase, the only other thing `step` looks at.
  have samePhase : ({ u with cards := cs } : State).phase = ({ u with cards := ct } : State).phase := rfl
  generalize ({ u with cards := cs } : State) = s at *
  generalize ({ u with cards := ct } : State) = t at *
  -- So both are refused alike, or both are accepted with the same events.
  unfold step
  rw [samePhase, allowed]
  cases t.phase <;> cases check t a m <;> simp [Except.map, announced]

whole_views_reveal_nothing_hidden takes the events as given, and these two are what make that safe for quest cards. The statements take two lists of cards, cs and ct, and ask for the same players (samePlayers, the first of each pair) and the same cards in any order (sameCards, a permutation of the second of each pair). That is exactly "the same except for who played which card".

The oracle's secret

The assassin's job at the end is to find the oracle. Do the minions' views give the oracle away? Swap the oracle with a servant, and the minions can't tell:

/-- `six` with the oracle and a servant swapped. -/
def sixSwapped : State := { six with roles := [.oracle, .servant, .minion, .assassin, .servant, .servant] }

example : Proofs.Alba.LookSame 2 six sixSwapped := by
  unfold Proofs.Alba.LookSame; decide
example : Proofs.Alba.LookSame 3 six sixSwapped := by
  unfold Proofs.Alba.LookSame; decide

Their knowledge is the list of minions, which hasn't changed, and the oracle's role isn't theirs to see. So by views_reveal_nothing_hidden, no minion's view can tell the oracle from a servant. If the assassin finds the oracle, it's from how the oracle played, not from anything the engine said.

The reveal

When the game is over, everyone turns their card over:

/-- Every role, face up, once the game is over (as at the real table); nothing
while it goes on. -/
def revealed (s : State) : Option (List Role) :=
  match s.phase with
  | .finished _ => some s.roles
  | _ => none

revealed is one of the public facts in LookSame, so once the game is over, two games that look the same to a player have the same roles. Before the end, it's none in every game, so it reveals nothing:

/-- **When the game is over, everyone sees every role; until then, no one does.**

Every player's view carries the full list of roles exactly when the game has
finished, as when everyone turns their card over at the end. -/
theorem every_role_is_revealed_at_the_end (s : State) :
    (∀ w, s.phase = .finished w → s.revealed = some s.roles) ∧
      (∀ p, (∀ w, p ≠ .finished w) → s.phase = p → s.revealed = none) := by
  constructor
  · intro w finished; simp [State.revealed, finished]
  · intro p going current
    subst current
    unfold State.revealed
    split
    · rename_i w finished; exact absurd finished (going w)
    · rfl

Exercises

  1. At the table six, swap the minion in seat 2 with the servant in seat 4. Show that the swapped game looks the same to the servant in seat 0, but not to the oracle in seat 1. Why not to the oracle?
  2. Prove that a servant knows no one: if s.role i = .servant, then s.knowledge i = [].
  3. In Games/Alba/Game.lean, make observe leak the quest cards: add ("cards", Json.ofList pairJson s.cards.reverse) to the shared part. Run make proofs. What fails? Then put it back with git restore Games/Alba/Game.lean.
Solution
  1. The oracle's knowledge lists the minions, and the minions have moved, so knowledge 1 differs:

    /-- `six` with the minion and a servant swapped. The servants can't tell. -/
    def sixOtherMinion : State := { six with roles := [.servant, .oracle, .servant, .assassin, .minion, .servant] }
    
    example : Proofs.Alba.LookSame 0 six sixOtherMinion := by
      unfold Proofs.Alba.LookSame; decide
    example : ¬ Proofs.Alba.LookSame 1 six sixOtherMinion := by
      unfold Proofs.Alba.LookSame; decide
    
    #guard toString (observe six (.player 0)) == toString (observe sixOtherMinion (.player 0))
    
  2. One simp does it:

    /-- A servant knows no one on the minions' side. -/
    theorem servants_know_nothing {s : State} {i : Nat} (servant : s.role i = .servant) : s.knowledge i = [] := by
      simp [State.knowledge, servant, Role.minionSide]
    

    simp unfolds knowledge, uses servant to work out the role, and Role.minionSide to see that a servant isn't on the minions' side.

  3. The proof of views_reveal_nothing_hidden fails, at the simp only for the observation: LookSame doesn't include s.cards, so nothing lets simp show the two observations are equal. No proof could, since the statement is now false. make test still passes: no test looks for a cards field in a player's view, and no test could look for every possible leak. The engine's views and the proof are tied together: changing what a player is sent means changing what the guarantee promises.