# Combinatorics: Tic-Tac-Toe

I have found information on how many various unique games of tic-tac-toe (naughts and crosses) can be played.

However, I am working to build an AI on the TI-84+ which uses a learning system which was originally implemented in M.E.N.A.C.E

I have created all the inputs, and have started the logic. In order to continue I need to know how much memory to allocate. Since I am not good at combinatorics, I thouggt I would ask here:

How many unique gameboards are there in tic-tac-toe which contain 1, 3, 5, or 7 moves and no winning pattern? I know that there is 9 boards after the first move, and 504 after the third move. After the fifth move there is 15,120 but we remove the 1440 winning boards for 13680 boards after the fifth move. 13680+504+9= 14193 boards. This is where I get stuck. How do I deal with the board layouts with 7 moves given that there are boards which have winning combinations after 6 moves?

• Alternatively, instead of finding the exact number of boards, you could just find some suitable upper bound and allocate that amount of memory. Jun 20 '18 at 14:51
• You may find an interesting video on YouTube where Matt Parker (Standupmath) built a learning sytsem for TicTacToe out of matchboxes and coloured beans. Of course he also explains some of the math. Jun 20 '18 at 14:53
• I tried that Bob, but in order to be able to manipulate the data it has to be the exact amount. Jun 20 '18 at 15:00
• You could identify board positions that are rotations or reflections of one another.
– wjm
Jun 20 '18 at 15:00
• Hagen, I will check it out. Thank you. Misha, I understand it may be more than what many people think a calculator can handle, but there are ways to compress data. For example, the data can be compressed into a different base depending on which slots are available in the gameboard and such. I was also thinking of graphical encoding using pixels. However, the final decision would need to be based on how many unique data points I have to store. Raptor, I could, but rotation and mirroring of matricies (or lists corresponding to matricies) is not easy in TI-Basic, though that would be 304 boards Jun 20 '18 at 15:07

Here is an alternate suggestion to avoid storing this many boards and make use of symmetry, without having to do explicit calculation.

Using matrices to store board, a $3\times 3$ board $A$ can be converted to a number by computing $$\begin{bmatrix}1000000 & 1000 & 1\end{bmatrix} A \begin{bmatrix}100 \\ 10 \\ 1\end{bmatrix}.$$ (This simply concatenates the entries of $A$ as digits, which saves all the information you need assuming that each entry is either $0$, $1$, or $2$. You can use powers of $3$ instead of powers of $10$ here, and that will also work, if you want shorter numbers.) Let $B$ be the matrix $$B = \begin{bmatrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0\end{bmatrix}.$$ Then the eight rotations and reflections of $A$ can be computed (easily, in TI-Basic) as $A$, $A^{\mathsf T}$, $BA$, $BA^{\mathsf T}$, $AB$, $A^{\mathsf T}B$, $BAB$, $BA^{\mathsf T}B$.

Maintain two lists: one that will contain numbers encoding board positions, and one that will contain the AI's data about each position. When you want to look up a position, convert all eight matrices above to numbers, take the smallest, and look it up in the first list. If it's there, use the data from the corresponding element of the second list. If it's not there, add a new entry to both lists.

(You'll have to do some work to take the move we obtain this way and rotate it back to the original board, but it is worth it.)

This will naturally create a list (well, two lists) of no more than $304$ elements, because we only allocate memory to positions we actually encounter - but we never have to explicitly figure out which positions those are.

• That might work, since the AI takes an input of the partial probabilities for each layout. The only issue I forsee with that could be large counts of “beads”. Example ai input: 5,0,0,7,0,1,0,2,0. 5/15 chance for slot 1, 7/15 chance for slot 4, 1/15 slot 5 etc. Jun 20 '18 at 16:11
• Why not store it as a $9$-digit number? That's awkward if there are more than 9 beads of one type, but how likely is that? Jun 20 '18 at 16:25
• Extremely likely. Considering that if I were to make it exactly like the original it would start with 2 for each position. A win gives +3 for that position, tie +1, loss -1. Perhaps what I could do is use the list as an index to a string. I have 10 strings available, And I could store the values as a 2-digit base 60 value (0-9,A-Z,a-z). That would allow for numbers up to 120 without issues, and I could cap it there since after it reaches 120 that would likely be after it has achieved optimal play. Then I just need the list of unique gamboards, and a number representing the string and index Jun 20 '18 at 22:54

Assuming that rotations and mirror images are unique, one arrives at the following numbers:

1. Boards with 1 non-winning move: ${9 \choose 1} = 9$
2. Boards with 3 non-winning moves: ${9 \choose 2} {7 \choose 1} = 252$
3. Boards with 5 non-winning moves: ${9 \choose 3} {6 \choose 2} - 8 {6 \choose 2} = 1140$
4. Boards with 7 non-winning moves: ${9 \choose 4} {5 \choose 3} - 8 {6 \choose 1} {5 \choose 3} - 2 {6 \choose 4} - 6 {3 \choose 2} {3 \choose 2} = 696$

For the number of boards with 3 non-winning positions, you forgot to divide by 2, the number of orders the first player can select the two tokens. For the last option, one can start from all possible options, and subtract options which:

1. Result in the first player getting three in a row. There are eight ways in which this can be achieved, with one remaining token to be placed in any of the six remaining squares, and three more tokens for the second player in the remaining five;

2. Result in the second player achieving three in a row diagonally. There are two ways to select the diagonal, after which four more tokens must be divided over the six remaining squares;

3. Result in the second player getting three in a row horizontally or vertically, without the first player getting three in a row. Once the row or column is selected, the four tokens of the first player must be equally divided over the two other rows or columns (i.e., they must contain two tokens each).

Note that if no distinction is made between rotations and mirror images, these numbers can be significantly reduced.

• That number seems quite low to me. If the player plays 1, then there are the following board layouts with three pieces: 123, 124, 125, 126, 127, 128, 129. Then 132, 134, 135, 136, 137, 138, 139. So if the first move is 1, there are 56 possible boards after the next two moves. Repeat for if the player played 2, 3, etc up to 9. That would be 9*8*7, or 9!/6! This is how I got the 504 possible board layouts after 3 moves. Note that ALL 504 do not contain any winning sets as there are not yet 5 pieces on the board Jun 20 '18 at 15:53
• @Trenly Do you consider for example 132 and 231 to be the same? The end result looks the same though the moves were done in a different order. The answer above does considers them the same, i.e. looks only at the end result, not the order of the moves. Jun 20 '18 at 15:56
• @Trenly As Jaap Scherphuis remarked above, my solution assumes that playing 1-3-2 would be the same as playing 2-3-1. If you want to train an AI to play the optimal move, it does not matter in which order the tokens were placed: only the current state of the board matters. The solution above gives the total number of states for each number of non-winning moves performed by the two players. Jun 20 '18 at 16:10