Consider the family of generalized tictactoe games, defined as follows. Each particular game is specified by a set $\mathcal S$ of squares and a collection $\mathcal W$ of winning positions. Each winning position is a subset of $\mathcal S$. For example, in standard tictactoe, $\mathcal S$ is a set of 9 squares and $\mathcal W$ is a collection of 8 subsets of $\cal W$: the three rows, the three columns, and the two diagonals. In other respects, the game is identical to standard tictactoe. Starting from an empty board, players alternate placing their marks on an empty square. A player who marks every square in a winning position wins the game. It is a tie if all squares are marked and neither player has won.

Let $N= {\mathcal S}$, the number of squares. Give an upper bound on the number of nodes in the complete game tree for generalized tictactoe as a function of $N$.

Give a lower bound on the size of the game tree for the worst case, where ${\mathcal W} = {{\,}}$.

Propose a plausible evaluation function that can be used for any instance of generalized tictactoe. The function may depend on $\mathcal S$ and $\mathcal W$.

Assume that it is possible to generate a new board and check whether it is a winning position in 100$N$ machine instructions and assume a 2 gigahertz processor. Ignore memory limitations. Using your estimate in (a), roughly how large a game tree can be completely solved by alpha–beta in a second of CPU time? a minute? an hour?