tic-tac-toe-proof.md

Explaining Tic-Tac-Toe using Entropy

• The state space of a game is 9!
• there are 9 moves per game
• on average there are 5 degrees of freedom for any given move
• on average there are 4 previous actions before the 'current turn'

Defining the Board

We can define a board as membership in any of 7 sets:

1 set == The empty Set 3 sets for row membership (A, B, C) 3 sets for column membership (D, E, F)

Defining the gamepiece

A gamepiece is composed of 2 elements: Location and State

Location is defined as the gamepiece being a member of 1 row and 1 column set or the empty set.

State is represented as a membership in a set describing all places containing an 'X' or an 'O'.

Defining Game Branching

Gameplay can be modeled using a branching tree notation.

We can model past moves as:

3^4 # entropy of move history

We can model the X/O alternating game 'choice' (when playing as a single player game):

2^5

Conclusion

By combining all these factors we have shown that the defined set memberships must be correct.

This can be directly applied to Type theory as a means of demonstrating that a given type model correctly describes some target problem set.

9! = 3^4 * 2^5 * 2 * 2 * 5 * 7

Corrected Solution

Here we find that the other factors pulled out of the state-space
represent sets that can be used to encode information ( more to follow with diagrams)

The equation below uses these factors:

7: number of sets needed to encode 3 * 3 grid [[0,1,2] * [3,4,5]] <- here we count the bounding set also
5: number of sets needed to encode choice of 4 possibilities [[0,1] * [2,3]] <- also here
2*2:encoded information about grid position: [0,1] * [X,O]

Where [0,1] choice indicates membership in the 'future' - play or the 'past' (move taken)

Using this encoding we can now use our 3 * 3 grid to represent the 9 total moves of a game.

Input:

9! = 3^x * 2^y * z * 2 * 2 * 5 * 7

Integer solutions:

x = 2, y = 5, z = 9

x = 3, y = 4, z = 6

x = 3, y = 5, z = 3

x = 4, y = 2, z = 8

View solution on Wolframalpha

Freedom vs. History

Consider using Z to represent move history rather than 'degrees of freedom'

Choosing z=9 makes the most sense due to there being exactly 9 moves in a game

Additionally we can reflect that now

X = 2 could represent the choice to place X/O

And

Y = 5 could now be thought to represent the average 'degrees of freedom' from a random gamestate

It seems I'm using: https://en.wikipedia.org/wiki/Sigma-algebra