Game Semantics

Tic-Tac-Toe

The game of tic-tac-toe as an arena: Opponent starts, Proponent plays X. Occupancy and terminal positions are arena legality, so every strategy is automatically a legal playing policy. Perfect play is minimax; it never loses.

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

Arena

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

Strategies

perfect

Minimax. Never loses with X.

Trace against auto. (stuck — Ω)

start? 0₀
x-8! 1₁
o-0? 2₂
x-7! 3₃
o-1? 4₂

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.

ε
Ostart?
Px-8!

center-first

Take the centre if free, otherwise the first empty cell.

Trace against auto. (stuck — Ω)

start? 0₀
x-4! 1₁
o-0? 2₂
x-1! 3₃
o-2? 4₂

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.

ε
Ostart?
Px-4!

naive

Always the first empty cell (row-major).

Trace against auto. (stuck — Ω)

start? 0₀
x-0! 1₁
o-1? 2₂
x-2! 3₃
o-3? 4₂

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.

ε
Ostart?
Px-0!

bot

The empty strategy Ω: Proponent never moves.

Trace against auto. (stuck — Ω)

start? 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.

ε
Ostart?
Ω