Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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
@stackdump

This comment has been minimized.

Copy link
Owner Author

stackdump commented Dec 11, 2017

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
@stackdump

This comment has been minimized.

Copy link
Owner Author

stackdump commented Dec 11, 2017

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.