Some theory

There are some theoretical bounds on the size of the failure database our system can create. 'X' has nine choices for play on his first move, 'O' has eight choices for play on his first move on a board that already has one 'X' placed in one of the nine squares, etc. Now assume that for the game of tic-tac-toe there exists a ratio $r \in [0.0, 1.0]$ , where r is a ratio or percentage of moves available either to 'X' or to 'O' on any given turn in any given game that lead to failure. If such a ratio $r$ exists, then we know, at least theoretically, the size of the failure database. Assume $s$ is the theoretical size of our failure database.

$$s = 9r \left( \begin{array}{cc}9 \\ 0\end{array} \right) % s... ... \left( \begin{array}{cc}7 \\ 1\end{array} \right) + % (7 1) +$$

$$\par 5r \left( \begin{array}{cc}9 \\ 2\end{array} \right) % ... ... \left( \begin{array}{cc}5 \\ 3\end{array} \right) + % (5 3) +$$

$$r \left( \begin{array}{cc}9 \\ 4\end{array} \right) % r (9 ... ...gin{array}{cc}5 \\ 4\end{array} \right) % (5 4) = 19,107r \\$$

The maximum value of $s$ occurs when $r = 1.0$. Call this maximum value $s_{max}$. Obviously, $s_{max} = 19,107$. In practice, and in our implementation, we know the experimental value of $s$, called $s_{exp}$, , and we can solve the above equation for the experimental value of $r$, $r_{exp}$.

$$r_{exp} = \frac{s_{exp}}{s_{max}} \\$$

Our experimental results are reported later, including the experimental values of $s_{exp}$. From these experimental results, we compute a value for $r_{exp}$ for the game of tic-tac-toe, assuming the ratio $r$ exists.

So, theoretically, in the worst case, for the game of tic-tac-toe, the failure database will be no larger than $19,107$. In this worst case, all possible moves for either 'X' or 'O' on any given turn in any given game lead to failure. This is a logical impossibility, since in any single completed game of tic-tac-toe, 'X' and 'O' can't both lose in the same game. Just think of $19,107$ as an upper-bound on the size of our failure database, $s$, in the game of tic-tac-toe. The actual size of the failure database is less than half its maximum size, and we report these results later.

Hosted by www.Geocities.ws