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?
Best Answer
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.