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 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:
- If
pisn't the player whose turn it is, refuse with a reason. (≠is not equal;⟨"not your turn"⟩makes aRejectionfrom its one field.) - Take the player's hand, and
recycleit: if their stack is empty, turn the face-up pile over to make a new one. - If there is still no card, refuse.
- Otherwise, move the top card
cto the face-up pile, pass the turn, count the flip, andsettle: 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:
Exercises¶
- 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 callingplayagain on the rest. - 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.