Create a gist now

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:

https://gist.github.com/stackdump/2be8345c71ab111a6c37d97bdea84234

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

thus:

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

Read about Computational Complexity here: https://en.wikipedia.org/wiki/Game_complexity#Computational_complexity

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.

Owner

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':

FACTOR?
(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).
foo

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment