Nov 22, 2020

Scotland Yard: Part 1

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

This is part 1 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.

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.

📖 Introduction

Scotland yard is a popular board game, named after Scotland Yard, the headquarters of London’s Metropolitan Police Service. It is played by 2-6 players in which one of the players is the criminal (Mr. X) and the remaining are detectives. As is intuitive, the objective of the game for the detectives is to catch the criminal, while the objective of the criminal is to run away from its pursuers for 22 rounds. It is an asymmetric board game since the players do not have the same goal.

📜 Rules

Let’s take a look at the rules once, before we jump into analysing the game.

Movement of players:

Each detective and the criminal is assigned a pawn to mark their position on the board. There are a total of 199 positions on the Scotland Yard board. Each position can represent 1-3 stations, a taxi, a bus, and an underground route, which is marked by a number and the colour of the station it represents.

Every station on the map can be reached with the taxi (yellow). However, the distance that you can travel is short: You can only move (along the yellow line) to the next station.

The bus (turquoise) only drives from stations with a turquoise semi-circle; a bus will take you a little further than the taxi (along the bus line).

The underground (red) travels along the red line and covers the furthest distances the quickest. However, there are only a few underground stations (stations with a red inner rectangle) on the map.

All playing pieces can only be moved to unoccupied stations. If there are no unoccupied stations for Mister X to travel to, he has lost the game. Mister X also loses if one of the detectives moves to the station where Mister X is located.

Tickets

Each detective receives ticket cards that allow him to across the board. At the start of the game, each detective gets 4 underground tickets, 8 bus tickets, and 11 taxi tickets, and each detective receives 5 black tickets and 2 double move tickets.

In each round, after a detective has used up a ticket to travel to another position, they cannot use them again, however, this ticket is now available for Mr. X’s use. If a detective no longer has any tickets or can’t move from his current station with the tickets he has left, they have to sit out.

A black ticket allows Mr.X to hide the route he used and also travel by ferry (a route only he is allowed), and a double move ticket allows him to make two moves to two different stations in one round.

Initial Starting Position

To determine each player’s starting position, a set of start cards marked D and X are shuffled separately and each detective selects from the D cards and places their playing piece on the respective position. Mr. X picks an X card but doesn’t reveal his position to the detectives or place his playing piece on the board.

Gameplay

In total, 22 rounds are played. In each round, Mr. X first makes their move, concealing his new position from the remaining players, and writes down the station he moved to on a paper, hiding the station with the ticket they used. (The detectives can see which mode of transport Mr.X has used.)

When a detective makes a move, the used-up ticket is placed in the general draw pile where Mr. X gets his tickets (so Mr. X basically has an unlimited number of tickets).

Moving Mr. X

Each turn Mr. X conceals his move. However, there are special moves (3rd, 8th,13th, 18th, and 24th moves) where Mr. X must surface. He has to reveal his current position before moving to a new station, which gives detectives the chance to co-ordinate and corner the criminal!

Moving the Detectives

The detectives use their tickets to move around the board. If they run out of tickets or don’t have the required ticket to move out of a station, they must sit out of the game. Detectives can’t trade tickets among themselves and all their remaining tickets have to be visible to Mr. X, so he can see the remaining means of transportation they have left.

Winning the Game

Mr. X wins if -

He is able to move around the board for 22 rounds without being caught.

The detectives win if -

They corner Mr. X (he has no stations to go to where a detective is not present)
They move to a station where Mr. X is currently

Now that we understand how to play, let’s dive into different aspects of the game!

🎯 Objective

The goal of this page is to analyze the game Scotland Yard.

We start off by venturing into proofs for Scotland Yard being a PSPACE problem and the similarities between Scotland Yard and a game of perfect information. It is easy to feel daunted by these claims, trust me I felt it too. To make it easier, we remove all the layers of abstraction from the game first. We convert the game into a problem of Groups, Graphs, and Sets.

It is understandable if you think it still is going to be tough. We ensure that you will understand what these jargons are and how they interact with the game itself. We firstly introduce Games with the viewpoint of perfect and imperfect information. Then we connect Scotland Yard to that idea and remove all the layers of abstraction. Once that is done, we proceed with proofs.

🏗️ Laying the Foundation

To properly explain some concepts, we need to define some terms:

Extensive Games: Games that allow the representation of various key aspects. These aspects include a set of players, each player’s moves, their decisions, the information (possibly imperfect) about a player, and their payoffs for all possible outcomes. Essentially, they are games that can be represented with a game (decision) tree.

Perfect Information Game: In a perfect information game, a player has complete information about all events which have previously occurred in the game.

Imperfect Information Game: Games which have some aspects of the game hidden are called imperfect information game.

It is easily understandable why Scotland Yard comes under the bracket of the extensive game with imperfect information. For it to be an extensive game, it should formally represent each and every aspect of the game, which is the moves and mode of commutation each player uses. Even if the moves are hidden, they are definite and are represented. Since the moves are hidden, it is impossible for the detectives to know which route the criminal has taken, which makes it an imperfect information game.

Now, let’s look into some abstraction or representations.

Any win-loss game $G$ with perfect information can be represented as a 4-tuple $$G = < N, H, P, U>$$

$ N $: Represents the number of total players.
$H$: Is a set of histories. A history ($h$) represents a given state of the board at some point in time. Every $h = <a_1, a_2, . . a_p > $, where $a_i$ is an action. Each history is an ordered list of actions.
$h’$ = $<h, a'>$ represents the immediate successor of $h$, where $h’$ = $< a_1, a_2 . . . a_p, a'>$. There are two types of history, terminal ($Z$) and non-terminal ($H-Z$). Terminal represents an end condition, after which no other action can be taken. A history becomes terminal when a player wins.
$P$: Is the player function. It assigns to each non-terminal history a particular player. Formally, we define it as $P:$ { $H - Z$ } $\rightarrow N$. We say that a history $h$ belongs to $P(h)$, essentially when the last action in the set of actions that is $h$ is made by the player.
$U$: Is the utility function, assigning each terminal history to a player. (the player has won the game). The formal definition would be $U: Z \rightarrow N$

Given $G$ defined as above, a function $S$ is called a strategy for a player $\space i \in N i∈N$ if it maps for every history $h$ belonging to $i$ to an action $A(h)$.

An extensive game with imperfect information extends a game with perfect information. To represent the former, all you need is to add is an Information function in the original tuple.

$$G = < N, H, P, \langle \mathcal{I}_i \rangle _{i \in N}, U >$$

The only difference in this is that $\mathcal{I}_i$ carries information sets for each $i \in N$. $\mathcal{I}_i =$ {$I_1, I_2, . . . I_q$}. where each $I$ represents a set of histories, there having been $q$ rounds of the game played so far. Each $I$ basically is a set of histories (or state changes of the board) of that round (till $i$ makes an action again). Intuitively, an extensive game with imperfect information models the situation in which player $i$ knows that some history $h \in I \in \mathcal{I}_i$ has happened, but there are unable to tell h apart from the other histories in $I$.

In simple terms, they know other players have made a move based on the last action they took, but are not completely sure of the previous actions the player took.

A function $S$ is called a strategy for a player $i$ in $G$ if it maps every information partition $I \in \mathcal{I}_i$ belonging to $i$ onto action in $A(I)$

Assumptions for Mathematical Modelling

For convenience, there are some assumptions which have been taken.

There is only 1 mode of transport, that is Taxi. The same method described as follows can be easily translated with more modes of transport.
A player will have $k$ amount of tickets of Taxi, where $k$ = number of rounds.
There are only two players, Detective and Mr X.
Only 1 player will be controlling all detectives.
Value of $k$ will be always $\leq |V|$, where $V$ is the number of nodes in the graph.
We have used digraph to represent the game board.
Mr. X will always play the first move in each round.
Mr. X will be considered to be caught IF AND IF ONLY it is on a node occupied by a detective at the END of the round (after detectives have moved).
Mr X will win if and if only the game goes on for $>k$ rounds, otherwise Detectives have won.

📝 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.