stackdump

Some time ago, we explored modeling the classic game of Tic-Tac-Toe as a Petri net, demonstrating how this formalism could elegantly represent the interplay between game states and transitions. Today, we revisit this idea with fresh insights and a more advanced approach using Petri.jl, a Julia library that offers powerful tools for constructing and analyzing Petri nets.

From Concept to Visualization

Petri.jl allows us to model Tic-Tac-Toe in a way that's both expressive and computationally robust. Below is a visualization of the Petri net we constructed for Tic-Tac-Toe:

This graph showcases the game states as places and the player moves as transitions. Each directed arc represents the flow of tokens—analogous to moves advancing the game toward its conclusion.

Revisiting the Formalism

At its core, the Tic-Tac-Toe model encapsulates the following:

1. Places: Represent the current state of the game (e.g., empty squares, player moves).

2. Transitions: Represent the legal moves available to each player.

3. Tokens: Indicate the state of play (e.g., which squares are occupied by X or O).

This approach highlights the game's structure, showing how states evolve as moves are made.

Analyzing Dynamics with ODEs

One of the most exciting possibilities opened up by Petri.jl is the ability to translate our Petri net into a system of Ordinary Differential Equations (ODEs). This enables a quantitative analysis of the game dynamics.

For

• Each place corresponds to a variable representing the state of the board.
• Transitions influence these variables based on player actions.
• Solving the ODE system reveals trajectories of game progression.

Ensuring the Plot Matches the Game with Internal Win Conditions

The plots above appear to converge quickly to stable values, aligning with the game rules: the Next turn transition activates at t=1, and all moves settle to 0 starting at t=2. However, to confirm that this behavior accurately represents the game, we extended the Petri net model to include win conditions directly within the ODE system.

By embedding these conditions, we create a new ODEProblem that integrates both state dynamics and game logic. This approach ensures that the model can verify win outcomes internally, providing a stronger connection between the ODE-generated results and the expected behavior of Tic-Tac-Toe.

Model Checking X/O Win ratio

The extended model the Petri net to include places representing win conditions for each player. Each time a win condition was met, a token was deposited in the corresponding winx_ or wino_ place. After we solved and plotted the result, we measured this ratio at t=9.

Remarkably, the results showed only a 0.85% error compared to the expected statistical win ratios for Tic-Tac-Toe. This seems to demonst the model's accuracy in reflecting real-game dynamics.

Why This Matters

Revisiting our Tic-Tac-Toe model with modern tools like Petri.jl underscores how mathematical frameworks evolve alongside computational advancements. It also highlights the versatility of Petri nets in capturing not just static systems but also dynamic, strategy-driven games like Tic-Tac-Toe.

Next Steps

This approach is just the beginning. Future explorations could include:

• Extending the model to other games with more complex rules.
• Investigate how adding other Petri-net structures affect the dynamics of the ODE plots.

Python notebook with source code used in this post is available here