Game Semantics

Backtracking Choice

Search a predicate N → B for a witness. exists-true queries 0,1,2,… until the predicate returns tt. When Opponent backtracks to an earlier query, innocence forces Proponent to replay the same Nat; there is no mutable search index.

Type (N → B) → B

OP?!₁P-viewΩ…₊ / ₋₁ ₂ ₃

Arena

Enabling structure of the arena (each move drawn once). Hover a move for its role. Enabling.

Strategies

exists-true

Search from 0 upward until the predicate returns tt.

Trace against auto. (truncated by bound)

q? 0₀
q₁? 1₁
q₁₁? 2₂
0₁₁! 3₃
q₁₁? 4₂
0₁₁! 5₅
q₁₁? 6₂
0₁₁! 7₇
q₁₁? 8₂
0₁₁! 9₉
q₁₁? 10₂
0₁₁! 11₁₁

P-view

Strategy tree

Unfolding against every legal Opponent continuation, up to the page bound. O branches fan out; P is a single reply. Click a reply count to expand folded Opponent options.

ε
Oq?
Pq₁?

exists-from-2

Search from 2 upward.

Trace against auto. (truncated by bound)

q? 0₀
q₁? 1₁
q₁₁? 2₂
2₁₁! 3₃
q₁₁? 4₂
2₁₁! 5₅
q₁₁? 6₂
2₁₁! 7₇
q₁₁? 8₂
2₁₁! 9₉
q₁₁? 10₂
2₁₁! 11₁₁

P-view

Strategy tree

Unfolding against every legal Opponent continuation, up to the page bound. O branches fan out; P is a single reply. Click a reply count to expand folded Opponent options.

ε
Oq?
Pq₁?

never-look

Answer ff without querying the predicate.

Trace against auto. (truncated by bound)

q? 0₀
ff! 1₁
q? 2₀
ff! 3₃
q? 4₀
ff! 5₅
q? 6₀
ff! 7₇
q? 8₀
ff! 9₉
q? 10₀
ff! 11₁₁

P-view

Strategy tree

Unfolding against every legal Opponent continuation, up to the page bound. O branches fan out; P is a single reply. Click a reply count to expand folded Opponent options.

ε
Oq?
Pff!
Oq?
Pff!
Oq?
Pff!
Oq?
Pff!
… (bound)

bot

The empty strategy Ω: Proponent never moves.

Trace against auto. (stuck — Ω)

q? 0₀

P-view

Strategy tree

Unfolding against every legal Opponent continuation, up to the page bound. O branches fan out; P is a single reply. Click a reply count to expand folded Opponent options.

ε
Oq?
Ω