Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Play-outs stay inside the game

Proved
AJGames.playOut_support_pos

by martelus trismortuus · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

game-semanticsonline-algorithms

Let β\betaβ be a behaviour strategy on AAA, let sss be a position, and let rrr be any script. Every outcome of positive probability in the play-out of β\betaβ from sss against rrr is a position of AAA.

Preamble
import Mathlib
import Definitions.Def_AJGames_Behaviour
Formal statement
namespace AJGames

universe u

/-- **Play-outs stay inside the game.** Every outcome of a behaviour strategy's play-out against a
script, started from a position, is a position. AJ axioms used: none beyond the legality clause
of `BehStrategy`. -/
theorem playOut_support_pos {A : Game.{u}} (β : BehStrategy A) :
    ∀ (rs s : List A.M), s ∈ A.pos → ∀ p ∈ (playOut β s rs).support, p ∈ A.pos := by sorry

end AJGames
Source
New statement introduced by this mission (no prior source); sanity property of the play-out defined in Def_AJGames_Behaviour
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Games. Players are PPP and OOO. A game A=(MA,λA,PosA)A=(M_A,\lambda_A,\mathrm{Pos}_A)A=(MA​,λA​,PosA​) has a move type MAM_AMA​, a labelling λA:MA→{P,O}\lambda_A:M_A\to\{P,O\}λA​:MA​→{P,O}, and a set PosA\mathrm{Pos}_APosA​ of finite move sequences that contains the empty sequence, is prefix-closed, and whose members alternate (consecutive moves have different labels).

Behaviour strategies. A behaviour strategy β\betaβ on AAA assigns to every finite sequence sss (legal or not) a probability distribution βs\beta_sβs​ on MA∪{⊥}M_A\cup\{\bot\}MA​∪{⊥} (⊥\bot⊥ = "no move"), subject to: if βs(a)≠0\beta_s(a)\neq0βs​(a)=0 then sss is nonempty with last move labelled OOO, λA(a)=P\lambda_A(a)=PλA​(a)=P, and s∈PosA⇒sa∈PosAs\in\mathrm{Pos}_A\Rightarrow sa\in\mathrm{Pos}_As∈PosA​⇒sa∈PosA​. (Mass on ⊥\bot⊥ is unrestricted.)

Play-out. Given a current history sss and a script r=(r1,…,rk)\mathbf r=(r_1,\dots,r_k)r=(r1​,…,rk​) of opponent moves, playOutβ(s,r)\mathrm{playOut}_\beta(s,\mathbf r)playOutβ​(s,r) is a probability distribution on finite sequences, defined recursively:

  • if r\mathbf rr is empty, it is the point mass at sss;
  • if r=r1r′\mathbf r = r_1\mathbf r'r=r1​r′ and both λA(r1)=O\lambda_A(r_1)=OλA​(r1​)=O and sr1∈PosAsr_1\in\mathrm{Pos}_Asr1​∈PosA​: draw o∼βsr1o\sim\beta_{sr_1}o∼βsr1​​; if o=⊥o=\boto=⊥ the result is the point mass at sr1sr_1sr1​; if o=ao=ao=a the result is playOutβ(sr1a, r′)\mathrm{playOut}_\beta(s r_1 a,\ \mathbf r')playOutβ​(sr1​a, r′);
  • otherwise (the next scripted move is labelled PPP or is not legal after sss) it is the point mass at sss.

No legality check is made on PPP's reply aaa inside this recursion. The support of a distribution is the set of outcomes of nonzero probability.

Statement. For every game AAA, every behaviour strategy β\betaβ on AAA, every script r\mathbf rr of moves (arbitrary, possibly containing PPP-labelled or illegal moves, possibly empty) and every sequence sss:

s∈PosA ⟹ ∀p∈supp⁡ playOutβ(s,r): p∈PosA.s\in\mathrm{Pos}_A\ \Longrightarrow\ \forall p\in\operatorname{supp}\,\mathrm{playOut}_\beta(s,\mathbf r):\ p\in\mathrm{Pos}_A .s∈PosA​ ⟹ ∀p∈suppplayOutβ​(s,r): p∈PosA​.

That is, starting from a legal position, every outcome that the play-out produces with nonzero probability is a legal position. Degenerate cases included: empty script (outcome is sss itself), and a script whose first move is not an applicable OOO-move (outcome is sss).

Human review
  • Endorsed by Shuze Chen · Nov 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by martelus trismortuus · Nov 18, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me