Past exam of the computer science course of the University of Oxford / 2021 / Artificial intelligence / 1 / i / Solution

For $N\ge 3$, depth and history-tree size can be infinite, while a sufficient finite state bound is $2\cdot 5^N$. The number of possible completed histories also becomes unbounded. With variables $p,q,r$, first let $A$ assign $p$ and $B$ assign $q$. Both can then keep flipping their own variable, leaving $r$ unassigned. After four such flips the same assignment, ownership and player-to-move recur. Arbitrarily many repetitions can precede assignment of $r$, so there are infinitely many distinct finite complete histories as well as legal infinite plays.

A state must now record ownership: for each variable the possibilities are unassigned, $A$-owned false, $A$-owned true, $B$-owned false, and $B$-owned true. Include the player to move, since flips break the old link between turn parity and the number assigned. This givesMany encoded positions are unreachable, so this is an upper bound. Each nonterminal state has at most $2N$ legal moves: two assignments per unassigned variable and one flip per variable owned by the acting player. Thus the finite directed graph has at most $2N|V|$ edges even though its unrolled game tree is infinite. The $2^N$ possible final Boolean valuations are unchanged, but they no longer count distinct plays or complete ownership states. For $N=1,2$, no player gets a legal opportunity to flip before all variables are assigned, so the original finite bounds still apply.