What a legal play is¶
When is a play allowed? In Snap the answer was buried in step: a few ifs,
each refusing something. Lol has more to say. You must hold the card. The
Valkyrie is sometimes forced. Some cards need a target, the target must be
allowed, and only the Raider names a card, which can't be the Raider.
Lol says all of this twice. Once as a statement of what a legal play is, written to be read. Once as code that the engine runs to check a play. Then a proof shows that the two say exactly the same thing. This chapter reads all three.
A play¶
/-- The play: which card, and its arguments. -/
structure Action where
card : Card
target : Option Nat := none
guess : Option Card := none
deriving DecidableEq, Repr
A play is a card, with an optional target seat and an optional guess. The JSON a browser sends is turned into one of these before the rules see it.
Rules as statements¶
In Snap's first-proofs chapter you met Prop, the type of statements, and a
def whose type is Prop defines a property. Here is the first part of the
rules, about guesses:
/-- The Raider names any card except the Raider; no other card names one. -/
def GuessOk (a : Action) : Prop :=
if a.card = .raider then ∃ g, a.guess = some g ∧ g ≠ .raider else a.guess = none
Read it as: if the card is the Raider, there is some card g that is the
guess, and g is not the Raider; otherwise there is no guess. It uses four
pieces of logic:
∃ g, …is there exists agsuch that … (type\ex).∧is and (type\and).≠is not equal (type\ne).if … then … else …works inside a statement just as in code: the statement says one thing in one case and another in the other.
The if needs one thing to work: Lean must be able to decide its condition,
a.card = .raider. It can, because Card derives DecidableEq. You can't
write if over a condition that can't be decided.
Next, targets:
/-- A targeting card names an allowed target (and a fitting guess), unless no
one else can be targeted, in which case it is played at no one, naming
nothing (Loki can always target its player). Other cards take no target. -/
def AimOk (s : State) (me : Nat) (a : Action) : Prop :=
if a.card.aims then
match a.target with
| none => a.card ≠ .loki ∧ s.targets me = [] ∧ a.guess = none
| some t => t ∈ allowedTargets s me a.card ∧ GuessOk a
else a.target = none ∧ a.guess = none
A match works inside a statement too. For a card that aims (one that needs
a target):
- with no target, it must not be Loki, no one else must be targetable, and there must be no guess;
- with a target
t, the target must be allowed for this card, and the guess must be right.∈is is an element of (type\in).
It uses three helpers from the rules file:
/-- Does this card need a target? -/
def Card.aims : Card → Bool
| .raider | .seer | .holmgang | .loki | .trader => true
| _ => false
/-- Whom a card may target: any legal target, or yourself as well for Loki. -/
def allowedTargets (s : State) (me : Nat) (c : Card) : List Nat :=
if c = .loki then s.targets me ++ [me] else s.targets me
/-- Must the Valkyrie be played from this hand? -/
def valkyrieForced (hand : List Card) : Bool :=
hand.contains .valkyrie && (hand.contains .loki || hand.contains .trader)
In Card.aims, one line lists five patterns, each after a |, that share
one result; _ then matches every other card. l.contains x is Bool:
true if x is in l. || is or, on Bool.
And the whole rule:
/-- **A legal play**: a player still in the round plays a card they hold;
if they hold the Valkyrie with Loki or the Trader, it is the Valkyrie; and
its target and guess fit the card. -/
def Legal (s : State) (me : Nat) (a : Action) : Prop :=
(s.player me).out = false ∧
a.card ∈ (s.player me).hand ∧
(valkyrieForced (s.player me).hand = true → a.card = .valkyrie) ∧
AimOk s me a
A legal play has four parts, joined by ∧. The third says if the Valkyrie
is forced, the card is the Valkyrie. → (type \to) is implies. Notice
what it doesn't say: when the Valkyrie isn't forced, it says nothing about
the card at all, so any card you hold will do.
Legal table 0 a is a statement about one play, and you can ask for its
type like any other value:
/-- info: Legal table 0 { card := Card.raider, target := some 1, guess := some Card.holmgang } : Prop -/
#guard_msgs in
#check Legal table 0 ⟨.raider, some 1, some .holmgang⟩
Proving a play is legal¶
A statement made of ∧s is proven by proving each part. Here is a proof that
seat 0 on the small table from the last chapter may play the Seer at seat 1:
/-- Seat 0 may play the Seer at seat 1. -/
example : Legal table 0 ⟨.seer, some 1, none⟩ := by
refine ⟨rfl, ?_, ?_, ?_⟩
· -- The Seer is in seat 0's hand.
decide
· -- The Valkyrie isn't forced, so there is nothing to show.
decide
· -- Seat 1 is an allowed target, and the Seer names no card.
unfold AimOk GuessOk
decide
refine ⟨rfl, ?_, ?_, ?_⟩ proves the first part (seat 0 isn't out) by
rfl and leaves a goal for each of the other three. decide handles the
first two: they are about a concrete hand, so Lean can work them out. The
third needs unfold first. decide asks Lean to find a way to decide the
statement, and that search doesn't look inside definitions, so it can't see
what AimOk means until it has been unfolded.
The code that runs¶
Proofs like that one are fine for one play. The engine has to answer every
play as it arrives, and give a reason when it refuses. That is check:
/-- Is this play legal for `me` now? Returns the reason if not. -/
def check (s : State) (me : Nat) (a : Action) : Option String :=
if (s.player me).out then some "you are out of this round"
else if !(s.player me).hand.contains a.card then some "you do not hold that card"
else if valkyrieForced (s.player me).hand && a.card != .valkyrie then some "you must play the Valkyrie"
else checkAim s me a
It gives back Option String: none if the play is fine, or some reason.
It tests the same things as Legal, in the same order, and passes the
target and guess on to two more functions:
def checkAim (s : State) (me : Nat) (a : Action) : Option String :=
if !a.card.aims then
if a.target.isSome || a.guess.isSome then some "that card takes no target" else none
else
match a.target with
| none =>
if a.card = .loki then some "Loki needs a target (possibly yourself)"
else if !(s.targets me).isEmpty then some "choose a target"
else if a.guess.isSome then some "no target to guess about" else none
| some t =>
if !(allowedTargets s me a.card).contains t then some "not a valid target"
else checkGuess a
def checkGuess (a : Action) : Option String :=
if a.card = .raider then
match a.guess with
| none => some "name a card"
| some .raider => some "the Raider cannot name a Raider"
| some _ => none
else if a.guess.isSome then some "only the Raider names a card" else none
/-- info: none -/
#guard_msgs in
#eval check table 0 ⟨.raider, some 1, some .holmgang⟩
/-- info: some "not a valid target" -/
#guard_msgs in
#eval check table 0 ⟨.raider, some 2, some .holmgang⟩
/-- info: some "the Raider cannot name a Raider" -/
#guard_msgs in
#eval check table 0 ⟨.raider, some 1, some .raider⟩
/-- info: some "you do not hold that card" -/
#guard_msgs in
#eval check table 0 ⟨.trader, some 1, none⟩
/-- info: some "choose a target" -/
#guard_msgs in
#eval check table 0 ⟨.seer, none, none⟩
play calls check, and refuses the play with its reason, or carries it
out:
/-- A play: legal for the player to act, carried out by `apply`. -/
def play (s : State) (actor : Nat) (a : Action) : Except Rejection (State × List Event) :=
match s.phase with
| .finished _ => .error ⟨"game is over"⟩
| .playing =>
if actor ≥ s.players.length then .error ⟨"no such player"⟩
else if actor != s.turn then .error ⟨"not your turn"⟩
else match check s actor a with
| some reason => .error ⟨reason⟩
| none => .ok (apply s actor a)
Proving that they agree¶
So there are two descriptions of a legal play. Legal is easy to read, but
the engine can't run it. check runs, but you would have to read every
branch to know what it allows. If they ever disagreed, every guarantee
stated with Legal would be about the wrong game.
This theorem, in Proofs/LoL/Bookkeeping.lean, rules that out:
/-- **The executable check and the plain statement agree.** `check` accepts a
play exactly when it is `Legal`. -/
theorem check_none_iff_legal (s : State) (me : Nat) (a : Action) : check s me a = none ↔ Legal s me a := by
unfold check Legal
rw [← checkAim_none_iff]
by_cases out : (s.player me).out <;> simp only [out, ↓reduceIte, reduceCtorEq, Bool.true_eq_false,
false_and, true_and]
by_cases held : a.card ∈ (s.player me).hand
· by_cases valk : valkyrieForced (s.player me).hand = true
· by_cases isValk : a.card = .valkyrie
· rw [isValk] at held; simp [held, valk, isValk]
· simp [held, valk, isValk]
· simp [held, valk]
· simp [held]
↔ (type \iff) is if and only if: each side implies the other. So:
check accepts a play exactly when it is Legal. Not "every play it
accepts is legal", which a check that refused everything would satisfy;
and not "every legal play is accepted", which a check that accepted
everything would satisfy. Both.
The proof follows the shape of check:
unfold check Legalputs both definitions in the goal.rw [← checkAim_none_iff]uses another theorem, proved just before this one, thatcheckAim s me a = none ↔ AimOk s me a. Rewriting right to left replacesAimOk s me ainLegalwithcheckAim s me a = none, so both sides now end with the same thing.by_cases out : (s.player me).outsplits the proof in two: the case where the player is out, and the case where they aren't, with the fact namedoutin each.check's firstiftests exactly that.<;>runs the tactic after it on every goal the tactic before it made.simp only […]simplifies using only the facts listed.↓reduceItetellssimpto simplify anifwhose condition it knows. In the case where the player is out,checksayssome "you are out of this round", which isn'tnone, andLegal's first part is false, so both sides are false and the case is done. Only the other case is left.- The next
by_casesdo the same for holding the card, for the Valkyrie being forced, and for the card being the Valkyrie: one split for eachifincheck. In each case,simp, given the facts of that case, finishes.
The theorem it uses for guesses is a good one to read too:
/-- The guess check accepts exactly the guesses `GuessOk` describes. -/
theorem checkGuess_none_iff (a : Action) : checkGuess a = none ↔ GuessOk a := by
obtain ⟨card, target, guess⟩ := a
unfold checkGuess GuessOk
by_cases raider : card = .raider
· subst raider
cases guess with
| none => simp
| some g => cases g <;> simp
· cases guess <;> simp [raider]
obtain ⟨card, target, guess⟩ := a takes the play apart into its three
fields. subst raider uses card = .raider to replace card everywhere.
cases guess with splits on whether there is a guess, like a match. And
cases g <;> simp splits on every one of the eight cards the guess could be,
and lets simp check each.
A theorem stated with ↔ is used in either direction. .mp turns the left
side into the right, and .mpr the right into the left:
/-- The check accepts it, so it is legal. -/
example : Legal table 0 ⟨.raider, some 1, some .holmgang⟩ :=
(Proofs.LoL.check_none_iff_legal table 0 _).mp rfl
Here check gives none, which rfl sees by working it out, so .mp
gives a proof that the play is legal.
Deciding Legal with check¶
Try decide on Legal table 0 a and it fails: Lean doesn't know how to
decide Legal. But check_none_iff_legal gives a way: to decide whether a
play is legal, run check and see if it says none. Lean can be told that
with an instance, a definition its search uses:
/-- Whether a play is legal can be worked out: run `check`. -/
instance legalDecidable (s : State) (me : Nat) (a : Action) : Decidable (Legal s me a) :=
decidable_of_iff _ (Proofs.LoL.check_none_iff_legal s me a)
example : Legal table 0 ⟨.raider, some 1, some .holmgang⟩ := by decide
example : ¬ Legal table 0 ⟨.raider, some 2, some .holmgang⟩ := by decide
decidable_of_iff makes a way to decide one statement from a way to decide
another and a proof that they are equivalent. With this instance, decide
proves facts about legal plays by running the engine's own check, and the
proof that the check is right is what makes that a proof.
Guarantees that follow¶
Once it is known that every accepted play is Legal, the rules become
guarantees almost for free. The Valkyrie rule is one line:
/-- **The Valkyrie rule.**
A player holding the Valkyrie together with Loki or the Trader can only play
the Valkyrie. -/
theorem valkyrie_must_be_played (accepted : step s a (.play act) = .ok (s', evs))
(forced : valkyrieForced (s.player a).hand = true) : act.card = .valkyrie :=
(accepted_play (play_of_step accepted).2).2.2.2.1.2.2.1 forced
accepted_play is a lemma saying an accepted play was made on the player's
turn, in a game being played, and was Legal, all joined by ∧. .1 and
.2 take the left and right of an ∧, so .2.2.2.1 walks along the chain
to Legal, and .2.2.1 then picks its third part: if forced, then the
Valkyrie. Applied to forced, that is the conclusion.
The other direction matters just as much: the engine must never offer a play
that it would then refuse. The plays it offers are built in Game.lean:
/-- Every play the engine offers `me`, with every combination of arguments. -/
def offeredPlays (s : State) (me : Nat) : List Action :=
if toAct s me then ((s.player me).hand.eraseDups.filter (enabled s me)).flatMap (plays s me) else []
/-- May `c` be played from `me`'s hand now? (The Valkyrie rule.) -/
def enabled (s : State) (me : Nat) (c : Card) : Bool :=
!(valkyrieForced (s.player me).hand && c != .valkyrie)
and this guarantee says they are all accepted:
/-- **Every play the engine offers is accepted.**
The engine never advertises a play that it would then refuse: for the player
to act, every offered card with every offered combination of target and guess
is accepted by `step`. (Clients receive these same choices as JSON.) -/
theorem offered_plays_are_accepted (me : Nat) (a : Action) (offered : a ∈ offeredPlays s me) :
∃ result, step s me (.play a) = .ok result := by
unfold offeredPlays at offered
split at offered
· rename_i acting
simp only [toAct, Bool.and_eq_true, beq_iff_eq, decide_eq_true_eq, Bool.not_eq_true',
List.isEmpty_iff] at acting
obtain ⟨⟨⟨⟨playing, noneWaiting⟩, onTurn⟩, real⟩, notOut⟩ := acting
subst onTurn
simp only [List.mem_flatMap, List.mem_filter] at offered
obtain ⟨c, ⟨inHand, mayPlay⟩, offeredPlay⟩ := offered
obtain ⟨sameCard, aimOk⟩ := offered_aims_are_ok s s.turn c a offeredPlay
-- The offered play is legal...
have legal : Legal s s.turn a := by
refine ⟨notOut, sameCard ▸ List.mem_eraseDups.mp inHand, fun forced => ?_, aimOk⟩
simp [enabled, forced] at mayPlay
exact sameCard ▸ mayPlay
-- ...so the engine's check passes, and `step` carries it out.
have passed := (check_none_iff_legal s s.turn a).mpr legal
refine ⟨apply s s.turn a, ?_⟩
simp [step, play, noneWaiting, playing, Nat.not_le.mpr real, passed]
· simp at offered
The proof builds legal : Legal s s.turn a from what offeredPlays checked,
then uses check_none_iff_legal the other way round, with .mpr, to get
passed : check s s.turn a = none, and finally lets simp run step with
those facts. Notice that enabled uses valkyrieForced, the same function
as Legal. That will matter when you change the rules.
Exercises¶
- Prove that a legal play is of a card the player holds. (Which part of
Legalis it?) - Prove that if
checkgives a reason, the play isn't legal. Hint: assume it is legal withintro, usecheck_none_iff_legalto rewrite the hypothesis, and see what is left. - On the small table, prove that no card may be played at seat 2, whatever
the card. Use
cases c <;> decide. - Change the table so that seat 1 is protected too, and prove that seat 0 may then play the Raider at no one, naming nothing.
Solution
theorem legal_plays_are_held {s : State} {me : Nat} {a : Action} (legal : Legal s me a) :
a.card ∈ (s.player me).hand :=
legal.2.1
theorem refused_is_not_legal {s : State} {me : Nat} {a : Action} {reason : String}
(refused : check s me a = some reason) : ¬ Legal s me a := by
intro legal
rw [(Proofs.LoL.check_none_iff_legal s me a).mpr legal] at refused
cases refused
/-- No one may target the protected seat 2. -/
example (c : Card) : ¬ Legal table 0 ⟨c, some 2, none⟩ := by
cases c <;> decide
/-- With everyone else protected, the Raider is played at no one. -/
example : Legal { table with players := table.players.set 1 { hand := [.holmgang], protected_ := true } } 0
⟨.raider, none, none⟩ := by decide
In the second, after the rewrite, refused says none = some reason,
and cases refused closes the goal: there is no way none could equal
some reason, so there are no cases left to prove. In the third,
cases c makes one goal per card and decide uses the instance
above in each. The fourth works because AimOk allows a targeting card
to be played at no one exactly when no one else can be targeted.