Behaviour strategies, play probability and play-out against a script
DefinitionAJGames_BehaviourA behaviour strategy for Player in assigns to every finite sequence a probability distribution on . A move may have positive probability only if three conditions hold:
- Player is to move at , meaning the last move of is an Opponent move;
- is a Player move;
- is a position whenever is.
The file defines the following derived notions.
- The probability of a play is the product, over the Player moves of , of the probability gave after the prefix preceding it.
- depends on a function of histories when implies ; history-free is the case where returns the last move.
- A deterministic strategy is read as a behaviour strategy by putting all mass on 's Player move when it has one, and on otherwise.
- The play-out of from a position against a script of moves is a distribution on finite plays. If is an Opponent move and is a position, play it and draw from . A move continues the play with ; stops it, and is the outcome. Otherwise, and when the script is exhausted, the outcome is .
The play-out is the semantics of a randomised online algorithm against an oblivious adversary.
Formalization Note Opponent's moves are not randomised; an oblivious adversary fixes them in advance. Distributions are Mathlib PMFs.
import Mathlib
import Definitions.Def_AJGames_Strategy
/-!
# Behaviour strategies in Abramsky–Jagadeesan games
A *behaviour strategy* for Player gives, at every position, a probability distribution over Player's
next move, or `none` (no move). This is Kuhn's notion of behaviour strategy (H. W. Kuhn,
*Extensive games and the problem of information*, Contributions to the Theory of Games II, 1953)
placed on AJ games (Abramsky and Jagadeesan, J. Symbolic Logic 59(2), 1994, Definition 2). It is the
form in which randomised online algorithms, such as memoryless policies, appear as strategies.
**Formalization Note.** Finite-play (safety) fragment. Opponent moves are not randomised: an
oblivious adversary fixes them. `playProb β s` is the probability that Player, following `β`, makes
every Player move of `s` when Opponent plays the Opponent moves of `s`. A deterministic strategy
`σ` is read as the behaviour strategy `ofStrategy σ`, which puts all its mass on `σ`'s move when
`σ` has one and on `none` otherwise.
-/
namespace AJGames
universe u
open scoped ENNReal
variable {A : Game.{u}}
/-- Player is to move at `s`: the last move of `s` was an Opponent move. Opponent opens, so
Player is not to move at `[]`. -/
def PlayerToMove (A : Game.{u}) (s : List A.M) : Prop :=
∃ m, s.getLast? = some m ∧ A.lab m = Pl.O
/-- A behaviour strategy for Player in `A`: a distribution over Player's next move (or `none`) at
every position. Moves in the support are legal Player moves, offered only when Player is to move. -/
structure BehStrategy (A : Game.{u}) where
next : List A.M → PMF (Option A.M)
legal : ∀ s a, next s (some a) ≠ 0 →
PlayerToMove A s ∧ A.lab a = Pl.P ∧ (s ∈ A.pos → s ++ [a] ∈ A.pos)
/-- Probability of a play, computed on the reversed play (last move first). -/
noncomputable def playProbRev (β : BehStrategy A) : List A.M → ℝ≥0∞
| [] => 1
| a :: r => playProbRev β r * (if A.lab a = Pl.P then β.next r.reverse (some a) else 1)
/-- The probability that Player, following `β`, makes every Player move of `s` when Opponent
plays the Opponent moves of `s`: the product of `β`'s probabilities of its own moves. -/
noncomputable def playProb (β : BehStrategy A) (s : List A.M) : ℝ≥0∞ :=
playProbRev β s.reverse
/-- `β` is history-free: its next-move distribution depends only on the last move. -/
def BehStrategy.HistoryFree (β : BehStrategy A) : Prop :=
∀ s t : List A.M, s.getLast? = t.getLast? → β.next s = β.next t
/-- `β` depends on the history only through `f`. `HistoryFree` is the case `f = List.getLast?`;
a memoryless online policy depends on (current configuration, last request). -/
def BehStrategy.DependsOn {S : Type*} (β : BehStrategy A) (f : List A.M → S) : Prop :=
∀ s t : List A.M, f s = f t → β.next s = β.next t
/-- If `σ` has a Player move at `s`, then Player is to move at `s`. -/
theorem Strategy.playerToMove_of_move (σ : Strategy A) {s : List A.M} {b : A.M}
(hb : s ++ [b] ∈ σ.carrier) (hP : A.lab b = Pl.P) : PlayerToMove A s := by
cases hl : s.getLast? with
| none =>
have : s = [] := List.getLast?_eq_none_iff.1 hl
subst this
have := σ.first_O b [] (by simpa using hb)
rw [hP] at this; cases this
| some m =>
refine ⟨m, hl, ?_⟩
have halt := A.alt _ (σ.subset_pos hb)
have hne : A.lab m ≠ A.lab b := (List.isChain_append.1 halt).2.2 m hl b (by simp)
rw [hP] at hne
cases h : A.lab m
· exact absurd h hne
· rfl
open Classical in
/-- A deterministic strategy read as a behaviour strategy: all mass on `σ`'s move when it has one,
otherwise on `none`. -/
noncomputable def ofStrategy (σ : Strategy A) : BehStrategy A where
next s := if h : ∃ b, s ++ [b] ∈ σ.carrier ∧ A.lab b = Pl.P then PMF.pure (some h.choose)
else PMF.pure none
legal := by
intro s a ha
by_cases h : ∃ b, s ++ [b] ∈ σ.carrier ∧ A.lab b = Pl.P
· rw [dif_pos h, PMF.pure_apply] at ha
have hab : some a = some h.choose := by
by_contra hne; exact ha (if_neg hne)
cases hab
obtain ⟨hmem, hP⟩ := h.choose_spec
exact ⟨σ.playerToMove_of_move hmem hP, hP, fun _ => σ.subset_pos hmem⟩
· rw [dif_neg h, PMF.pure_apply] at ha
exact absurd (if_neg (by simp)) ha
open Classical in
/-- **Play-out against an oblivious adversary** (stop-counts semantics). From position `s`, the
adversary's remaining script is `rs`. The next request `r` is played if it is a legal Opponent move;
Player then draws from `β.next`. A move `a` continues the play; `none` stops it, and the play so far
is an outcome with that probability. The play also stops when the script runs out or the next
request is not a legal Opponent move. -/
noncomputable def playOut (β : BehStrategy A) : List A.M → List A.M → PMF (List A.M)
| s, [] => PMF.pure s
| s, r :: rs =>
if A.lab r = Pl.O ∧ s ++ [r] ∈ A.pos then
(β.next (s ++ [r])).bind fun o =>
o.elim (PMF.pure (s ++ [r])) fun a => playOut β (s ++ [r] ++ [a]) rs
else PMF.pure s
end AJGames
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back: Def_AJGames_Behaviour
Background (from the context files)
A game consists of a type of moves , a labelling , and a set of finite sequences of moves (the positions) such that: the empty sequence is a position; every prefix of a position is a position; and every position is alternating, i.e. any two consecutive moves in it have different labels. Nothing requires the first move of a position to have label .
A (deterministic) strategy on is a set of positions which contains , is prefix-closed, in which every non-empty play starts with an -labelled move, which is deterministic (if and with , then ), and receptive (if , and , then ). Plays in may end on an -move with no -answer in .
Throughout, is an arbitrary game (in a fixed universe). "Sequence" below means an arbitrary finite list of moves of , not necessarily a position. is with appended; is the last move of if and undefined ("none") if .
PlayerToMove
For a game and a sequence , holds iff is non-empty and its last move has label :
It is false at the empty play , and false whenever ends with a -move. It does not require .
BehStrategy (behavioural strategy)
A behavioural strategy on consists of:
- a map assigning to every finite sequence of moves (position or not) a probability distribution on (a probability mass function on the option type, total mass );
- a legality condition: for every sequence and every move , if then
- (so is non-empty and ends with an -move),
- , and
- if then .
The value "none" represents not moving (stopping). There is no constraint on the mass placed on none: it may be anything from to at any . Consequences of the condition: at the empty play , and at every sequence ending with a -move, is the point mass on none. For sequences ending in an -move, positive mass may sit on any -labelled move with no positional constraint.
playProbRev and playProb
is defined by recursion on a list written in reverse order (most recent move first), with values in :
Then . Unfolded, for :
-moves contribute factor ; the empty play has probability ; a sequence with no -moves has probability . No membership in is checked, and no factor accounts for stopping (mass on none is never used).
BehStrategy.HistoryFree
is history-free iff for all sequences with (where both being empty counts as equal, and a non-empty sequence never matches an empty one), . The condition ranges over all sequences, not only positions.
BehStrategy.DependsOn
For any type and any function from sequences to , depends on iff for all sequences , implies (i.e. factors through ). For constant this forces to be constant, hence (by legality at ) everywhere the point mass on none.
Strategy.playerToMove_of_move (theorem)
For every strategy on , every sequence and every move : if and , then , i.e. is non-empty and its last move has label .
ofStrategy
Given a strategy on , is the behavioural strategy with
where is a witness selected by the axiom of choice among such (by determinism of the witness is in fact unique), and denotes a point mass. Thus it is deterministic; it stops (none) at every where has no -extension, including , sequences ending with a -move, sequences not in , and plays in ending with an -move that leaves unanswered. Legality holds by the theorem above and .
playOut
, for a current sequence and a finite list of moves (an opponent script fixed in advance), is a probability distribution on finite sequences, defined by recursion on :
- .
- :
- if and : draw ; if , the result is (the play stops after and the rest of the script is discarded); if , continue with ;
- otherwise (if is -labelled or is not a position) the result is : and the rest of the script are discarded and the play stops at .
Remarks: the script entries are not adapted to the random replies; an entry that is illegal after a particular reply stops the play there. No check that is made in the recursion (legality of supplies it when is a position). The starting itself is not checked to be a position. Outcomes can end on a -reply (script exhausted after a reply), on an -move (stop by none), or earlier (illegal or -labelled script entry). With the outcome is with probability .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.