Modeling Computational Complexity of Tic-Tac-Toe using Information Theory and Sets

tic-tac-toe-coding.md

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.

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).