Skip to content

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 a g such 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⟩

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:

  1. unfold check Legal puts both definitions in the goal.
  2. rw [← checkAim_none_iff] uses another theorem, proved just before this one, that checkAim s me a = none ↔ AimOk s me a. Rewriting right to left replaces AimOk s me a in Legal with checkAim s me a = none, so both sides now end with the same thing.
  3. by_cases out : (s.player me).out splits the proof in two: the case where the player is out, and the case where they aren't, with the fact named out in each. check's first if tests exactly that.
  4. <;> runs the tactic after it on every goal the tactic before it made. simp only […] simplifies using only the facts listed. ↓reduceIte tells simp to simplify an if whose condition it knows. In the case where the player is out, check says some "you are out of this round", which isn't none, and Legal's first part is false, so both sides are false and the case is done. Only the other case is left.
  5. The next by_cases do the same for holding the card, for the Valkyrie being forced, and for the card being the Valkyrie: one split for each if in check. 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.

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

  1. Prove that a legal play is of a card the player holds. (Which part of Legal is it?)
  2. Prove that if check gives a reason, the play isn't legal. Hint: assume it is legal with intro, use check_none_iff_legal to rewrite the hypothesis, and see what is left.
  3. On the small table, prove that no card may be played at seat 2, whatever the card. Use cases c <;> decide.
  4. 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.