What players know¶
Lol is a game of deduction. The Seer shows you another player's card, a tied Holmgang shows two players each other's card, and a trade tells each trader what the other now holds. Players remember these things, and the screen should show what each of them knows. But only what they know, and only while it's still true.
This chapter is about how the rules keep track of that, and what is proven about it.
Knowledge is part of the state¶
It would be easy to leave remembering to the browser. Lol doesn't: what each player knows is a field of the state, kept by the rules like any other.
/-- `viewer` knows that `holder` holds `card`: something they saw (a Seer
reveal, a tied duel, a trade). It lasts until `holder` next plays, when it is
forgotten whichever card they play, as people forget at the table. -/
structure Known where
viewer : Nat
holder : Nat
card : Card
deriving DecidableEq, Repr, Inhabited
A Known is one fact: viewer knows that holder holds card. The
state keeps a list of them, known. Three functions change it:
/-- `viewer` now knows that `holder` holds `c` (replacing what they knew of `holder`). -/
def learn (s : State) (viewer holder : Nat) (c : Card) : State :=
{ s with known := ⟨viewer, holder, c⟩ :: s.known.filter fun k => !(k.viewer == viewer && k.holder == holder) }
/-- Nobody can follow `holder`'s hand any more. -/
def forget (s : State) (holder : Nat) : State :=
{ s with known := s.known.filter fun k => k.holder != holder }
/-- `a` and `b` swapped hands in public: whatever was known of one is now known of the other. -/
def followSwap (s : State) (a b : Nat) : State :=
{ s with known := s.known.map fun k =>
if k.holder == a then { k with holder := b } else if k.holder == b then { k with holder := a } else k }
learn adds a fact, and drops anything the viewer knew before about the
same holder. forget drops every fact about one holder. followSwap is for
the Trader: if two hands swap in public, whatever anyone knew about one hand
is now true of the other holder.
The rules call these at the right moments. A card's effects are in
resolve, one match case per card:
/-- Resolve `c`'s effect, played by `me` (whose hand no longer holds `c`). -/
def resolve (s : State) (me : Nat) (a : Action) : State × List Event :=
match a.card, a.target with
| .raider, some t =>
match a.guess, (s.player t).hand.head? with
| some g, some h => if g = h then s.eliminate t else (s, [])
| _, _ => (s, [])
| .seer, some t =>
match (s.player t).hand.head? with
| some h => ((s.learn me t h).waitFor [me], [.saw me t h])
| none => (s, [])
| .holmgang, some t =>
match (s.player me).hand.head?, (s.player t).hand.head? with
| some m, some h =>
let shown := [Event.duel me t m h]
if m.value < h.value then let (s, e) := s.eliminate me; (s, shown ++ e)
else if h.value < m.value then let (s, e) := s.eliminate t; (s, shown ++ e)
else (((s.learn me t h).learn t me m).waitFor [me, t], shown)
| _, _ => (s, [])
| .shieldmaiden, _ => (s.modify me fun p => { p with protected_ := true }, [])
| .loki, some t =>
match (s.player t).hand.head? with
| some h =>
let s := (s.modify t fun p => { p with hand := [], discards := p.hand ++ p.discards }).forget t
let shown := [Event.discarded t h]
if h = .runestone then let (s, e) := s.eliminate t; (s, shown ++ e)
else let (s, e) := s.draw t; (s, shown ++ e)
| none => (s, [])
| .trader, some t =>
let mine := (s.player me).hand
let theirs := (s.player t).hand
let swapped := ((s.modify me fun p => { p with hand := theirs }).modify t fun p => { p with hand := mine }).followSwap me t
-- Each now knows the other's hand: it is the card they just gave away.
let swapped := match mine.head?, theirs.head? with
| some m, some h => ((swapped.learn me t m).learn t me h).waitFor [me, t]
| _, _ => swapped
(swapped, [])
| .runestone, _ => s.eliminate me
| _, _ => (s, [])
Look at the Seer's case: the player learns the target's card, the game
starts waiting for the player (more on that below), and the event saw is
produced. The tied Holmgang teaches both duellists; the Trader follows the
swap, then teaches both traders. Loki makes its target discard, so it
forgets what anyone knew of them.
And whatever card you play, taking your turn wipes what anyone knew of your hand, as people forget at the table:
/-- Move the played card from the player's hand to their discards. Taking
their turn also wipes what anyone knew of their hand. -/
def discardPlayed (s : State) (me : Nat) (c : Card) : State :=
(s.modify me fun p => { p with hand := p.hand.erase c, discards := c :: p.discards }).forget me
Who hears what¶
A move produces events, as in Snap. In Lol, some of them are private:
inductive Event where
/-- Public: what was played, at whom, naming what. -/
| played (p : Nat) (c : Card) (target : Option Nat) (guess : Option Card)
/-- Private to `p`: the card they drew. -/
| drew (p : Nat) (c : Card)
/-- Private to the Seer's player: what the target holds. -/
| saw (p target : Nat) (c : Card)
/-- Private to both duellists: both hands. -/
| duel (p target : Nat) (mine theirs : Card)
/-- Public: a discarded hand (Loki), face up. -/
| discarded (p : Nat) (c : Card)
| eliminated (p : Nat) (c : Option Card)
/-- Public: the round's winners and every remaining hand, revealed. -/
| roundWon (winners : List Nat) (hands : List (Nat × Card))
| newRound (round first : Nat)
| finished (winners : List Nat)
/-- Public: `p` acknowledged the card they were shown. -/
| nodded (p : Nat)
deriving DecidableEq, Repr
def Event.audience : Event → Engine.Audience
| .drew p _ => .only [p]
| .saw p _ _ => .only [p]
| .duel p t _ _ => .only [p, t]
| _ => .everyone
Each event says who may hear it. A drawn card goes to the drawer only, what the Seer saw to the Seer's player only, and a duel to its two duellists. The engine, which every game shares, sends each player only the events they are in the audience of.
To try moves, here are two small helpers, like the ones in Snap's chapter on a move:
/-- The game after a move, if it was accepted (or unchanged, if not). -/
def after (s : State) (p : Nat) (m : Move) : State :=
match step s p m with
| .ok (s', _) => s'
| .error _ => s
/-- The events of a move, or none if it was refused. -/
def events (s : State) (p : Nat) (m : Move) : List Event :=
match step s p m with
| .ok (_, evs) => evs
| .error _ => []
On the small table from the cards chapter, seat 0 plays the Seer at seat 1:
def peeked : State := after table 0 (.play ⟨.seer, some 1, none⟩)
/-- info: [{ viewer := 0, holder := 1, card := Games.LoL.Card.holmgang }] -/
#guard_msgs in
#eval peeked.known
/-- info: [0] -/
#guard_msgs in
#eval peeked.awaiting
/-- info: [Engine.Audience.everyone, Engine.Audience.only [0]] -/
#guard_msgs in
#eval (events table 0 (.play ⟨.seer, some 1, none⟩)).map Event.audience
Seat 0 now knows that seat 1 holds the Holmgang. The play produced two events: the announcement that the Seer was played, which everyone hears, and what was seen, which only seat 0 hears.
What a player is shown of the state is filtered the same way. Their view includes only the facts they are the viewer of:
/-- What the viewer knows about other hands (everything, for the debug view). -/
def knownJson (s : State) : Viewer → Json
| .player i => .arr ((s.known.filter (·.viewer == i)).map fun k =>
Json.obj #[("seat", Json.ofNat k.holder), ("card", k.card.toJson)]).toArray
| .debug => .arr (s.known.map fun k =>
Json.obj #[("viewer", Json.ofNat k.viewer), ("seat", Json.ofNat k.holder), ("card", k.card.toJson)]).toArray
Nods¶
After a reveal, the rules wait for the players who were shown a card to
acknowledge it, with a nod, before play goes on. That is the awaiting
field, set by waitFor:
/-- The game waits for each of `players` to nod. -/
def waitFor (s : State) (players : List Nat) : State := { s with awaiting := players }
A nod is a move of its own, beside a play:
/-- What a player may submit: a play, or a nod. -/
inductive Move where
| play (a : Action)
| nod
deriving DecidableEq, Repr
/-- The transition function. While anyone has yet to nod, no one plays. -/
def step (s : State) (actor : Nat) : Move → Except Rejection (State × List Event)
| .play a => if s.awaiting.isEmpty then play s actor a else .error ⟨"waiting for a nod"⟩
| .nod => nod s actor
While anyone is awaited, every play is refused, and only an awaited player may nod:
/-- info: "waiting for a nod" -/
#guard_msgs in
#eval match step peeked 1 (.play ⟨.holmgang, some 0, none⟩) with
| .error r => r.reason
| .ok _ => "accepted"
/-- info: "there is nothing for you to acknowledge" -/
#guard_msgs in
#eval match step peeked 1 .nod with
| .error r => r.reason
| .ok _ => "accepted"
/-- A nod: a player who was shown a card acknowledges it. The last nod ends
the turn that showed it. -/
def nod (s : State) (actor : Nat) : Except Rejection (State × List Event) :=
match s.phase with
| .finished _ => .error ⟨"game is over"⟩
| .playing =>
if s.awaiting.contains actor then
let after := finishPlay { s with awaiting := s.awaiting.erase actor }
.ok (after.1, [.nodded actor] ++ after.2)
else .error ⟨"there is nothing for you to acknowledge"⟩
A play that shows nobody anything ends the turn at once. One that shows
someone a card leaves the turn where it is, and the last nod ends it.
finishPlay decides which:
/-- End the turn (pass it on, or end the round) unless someone has yet to nod
at a card they were shown; then the last nod ends it instead. -/
def finishPlay (s : State) : State × List Event :=
if s.awaiting.isEmpty then advance s else (s, [])
def nodded : State := after peeked 0 .nod
/-- info: [] -/
#guard_msgs in
#eval nodded.awaiting
/-- info: 1 -/
#guard_msgs in
#eval nodded.turn
/-- info: [{ viewer := 0, holder := 1, card := Games.LoL.Card.holmgang }] -/
#guard_msgs in
#eval nodded.known
After seat 0's nod, no one is awaited, and it is seat 1's turn. Seat 0 still knows what seat 1 holds. But not for long: when seat 1 takes their turn, whatever they play, it is forgotten.
/-- Seat 1 takes their turn: here, Loki at seat 0. -/
def lokied : State := after nodded 1 (.play ⟨.loki, some 0, none⟩)
/-- info: [] -/
#guard_msgs in
#eval lokied.known
What is proven about nods¶
/-- **No one plays while someone has yet to acknowledge a card they were shown.** -/
theorem no_play_while_a_nod_is_awaited (waiting : s.awaiting ≠ []) (a : Nat) (act : Action) :
∃ reason, step s a (.play act) = .error reason := by
-- `step` refuses every play until no nod is outstanding.
simp [step, List.isEmpty_iff, waiting]
step refuses a play as soon as awaiting isn't empty, so simp, told
about step and the fact waiting, works it out.
/-- **While anyone has yet to nod, it is still the turn of the player who
showed them a card, and that player is among those awaited.**
Whatever the card (a Seer reveal, a tied Holmgang, a trade), a play that
leaves anyone to nod does not pass the turn on. -/
theorem a_reveal_keeps_the_turn (accepted : step s a (.play act) = .ok (s', evs)) (waiting : s'.awaiting ≠ []) :
a ∈ s'.awaiting ∧ s'.turn = s.turn := by
obtain ⟨clear, played⟩ := play_of_step accepted
obtain ⟨-, -, -, -, result, -⟩ := accepted_play played
have turn := resolve_turn (discardPlayed s a act.card) a act
rw [result] at waiting ⊢
unfold apply finishPlay at waiting ⊢
dsimp only at waiting ⊢
split
· -- Had the effect left no one to nod, ending the turn would leave no one either.
rename_i none
simp only [none, ↓reduceIte] at waiting
exact absurd (advance_clears _ (List.isEmpty_iff.mp none)) waiting
· rename_i some
refine ⟨?_, turn.trans rfl⟩
rcases resolve_awaiting (discardPlayed s a act.card) a act with same | mem
· -- Before the play no one was awaited, so the effect made someone wait.
have : (discardPlayed s a act.card).awaiting = [] := clear
rw [same, this] at some
exact absurd rfl some
· exact mem
Whatever the card, if a play leaves anyone to nod, the turn hasn't moved, and the player who made it is among those awaited.
Everything known is true¶
The most important promise about knowledge: if the screen tells you a player holds a card, they do. Here is what that means, as a property of a state:
/-- Everything anyone knows about another hand is true. -/
def KnowledgeTrue (s : State) : Prop := ∀ k ∈ s.known, k.card ∈ (s.player k.holder).hand
For every fact k in known, the holder really has that card in hand.
∀ k ∈ s.known, … is for every k in s.known (type \all or
\forall).
This is an invariant, like Snap's full deck, and it is proven the same way, in two parts. It holds at the start, because a new game starts with nobody knowing anything:
/-- **A new game starts with nobody knowing anyone else's hand.** -/
theorem new_games_start_with_no_knowledge (n seed rings : Nat) : (init n seed rings).1.known = [] := by
-- A new game is a fresh deal, and laying out a round clears all knowledge.
unfold init State.deal
exact dealFrom_known _ _ _ _
And every accepted move keeps it:
/-- **Everything a player is shown as known is true.**
Whenever the engine tells a player that another holds a certain card (learned
from a Seer, a tied Holmgang or a trade), that player really does hold it.
Starting from true knowledge, every accepted play keeps it true: knowledge of
a hand is forgotten when its holder takes their turn, is eliminated, or is
made to discard by Loki, and follows a card through a trade. -/
theorem known_cards_are_really_held (true_ : KnowledgeTrue s) (accepted : step s a m = .ok (s', evs)) :
KnowledgeTrue s' := by
rcases accepted_move accepted with ⟨act, -, -, played⟩ | ⟨-, -, -, rfl, -⟩
· obtain ⟨-, real, -, legal, result, -⟩ := accepted_play played
-- Each part of the play (discarding, the card's effect, and the end of the
-- turn or round) keeps knowledge true; the bookkeeping checks each one.
rw [result]
exact apply_true true_ legal real
· -- A nod changes no knowledge and no hand; ending the turn keeps knowledge true.
exact finishPlay_true _ true_
The guarantee is short because the work is in the bookkeeping: one lemma for each part of a play (discarding the played card, the card's effect, ending the turn or the round), each saying that part keeps knowledge true. The hard part is the trade, where a fact about one hand has to become a fact about another. Here is one of the simpler lemmas, for learning:
/-- Learning a card someone really holds keeps knowledge true. -/
theorem learn_true {s : State} {v h : Nat} {c : Card} (true_ : KnowledgeTrue s)
(holds : c ∈ (s.player h).hand) : KnowledgeTrue (s.learn v h c) := by
intro k known
simp only [State.learn, List.mem_cons, List.mem_filter] at known
rcases known with rfl | ⟨old, -⟩
· exact holds
· exact true_ k old
After intro, known says k is in the new list. The new list is the new
fact in front of a filtered old list, so rcases … with rfl | ⟨old, -⟩
splits the two cases (rcases is obtain with more patterns; rfl as a
pattern replaces k by the new fact everywhere). If k is the new fact,
the assumption holds proves it. If it is an old fact, it was true before,
and the filter didn't touch the hands.
Secrecy, briefly¶
Snap's secrecy chapter showed how the project states "reveals nothing": two games that differ only in hidden things give a player the same view. Lol's version of "differ only in hidden things" has more in it:
/-- `s` and `t` look the same to player `i`: they agree on everything public
(each player's discards, elimination, protection, rings and hand size; the
deck's size; the face-up cards; whose turn; the round; the ring target; the
phase; who must nod), on `i`'s own hand, and on what `i` has learned of other hands. They
may differ in everything else: the other players' cards, the order and
content of the deck, the hidden card, what other players know, and the
random generator. -/
def LookSame (i : Nat) (s t : State) : Prop :=
s.players.length = t.players.length ∧
(∀ j, (s.player j).discards = (t.player j).discards ∧ (s.player j).out = (t.player j).out ∧
(s.player j).protected_ = (t.player j).protected_ ∧ (s.player j).rings = (t.player j).rings ∧
(s.player j).hand.length = (t.player j).hand.length) ∧
(s.player i).hand = (t.player i).hand ∧
s.deck.length = t.deck.length ∧ s.faceUp = t.faceUp ∧ s.turn = t.turn ∧ s.round = t.round ∧
s.ringsToWin = t.ringsToWin ∧ s.phase = t.phase ∧
s.known.filter (·.viewer == i) = t.known.filter (·.viewer == i) ∧ s.awaiting = t.awaiting
Two games look the same to player i when every public fact agrees, i's
own hand is the same, and so is what i knows. Other hands, the deck's
order, the hidden card and what other players know may all differ. Note
the line about knowledge: the view is allowed to depend on your own
knowledge, because you really learned it, and on nothing else that's hidden.
The guarantee, whole_views_reveal_nothing_hidden, is proved like Snap's.
Exercises¶
- Prove that a state where nobody knows anything satisfies
KnowledgeTrue. Hint: afterintro k known, rewriteknownwith the hypothesis that the list is empty. What is left? - Prove that after
s.forget h, nothing is known abouth. - Prove that
after s p mkeeps knowledge true, for any move, usingknown_cards_are_really_held. Then use it twice to show that the knowledge on the small table after the Seer and the nod is true. - Remove
.forget mefromdiscardPlayedinGames/LoL/Rules.lean. Before running anything, predict: do the tests fail? Do the proofs? Then runmake testandmake proofs, and put it back withgit restore Games/LoL/Rules.lean.
Solution
/-- Nobody knows anything: then everything they know is true. -/
theorem nothing_known_is_true (s : State) (empty : s.known = []) : Proofs.LoL.KnowledgeTrue s := by
intro k known
rw [empty] at known
cases known
/-- After `forget h`, nothing is known of `h`'s hand. -/
theorem forget_forgets (s : State) (h : Nat) : ∀ k ∈ (s.forget h).known, k.holder ≠ h := by
intro k known
simp [State.forget] at known
exact known.2
/-- Any accepted move keeps knowledge true, and a refused one changes nothing. -/
theorem after_true {s : State} {p : Nat} {m : Move} (true_ : Proofs.LoL.KnowledgeTrue s) :
Proofs.LoL.KnowledgeTrue (after s p m) := by
unfold after
split
· rename_i accepted
exact Proofs.LoL.known_cards_are_really_held true_ accepted
· exact true_
/-- So everything known after the peek and the nod is true. -/
example : Proofs.LoL.KnowledgeTrue nodded :=
after_true (after_true (nothing_known_is_true table rfl))
In the first, after the rewrite, known says k is in the empty list,
and cases known finds there is no way for that to be true. In the
third, split splits on the match in after: an accepted move, where
the guarantee applies, or a refused one, where nothing changed. split
adds the fact step s p m = .ok … to the first case without a name you
can use, and rename_i accepted names it.
For the fourth: the tests fail. One scenario test, forgotten when the
holder takes their turn, whatever they play, fails, and the random
games fail everything known is true over and over: a player plays the
very card someone knew they held, and the knowledge stays, now false.
The proofs fail too, in the bookkeeping, at the three lemmas whose
proofs relied on the forget in discardPlayed. Two of them are about
cards and arm rings, and what they state is still true: only their
arguments need a new step. The third, discardPlayed_true, states
something that is now false. Read the errors: none of them says "this is
false", each says a step of the argument no longer fits. It's the tests
that show which guarantee has really become false. Lean tells you where
an argument broke; deciding why is your job.