Tic-Tac-Toe Petri-Net Model

Navigation

• Overview
• Stage 1 — Grid & Turns
• Stage 2 — Adding History
• Pattern Collectors & Win Detection
• Visualizations
• Conclusion & Future Work

Overview

This post walks through two complementary Petri-net formulations of tic-tac-toe, progressing from a minimal turn-based grid to a memory-augmented model capable of reasoning about win conditions. These examples demonstrate how Petri nets naturally encode available actions, enforce alternation, and accumulate structured history for higher-level reasoning.

The final sections outline how these models can be converted into ODE systems via Petri.jl and how to apply parameter sweeps to explore strategy, reachability, and path likelihoods.

Stage 1 — Grid & Turns

In the first stage, we represent the tic-tac-toe grid as nine places P00–P22, each initialized with a token indicating an empty cell.

For every square we define:

• Xij transitions — claim the square for X
• Oij transitions — claim the square for O

A dedicated Next place enforces turn-taking:

• Each X move deposits a token into Next
• Each O move consumes that token
• O moves cannot fire unless Next is marked, preserving alternation

This structure cleanly separates:

1. Geometry
2. Legal actions
3. Alternating turn flow

All purely through token movement and local composability—no global logic required.

Model Diagram (Stage 1)

Stage 2 — Adding History

The second version keeps the same grid & turn logic but introduces a memory layer.

Whenever a move fires (e.g. X00):

• It consumes from the empty square P00
• It deposits a token into a dedicated history place _X00

Similarly, all O moves populate _Oij history places.

This upgrades the model from state of the board to sequence of moves. Now we can reason about why the board reached its state—not just its current configuration.

Model Diagram (Stage 2)

Pattern Collectors & Win Detection

Once we have history places, we can build pattern collectors—transitions that listen for combinations like:

• Top row: X00_X01_X02
• Left column: X00_X10_X20
• Main diagonal: X00_X11_X22

A pattern collector consumes history tokens from the three required squares, producing a structural token such as:

• X_has_top_row
• O_has_diag
• etc.

Finally, we add win detection transitions:

• win_x fires when any X pattern place marks
• win_o fires for O patterns

This creates a fully compositional win-detection system without any global conditional logic.

Notice above how a winning set of moves activates a win detection transition that populates the win_x place.

Conclusion & Future Work

This expanded tic-tac-toe model demonstrates how a simple, familiar game becomes deeply expressive when framed through Petri-net structure. By building the system in layers—first the grid and turn alternation, then history tracking, then pattern collectors and win detection—we move from a minimal rules engine to a fully compositional model capable not only of representing what happened, but why.

Every rule arises locally from token flow. There’s no central controller, no global conditional logic—just the emergent behavior of places, transitions, and structured history. This is exactly the kind of model that scales: easy to embed, extend, analyze, or parameterize.

In a follow-up post, we’ll take this exact Petri net into Petri.jl, where we’ll:

• convert the discrete model into a continuous ODE system,
• run parameter sweeps to explore strategies, reachability, and path likelihoods,
• and examine how continuous relaxation reveals dynamics that aren’t obvious in the discrete state graph.

This model forms a solid analytical foundation—next time, we’ll turn it into a dynamical system and explore what the engine beneath the game can tell us.