Nov 22, 2020

Scotland Yard: Part 2

This blog contains an explanation of the paper ‘The complexity of Scotland Yard’ by Merlijn Sevenster.

This is part 2 of a two part blog. Part 1 explains the game, and lays out the foundations required for formalisation of the game. It also lists out the various assumptions we are going to consider in the game. Part 2 formalises the game and proves that it is of PSPACE complexity.

The blog was originally published on ‘GameLab’ for our course project. The website also contains additional information about heuristics used in Scotland Yard, and similar analysis for other board games.

🤵 Formalisation

We now know how to formalise any given perfect or imperfect information game. Now let’s connect it to the game Scotland Yard.

Let $SY$ = $\langle G, \langle u_* \overrightarrow{v_*} \rangle, f \rangle $ be a Scotland Yard instance. Then, let the extensive Scotland Yard game constitute by $\mathcal{SY}$ be defined as the tuple $$ \mathcal{SY}(SY) = \langle N, H, P, \bullet, U \rangle $$

Here,

$G$ represents a digraph
$u_*$ represents the position of Mr X.
$\overrightarrow{v_*}$ is $n$ dimensional vector, where $n$ is the number of detectives. Each element in the vector represents the initial node of the detective.
$f$ is a function which when fed a number (no. of rounds) chooses one of the two elements from the set { $show, hide$ }. This denotes whether Mr X needs to show their position or not.
$N$ represents total number of players. For convenience, $N =${$\forall, \exists$} where $\forall$ represents Mr X and $\exists_1, \exists_2 . . \exists_{N-1}$ represent the detectives.
$H$ represents a set of histories. Let $\prec$ be the immediate successor relation on $H$. So you can say that $\langle h \rangle \prec \langle h, u \rangle$ where $\langle h \rangle, \langle h, u\rangle \in H$
$P$ represents the player function. Due to notational convenience, it is easy to assign the value of the player function. $P(\langle h, u \rangle) = \forall P$ and $P(\langle h, u , \overrightarrow{v} \rangle ) = \exists$ no matter $u$ or $\overrightarrow{v}$
$\bullet$ is the indistinguishability relation. It is defined on the group $H$. For any two histories $h, h’ \in H$ where the length of both histories is equal, $h \bullet h’$ when:

If $h = \langle u_* , \overrightarrow{v_*}, u_1, \overrightarrow{v_1}, . . . u_i, \overrightarrow{v_i} \rangle $and $h’ = \langle u_* , \overrightarrow{v_*}, u’_1, \overrightarrow{v’_1}, . . . u’_i, \overrightarrow{v’_i} \rangle$ then
1. $\overrightarrow{v_j} = \overrightarrow{v’_j} \space \forall \space 1 \leq j \leq i$ and
2. $u_j = u’_j \space \forall \space 1 \leq j \leq 1$ such that $f(j) = show$
$U : Z \rightarrow $ {$win,lose$} is the utility function which determines whether $\exists$ won or not.

$$ U(\langle h, u, \overrightarrow{v} \rangle) = \begin{cases} win, \space \space u\in \overrightarrow{v} \\\ lose, \space \space u \notin \overrightarrow{v} \end{cases} $$

It is easy to see that the operation $\bullet$ is Equivalent to the group $H$. We write $\mathcal{H} \subseteq \wp(H)$ for the set of equivalent classes, or information cells, in which $H$ is partitioned by $\bullet$.

$\mathcal{H} = \{ C_1, C_2 . . . C_n\}$ where $H = C_1 \cup C_2 . . \cup C_m$ for every $1 \leq i \leq m$, if $h \bullet h’$ where $h, h’ \in C_i$.

We lift the relation $\prec$ to $H$, using the same symbol: For any pair $C, C’ \in H$ we write $C \prec C’$ if there exists histories $h \in C$ and $h’ \in C’$ such that $h \prec h’$

We can also extend this as if $h, h’ \in C$ and $C \in H$, then $P(h) = P(h’)$. Thus the player function is meaningfully lifted as follows: if $C \in H$ and $h \in C$, then $P(C) = P(h)$.

Consider an example game $G^x$. Let $f^x$ be the information function where $f^x(1) = hide$ and $f^x(2) = show$. Let $u_*$ and $v_*$ as the initial position of $\forall$ and $\exists$. Consider that number of detectives to be 1. Let’s play this game.

The set of histories we can get from this game are:

where ! marks terminal histories. To reflect that this is a game of imperfect information, we can write $\mathcal{H}$ as

A graphical representation of this would be:

Perfect Information Scotland Yard

So, Perfect Information means that each and every aspect of the game is explicitly expressible. The only difference we need to model here is $\forall$‘s whereabouts. Since describing each position will convert Scotland Yard into a simple game of Cops and Thieves, we don’t do that. Instead, to preserve the game, we describe the position of $\forall$ as a set of possible nodes.

More abstractly, $\forall$$’s powers are lifted from the level of picking up vertices to the level of picking up sets of vertices. $\exists$’s powers remain unaltered, as compared to the game with imperfect information that was explicated above. It is defined as:

$$ \mathcal{SY-PI}(SY) : \langle N_{PI}, H_{PI}, P_{PI}, U_{PI} \rangle $$

The above mentioned example will be converted to

Effective Equivalence

In this section, we establish that $\exists$ has a winning strategy in $\mathcal{SY}(SY)$ iff it has a winning strategy in $\mathcal{SY-PI}(SY)$. In order to prove this, it will be shown that $\langle H, \prec \rangle$ is isomorphic to $\langle H_{PI}, \prec_{PI} \rangle$ in virtue of the bijection $\beta$

The function $\beta$ is a map from histories in the perfect information game $\mathcal{SY-PI}(SY)$ to information cells in the game $\mathcal{SY}$. To formally define it, $\beta: H_{PI} \rightarrow \wp(H)$.

For example, in the above mention $G^X$ we will map $\beta(\langle u_*, v_*, u_1 \rangle)$ where $u_1 = \{a, b\}$ to $C_1$ where $C_1 = \{\langle u_*, v_* , a\rangle , \langle u_*, v_*, b \rangle \}$

Just as a reminder, $C_i$ represents an indistinguishable state for $\exists$ in $\mathcal{SY}(SY)$.

The perfect information Scotland Yard game was defined in such a way that $\exists$‘s imperfect information in $\mathcal{SY}(SY)$ is propagated to perfect information about sets in $\mathcal{SY-PI}(SY)$.

Example of $\beta$ in lieu of above mentioned example would be:

It is important to note that though here $\beta$ is defined to have a codomain $\wp(H)$, it ends up having a range of $\mathcal{H}$. This is due to the output always being $C_i$ and $\mathcal{H} = \{C_1, C_2 . . C_m \}$

To better define $\beta$ and actually make it bijective, we redefine it as

$$\beta: H_{PI} \rightarrow \mathcal{H}$$

Now, let’s prove that the groups $\langle H, \prec \rangle$ and $\langle H_{PI}, \prec_{PI} \rangle$ are isomorphic.

It is proved that $\beta$ is a bijection between $H_{PI}$ and $\mathcal{H}$. It remains to be shown that $\beta$ preserves structure.

Recall that for $C’ \in \mathcal{H}$ to be an immediate successor of $C \in \mathcal{H}$, there must exist two histories $g, g’$ in $C, C’$ respectively such that $g \prec g’$ (Proved earlier).

What this proves is that for any histories $h, h’ \in H_{PI}$ it is the case that $h \prec_{PI} h’$ iff $\beta(h) \prec \beta(h’)$

The claim is proved by a straightforward inductive argument on the length of the histories in $H_{PI}$

Making use of the fact that $\langle H_{PI}, \prec_{PI} \rangle$ and $\langle H, \prec \rangle$ are isomorphic groups, an inductive argument proves that $S$ is a winning strategy for $\exists$ in $\mathcal{SY-PI}$ iff $S(\beta)$ is a winning strategy for $\exists$ in $\mathcal{SY}(SY)$.

🌌 PSPACE

Let $\text{SCOTLAND YARD}$ be the set of all Scotland Yard instances such that $\exists$ has a winning strategy in $\mathcal{SY}(SY)$.

If we are able to prove that there is a winning strategy in PSPACE for $\mathcal{SY}(SY)$, then it will stand true for $\mathcal{SY-PI}(SY)$ as well.

Papadimitriou, namely, observed that deciding the value of a game with perfect information can be done in PSPACE if the following requirements are met:

The length of any legal sequence of moves is bounded by a polynomial in the size of the input
Given a “board position” of the game there is a polynomial-space algorithm which constructs all possible subsequent actions and board positions; or, if there aren’t any, decides whether the board position is a win for either player.

$SY−PI(SY)$ meets those condition.

For the first point, the length of the description of any history is bounded by the number of rounds $k$, of the game. By assumption, $k \leq |V|$, thus it is polynomially bounded.

For the second point, as we have seen till now, each board game can be represented in form of a decision tree. More formally, if $\langle h, U, \overrightarrow{v} \rangle$ is a non terminal history, then its successors are either (depending on $f$) only $\langle h, U, \overrightarrow{v}, \{w_1 ,. . ., w_m \} \rangle$ or all of $\langle h, U, \overrightarrow{v}, \{ w_1 \} \rangle$, . . . , $\langle h, U, \overrightarrow{v}, \{ w_m \} \rangle$

Where $E(U-\{\overrightarrow{v}\}) = \{ w_1, w_2 , . . , w_m\}$. These can easily be constructed in PSPACE.

HENCE PROVED $\mathcal{SY-PI}(SY)$, AND CONSEQUENTLY, $\mathcal{SY}(SY)$ ARE PSPACE IN COMPLEXITY.

NOTE It is later shown that if there were a Scotland yard instance such that each $f = show$, then it would be PSPACE HARD in complexity. Also if each $f = hide$, then it would be NP HARD in complexity. These proofs are omitted due to the complexity of the math involved.

📝 References

P. Nijssen and M. H. M. Winands, “Monte Carlo Tree Search for the Hide-and-Seek Game Scotland Yard,” in IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 4, pp. 282-294, Dec. 2012, doi: 10.1109/TCIAIG.2012.2210424.
Sevenster, Merlijn. (2006). The complexity of Scotland Yard. Journal of Pharmacology and Experimental Therapeutics - J PHARMACOL EXP THER.