Skip to content

A table

A game's state is not all a table needs. It also needs the moves made so far, the events each player may read, the players' names and the keys that open each seat. None of that belongs to any game's rules, so the engine keeps it, once, for every game, in a session.

The session

structure Session (σ : Type) where
  config : Json
  state : σ
  /-- Accepted actions as `{actor, action}`, in order. -/
  log : Array Json := #[]
  /-- Events emitted by accepted actions, in order, with their audience. -/
  events : Array (Audience × Json) := #[]
  /-- Which game this is at the table: 1, then 2 after a rematch, and so on. -/
  games : Nat := 1
  /-- The table's keys, once locked (`lock`). Until then no request opens it. -/
  keys : Option Keys := none
  /-- What the players are called, seat by seat (from the config's "names"). -/
  names : List String := []
  deriving Inhabited

Session σ is a session of the game whose state is σ: Session Games.Snap.State is a Snap table, Session Games.Alba.State an Alba one. Around the game's state it keeps:

  • config, the JSON the table was started from, and log, every accepted move with who made it. With the two, the whole game can be replayed, because the deal comes from the config's seed.
  • events, every event so far, each tagged with its Audience: who may see it.
  • keys, once the table is locked, and names, the players' names.

Array is like List, but stored in one block of memory, so adding to the end and reading by position are fast. #[] is the empty array.

A session is started from a config. The engine asks the game to init, and checks the names itself: one per seat, none empty, all different.

/-- A config: the seed for the deal, and the players' names. -/
def config : Json := .obj #[("seed", 3), ("names", .arr #["Ada", "Brian"])]

/-- A Snap table, started from that config. -/
def table : Session Games.Snap.State :=
  match Session.start config with
  | .ok s => s
  | .error _ => default

/-- info: ["Ada", "Brian"] -/
#guard_msgs in
#eval table.names

/-- info: "config 'names': every name must be different" -/
#guard_msgs in
#eval match Session.start (σ := Games.Snap.State) (.obj #[("names", .arr #["Ada", "Ada"])]) with
  | .ok _ => "started"
  | .error e => e

The match handles a failed start; this one can't fail, so it never reaches default (a session with every field at its default, which deriving Inhabited provides).

nameOf turns the list of names into a Names function, falling back to seatName for a seat with no name:

/-- What seat `i`'s player is called. -/
def nameOf (s : Session σ) : Names := fun i => s.names.getD i (seatName i)

s.names.getD i (seatName i) reads position i of the list, or gives the default if there is none.

What a player is sent

/-- What `v` sees: the same shape for every game. Refused for a seat that
does not exist. -/
def view (s : Session σ) (v : Viewer) : Except String Json :=
  if !s.admits v then .error s!"no such seat (the game has {Game.seats s.state})" else
  .ok <| .obj #[
    ("game", Game.name σ),
    ("seats", Json.ofNat (Game.seats s.state)),
    ("names", Json.ofList Json.str s.names),
    ("you", match v with | .player i => Json.ofNat i | .debug => .null),
    ("phase", (Game.phase s.nameOf s.state).toJson),
    ("waitingFor", Json.ofList Json.ofNat (Game.waitingFor s.state)),
    ("catalogue", Game.catalogue s.state),
    ("observation", Game.observe s.state v),
    ("actions", .arr (Game.actions s.nameOf s.state v |>.map ActionSpec.toJson).toArray),
    ("events", .arr (visible s.events v)),
    ("outcome", (s.outcome.map Outcome.toJson).getD .null)]

Apart from the replies to their own moves, this is all a player is ever sent about a game, and it has the same shape for every game. Each part is the game's answer to one of the class's questions, asked with the table's names: the phase, who is awaited, the catalogue, the observation for this viewer, the moves offered to them, the events they may see and the outcome. visible keeps only the events whose audience admits the viewer.

A view for a seat the game doesn't have is refused:

/-- info: {"id":"playing","title":"Play","text":"Ada to flip. Call snap whenever the two face-up cards match."} -/
#guard_msgs in
#eval match table.view (.player 0) with
  | .ok j => IO.println ((j.get? "phase").getD .null)
  | .error e => IO.println e

/-- info: no such seat (the game has 2) -/
#guard_msgs in
#eval match table.view (.player 2) with
  | .ok j => IO.println j
  | .error e => IO.println e

IO.println prints a value as text: for Json, the JSON the browser would receive.

Making a move

/-- Apply one client action. On rejection the session is returned unchanged. -/
def submit (s : Session σ) (actor : Nat) (action : Json) : Session σ × Json :=
  if actor ≥ Game.seats s.state then (s, refusal "seat" "no such seat") else
  match (Game.decodeAction (σ := σ) action) with
  | .error e => (s, refusal "malformed" s!"malformed action: {e}")
  | .ok a =>
    match Game.step s.state actor a with
    | .error r => (s, refusal "illegal" r.reason)
    | .ok (state', evs) =>
      let evs := (evs.zipIdx.map fun (e, k) =>
        (Game.audience (σ := σ) e, eventJson (σ := σ) s.nameOf (s.events.size + k) e)).toArray
      let mine := visible evs (.player actor)
      ({ s with state := state'
                log := s.log.push (.obj #[("actor", Json.ofNat actor), ("action", action)])
                events := s.events ++ evs },
       .obj #[("ok", true), ("events", .arr mine)])

A move arrives as JSON from a seat number. submit checks, in order:

  1. that the seat exists (code seat),
  2. that the JSON is a move of this game, using the game's decodeAction (code malformed),
  3. that the rules allow it, using the game's step (code illegal).

Only then does it build the new session, with { s with … }: the new state, the move added to the log, and the new events added to the history. Each event is numbered (seq), given its plain-words text, and tagged with its audience. The reply to the mover contains only the new events they may see.

def flipMove : Json := .obj #[("id", "flip")]

/-- info: {"ok":false,"code":"seat","reason":"no such seat"} -/
#guard_msgs in
#eval IO.println (table.submit 7 flipMove).2

/-- info: {"ok":false,"code":"malformed","reason":"malformed action: unknown action 'jump'"} -/
#guard_msgs in
#eval IO.println (table.submit 0 (.obj #[("id", "jump")])).2

/-- info: {"ok":false,"code":"illegal","reason":"not your turn"} -/
#guard_msgs in
#eval IO.println (table.submit 1 flipMove).2

/-- info: {"ok":true,"events":[{"seq":0,"text":"Ada turned A♥","type":"flipped","player":0,"card":{"rank":1,"suit":"H","label":"A♥","red":true}}]} -/
#guard_msgs in
#eval IO.println (table.submit 0 flipMove).2

/-- info: #[{"actor":0,"action":{"id":"flip"}}] -/
#guard_msgs in
#eval IO.println (table.submit 0 flipMove).1.log

Rejection changes nothing

Look at the three refusals in submit: each gives back s, the session it was given. The engine proves that, for every game:

/-- **A rejected action changes nothing.**

If the action decodes but the game's rules refuse it, the session is returned
exactly as it was: no state change, no log entry, no events. -/
theorem rejected_action_changes_nothing (s : Session σ) (actor : Nat) (sent : Json)
    {act : Game.Action σ} {why : Rejection}
    (decoded : Game.decodeAction (σ := σ) sent = .ok act)
    (refused : Game.step s.state actor act = .error why) :
    (s.submit actor sent).1 = s := by
  -- The rules' refusal is passed straight back with the original session.
  simp only [Session.submit, decoded, refused]
  split <;> rfl

Game.decodeAction (σ := σ) sent = .ok act names the hypothesis that the move decodes, and refused the hypothesis that the rules refuse it. The conclusion, (s.submit actor sent).1 = s, is about the whole session: not only the state, but the log, the events and the keys. .1 is the first half of the pair submit returns. The proof unfolds submit, rewrites with the two hypotheses, and what is left is s = s in every branch.

Its companions say the same for a malformed move and for a seat that doesn't exist:

/-- **A malformed action changes nothing.**

If the engine cannot even decode what a client sent, the session is returned
exactly as it was. -/
theorem malformed_action_changes_nothing (s : Session σ) (actor : Nat) (sent : Json) {why : String}
    (malformed : Game.decodeAction (σ := σ) sent = .error why) :
    (s.submit actor sent).1 = s := by
  -- `submit` checks the seat and decodes first, and rejects before touching the session.
  simp only [Session.submit, malformed]
  split <;> rfl

These theorems know nothing about any game: σ could be any type with a Game instance. So each game gets them for nothing. A game's own theorems say when its rules refuse a move; the engine's say what a refusal does to the table. Put together, they say something about one game's tables, as the exercises show.

Names are only labels

Rename the players and make the same move. The words differ:

/-- The same table, with its players called something else. -/
def renamed : Session Games.Snap.State := { table with names := ["Cat", "Dan"] }

/-- info: {"ok":true,"events":[{"seq":0,"text":"Cat turned A♥","type":"flipped","player":0,"card":{"rank":1,"suit":"H","label":"A♥","red":true}}]} -/
#guard_msgs in
#eval IO.println (renamed.submit 0 flipMove).2

#guard toString (renamed.submit 0 flipMove).1.log == toString (table.submit 0 flipMove).1.log

but the #guard shows the log is the same. The engine proves this for every move, at every table, of every game:

/-- **Names are only labels: renaming the players changes nothing in the game.**

A move has the same effect on the game, and is logged the same, whatever the
players are called; only the words of the events differ. -/
theorem names_change_nothing_in_the_game (s : Session σ) (ns : List String) (actor : Nat) (sent : Json) :
    ({ s with names := ns }.submit actor sent).1.state = (s.submit actor sent).1.state ∧
      ({ s with names := ns }.submit actor sent).1.log = (s.submit actor sent).1.log := by
  unfold Session.submit
  dsimp only
  split
  · exact ⟨rfl, rfl⟩
  · split
    · exact ⟨rfl, rfl⟩
    · split
      · exact ⟨rfl, rfl⟩
      · exact ⟨rfl, rfl⟩

{ s with names := ns } is the same session with other names. The proof unfolds submit and follows each if and match with split; in every branch the state and the log are built from the same things, so rfl closes each, and exact ⟨rfl, rfl⟩ proves both halves of the ∧. (dsimp only makes the small simplifications that need no lemmas, such as reading the names field of { s with names := ns }.)

Keys

Anyone who can reach a server can send it a request. So a table is locked with keys: one secret per seat, and one for the owner, which opens the all-seeing debug view. The hosts make the keys and hand each player only their own.

/-- The secrets that open a table: one per seat, and the owner's (which opens
the all-seeing view). Hosts make them, from a secure random source, and hand
each player only their own; the engine checks every request against them. -/
structure Keys where
  seats : List String
  owner : String
  deriving Inhabited, Repr
/-- Lock a session with its keys: exactly one per seat, none empty, all
different (the owner's too), so no key can open two places. -/
def lock (s : Session σ) (k : Keys) : Except String (Session σ) :=
  if k.seats.length ≠ Game.seats s.state then .error "keys: one key per seat is needed"
  else if (k.owner :: k.seats).any (·.isEmpty) then .error "keys: a key must not be empty"
  else if !(k.owner :: k.seats).Nodup then .error "keys: every key must be different"
  else .ok { s with keys := some k }

lock refuses keys that are missing, empty or repeated. Nodup says a list has no duplicates. opens says whether a key opens a place, and viewAs and submitAs check it before doing anything:

/-- Does `key` open viewer `v`'s place: a seat with that seat's key, the
all-seeing view with the owner's? An unlocked session opens to no one. -/
def opens (s : Session σ) (v : Viewer) (key : String) : Bool :=
  match s.keys, v with
  | some k, .player i => k.seats[i]? == some key
  | some k, .debug => k.owner == key
  | none, _ => false
/-- A move, made only with the actor's own seat's key. -/
def submitAs (s : Session σ) (actor : Nat) (key : String) (action : Json) : Session σ × Json :=
  if s.opens (.player actor) key then s.submit actor action
  else (s, refusal "key" "this seat's key is needed")

k.seats[i]? reads position i of the list, or none if there is none, so a seat beyond the end is opened by nothing. Here is a table locked with keys, and Brian's key tried on Ada's seat:

def keys : Keys := { seats := ["ada-secret", "brian-secret"], owner := "owner-secret" }

def locked : Session Games.Snap.State :=
  match table.lock keys with
  | .ok s => s
  | .error _ => default

/-- info: key: this place's key is needed -/
#guard_msgs in
#eval match locked.viewAs (.player 0) "brian-secret" with
  | .ok j => IO.println j
  | .error e => IO.println e

/-- info: {"ok":false,"code":"key","reason":"this seat's key is needed"} -/
#guard_msgs in
#eval IO.println (locked.submitAs 0 "brian-secret" flipMove).2

/-- info: keys: every key must be different -/
#guard_msgs in
#eval match table.lock { keys with owner := "ada-secret" } with
  | .ok _ => IO.println "locked"
  | .error e => IO.println e

The proofs say what this means for every game. Only a seat's own key opens its view:

/-- **A seat's view goes only to whoever holds that seat's key.** -/
theorem only_the_seats_key_opens_its_view (s : Session σ) (i : Nat) (key : String) (j : Json)
    (shown : s.viewAs (.player i) key = .ok j) :
    ∃ k, s.keys = some k ∧ k.seats[i]? = some key := by
  unfold Session.viewAs at shown
  cases locked : s.keys with
  | none => simp [Session.opens, locked] at shown
  | some k =>
    by_cases opened : s.opens (.player i) key
    · simp only [Session.opens, locked, beq_iff_eq] at opened
      exact ⟨k, rfl, opened⟩
    · simp [opened] at shown

No key opens two seats:

omit [Game σ] in
/-- **No key opens two seats.**

On a locked table every key is different, so whatever opens seat `i` and
seat `j` shows that `i` and `j` are the same seat. -/
theorem no_key_opens_two_seats (s : Session σ) (k : Keys) (locked : s.keys = some k)
    (distinct : (k.owner :: k.seats).Nodup) {i j : Nat} {key : String}
    (opensI : s.opens (.player i) key) (opensJ : s.opens (.player j) key) : i = j := by
  simp only [Session.opens, locked, beq_iff_eq] at opensI opensJ
  have nodup : k.seats.Nodup := (List.nodup_cons.mp distinct).2
  obtain ⟨hi, -⟩ := List.getElem?_eq_some_iff.mp opensI
  exact nodup.eq_of_getElem?_eq hi (opensI.trans opensJ.symm)

omit [Game σ] in tells Lean that this theorem doesn't need the Game instance that the variable line would otherwise add: keys are the same whatever the game. The proof takes apart what opens says for each seat, k.seats[i]? = some key and k.seats[j]? = some key, and uses the fact that a list with no duplicates has each value at one position only.

And a move without the mover's key changes nothing:

/-- **A move made without the actor's own seat's key changes nothing.** -/
theorem a_move_without_the_key_changes_nothing (s : Session σ) (actor : Nat) (key : String) (sent : Json)
    (shut : s.opens (.player actor) key = false) :
    (s.submitAs actor key sent).1 = s := by
  simp [Session.submitAs, shut]

Secrecy, for every game

In Snap's chapter on secrecy, the proof that a view reveals nothing hidden started with a lemma from the engine. Here it is:

/-- A view is built from nothing but its parts: the seat count and the
players' names, the phase, who is awaited, the catalogue, the viewer's
observation and offers, the events they are admitted to, and the outcome. Two
sessions that agree on those (the worded parts for any names) give the viewer
exactly the same view. (Each game's secrecy guarantee uses this to cover
everything a player is sent.) -/
theorem view_is_built_from_its_parts {σ : Type} [Engine.Game σ] {s t : Engine.Session σ} {v : Engine.Viewer}
    (seats : Engine.Game.seats s.state = Engine.Game.seats t.state) (names : s.names = t.names)
    (phase : ∀ who, Engine.Game.phase who s.state = Engine.Game.phase who t.state)
    (waiting : Engine.Game.waitingFor s.state = Engine.Game.waitingFor t.state)
    (catalogue : Engine.Game.catalogue s.state = Engine.Game.catalogue t.state)
    (observe : Engine.Game.observe s.state v = Engine.Game.observe t.state v)
    (actions : ∀ who, Engine.Game.actions who s.state v = Engine.Game.actions who t.state v)
    (events : Engine.Session.visible s.events v = Engine.Session.visible t.events v)
    (outcome : ∀ who, Engine.Game.outcome who s.state = Engine.Game.outcome who t.state) :
    s.view v = t.view v := by
  have named : s.nameOf = t.nameOf := by funext i; simp [Engine.Session.nameOf, names]
  cases v <;>
    simp only [Engine.Session.view, Engine.Session.admits, Engine.Session.outcome, seats, names, named, phase,
      waiting, catalogue, observe, actions, events, outcome] <;>
    rfl

It says: if two sessions agree on every part view is built from, the viewer's views of them are equal. It is the one place where the shape of a view is taken apart, so a game's secrecy proof never needs to look at it. Each game supplies only its own part: that its phase, its observation, its offers and its outcome are the same for two games that look the same to the player. Snap, Lol and Alba each do this for their own secrets, with their own LookSame.

∀ who in the hypotheses matters. The worded parts must agree for any names, not only the table's, which is part of why secrecy holds whatever the players are called.

Exercises

  1. On the locked table above, make Ada's first flip with her own key. What is the reply?
  2. Prove that a table that hasn't been locked opens to no one, in any game. (Hint: simp, told about Session.opens and your hypothesis.)
  3. Prove that a finished Snap table ignores every move it can decode, by putting together Snap's finished_game_rejects_everything and the engine's rejected_action_changes_nothing. (Hint: obtain the reason from the first, then exact the second.)
Solution
/-- info: {"ok":true,"events":[{"seq":0,"text":"Ada turned A♥","type":"flipped","player":0,"card":{"rank":1,"suit":"H","label":"A♥","red":true}}]} -/
#guard_msgs in
#eval IO.println (locked.submitAs 0 "ada-secret" flipMove).2

/-- A table that has not been locked opens to no one, in any game. -/
theorem unlocked_opens_to_no_one {σ : Type} [Game σ] (s : Session σ) (v : Viewer) (key : String)
    (unlocked : s.keys = none) : s.opens v key = false := by
  simp [Session.opens, unlocked]

open Games.Snap in
/-- A finished Snap table ignores every move it can decode. -/
theorem finished_table_changes_nothing (s : Session State) (actor : Nat) (sent : Json) (act : Action)
    {w : Option (Fin 2)} (decoded : Game.decodeAction (σ := State) sent = .ok act)
    (over : s.state.phase = .finished w) :
    (s.submit actor sent).1 = s := by
  obtain ⟨why, refused⟩ := Proofs.Snap.finished_game_rejects_everything over actor act
  exact Proofs.Engine.rejected_action_changes_nothing s actor sent decoded refused

The third is the pattern for every game: the game proves when its rules refuse, and the engine proves what refusing does. Lean accepts refused, a fact about Snap's step, where the engine's theorem wants one about Game.step, because the instance says step := step, and Lean sees that the two are the same.