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?
 A: 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.
A: Assuming that rotations and mirror images are unique, one arrives at the following numbers:


*

*Boards with 1 non-winning move: ${9 \choose 1} = 9$

*Boards with 3 non-winning moves: ${9 \choose 2} {7 \choose 1} = 252$

*Boards with 5 non-winning moves: ${9 \choose 3} {6 \choose 2} - 8 {6 \choose 2} = 1140$

*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:


*

*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;

*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;

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