= Solution
\b[The depth assertion is false.] Each move occupies one new square, so the general bound is $n^2$, not $n$. On a $2\times2$ board no knights attack, and a play has four moves. More generally, filling a single checkerboard colour gives a legal partial play of length $\lceil n^2/2\rceil$, since knight moves always change colour.
\b[The opponent-independent “best possible move” assertion is false.] <Minimax search> maximizes the guaranteed <utility> against an opponent choosing the worst continuation. It need not maximize the outcome against a particular weaker opponent. If a winning <strategy> is available, its guaranteed win cannot be improved on in win/loss utility; if every root move loses against perfect play, all have the same minimax value, yet some may exploit a weaker opponent better. Thus the valid universal statement is that a minimax <strategy> guarantees its minimax value, not that its root choice is best for every possible opponent behavior.<CS 188 minimax notes>[§3.2, opening assumption: the opponent chooses the move worst for the agent]{ref}
\b[The $O(n)$ storage assertion is false for the usual minimax implementation.] Here the maximum <branching factor> is $O(n^2)$ and maximum depth is $O(n^2)$. A conventional <depth-first search> retaining pending successors uses the usual $O(bm)=O(n^4)$ search-node bound. Generating successors lazily and applying/undoing moves in one board can reduce this to $O(n^2)$ stack frames plus board storage; neither accounting should confuse the board side length $n$ with its $n^2$ squares.
\b[The winning-strategy assertion is true.] The game is finite, has perfect information, alternates two players, and has no draw under the <normal-play convention>. A terminal position is losing for the player to move. By <backward induction>, a nonterminal position is winning exactly when at least one legal move reaches a losing position; otherwise it is losing. This labels every position, including the initial board, so exactly one of the two players has a winning <strategy>.
Back to article page
