How to determine the size of the complete game tree for basic [M]?

If two completed $k^2\times k^2$ sudoku boards are equivalent by virtue of the allowed symmetries (the dihedral symmetries of a square plus swaps of two rows or two columns within the range of a $k$-sub-square), then any game leading to one such square is equivalent to a game (with appropriately permuted moves) leading to the other such square.

Therefore the counting of nonequivalent game sequences that lead to completed sudoku boards is the number of nonequivalent complete sudoku boards times the permutations of entries (moves) in a board. The latter is $(k^4)!$.

Sketch (to be expanded) For $k=2$ there are exactly six nonequivalent completed sudoku boards. In brief the possible completed boards are equivalent to one of the two forms:

$$ \begin{bmatrix} 1 & a & b & c \\ b & c & 1 & a \\ a & 1 & c & b \\ c & b & a & 1 \end{bmatrix} \;\;\;\; \begin{bmatrix} 1 & a & c & b \\ b & c & 1 & a \\ a & 1 & b & c \\ c & b & a & 1 \end{bmatrix} $$

where $a,b,c$ are a permutation of $2,3,4$. The instances of one form are never equivalent to instances of the other form (easily checked by considering the determinants of the four $2\times 2$ sub-squares), but we don't get six nonequivalent boards of each form, only three.

This is because in the left form, choosing $c$ leaves $a,b$ to pick, but $a,b$ can be swapped by allowed symmetries. So choosing $c$ gives the representative three cases.

In the right form, choosing $a$ leaves $b,c$ to pick, but $b,c$ can be swapped by allowed symmetries. So choosing $a$ gives the representative three cases.

It follows that there are $6 = 3+3$ nonequivalent completed $4\times 4$ sudoku boards, and thus the count of nonequivalent $4\times 4$ game sequences:

$$ 6\cdot 16! \approx 1.26\times 10^{14} $$