Votes and quests¶
In most card games, players take turns. In Alba, a vote is cast by everyone, in secret, in any order, and nobody sees how anyone voted until the last vote is in. The same goes for the cards a Band plays on a quest. This chapter is about how rules written as one move at a time handle moves made by everyone at once.
The state of a game¶
structure State where
/-- One role per seat. -/
roles : List Role
leader : Nat
/-- The current quest, counting from 0. -/
quest : Nat := 0
/-- Completed quests, in order: `true` for a success. -/
results : List Bool := []
/-- Consecutive rejected proposals. -/
rejections : Nat := 0
phase : Phase := .proposing
/-- The proposed (then approved) team. -/
team : List Nat := []
/-- Players ready to vote on the current proposal (or, at the end, for the assassin's choice). -/
ready : List Nat := []
/-- Votes cast on the current proposal: seat and approval. Hidden until all are in. -/
votes : List (Nat × Bool) := []
/-- Quest cards played: seat and success. Never revealed individually. -/
cards : List (Nat × Bool) := []
/-- Whom the assassin named, once they have. -/
accused : Option Nat := none
/-- How everyone voted on the last proposal put to the vote, left face up
on the table until the next vote is revealed (as players leave their vote
tokens out). Public. -/
lastVotes : List (Nat × Bool) := []
deriving DecidableEq, Repr, Inhabited
Nat × Bool (type \x for ×) is a pair: a seat and a yes-or-no. So
votes holds each vote cast so far, with who cast it, and cards holds
each quest card played. Both are in the state, because the engine has to
remember them, but the doc comments say they are hidden. The next
chapter proves that they are.
The phases of a round:
inductive Phase where
| proposing
/-- A team is proposed; voting opens once every player is ready. -/
| discussing
| voting
| questing
/-- Three quests have succeeded: the table talks it over; the assassin's
choice opens once every player is ready. -/
| deliberating
/-- The assassin names the player they think is the oracle. -/
| assassinating
/-- The game is over; `minionsWin` says which side won. -/
| finished (minionsWin : Bool)
deriving DecidableEq, Repr, Inhabited
And the moves a player can make:
/-- What a player may submit. -/
inductive Move where
| propose (team : List Nat)
/-- Done discussing: ready to vote on this proposal, or ready for the assassin's choice. -/
| ready
| vote (approve : Bool)
| play (success : Bool)
| accuse (target : Nat)
deriving DecidableEq, Repr
Which moves are legal¶
As in Lol, the rules say which moves are legal twice: once as a statement,
Legal, and once as a function, check, that gives a reason for refusing.
A bookkeeping lemma, check_none_iff_legal, proves they agree.
/-- **A legal move.**
* Propose: the leader, while proposing, names exactly the required number of
distinct players, all real seats.
* Ready: a real player, while discussing a proposal or deliberating before the
assassin's choice, who is not yet ready.
* Vote: a real player, while voting, who has not yet voted on this proposal.
* Play: a team member, while questing, who has not yet played; a fail only
from the minions' side.
* Accuse: the assassin, once everyone is ready for the choice, names any
other real player, a fellow minion included (that simply cannot win). -/
def Legal (s : State) (actor : Nat) : Move → Prop
| .propose team =>
s.phase = .proposing ∧ actor = s.leader ∧ team.length = teamSize s.players s.quest ∧ team.Nodup ∧
∀ p ∈ team, p < s.players
| .ready => (s.phase = .discussing ∨ s.phase = .deliberating) ∧ actor < s.players ∧ actor ∉ s.ready
| .vote _ => s.phase = .voting ∧ actor < s.players ∧ actor ∉ s.voters
| .play success =>
s.phase = .questing ∧ actor ∈ s.team ∧ actor ∉ s.playedBy ∧
(success = false → (s.role actor).minionSide = true)
| .accuse target =>
s.phase = .assassinating ∧ s.role actor = .assassin ∧ actor < s.players ∧ target < s.players ∧
target ≠ actor
Look at what Legal doesn't say. Only propose needs actor = s.leader.
Anyone may vote while voting, so long as they're a real player who hasn't
voted yet; anyone on the team may play a card while questing. There is no
"whose turn is it". That is all it takes to allow moves in any order.
∈ and ∉ (type \in and \notin) are is in and is not in a list.
team.Nodup says no one appears twice.
What a move does¶
/-- Carry out a legal move. -/
def apply (s : State) (actor : Nat) : Move → State × List Event
| .propose team => ({ s with phase := .discussing, team, ready := [], votes := [] }, [.proposed actor team])
| .ready =>
let s := { s with ready := actor :: s.ready }
if s.ready.length = s.players then
if s.phase = .deliberating then ({ s with phase := .assassinating, ready := [] }, [.readied actor, .choiceOpen])
else ({ s with phase := .voting, ready := [] }, [.readied actor, .votingOpen])
else (s, [.readied actor])
| .vote approve =>
let s := { s with votes := (actor, approve) :: s.votes }
if s.votes.length = s.players then
let r := tally s
(r.1, [.voted actor] ++ r.2)
else (s, [.voted actor])
| .play success =>
let s := { s with cards := (actor, success) :: s.cards }
if s.cards.length = s.team.length then
let r := resolveQuest s
(r.1, [.cardPlayed actor] ++ r.2)
else (s, [.cardPlayed actor])
| .accuse target =>
let r := finish { s with accused := some target } (s.role target == .oracle)
(r.1, [.accused actor target (s.role target == .oracle)] ++ r.2)
Each vote is added to votes, and the move announces only .voted actor:
who voted, not how. If that vote was the last (s.votes.length = s.players),
tally resolves them all at once. A quest card works the same way, with
resolveQuest when the whole team has played. The ready move works the
same way too: voting only opens when the last player is ready.
Let's play some of it. Here is a table of five, and a helper that makes a list of moves and says which one was refused, if any:
/-- A table of five: the oracle in seat 0, the assassin in seat 1, a minion in
seat 2, and two servants. Seat 0 leads. -/
def table : State := { roles := [.oracle, .assassin, .minion, .servant, .servant], leader := 0 }
/-- Make the moves in order, stopping at the first one refused. -/
def moves (s : State) : List (Nat × Move) → Except String State
| [] => .ok s
| (p, m) :: rest =>
match step s p m with
| .ok (s', _) => moves s' rest
| .error r => .error s!"seat {p}: {r.reason}"
The leader proposes seats 0 and 3. No one may vote yet:
def proposed : State := (moves table [(0, .propose [0, 3])]).toOption.get!
/-- info: Except.error "seat 1: not the time to vote" -/
#guard_msgs in
#eval (moves proposed [(1, .vote true)]).map (·.phase)
(.toOption.get! takes the state out of the Except, and would stop with
an error if a move had been refused: fine for examples.)
Players say they are ready, in any order. Voting opens with the fifth:
/-- info: Except.ok (Games.Alba.Phase.discussing) -/
#guard_msgs in
#eval (moves proposed [(4, .ready), (0, .ready), (2, .ready), (1, .ready)]).map (·.phase)
/-- info: Except.ok (Games.Alba.Phase.voting) -/
#guard_msgs in
#eval (moves proposed [(4, .ready), (0, .ready), (2, .ready), (1, .ready), (3, .ready)]).map (·.phase)
Four of the five vote, in no particular order. The game is still voting, and
voters (the seats that have voted) is all anyone may know:
def fourIn : State := (moves voting [(3, .vote true), (1, .vote false), (4, .vote true), (0, .vote true)]).toOption.get!
/-- info: Games.Alba.Phase.voting -/
#guard_msgs in
#eval fourIn.phase
/-- info: [0, 4, 1, 3] -/
#guard_msgs in
#eval fourIn.voters
voters lists the most recent voter first, because each vote is added at
the front of the list. The fifth vote resolves them all:
/--
info: [Games.Alba.Event.voted 2,
Games.Alba.Event.votesRevealed [(3, true), (1, false), (4, true), (0, true), (2, false)] true]
-/
#guard_msgs in
#eval match step fourIn 2 (.vote false) with
| .ok (_, events) => events
| .error _ => []
/-- info: Except.ok (Games.Alba.Phase.questing) -/
#guard_msgs in
#eval (moves fourIn [(2, .vote false)]).map (·.phase)
Only now is every vote announced, in the order cast, together with the result: approved, three to two.
These are proven, not only tried. No vote while the table is still talking:
/-- **No vote is accepted until everyone is ready.**
After a proposal the table discusses; while it does, every vote is refused. -/
theorem no_vote_while_discussing (discussing : s.phase = .discussing) (a : Nat) (approve : Bool) :
∃ reason, step s a (.vote approve) = .error reason := by
simp [step, check, discussing]
∃ reason, … (type \ex) says there is a reason for which …: the vote is
refused, whatever the reason. The proof is one simp: with the phase known,
check works out to a refusal.
Voting opens only when the last player is ready:
/-- **Voting opens exactly when the last player becomes ready.**
The only move that opens voting is a `ready`, and only when it completes the
table: everyone else was already ready. -/
theorem voting_opens_when_everyone_is_ready (accepted : step s a m = .ok (s', evs))
(wasNot : s.phase ≠ .voting) (opens : s'.phase = .voting) :
m = .ready ∧ (a :: s.ready).length = s.players := by
obtain ⟨-, legal, result, -⟩ := accepted_step accepted
subst result
cases m with
| propose team => simp [apply] at opens
| ready =>
refine ⟨rfl, ?_⟩
simp only [apply] at opens
split at opens
· rename_i complete; exact complete
· exact absurd opens wasNot
| vote b => exact absurd legal.1 wasNot
| play b =>
-- A quest card leaves the quest running or resolves it, never to voting.
simp only [apply] at opens
split at opens
· unfold resolveQuest finish nextProposal at opens
dsimp only at opens
split at opens
· simp at opens
· split at opens <;> simp at opens
· simp only at opens; rw [legal.1] at opens; simp at opens
| accuse t => simp [apply, finish] at opens
The statement says: if an accepted move took a game that wasn't voting to
one that is, the move was ready, and the player who made it completed the
table. The proof goes through the five kinds of move with cases m with. A
few things in it are new:
subst resultreplacess'everywhere by whatresultsays it equals.split at openssplits on anifin the hypothesisopens, rather than in the goal.rename_i completenames the hypothesis thatsplitmade, which Lean had left nameless.absurd opens wasNot:openssays the phase is voting andwasNotsays it isn't, so this case can't happen.
And each player votes once, while voting:
/-- **Each player votes at most once on a proposal, and only while voting.** -/
theorem one_vote_each {approve : Bool} (accepted : step s a (.vote approve) = .ok (s', evs)) :
s.phase = .voting ∧ a < s.players ∧ a ∉ s.voters :=
(accepted_step accepted).2.1
Here the proof is a single term: accepted_step says an accepted move was
Legal, and .2.1 picks that part out of its ∧s.
The tally¶
/-- All votes are in: approve on a strict majority, else reject. -/
def tally (s : State) : State × List Event :=
let approved := decide (2 * (s.votes.filter (·.2)).length > s.players)
let shown := Event.votesRevealed s.votes.reverse approved
if approved then
({ s with phase := .questing, rejections := 0, votes := [], cards := [], lastVotes := s.votes.reverse }, [shown])
else if s.rejections + 1 ≥ rejectionLimit then
let r := finish { s with rejections := s.rejections + 1, lastVotes := s.votes.reverse } true
(r.1, [shown] ++ r.2)
else (nextProposal { s with rejections := s.rejections + 1, lastVotes := s.votes.reverse }, [shown])
The team is approved on a strict majority: more than half. The rule is
written 2 * approvals > players rather than approvals > players / 2,
because division on Nat rounds down, and 2 * … avoids having to think
about it. With six players, three approvals is a tie, and a tie rejects:
/-- Votes in seat order: `true` approves. -/
def votesOf (bs : List Bool) : List (Nat × Bool) := bs.zipIdx.map fun (b, i) => (i, b)
/-- A table of `n` (only the count matters here) with these votes in. -/
def withVotes (n : Nat) (bs : List Bool) : State :=
{ roles := List.replicate n .servant, leader := 0, phase := .voting, votes := votesOf bs }
/-- info: Games.Alba.Phase.questing -/
#guard_msgs in
#eval (tally (withVotes 5 [true, true, true, false, false])).1.phase
/-- info: Games.Alba.Phase.proposing -/
#guard_msgs in
#eval (tally (withVotes 6 [true, true, true, false, false, false])).1.phase
decide (…) turns a statement Lean can work out into a Bool: the rules
write the condition as a statement, and get a yes or no to branch on.
The guarantee says the same, for every state:
/-- **A team is approved exactly on a strict majority.**
When the last vote is in, the votes are tallied: the team goes on its quest
exactly when more than half the players approved. -/
theorem approved_exactly_on_a_strict_majority (s : State) :
(tally s).1.phase = .questing ↔ 2 * approvals s > s.players :=
tally_approves s
↔ (type \iff) is if and only if: each side implies the other. So the
team goes on its quest when there's a strict majority, and only then.
A rejection passes the lead on. Too many in a row and the minions win:
/-- Propose a team and have everyone reject it. -/
def rejectRound (leader : Nat) : List (Nat × Move) :=
[(leader, .propose [0, 3])] ++ allReady 5 ++ (List.range 5).map (·, .vote false)
/-- info: Except.ok (Games.Alba.Phase.proposing, 4) -/
#guard_msgs in
#eval (moves table ([0, 1, 2, 3].flatMap rejectRound)).map fun s => (s.phase, s.rejections)
/-- info: Except.ok (Games.Alba.Phase.finished true) -/
#guard_msgs in
#eval (moves table ([0, 1, 2, 3, 4].flatMap rejectRound)).map (·.phase)
/-- **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
Notice that this statement says rejectionLimit, the rules' own name for the
number, and not 5. Keep that in mind for the last chapter.
Quest cards¶
The moves are refused for the reasons check gives:
def onQuest : State := (moves fourIn [(2, .vote false)]).toOption.get!
/-- info: Except.error "seat 3: you may only play success" -/
#guard_msgs in
#eval (moves onQuest [(3, .play false)]).map (·.phase)
/-- info: Except.error "seat 1: you are not on the team" -/
#guard_msgs in
#eval (moves onQuest [(1, .play false)]).map (·.phase)
The most important rule about quest cards is that a servant can't fail a quest:
/-- **A servant can never play a fail.** -/
theorem a_servant_never_fails (servant : (s.role a).minionSide = false) :
∃ reason, step s a (.play false) = .error reason := by
-- `check` refuses it, whatever the phase.
unfold step
split
· exact ⟨_, rfl⟩
· have refused : check s a (.play false) ≠ none := by
intro passed
have legal := (check_none_iff_legal s a _).mp passed
have := legal.2.2.2 rfl
rw [servant] at this; exact Bool.false_ne_true this
split
· exact ⟨_, rfl⟩
· rename_i none; exact absurd none refused
The proof follows step. unfold step and split give one goal per phase
branch: a finished game refuses everything, so the reason is whatever it
gave, ⟨_, rfl⟩ (the _ lets Lean fill in the reason). Otherwise it shows
that check refuses, by assuming it didn't (intro passed) and reaching a
contradiction: check passing means the move is Legal, Legal says a fail
comes from the minions' side, and servant says this player isn't.
Bool.false_ne_true is the fact that false ≠ true (≠, typed \ne, is
not equal).
When the last card is in, the quest is resolved:
/-- All cards are in: the quest succeeds unless there are enough fails. -/
def resolveQuest (s : State) : State × List Event :=
let fails := (s.cards.filter fun c => !c.2).length
let succeeded := decide (fails < failsNeeded s.players s.quest)
let s := { s with results := s.results ++ [succeeded] }
let shown := Event.questDone s.quest fails succeeded
if s.failures ≥ questsToWin then
let r := finish s true
(r.1, [shown] ++ r.2)
else if s.successes ≥ questsToWin then ({ s with phase := .deliberating, team := [], ready := [], cards := [] }, [shown])
else (nextProposal { s with quest := s.quest + 1 }, [shown])
Count the fails, compare with failsNeeded, record the result, and
announce questDone with the number of fails, and nothing about who played
them. The guarantee:
/-- Fails played on the current quest. -/
def fails (s : State) : Nat := (s.cards.filter fun c => !c.2).length
/-- **A quest fails exactly when it gets enough fails.**
Resolving a quest records it as a success exactly when the number of fails is
below the threshold: one, or two on the fourth quest with seven or more
players. -/
theorem quest_result_is_the_fail_count (s : State) :
(resolveQuest s).1.results = s.results ++ [decide (fails s < failsNeeded s.players s.quest)] :=
resolveQuest_results s
Exercises¶
- Use
tallyand thewithVoteshelper to find out whether a table of seven approves with three approvals, and with four. - Prove that no vote is accepted while a team is on its quest. (Copy the
shape of
no_vote_while_discussing.) - Prove that a player whose vote was accepted is a real player
(
a < s.players), usingone_vote_each.
Solution
-
Three of seven isn't more than half, so it rejects; four approves:
-
and 3.:
/-- No vote is accepted while a team is on its quest. -/ theorem no_vote_while_questing {s : State} (questing : s.phase = .questing) (a : Nat) (approve : Bool) : ∃ reason, step s a (.vote approve) = .error reason := by simp [step, check, questing] /-- Whoever's vote was accepted is a real player. -/ theorem voters_are_real {s s' : State} {a : Nat} {approve : Bool} {evs : List Event} (accepted : step s a (.vote approve) = .ok (s', evs)) : a < s.players := (Proofs.Alba.one_vote_each accepted).2.1A theorem is a function:
one_vote_each acceptedis a proof of the three facts joined by∧, and.2.1picks out the second.