2020 Summer Science Research Project

ARTIFICIAL INTELLIGENCE FOR THE BOARD GAME "SCOTLAND YARD"

Student: Hanh Phan '22

Research Mentor: Dr. Sean McCulloch

Abstract

Board games have always played an important role on kids’ growth; they bring a lot of fun when friends or families play together. Scotland Yard is a board game that depicts the hunt for Mr. X through the streets of London. There are six players (five detectives and Mr. X) whose jobs are to move from point to point around the map of London using taxis, buses, and underground tickets. The five detectives would try their best to catch Mr. X. Mr. X’s transportation is mostly revealed every round while his exact location is known sometimes through the game. The game ends when either it reaches round 24 or Mr. X is caught by any detective. Our study created a computer version of Scotland Yard that allows six players to play in turn. We also created a bot who plays as five detectives and makes the best moves to catch Mr. X. Using breadth first search algorithm for the map, a detective knows his shortest path to reach Mr. X. For every round, each detective gets updated about Mr. X based on his transportation or his last revealed location. A detective could choose to move towards Mr. X’s current possible locations, Mr. X’s predicted locations next round or an Underground station where it would be easy to get to a distant location in one move. Before any detective makes a move, they all communicate and decide which move is the best for all.

The Game

Scotland Yard's map was built based on the streets of London. There are 199 locations on the map where each player can be at. Each detective starts with 10 Taxi, 8 Bus, and 4 Underground tickets. Mr. X has 2 Double tickets (allows him to make 2 moves at one round) and 5 Black tickets (hides Mr. X's means of transportation). 

AI Agent: The Planner

Our study focused on creating and AI agent named The Planner who plays as 5 detectives to catch Mr. X. The main goal is to manage communication among the five detectives. Based on Mr. X's revealed information including his means of transportation and his current locations at round 3, 8, 13, and 18, the five detectives have some knowledge of where Mr. X maybe at, so they can chase Mr. X effectively.

Before Mr. X appeared the first time (round 3), the detectives move towards the nearest Underground station, which will allow them to move comfortably and widely on the map when Mr. X shows up.

After round 3, every time Mr. X moves, his means of transportation is announced to five detectives. Their knowledge about Mr. X's current location is updated. Using the Breadth First Search algorithm, The Planner finds the shortest path for each detective to reach Mr. X's possible locations. If there are a lot of paths with the same distance, The Planner will choose the most effective one that saves Underground tickets. It connects the five detectives, let them "discuss" and then "decide" which destination to head to. One of the main goals is that no 2 detectives are trying to reach the same destination. If a detective is moving to one of Mr. X's possible locations, he informs other detectives so that they can remove that position from their list of Mr. X's locations. If the set of Mr. X's possible locations gets too large, the detectives will try to move to well-connected locations before Mr. X shows up again.

Achievements &  What's Next

The current AI agent knows the main ways of chasing Mr. X effectively, but there are a lot more things future researchers can do to make it smarter such as deciding the moves for detectives when Mr. X plays a Double tickets and deciding whether a detective should move to a Mr. X's possible locations or a well-connected location for each move.