Skip to content

A move

Everything so far has been pieces. This chapter puts them together: the state of a whole game, and the function that applies a move to it. That function, step, is what the engine calls every time a player clicks a button.

The state of a game

structure State where
  hand0 : Hand
  hand1 : Hand
  turn : Fin 2 := 0
  flips : Nat := 0
  maxFlips : Nat
  phase : Phase := .playing
  deriving DecidableEq, Repr, Inhabited

Everything about a game in progress is here: both hands, whose turn it is, how many flips have been made and how many are allowed, and whether the game is over. Some fields have defaults, so a new game only needs its hands and its flip limit:

def start : State :=
  { hand0 := { down := [⟨1, 0⟩, ⟨5, 0⟩] }, hand1 := { down := [⟨1, 2⟩, ⟨9, 3⟩] }, maxFlips := 10 }

Nothing changes

Lean has no assignment: you can't change a field of a value. Instead, { s with flips := 3 } makes a new state, a copy of s with one field different. The old one is still there, unchanged:

/-- info: 3 -/
#guard_msgs in
#eval { start with flips := 3 }.flips

/-- info: 0 -/
#guard_msgs in
#eval start.flips

This sounds wasteful, but it is what makes rules easy to reason about. A move is a function from the state before to the state after, and both states are plain values you can compare, store or prove things about.

Two small functions read and replace a player's hand, by number:

def hand (s : State) : Fin 2 → Hand
  | 0 => s.hand0
  | 1 => s.hand1
def setHand (s : State) : Fin 2 → Hand → State
  | 0, h => { s with hand0 := h }
  | 1, h => { s with hand1 := h }

Moves that can be refused

A move isn't always allowed: it might not be your turn. So a move doesn't simply give back a new state. It gives back either a reason for refusing, or a new state with the events it caused. The type for "an error or a value" is Except, and its two alternatives are .error and .ok. Here is a flip:

def flip (s : State) (p : Fin 2) : Except Rejection (State × List Event) :=
  if p ≠ s.turn then .error ⟨"not your turn"⟩ else
  let h := s.hand p
  let h' := recycle h
  match h'.down with
  | [] => .error ⟨"no cards to flip"⟩
  | c :: rest =>
    let r := settle { s.setHand p { down := rest, up := c :: h'.up } with turn := other p, flips := s.flips + 1 }
    .ok (r.1, (if h.down.isEmpty then [Event.recycled p] else []) ++ [.flipped p c] ++ r.2)

Read it line by line:

  1. If p isn't the player whose turn it is, refuse with a reason. (≠ is not equal; ⟨"not your turn"⟩ makes a Rejection from its one field.)
  2. Take the player's hand, and recycle it: if their stack is empty, turn the face-up pile over to make a new one.
  3. If there is still no card, refuse.
  4. Otherwise, move the top card c to the face-up pile, pass the turn, count the flip, and settle: decide whether the game has just ended.

Here are the two helpers:

/-- With no face-down cards, the face-up pile is turned over to form the stack. -/
def recycle (h : Hand) : Hand :=
  if h.down.isEmpty then { down := h.up.reverse, up := [] } else h
/-- Decide whether the game has just ended. Applied after every accepted action. -/
def settle (s : State) : State × List Event :=
  if s.hand0.size = 0 then ({ s with phase := .finished (some 1) }, [.finished (some 1)])
  else if s.hand1.size = 0 then ({ s with phase := .finished (some 0) }, [.finished (some 0)])
  else if s.flips ≥ s.maxFlips then ({ s with phase := .finished none }, [.finished none])
  else (s, [])

Note what settle doesn't do: it never changes a card. It only ever changes the phase. You'll prove exactly that in a later chapter.

Snap

A snap is never refused: you can always shout. What happens depends on whether the top cards match:

def snap (s : State) (p : Fin 2) : State × List Event :=
  let me := s.hand p
  let them := s.hand (other p)
  if s.isMatch then
    let won := them.up ++ me.up
    let r := settle <| (s.setHand (other p) { them with up := [] }).setHand p
      { down := me.down ++ won.reverse, up := [] }
    (r.1, [.snapped p won.length] ++ r.2)
  else
    let r := settle <| (s.setHand p { me with up := [] }).setHand (other p)
      { them with down := them.down ++ me.up.reverse }
    (r.1, [.falseSnap p me.up.length] ++ r.2)

With a match, the caller takes both face-up piles under their stack. Without one, their own face-up pile goes under the other player's stack. <| passes everything after it as the argument to the function before it, which saves a pair of brackets.

step

Finally, the function the engine calls for every move:

/-- The transition function. -/
def step (s : State) (actor : Nat) (a : Action) : Except Rejection (State × List Event) :=
  match s.phase with
  | .finished _ => .error ⟨"game is over"⟩
  | .playing =>
    if h : actor < 2 then
      let p : Fin 2 := ⟨actor, h⟩
      match a with
      | .flip => flip s p
      | .snap => .ok (snap s p)
    else .error ⟨"no such player"⟩

A finished game accepts nothing. Otherwise the player's number, which comes from outside as a plain Nat, must be below 2; if h : actor < 2 names that fact h, so that ⟨actor, h⟩ can turn the number into a Fin 2, with the proof that it fits. Then a flip goes to flip, and a snap to snap.

Playing a few moves

To try moves in Lean, here is a small helper that says what happened:

/-- What happens when player `p` makes move `a`: the events, or why it was refused. -/
def try_ (s : State) (p : Nat) (a : Action) : String :=
  match step s p a with
  | .error r => s!"refused: {r.reason}"
  | .ok (_, events) => s!"accepted: {repr events}"

Moves out of turn, and by players who don't exist, are refused:

/-- info: "refused: not your turn" -/
#guard_msgs in
#eval try_ start 1 .flip

/-- info: "refused: no such player" -/
#guard_msgs in
#eval try_ start 7 .flip

A flip in turn is accepted:

/-- info: "accepted: [Games.Snap.Event.flipped 0 { rank := 1, suit := 0 }]" -/
#guard_msgs in
#eval try_ start 0 .flip

Both players turn an ace, and the second player snaps:

/-- The game after a move, if it was accepted (or unchanged, if not). -/
def after (s : State) (p : Nat) (a : Action) : State :=
  match step s p a with
  | .ok (s', _) => s'
  | .error _ => s

def twoFlips : State := after (after start 0 .flip) 1 .flip

/-- info: true -/
#guard_msgs in
#eval twoFlips.isMatch

/-- info: "accepted: [Games.Snap.Event.snapped 1 2]" -/
#guard_msgs in
#eval try_ twoFlips 1 .snap

/-- info: 3 -/
#guard_msgs in
#eval (after twoFlips 1 .snap).hand1.size

A snap with nothing showing is a false snap, which costs nothing yet:

/-- info: "accepted: [Games.Snap.Event.falseSnap 0 0]" -/
#guard_msgs in
#eval try_ start 0 .snap

Exercises

  1. Write play, which applies a list of moves to a game in order. Each move is a pair of a player and an action. Hint: handle the empty list, and a list (p, a) :: rest, by calling play again on the rest.
  2. Use it to find a short game that ends with a winner, and one that ends in a draw.
Solution
/-- Play a list of moves in order, each by the given player. -/
def play (s : State) : List (Nat × Action) → State
  | [] => s
  | (p, a) :: rest => play (after s p a) rest

def lastCard : State :=
  { hand0 := { down := [⟨2, 0⟩] }, hand1 := { down := [⟨3, 1⟩, ⟨8, 1⟩] }, maxFlips := 10 }

/-- info: Games.Snap.Phase.finished (some 1) -/
#guard_msgs in
#eval (play lastCard [(0, .flip), (0, .snap)]).phase

/-- info: Games.Snap.Phase.finished none -/
#guard_msgs in
#eval (play { start with maxFlips := 2 } [(0, .flip), (1, .flip)]).phase

In the first game, player 0 turns their only card, then calls a false snap and gives it away: with no cards left, they lose. In the second, the flip limit is 2, so two flips end it as a draw.