Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Modeling Computational Complexity of Tic-Tac-Toe using Information Theory and Sets

UPDATE: 20171203

This post wasn't well thought out or explored.

After reflecting on this more I have reformulated this information into a new post:

Describing With Set Theory:

We can attempt to describe a game of tic-tac-toe by abstracting various properties of a game and using what we know about the branching complexity of the game.

The total possible state space for a game is 9!

Encoding technique

Here we describe the GameBoard with 9 possible locations:

x=0 x=1 x=2
y=0 00 01 02
y=1 10 11 12
y=2 20 21 22

various factors

set of coordinates: (x,y) => 2

set of players: (X,O) => 2

set of 'places': (00,01,02,10,11,12,20,21,22) => 9

set of game-ending-moves: (5,6,7,8,9) => 5 [halting states]

We also assume:

The median number of moves in a game => 7

Vector size of a: game-action: (1,2,3,4,5,6,7,8,9) => 9

NOTE: ^ each move has probability of affecting 1 of 9 places on the board

Applying Big O theory

If we can assume the computational complexity of a game has Big O of 2^N

Tic-tac-toe has a Game-Tree Complexity of '5'

So we use N=5


9! / 2^5 = 2 * 2 * 9 * 5 * 7 * 9

Read about Computational Complexity here:

UPDATE: thinking more about this

The total permutations of games is 9! - which makes the assumption that every game will have 9 Total moves (not 7 as in the above example)

I'm not really sure how to correct this - the calculation of the total 'degrees of freedom' when combining factor-sets still seems like a good aproach, but perhaps there is some redundant information resulting from the choice of factors.


This comment has been minimized.

Copy link
Owner Author

@stackdump stackdump commented Dec 2, 2017

Attempt to Adjust Factors

Coordinates Move Seq Players Actions States ??
9! / 2^5 = (x,y) (0,1,2,3,4,5,6,7,8,9) (X,O) (00,01,11,10,11,12,20,21,22) (00,01,11,10,11,12,20,21,22,EMPTY) FACTOR?
11340 2 9 2 9 10 7

Mystery Factor

it seems like we should be able to identify something - unless we are way off about this whole approach.

We could try removing the coordinate factor (2)

And replace the mystery factor with 'set of all symbols used by factors':

(0,1,2,3,4,5,6,7,8,9,x,y,X,O) = 14

We'd have to fudge a little bit more and say 'EMPTY' represents the empty set: () - and so doesn't need a symbol ¯_(ツ)_/¯

Here is an example Petri-Net describing the game NOTE: above we've simplified turn_x, turn_o into just 'TURN' (as part of the state set).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.