Instantly share code, notes, and snippets.

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

@stackdump

This comment has been minimized.

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