Past exam of the computer science course of the University of Oxford / 2019 / Artificial intelligence / 2

Let $Q=\{1,\dots ,n{\}}^2$ be the board squares and let $\mathrm{Attack}(p,q)$ mean that the absolute coordinate differences are $(1,2)$ or $(2,1)$.

One variable per knight. Use $X_1,\dots ,X_k$, with each constraint domain equal to $Q$. For every pair $i<j$, requireEvery satisfying assignment places $k$ distinct nonattacking knights, and any such placement gives an assignment after labelling its knights. This has only $k$ variables and $O(k^2)$ binary constraints, but domains of size $n^2$. Relabelling the knights gives $k!$ assignments for the same unlabelled board, so the representation contains considerable redundancy.

One Boolean variable per square. Use $Y_q\in \{0,1\}$ for every $q\in Q$. Impose the cardinality constraintand for every knight-attack pair $p,q$ impose $Y_p+Y_q\le 1$. There are $n^2$ variables, each with a two-element constraint domain, and only $O(n^2)$ local attack restrictions, because each square attacks at most eight others. The single counting constraint is a global constraint, not a binary constraint.

The square encoding avoids knight-label redundancy and has sparse local attack relations; the knight encoding uses fewer variables when $k$ is small and makes single-knight moves natural. Both are exact representations of the nonattacking knights problem. Neither may impose one knight per row: several knights can legally share a row.

Use the knight-variable representation and build a placement one knight at a time. The initial state is the empty placement. An action places the next knight on an empty square attacking no previously placed knight; the search transition model appends that square. The goal test is that $k$ knights have been placed. Each action adds exactly one, so any solution has depth $k$.

Put $N=n^2$. At depth $j$, there are at most $N-j$ choices, hence branching factor at most $N$. A coarse search tree size bound is $1+N+\cdots +N^k$. Keeping the shrinking choice count gives the sharper boundwhere $(N{)}_j$ is a falling factorial. This counts ordered placements before attack pruning.

For a full expansion down to depth $k$, the number of depth-$k$ leaves is at most $(N{)}_k$, or approximately $n^{2k}$ when $k$ is small relative to $N$. If $I_k$ denotes the number of legal unlabelled $k$-knight placements, the exact number of legal depth-$k$ leaves is $k!I_k$. There can also be earlier dead-end leaves: a legal placement may leave no further nonattacking square. Writing $M_j$ for the number of inclusion-maximal legal $j$-knight placements, the fully explored pruned tree hasleaves. Its leaf count is still at most the unpruned $(N{)}_k$, since each early leaf replaces a disjoint nonempty subtree of the unpruned tree. Breadth-first search that stops at its first goal can construct less of the last layer; if no solution exists, it exhausts the reachable partial placements.

Identifying different insertion orders changes the representation. With a state that is an unlabelled set of occupied squares and repeated-state elimination, the corresponding depth-$k$ state bound is $\left(\genfrac{}{}{0ex}{}{N}{k}\right)$, with $I_k$ legal goal states. The factorial and binomial bounds refer to these different representations, not competing counts of the same tree.

Backtracking assigns one variable at a time and abandons a partial assignment as soon as it cannot extend to a solution. With forward checking, placing a knight deletes its occupied and attacked squares from every remaining knight's constraint domain. An empty constraint domain rejects the branch immediately; stronger constraint propagation, such as arc consistency, can detect additional incompatibilities among future choices.

This combines early rejection with depth-first storage. It retains the current assignment and domain changes rather than the entire breadth-first layer of partial placements. A direct knight-variable implementation uses $O(k{n}^2)$ space for explicit domains, plus its assignment and restoration trail, instead of an exponentially large breadth-first search search frontier. Propagation has a computational cost and does not guarantee improvement on every input, but often prevents exploration of vast inconsistent subtrees.

The minimum remaining values heuristic selects an unassigned variable with the fewest currently legal values, exposing the likeliest failure first. The degree heuristic selects a variable constrained to the largest number of other unassigned variables, often breaking minimum remaining values heuristic ties. Degree is measured in the remaining constraint graph, not by counting assigned neighbors. In the symmetric knight-variable encoding the remaining degrees can all tie, so the heuristic need not discriminate there.^[ref]

A useful local search state is any occupied-square subset $S\subseteq Q$, allowing temporary attacks. Let $C(S)$ count unordered attacking pairs and $N=n^2$. MaximizeACTIONS can offer insertion at an empty square, deletion of an occupied square, and relocation of one knight to an empty square. RESULT is respectively $S\cup \{q\}$, $S\setminus \{p\}$, and $(S\setminus \{p\})\cup \{q\}$. Insertions and deletions alone connect the whole state space; relocation is a useful additional proposal.

Every conflicting state has $F(S)\le N-(N+1)<0$, whereas the empty board has score zero. Every conflict-free state has score exactly its knight count. Hence every global maximizer is a maximum-size nonattacking placement. If a knight participates in $r\ge 1$ conflicts, deleting it changes the score by $-1+(N+1)r>0$, so a positive-conflict local stopping point cannot persist when improving deletions are considered.

From a random board, choose score-improving moves, with random restarts or occasional non-improving proposals to escape poor conflict-free local optima. A maximal placement is not necessarily a maximum placement: accepting only legal insertions can get stuck too early. This objective function defines the intended optimization precisely; a finite heuristic run still gives no general global-optimality certificate.

The depth assertion is false. Each move occupies one new square, so the general bound is $n^2$, not $n$. On a $2\times 2$ 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.

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.^[ref]

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.

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.