Old coursework submission

scotland_ yard.tex

\title{Representing Scotland Yard with data structures, and using Computational Thinking to determine Mr X's location}
\author{Matthew Barber\\
160056525}
\date{\today}

\documentclass{article}

\usepackage{tikz}
\usepackage{graphicx}
\usepackage{calc}
\usepackage{adjustbox}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{tikz-qtree}
\usepackage{float}
\usepackage{listings}
\usepackage{drawstack}
\usepackage{color}
\usepackage[inline]{enumitem}

\tikzstyle{T}=[yellow, ultra thick]
\tikzstyle{B}=[blue, ultra thick]
\tikzstyle{U}=[red, ultra thick]
\tikzstyle{F}=[black, ultra thick]

\tikzstyle{tree} = [level distance=4em,sibling distance=1.5em,
edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}]

% \begin{reusefigure}[<float spec>]{<ref>}
\newenvironment{reusefigure}[2][htbp]
{\addtocounter{figure}{-1}%
	\renewcommand{\theHfigure}{dupe-fig}% If you're using hyperref
	\renewcommand{\thefigure}{\ref{#2}}% Figure counter is \ref
	\renewcommand{\addcontentsline}[3]{}% Avoid placing figure in LoF
	\begin{figure}[#1]}
{\end{figure}}

\begin{document}
\maketitle

\section{Introduction}

The purpose of this essay is to analyse the mechanics of the strategy board game, Scotland Yard, and find ways to determine the possible places Mr X could be at a given moment of the game. Using such conclusions will also allow us to determine whether there are scenarios that the detectives can certainly capture Mr X.

\section{Data structures to represent the game}

\subsection{The playing board}
\label{board}

Scotland Yard incorporates a rough map of London but makes the actual game of avoiding detectives/capturing Mr X happen in a restricted set of locations distributed throughout the game’s board, which contain at least one route to another point. Each location is always available by taxi from at least one point, but the location may also contain a bus and/or train station. Routes can be for taxis, buses, trains, or ferries.

The specification of the playing board can be succinctly represented in the graph data structure. A graph is ``a collection of \textit{nodes} called \textit{vertices}, and the connections between them, called \textit{edges}'' (Broadhurst, 2016)\cite{broadhurst16}. Recognizing each locations as one node in a graph, with each route as a weighted and undirected edge,  you can translate Scotland Yard’s main game space to a graph fully representing the board.

We can ignore the locations' possible station types as the weights on edges infer that information.

\begin{figure}[H]
	\begin{subfigure}{0.5\textwidth}
		\caption{A visualized graph}
		
		\begin{tikzpicture}
			\begin{scope}[every node/.style={circle,thick,draw}]
				\node (1) at (0,0) {1};
				\node (2) at (2,1) {2};
				\node (3) at (2,-1) {3};
				\node (4) at (3,-3) {4};
				\node (5) at (5,-4) {5};
				\node (6) at (4,-5) {6};
			\end{scope}
			
			\path (1) edge[F, bend left=50] (5);
			\path (2) edge[U, bend left=10] (6);
			\path (1) edge[B, bend right=10] (4);
			\path (2) edge[B, bend left=10] (4);
			\path (4) edge[B, bend right=10] (6);
			\path (1) edge[T, bend left=20] (3);
			\path (2) edge[T, bend right=10] (3);
			\path (3) edge[T, bend left=10] (4);
			\path (4) edge[T, bend left=10] (5);
			\path (4) edge[T, bend left=10] (6);
			\path (5) edge[T, bend left=10] (6);
		\end{tikzpicture}
	\end{subfigure}
	\begin{subfigure}{0.5\textwidth}
		\caption{Adjacency list of the respective graph}
		\begin{tabular}{ll}
		Node & Connected to \\ \hline
		1 & 3,T; 4,B; 5,F \\
		2 & 3,T; 4,B; 6,U \\
		3 & 1,T; 2,T; 4,T \\
		4 & 1,B; 2,B; 3,T; 5,T; 6,T; 6,B \\
		5 & 1,F; 4,T; 6,T \\
		6 & 2,U; 4,T; 4,B
		\end{tabular}
		\resizebox{.5\textwidth}{!}{%
		\begin{tabular}{ll}
		\\
		\color{yellow} \textbf{Yellow} & Train (T) \\
		\color{blue} \textbf{Blue} & Bus (B) \\
		\color{red} \textbf{Red} & Underground Train (U) \\
		\textbf{Black} & Ferry (F)
		\end{tabular}}
	\end{subfigure}
\caption{A representation of a plausible portion of the Scotland Yard map}
\label{fig:map-graph}
\end{figure}

\subsection{Possible locations where Mr X could be}

Mr X's original position is unknown to the detectives, but after Mr X has used an action on certain turn, they must reveal their current location to the detectives (referred to as `surfacing'). After the first reveal at turn 3, every 5 turns after is also a reveal until turn 24.

Every action Mr X takes is restricted to using one route of any type connected to their location (traversing one edge to an adjacent node), and Mr X has to declare what mode of transport they are using (the weight of the edge they are using) by displaying a `detective ticket' of that route---expect if and when depleting a `black ticket', which indicates they have moved but not what mode of transport was used. The black ticket is also the only ticket that enables Mr X to use a ferry route. Mr X cannot enter a location occupied by a detective.

These restrictions allow the determination of all possible location Mr X can be after their reveal at turn 3 (before then, he could be practically anywhere on the map). A weighted tree graph would be an appropriate representation of the possible locations Mr X could be at afterwards however.

A tree can be defined as a ``data structure accessed beginning at the \textit{root} node. Each \textit{node} is either a \textit{leaf} or an \textit{internal node}. An internal node has one or more \textit{child} nodes and is called the \textit{parent} of its child nodes. All children of the same node are \textit{siblings}. Contrary to a physical tree, the root is usually depicted at the top of the structure, and the leaves are depicted at the bottom.'' (Black, 2008)\cite{black08}.

Each node represents a location on the board, with each edge weighted by the type of transport used as with in Figure \ref{fig:map-graph}. Every level represents a sequential turn.

Locations which can be accessed by multiple routes have separate nodes, distinguished by the weight of the incoming parent's edge.

For example, after Mr X reveals at location 100, there could be 8 possible locations he could move to.

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[tree]
	\Tree [.100 
		\edge[B]; 63
		\edge[T]; 80
		\edge[T]; 81
		\edge[B]; 82
		\edge[T]; 101
		\edge[B]; 111
		\edge[T]; 112
		\edge[T]; 113 ]
	\end{tikzpicture}
	\caption{Possible locations Mr X could be a turn after revealing at location 100}
	\label{fig:possible-locations}
\end{figure}

The detectives will be able to exclude certain possible locations as Mr X has to reveal which mode of transport he uses---in this case, the bus. The exception to this is the black ticket, in which no exclusions can be made.

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[tree]
	\Tree [.100 
		\edge[B]; 63
		\edge[B]; 82
		\edge[B]; 111 ]
	\end{tikzpicture}
	\caption{Refined Figure \ref{fig:possible-locations}, with Mr X using a bus route allowing the detectives to exclude all other routes}
	\label{fig:refined-possible-locations}
\end{figure}

In the next turn, the number of possibilities grow exponentially.

\begin{figure}[H]
	\begin{subfigure}{\textwidth}
		\centering
	\begin{tikzpicture}[tree]
	\Tree [.63 
		\edge[B]; 34
		\edge[T]; 48
		\edge[T]; 64
		\edge[B]; 65
		\edge[T]; 79
		\edge[B]; 79
		\edge[T]; 80
		\edge[B]; 100 ]
	\end{tikzpicture}
	\caption{Possible locations from location 63}
	\end{subfigure}

	\begin{subfigure}{\textwidth}
		\centering
	\begin{tikzpicture}[tree]
	\Tree [.82 
		\edge[B]; 57
		\edge[T]; 65
		\edge[B]; 65
		\edge[T]; 66
		\edge[T]; 81
		\edge[B]; 100
		\edge[T]; 101
		\edge[B]; 140 ]
	\end{tikzpicture}
	\caption{Possible locations from location 82}
	\end{subfigure}

	\begin{subfigure}{\textwidth}
		\centering
	\begin{tikzpicture}[tree]
	\Tree [.111 
		\edge[U]; 62
		\edge[U]; 79
		\edge[B]; 100
		\edge[T]; 110
		\edge[T]; 112
		\edge[T]; 124
		\edge[B]; 124
		\edge[U]; 153
		\edge[U]; 163 ]
	\end{tikzpicture}
	\caption{Possible locations from location 111}
	\end{subfigure}
	\caption{All possible locations two turns after Mr X's reveal, extending Figure \ref{fig:refined-possible-locations}}
\end{figure}

However, if Mr X declares they used a taxi, we can greatly reduce the number of possible locations.

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[tree]
	\Tree [.100 
	\edge[B]; [.63 
		\edge[T]; 48
		\edge[T]; 64
		\edge[T]; 79
		\edge[T]; 80 ]
	\edge[B]; [.82 
		\edge[T]; 65
		\edge[T]; 66
		\edge[T]; 81
		\edge[T]; 101 ]
	\edge[B]; [.111 
		\edge[T]; 110
		\edge[T]; 112
		\edge[T]; 124 ] ]
	\end{tikzpicture}
	\caption{All possible locations Mr X can be 2 turns after revealing}
\end{figure}

This means Mr X \textit{has} to be at locations on the bottom level of the above tree.

\subsection{Planning movements for the detectives}

For detectives, the decision for where to move should be reasoned by a few considerations to make for a winning strategy:

\begin{itemize}
\label{list}
	\item Before the first reveal of Mr X on turn 3, detectives will want to be near train stations for quick travel, and equally cover all directions.
	\item Semi-blocking (discouraging) Mr X from going to certain locations by placing a detective who could, on their next turn, enter one or more locations Mr X occupies.
	\item Moving a detective onto a location possibly occupied by Mr X in hopes of capturing them.
	\item Blocking where Mr X can go by placing a detective at a certain location respective to Mr X's location.
	\item Placing a detective at train or ferry stops where Mr X could get to/end up to reduce/eliminate chances of Mr X moving far away from a detective-concentrated zone.
\end{itemize}

Much of Mr X movements will be unpredictable from a pure logical sense, as for most turns there will be multiple locations as possibilities, and the chosen location is up to the whims of whoever is playing as Mr X.

However, the core strategy demonstrated in the above points---of containing Mr X by restricting escape routes, and closing in by further narrowing down on their location---requires detectives to weight their decisions of where to move immediately by where they can move in the following turns.

Similarly to determining Mr X's possible locations, a tree structure can represent all possible locations after multiple turns from an initial position (represented as the root node).

For example, Mr X could reveal himself at location 112. If other detectives are in close proximity around that area of the board, then Mr X will likely want to use a train station to create a large distance between themselves and the detectives. On the turn of the reveal, detectives can determine the possible train stops Mr X could be at 2 turns later.

The detectives will want to block the destinations that the train station could lead into. This could also allow for detectives to help narrow down Mr X by using the train enter Mr X's proximity on the following turn.

\begin{figure}[H]
	\begin{subfigure}{\textwidth}
		\centering
		\begin{tikzpicture}[tree]
		\Tree [.112 
		\edge[T]; [.111 
		\edge[U]; 67
		\edge[U]; 79
		\edge[U]; 153
		\edge[U]; 163 ] ]
		\end{tikzpicture}
		\caption{Mr X, if a train is used 2 turns after reveal at location 112}
		\label{mr-x-trains}
	\end{subfigure}
	\begin{subfigure}{0.5\textwidth}
		\centering
		\begin{tikzpicture}[tree]
		\Tree [.62
		\edge[T]; [.79 
		\edge[U]; 67
		\edge[U]; 111 ] ]
		\end{tikzpicture}
		\caption{Detective at location 79, covering train stations}
		\label{fig:detective-79}
	\end{subfigure}
	\begin{subfigure}{0.5\textwidth}
		\centering 
	\begin{tikzpicture}[tree]
		\Tree [.166
		\edge[T]; [.153 
		\edge[U]; 111
		\edge[U]; 163 ] ]
		\end{tikzpicture}
		\caption{Detective at location 154, covering train stations}
		\label{fig:detective-154}
	\end{subfigure}
	\caption{Possible movement trees, refined to demonstrate the strategy above}
\end{figure}

In this scenario, mapping out the possible locations for these two detectives shown in Figures \ref{fig:detective-79} and \ref{fig:detective-154} reveals that the detectives can mostly shut-down the scenarios in Figure \ref{mr-x-trains}:
\begin{itemize}
	\item Mr X cannot travel to locations 79 and 153 due to those being occupied by a detective.
	\item Mr X can travel to 67 and 163, but the respective detectives can move there via train on their turn to capture Mr X the following turn.
	\item Mr X could expend a double movement ticket to move to 67 or 163 and then beyond, which would be disadvantageous in and of itself for the detectives, however:
	\begin{itemize}
		\item Mr X has had to expend a powerful tool, which now weakens their future prospects.
		\item One detective on a station can follow Mr X to pressure them at their location.
	\end{itemize}
	\item If Mr X decides not to use the train, then a detective can move into location 111 to pressurize Mr X.
\end{itemize}

This example demonstrates that finding possible movements for all the detectives using a tree structure, and collating that information together, allows the detective team to strategically move themselves with respect to their options in future turns.
	
\subsection{Supporting algorithms}

To create a possible movements tree for both Mr X and the detectives, an algorithm needs to traverse a graph representation of the playing board as described in Section \ref{board}.

The core element of this algorithm is to check a node in the graph and check each edge connected to that node for whether Mr X or the individual detective piece cannot traverse the respective edge. The function \texttt{check} indicates that for both teams, they would not be able to traverse that edge and by extension reach the destination node if:
\begin{itemize}
	\item A detective is at the destination node.
	\item There is not a ticket type available (including black tickets for Mr X) of that edge's particular transport type (stored as a weight, as demonstrated in Figure \ref{fig:map-graph}) in their ticket pool.
	\item If a possible movement tree is being created for Mr X in retrospect (for example, finding all possible locations of Mr X 2 turns after a reveal), eliminate edges which are contrary to the ticket type publicly shown by Mr X for each respective turn.
\end{itemize}

\newcommand{\maxlevel}{maximum level of the desired possible movements tree}

The above function \texttt{check} is to be used repeatedly for every node on a particular tree level, for the amount of levels (turns ahead) desired. A queue, described by S.Adamchik (2009)\cite{adamchick09} as a data structure that contains multiple objects where new items are enqueued from the bottom and only the top item can be removed (following the first-in-first-out principle), would be appropriate to aid in creating the tree. 

For example, say we want to find the possible locations of Mr X a turn after they reveal on location 111. The set of all connected nodes is as follows:

\begin{itemize*}
	\item 62,U
	\item 79,U
	\item 100,B
	\item 110,T
	\item 112,T
	\item 124,T
	\item 124,B
	\item 153,R
	\item 164,R
\end{itemize*}

Say we know Mr X has used a bus ticket, we can then expect the following proceedings.

The initial position is first entered into the queue, following a control item specifying that future items placed above will be the children of the aforementioned root node.

\begin{figure}[H]
	\centering
	\begin{drawstack}
		\cell{111,0} \cellcom{Control item}
		\startframe
		\cell{111,X} \cellcom{Root node}
		\finishframe{Level 0}
	\end{drawstack}
	\caption{Initialized queue to generate possible movements tree}
\end{figure}

All connected nodes are applied the \texttt{check} function. The items of a transport type which is not via bus (B) will result in a return of \texttt{false}, meaning they are not entered into the queue. The items 100,B and 124,B will return \texttt{true} as they are bus paths, therefore being enqueued into the queue.

\begin{figure}[H]
	\centering
	\begin{drawstack}
		\startframe
		\cell{124,B} \cellcom{Location 124}
		\cell{100,B} \cellcom{Location 100}
		\finishframe{Level 1}
		\cell{111,0}
		\startframe
		\cell{111,X}
		\finishframe{Level 0}
	\end{drawstack}
	\caption{Completed queue to generate possible movements tree}
	\label{fig:queue}
\end{figure}

The first item of Figure \ref{fig:queue} can be dequeued to form the root node of a possible movements tree. The queue will now look as follows.

\begin{figure}[H]
	\centering
	\begin{drawstack}
		\cell{124,B}
		\cell{100,B}
		\cell{111,0}
	\end{drawstack}
	\caption{Queue in process of generating possible movements tree}
\end{figure}

The next item (111,0) in the queue, now the front-most, is dequeued. The integer value right to the comma indicates this item is a pointer for the subsequent items, with the 1st value indicating the node to branch of and the 2nd value indicating the level in which it resides.

Note that if the 1st value contains a value which has already been pointed to in that same level, it can be assumed that there is a subsequent node of the same value in that level which is to be pointed too.

With the pointer stored in the program, the subsequent items are dequeued and appropriately linked to their respective parent (in this case, node 111 in level 0) with the appropriate path weight.

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[tree]
	\Tree [.111 
	\edge[B]; 100 
	\edge[B]; 124 ]
	\end{tikzpicture}
	\caption{Completed possible movements tree}
\end{figure}

\section{Applying a programming paradigm in making decisions}

The Object Oriented Programming (OOP) paradigm could be applicable in an implementation of a decision-making program due to the dynamic nature of various variables in Scotland Yard which require interaction and mutation throughout a play session when using a decision-making program.

OOP can identify common features of the game (abstraction), and hold these items with useful procedures in a data structure (encapsulation). One can form an ``object'' which is made of attributes (respective data of Mr X or a detective) and methods (operations to interact with said data) with the aforementioned steps (Beal)\cite{bealNA}.

Both Mr X and the detectives constantly change their state in the game (in way of their respective ticket pools and current locations), and to find future possible game states requires knowing what the state of both sides are at a given turn.

A class---instructions made by a programmer to indicate common properties for objects that are made from the said class---could hold the available tickets and current location of any given player of the game. Included in the class would be methods which allows the program to receive this information (accessors methods) and change the values of the object's data (mutator methods) as described by Cheung (2010)\cite{cheung10}.

A base class could be the parent of two derived classes (Yaiser, 2012)\cite{yaiser12}, for Mr X and a detective, so as Beal\cite{bealNA} states allow the programmer to re-factor common properties (inherit) but change/create methods particular to either side (incur polymorphism).

The possible movements tree generation and decision-making aspects of the program could then access objects created from these classes---representing the characters in-play---using defined methods. As the game progresses, the objects can be mutated via mutator methods to update the state of the object, so the program can be useful throughout a play session as it has the current information of a game's state.

\section{Determining whether the capture of Mr X is a certainty for a given game state}

The question of whether the detectives can assuredly know if the capture of Mr X is possible in a given game state could only be answered either if:
\begin{itemize}
	\item Every single state of Scotland Yard has been simulated. This means every arrangement of starting positions for Mr X and the detectives has been run through every single decision made by Mr X, and subsequently every decision that could be made by the detectives, to be stored in a massive data-store such as a database or (multiple) trees.
	\item A generalized strategy for the detectives has been found, which works to capture Mr X before the end of the game, regardless of the decisions Mr X has taken (as these decisions are subject to unknown human whims).
\end{itemize}

The first scenario is theoretically possible, but something we cannot access as no one has made accessible a public store of such information for the Scotland Yard game. With use of methods described in this essay, it could be made, but due to the exponential nature of permutations a system like Scotland Yard would have when checking through all possible scenarios, creating such a store of possible states would be an extremely resource-intensive undertaking. 

Whether the second scenario, a generalized ``best'' strategy (makes the most appropriate decisions for the detectives), can be found is undetermined as of the time of this essay. This means that determine whether Mr X's capture is inevitable or not in \textit{any} given state is unknown.

Only for certain scenarios, namely if Mr X has revealed themselves in a position locked down by the detectives or if Mr X is far away from the detectives with not many turns left, can we plausibly make a determination on whether Mr X can be captured.

\section{Conclusion}

Whilst ultimately knowing whether or not the capture of Mr X is assured is out of our reach for most cases, this essay demonstrates the use of data structures (graphs, trees and queues) and the Object Orientated paradigm to aid in the creation of a decision-making program, to be used by the detectives to help increase their chances of capturing Mr X.

\newpage

\begin{thebibliography}{9}
	\bibitem{bealNA}
	Beal, V. (no date)
	\emph{Object Oriented Programming}.
	Available at:
	http://www.webopedia.com/TERM/O/object\_oriented\_programming\_OOP.html
	(Accessed: 17 December 2016).
	
	\bibitem{black08}
	Black, P.E. (2008)
	\emph{tree} in \emph{Dictionary of Algorithms and Data Structures}.
	Available at:
	https://www.nist.gov/dads/HTML/tree.html
	(Accessed: 17 December 2016).
	Atallah, M.J. (1998)
	\emph{Algorithms and Theory of Computation Handbook}.
	Edition 14.
	Boca Raton: CRC-Press.
	
	\bibitem{broadhurst16}
	Broadhurst, M.  (2016)
	\emph{Graph data structures}.
	Available at:
	http://www.martinbroadhurst.com/graph-data-structures.html (Accessed: 17 December 2016).
	
	\bibitem{cheung10}
	Cheung, S.Y. (2010)
	\emph{Accessor and Mutator methods}.
	Available at:
	http://www.mathcs.emory.edu/~cheung/Courses/170.2010/Syllabus/02/access+mutate.html
	(Accessed: 17 December 2016).
	
	\bibitem{adamchick09}
	S.Adamchik, V. (2009)
	\emph{Stacks and Queues}.
	Available at:
	https://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks\%20and\%20Queues/Stacks\%20and\%20Queues.html (Accessed: 17 December 2016).
	
	\bibitem{yaiser12}
	Yaiser, M. (2012)
	\emph{Object-oriented programming concepts: Inheritance}
	Available at:
	http://www.adobe.com/devnet/actionscript/learning/oop-concepts/inheritance.html
	(Accessed 17 December 2016).
\end{thebibliography}


\end{document}