Scotland Yard

Scotland Yard

Scotland Yard is a board game that has many similarities to the versions of "Cops and Robbers" we have looked at in class.  It involves 5 detectives or "cops" whose goal is to track down Mr. X or the "robber" with limited information about his whereabouts.

First off, I will explain the rules and game setup of Scotland Yard.  Then, I will explain how the Monte-Carlo Tree Search Strategy (MCTS) can be used to help the detectives find Mr. X in a shorter amount of time.

Let's get started...

Game Set Up & Rules

Scotland Yard is played with five detectives and one Mr. X.  Hence, the game can be played with at most six players and at least two, where one player would control all five detectives. The game is played on a map of London with numbered locations from one to 199.  The locations are connected to each other by four different transport types: taxi, bus, underground, and boat.  A player must play the proper ticket to move along the corresponding transport type.

The game board looks like this:

SOURCE: https://cf.geekdo-images.com/images/pic557147.jpg

As you can see, the locations are connected with white, red, blue, and black lines.  These lines correspond to taxi, bus, underground, and boat tickets respectively.  Players must use the proper ticket to move along the edges of the map. 

To begin, each player draws from a stack of tickets that contain 18 different starting locations and all five detectives place their pawns on the locations they drew. Mr. X, however, keeps his position a secret.  At the start, each detective receives:

10 taxi tickets,

8 bus tickets, and

4 underground tickets

and Mr. X receives:

4 taxi tickets, 

3 bus tickets, and

3 underground tickets.

Immediately you might be thinking: "Hey, that's not fair, Mr. X is at an extreme disadvantage!" However, while Mr. X does get less of each ticket, he also is granted five black-fare tickets, and two double-move tickets.  A black-fare ticket allows Mr. X to use any type of transport, including the boat (which the detectives do not have access to).  The double-move tickets allow Mr. X to perform two moves in one turn.  Additionally, whenever a detective uses a transport ticket, that ticket is given to Mr. X for further use.

Mr. X moves first, followed by the detectives.  No two detectives can occupy the same location. Throughout the game, Mr. X records his location in his log book and then covers it up with the type of ticket he used to get there.  Here is a picture of what Mr. X's log book might look like after seven rounds:

While the detectives are unaware of Mr. X's exact location, they are able to use the types of tickets he uses as clues.

You also may have noticed that moves numbered 3, 8, 13, 18, and 24 are all circled in the log book. This is to indicate that on those moves, Mr. X must reveal his location to the detectives.

The game is won when a detective lands on the same location as Mr. X.

I know the rules are a bit dense, so please do not hesitate to ask for clarification in the comments section.

Monte-Carlo Tree Search Strategy

The Monte-Carlo Tree Search Strategy (MCTS) has been applied to many other games such as Chinese Checkers.  However, it gets a bit more complicated when applied to games with imperfect information, such as Scotland Yard.

Basically, MCTS allows the detectives to break down the game board into smaller graphs and make better guesses as to where Mr. X might be hiding.  How it works is that each turn the detectives guess possible locations for Mr. X.  These guesses can be limited by removing the locations he cannot be based on his previous tickets used.  This list of possible locations should be updated every move.

After Mr. X makes a move, the new list of possible locations is denoted by the set N. N is calculated based on the old list of possible locations, or M, the current locations of the seekers (D), and the ticket played by Mr. X (t). So,

N = {set of all Mr. X's possible locations}

M = {previous possible locations of Mr. X}

D = {set of all detective's positions}

t = type of ticket used

Let's start with the easiest example, the beginning of the game, before any move has been taken by the detectives or Mr. X:

Let A = the 18 possible starting locations.

So, A = {13, 26, 29, 34, 50, 53, 91, 94, 103, 112, 117, 132, 138, 141, 155, 174, 197, 198}.  

Let's say the five detectives draw 13, 103, 112, 141, and 174. 

So, D = {13, 103, 112, 141, 174}.  

Thus, N = {26, 29, 34, 50, 53, 91, 94, 117, 132, 138, 155, 197, 198} 

or N = A - D since Mr. X cannot start on the same location as any detective.

Now, let's look at a bit tricker example of how to use MCTS.

Here is a visual of the area on the map I will use for this next example:

Let's assume that on round 8, Mr. X revealed himself to be at location 86.

And after Mr. X revealed himself, the detectives moved to 85, 115, 89, 116, and 127.

In round 9, Mr. X plays a black-fare ticket, which masks the type of transport he used to move.

Thus in round 9, N = {69, 87, 102, 103, 104}. Where N is ALL the adjacent locations to 86 since we do not know the ticket type.

Location 116 is also adjacent to 86, however, a detective occupies that spot, so it will not be added to N.

In round 10, we can do the same process, illustrated in this chart:

SOURCE: "Monte-Carlo Tree Search for the Game of Scotland Yard"

As you can see in the chart, detective 1 moved to 103 and detective 2 moved to 102, hence 102 and 103 can be removed from Mr. X's possible locations and our M for round 10 becomes M = {69, 87, 104}.

The chart shows that Mr. X uses a taxi ticket in round 10. We can use this information and the fact that we know Mr. X must be at location 69, 87, or 104 to calculate N.  In this case, N = {53, 68, 86, 70}. Since these are the only positions Mr. X can travel to with a taxi ticket from 69, 87 or 104 without hitting a detective.

We can continue this strategy until N becomes smaller and smaller and eventually we will know Mr. X's location for sure.

Concluding Remarks

While MCTS helps us in Scotland Yard to a certain extent, there is a way that the detectives can make their guesses even more precise.  Using a strategy called location categorization, each guess can be categorized into groups based on the probability Mr. X will move there.

In Scotland Yard we can use three different types of categorization: minimum distance, average distance, and station type. I will go more in depth on location categorization during my presentation.

MCTS along with location categorization can help the detectives reduce the randomness of Scotland Yard, and find Mr. X much faster.  It is important to note that Scotland Yard can be looked at as a giant game of "Cops and Robbers" with a lot of randomness sprinkled in.

I look forward to playing it with you all on Thursday!

Bibliography

Nijssen, A. M., and Mark HM Winands. "Monte-Carlo Tree Search for the Game of Scotland         Yard." Maastricht University. 2011 IEEE Conference on Computational Intelligence and Games. Web. <https://dke.maastrichtuniversity.nl/m.winands/documents/Cig2011pape42.pdf>.

Sevenster, Merlijn. "The complexity of Scotland Yard." University of Amsterdam. 8 Mar. 2006. Web. <http://www.illc.uva.nl/Research/Publications/Reports/PP-2006-18.text.pdf>.