Scotland Yard Board Game

Intro

In this post I will be discussing the board game known as Scotland Yard, a variation of the cops and robbers pursuit game involving 2 to 6 players. This variant of cops and robbers is played where the main goal of “Mister X” (the robber) is to survive until time expires, while multiple cops try to surround and capture the robber as quickly as possible. This game was invented in 1983 by the company Ravensburger, where the board is a map of London, hence the name Scotland Yard which is the name London’s police headquarters.

[1]

Rules

Bear with me on this one, there are a lot of rules in the game:

One player will control the robber (Mr. X), who’s moves remain secret except for during specific rounds of the game, while the other players each control a cop. The board is made up of 199 vertices, with each edge being a certain means of transportation. Each player starts with a fixed number of tokens, which are split between Taxi, Bus, Underground, and Water route passes. In order to move along an edge, the player must pay 1 token of that edge’s medium. So for example if a cop wanted to take a taxi to Piccadilly Circus they must pay 1 taxi token. All edges can be used by taxis, while Bus and Underground trips are available for longer trips across the board. The water routes can only be used by Mr. X. All the cops start with 10 taxi, 8 bus, and 4 underground tickets, while Mr. X gets 4 taxi, 3 bus, 3 underground, 2 double move, and black (all transport) tickets equal to the number of cops. One important wrinkle is that whenever a cop moves, his ticket payment goes to Mr. X, essentially giving Mr. X unlimited travel. During the game, Mr. X must reveal his location at rounds 3, 8, 13, and 18. The cops must coordinate and work together to catch Mr. X, while using his locations and travel options as clues. The game ends if the cops catch the robber (landing on the same vertex) or the robber survives until the cops run out of tokens and can no longer move.

Strategy

Since the game has imperfect information (cops do not know Mr. X’s location), there is no definitive strategy as this is not a cop-win game. The most prevalent strategy applicable to Scotland Yard is the Monte-Carlo Tree Search. A Monte-Carlo tree search is a heuristic search algorithm used to analyze the optimal move by creating a tree with all possible moves. This algorithm has four stages: Selection, Expansion, Playout, and Back-propagation. At each move, new trees must be created and “played out” to find the optimal move.

The problem with the algorithm, since the game has imperfect information, this strategy can only give the cops a few good choices from which they confer and make a decision. When the MCTS is applied to Scotland Yard, the fact that there is imperfect information means the algorithm isn’t perfect but the cops do have an advantage because they know the transportation method Mr. X has used. For example if Mr. X was at a cab only position last move, then the cops can accurately narrow it down to a few positions to corner Mr. X (as seen below).

[2]

Since Mr. X plays a new ticket every round, the possible locations must be updated to show this. The algorithm will return the list of locations from point p using ticket t.

Once the cops identify the possible locations for the robber, they then categorize the locations into the following: Minimum Distance, Average Distance, and Station Type. With minimum distance, each location is analyzed to see how many moves it will take a cop to arrive there. All locations with a minimum distance of 5 or more are grouped together because the locations closest to the cops are most dangerous to Mr. X so it is unlikely for him to move there. Average distance takes each location and, as you can probably guess, determines the average distance from all cops. Again, all locations with an average over 5 are grouped together. Finally, the station type classifies the different means of transportation connected to the possible location:

1 is strictly taxi,

2 is taxi and bus

3 is taxi, bus, and underground

3 is taxi, bus, and underground, plus a water route

Once this process is done, ideally the cops will take the best locations from the groups and match them up against results from previous games where the vertices were actual locations for Mr. X. The algorithm is used over a succession of games so the cops can see the trend of Mr. X’s movement, whoever he may be.

Grand Finale

So that is the Scotland Yard Board Game in a nutshell, the rules are complicated but the basic idea is to corner and surround the robber to ultimately capture him, without knowing where he is for the majority of the game. The Monte-Cristo Tree Search (I left out a lot of the confusing nuts and bolts) boils down to estimating where Mr. X moved and coordinating how to get there and not let him slip away! I will bring the game to class and we can play it, forewarning it will take a big chunk of class! 

See you Tuesday

- Harry C

Sources:

https://dke.maastrichtuniversity.nl/m.winands/documents/Cig2011pape42.pdf

https://books.google.com/books?id=BeBgNwOmxa4C&pg=PA211&lpg=PA211&dq=scotland+yard+analysis+math&source=bl&ots=U_TE1uKrmp&sig=IcEfpVRVDYfM_n1KhUD2YZQQcsY&hl=en&sa=X&ved=0CEYQ6AEwCGoVChMI_4GQm__2xwIVRVo-Ch3N-wfE#v=onepage&q=scotland%20yard%20analysis%20math&f=false

https://en.wikipedia.org/wiki/Monte_Carlo_tree_search

https://en.wikipedia.org/wiki/Scotland_Yard_(board_game)

---

[1] http://www.gorgoo.com/index.php?page=search/images&search=yard+board+games&type=images

[2] Nijssen, J.A.M.; Winands, M.H.M., "Monte-Carlo Tree Search for the game of Scotland Yard," in Computational Intelligence and Games (CIG), 2011 IEEE Conference on , vol., no., pp.158-165, Aug. 31 2011-Sept. 3 2011