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

The Rotor-Router Model

What is it? 

The Rotor-Router Model, created by Jim Propp, is a four sided device that is meant to represent that of random walk. A Random Walk  for a particular particle (or object) is a path which begins at an initial point (lets just say the origin) and that object chooses its next path/direction with equal probability, no mater the previous movement.

Most of us, including myself, practices random walk    
at least 3 times a week. GOOD JOB TEAM!

So... What about it?

We can prove that in a finite region, Zd, the exit time of simple random walk converges to a Euclidean ball in Rd. 

With a finite region A in Zd, let A' be the region (that is random) by starting a random walk at the origin. The random walk will stop when it first exits the finite region A. 

The internal diffusion limited aggregation (DLA) is the growth model that starts from the origin. The region of An, if you were to rescale to n^(1/d), converges to a Euclidean ball in Rd with a probability of 1 as n goes to infinity. 

When an object is placed in the center after going through its random walk and rotation, the particle eventually leaves the region A, after the clockwise rotation of 90 degrees and a new step in a new direction. This serves as a simulation of first-order properties of random walk.  

When the object, after random walk, reaches a point that is not in A, that point is added next to the region and eventually, there is a sequence of regions that is created called An. 

For example: If all the rotors are initially pointing north, 

the sequence will begin A1 = {(0,0)}, A2 = {(0,0),(1,0)}, A3 = {(0,0),(1,0),(0,-1)}, etc. 

The converging Euclidean Ball 

Theorem: 

We want to prove the shape for the rotor-router model that is similar to a model with internal DLA properties. The symmetric difference of sets R and S is denoted by sym(R,S).  For a region A in  Zd, the union of closed cubes in Rd, that is centered at the points of A, can be written as A*, We write L for d-dimensional Lebesgue measure. 

(Definition: Lebesgue measure, in measure theory, is the standard way of assigning a measure to subsets of n-dimesional Euclidean space. For n = 1,2, or 3, it coincides with the standard measure of length, area, or volume.) 

Let (A_n)_{n > 1}  be rotor-router aggregation in Z^d, starting from any initial configuration of rotors. Then as n tends to infinity L( n^-1/d sym⁽A_n*, B) ) converges to zero, where B is the ball of unit volume centered at the origin in R^d.

Conclusion:

All-in-all, the Rotor-Router Model is a device made to demonstrate a random walk of an object along a graph. There are theories that try to solve how and in which direction this object or particle moves, but theres not much else to it. But it is very interesting to see how in-fact this particle moves along the graph. There is a cool website to actually see how this is represented 

here:

 http://www.cs.uml.edu/~jpropp/rotor-router-model/

References:
http://people.duke.edu/~rnau/411rand_files/image008.jpg
http://research.microsoft.com/en-us/um/people/peres/router/router.html
https://en.wikipedia.org/wiki/Lebesgue_measure
 http://www.cs.uml.edu/~jpropp/rotor-router-model/

Spelunking Problem

Introduction

The spelunking problem deals with the idea of finding a spelunker who has become lost in a system of caves and focuses on determine what is the minimum number of searchers needed to find the lost spelunker regardless of how he behaves. A cave can be regarded as a collection of sets of pathways and intersections, so it can be modeled as a graph with the pathways being labeled as edges and the intersections labeled as vertices. Here is an example of modeling a Regina map as a graph.

Usually there are two ways to search graphs - searching just the vertices or searching each of the edges. In my post, I will focus on searching the edges of the graphs. Searching the edges of the graphs means the searchers will move along the different corridors making sure that the lost spelunker is not anywhere in that corridor. However, as you may think of, sometimes the lost spelunker may be wandering around inside the caves and not just standing in a stationary position. Under such situation, in order to make sure the lost spelunker cannot unknowingly circle back behind them and go back into a corridor they have already searched, the searches occasionally have to leave searchers at vertices in a stationary spot.

Terminology

Blockers: searchers who will stay stationary at one vertex.

Search plan: 

If the formal definition is hard to follow, you can just think of e(t) and f_i(t) as the positions at time t of a lost spelunker and the ith searcher. Then a search plan must catch the lost spelunker in a finite time.

Search number: denote s(G), is the minimum cardinality of all search plans for a graph G.
Note: the search number in the spelunking Problem can be regarded as capture time in general.
Tree: an undirected graph in which any two vertices are connected by exactly on path.
Twig: a twig of a connected graph G is an edge whose ends has degree 1 in G.

Searching Methods

There are two searching methods that always be used, one-tick searching and two-tick searching. One-tick searching means each searcher is allowed to move at most once and searchers can begin at any vertex. Two-tick searching means each searcher is allowed to move at most twice and searchers can begin at any vertex, but can move down only two edges at most.
Let us consider C_4, a circular graph with 4 vertices. In this case, we need 4 searchers to search it when apply the one-tick searching. But we don't need any blockers in this case. The example is shown below:

The numbers labeled represents the searchers, the edge labeled with the number 1 indicates searcher number a moves along the edge and a number 2 indicates searcher number 2 moves along that edge, etc. In general, one-tick searching is the fastest way to search graphs, since all searchers can move simultaneously and search the entire graphs at once. However, the disadvantage of this method is it requires a lot of searchers, especially for large graphs. So this method is not always feasible.

Now let us move to two-tick searching and again, we will look at C_4 graph. In this example, the colors indicate the order of the moves. Red is the first move and blue is the second. The numbers indicate the searchers as it is in the one-tick searching, an edge labeled with number 1 indicates searcher number 1 moves along that edge and number 2 indicates searcher number 2 moves along that edge. So the colored graph would looks like the following:

So under the assumption that both searchers can move at the same time, the spelunker could be found in at least two moves. And by the time the two searchers meet they would have found the lost spelunker with absolute certainty.

Search Number of A Connected Graph

In order to be consistent and easy to understand, let us assume the cave can be regarded as a finite connected graph in which the searchers and the lost spelunker must move continuously. Let G be a finite connected graph without loops or multiple edges. Then search number s(G) <= n+1, where n is the number of vertices of G. Understanding the terminology "blockers" will provide us with an easier way to explain why s(G) <= n+1. We can set a blocker at each vertex in G, then there are total of n blockers. So we only need an additional searcher follows any path which traverses every edge of G and thus acquire the search number s(G) <= n+1.
I found several examples that will help us to gain insight into the nature of s(G), and I will go over some of them in class on Tuesday since I don't know how to draw a graph in the blogger and it would be too abstruse without having a graph. So let us do it on Tuesday!

Search Numbers of Trees

After we get a general understanding of search number, let's move to our final goal--characterize s(T) for all trees T. 

First, let us understand what is a branch. If v is a vertex of tree T, a branch of T at v is a maximal subtree T' of T such that v is a vertex of degree 1 in T'. Below is an intuitive example

Figure 1

Figure 2

Figure 1 is a tree graph T and Figure 2 represents the branches of T at vertex v.

Theorem 2:

Let k >= 1, and T be a tree. Then s(T) >= k+1 if and only if T has a vertex v at which there are at least three branches T_1, T_2, T_3 satisfying s(T_j) >= k for j=1, 2, 3.

This theorem can be used to characterize all trees with a given search number. Before we attempt to prove this theorem, we should understand Lemma 4 and Theorem 1 since they need to be used while we prove theorem 2.

Lemma 4:

Let T_1, T_2, T_3 be disjoint trees each having at least one edge. For j = 1, 2, 3 let v_j be a vertex of degree 1 in T_j. Let T be the tree obtained by identifying v_1, v_2, v_3 into a single vertex v. If s(T_j)=k for j=1, 2, 3, then s(T)=k+1.

Theorem 1:

If H is a connected subgraph of G, then s(H) <= s(G).

Preceding stuff:

If T is a tree with s(G)=k, then for each integer r with 1 <= r <= k, T has a subtree T' such that s(T')=r.

Now let us do a simple proof of the forward direction of Theorem 2.

Proof:  Suppose T has a vertex v with branches T_1, T_2, T_3 such that s(T_j) >= k.

            Then v is of degree 1 in each T_j by the definition of branches.

            By the preceding stuff, we  know that T_j has a subtree T'_j with s(T'_j)=k in which v has degree of 1.

            The subtree T' spanned by T'_1, T'_2, T'_3 has s(T')=k+1 by Lemma 4.

            Therefore, s(T) >= k+1 by theorem 1.

For determining search number of trees, there are tons of proofs we can look at. Since our goal is to get a general understanding of spelunking problem, so I think this is a good place to stop. But I will go over the proof of Theorem 2 in class on Tuesday.

Final Thoughts

The spelunking problem is a very interesting topic that definitely worth exploring. There are many variations of this searching problem such as the searchers can radio each other to modify their search plan to incorporate the new information. And variations even exist in higher dimensions. But as deep as we explore this problem, the more Graph Theory knowledge will be required. So if you doesn't feel comfortable with all the proofs or terminologies mentioned above thats fine! We'll go over them together in class on Tuesday and hope everyone can at least get to know how this "game" be set and played by then.

Reference

T. D. Parsons. "Pursuit-Evasion in a Graph".

Selinger C. "Spelunking Problem: how the solution works".

Cops, Robbers and Alarms

About the Game:        
          Cops, Robbers and Alarms is a variation of Cops and Robbers in which the Cop has imperfect information—that is, she doesn’t know the exact location of the robber. Imperfect information makes intercepting her nefarious evader considerably more challenging, so the cop must install alarms on her beat. The game is played on a finite, undirected, copwin graph as in classical Cops and Robbers, but now the cop may set alarm systems on some of the vertices.

          When the robber occupies an “alarmed” vertex, the alarm will go off and the robber’s position is revealed to the cop. The alarms do not reveal the robber’s preimage, however, so the cop does not know the robber’s direction. (There is a variation called Cops, Robbers and Video Cameras, in which there are video surveillance systems that give the robber’s direction.)     

Rules of the Game:   

          Of course the cop cannot set alarms willy-nilly around the graph—that would be too easy! After all, classic Cops and Robbers is played on the trivial, fully-alarmed graph. Instead, the cop must obey a set of conditions determined at the beginning of the game. Let’s first consider a game with relatively lenient conditions:

1.               Each unalarmed vertex must have at least one alarmed neighbor
2.               Unalarmed vertices may not have unalarmed neighbors

          When these conditions are applied to an arbitrary undirected, copwin graph G, we get something like this (Figure 1). Open circles represent alarmed vertices. 

Figure 1. A copwin graph G with liberal alarm placement.

          This particular graph would make for a very quick game of Cops and Robbers on account of its many corners and alarms. In fact, the robber could not move anywhere on the graph undetected, due to condition 2. BORING…

          So let’s tighten up the conditions on G. Suppose we created an undirected, copwin graph G on which the alarmed vertices form a dominating set. A dominating set is a subset D of G such that every element not in the intersection of D and G is adjacent to at least one element of D. When we impose this condition on the graph in figure 1, we get the following:

Figure 2. A copwin graph G, where the set of alarmed vertices forms a dominating set.  

          This new restriction eliminated a few more alarms, making it easier for the robber to evade the cop. This new alarm configuration is only slightly better for the robber though. He has a path of five unalarmed vertices in the leftmost portion of the graph on which he could move. If he remains in that central location, however, he is likely to run into the cop or get forced into a corner—not to mention that going undetected can be just as telling as setting off alarms.      

         

Alarm Number and Capture Time:

          It's clear that the alarm number, A(G), plays a critical role in determining capture time. Alarm number also determines the finiteness of the game. In some cases, graphs that are copwin in classic play become robberwin (infinite game) if there aren't enough alarms.

Witness Version of Cops and Robbers:

          Cops, Robbers and Witnesses is another variation of Cops and Robbers that warrants consideration here. Cops, Robbers and Witnesses is similar to Cops, Robbers and Alarms in that it is also based on the premise of imperfect information. In the witness version of the game, the cop is given information from witnesses either irregularly or k-regularly. 

          With irregular information, sightings of the robber are reported at random time intervals during the game. A graph is copwin with irregular information if the graph is a tree—an undirected graph in which any two vertices are connected by one unique path.

          In the case of k-regular sightings, the cop is informed of the robber's position every k units of time. A graph on which a cop can win with k-regular information is said to be k-winnable. 

Conclusion:

          Cops, Robbers and Alarms is unique in its treatment of imperfect information vis-à-vis Hunter vs. Mole or Cop vs. Gambler. Capture time and the success of gameplay depend entirely on the alarm number, A(G) (or the k-regularity of information), rather than on probability. We will continue our exploration of the game and look at some different game conditions and graph types in class on Tuesday. 

Works Consulted:

Jeliazkova, D. (2006). "Aspects of the Cops and Robber Game Played with Incomplete Information." Acadia University.

Clarke, N.E. (2008). A Witness Version of the Cops and Robber Game." Discrete Mathematics. 309(10). pp. 3292-3298.   

Cop vs Gambler

What is cop vs. gambler?
A variation of cop vs. robber where the robber is not restricted by the graphs edges, and instead moves accordingly to to a time-independent probability distribution. The cop moves from vertex to adjacent vertex with the goal of minimizing expected capture time; making the gamblers goal to maximize it

Things to know:
graph: connected and undirected with V(G) = {$v_{1}, v_{2},..., v_{n}$}
cop: same as original rules, can move from vertex to adjacent vertex and stay put on each turn
gambler: chooses probability distribution $p_{1}, p_{2},...,p_{n}$ on V(G). Each time t >= 0 he is at vertex $v_{i}$ with probability p
note: The gambler can pick whatever probabilities he wants as long as they sum to 1.

Conditions:
-players move simultaneously
-players move in the dark
-game continues until gambler is captured (both cop and gambler occupy the same vertex)

Vocabulary:
capture time- remains the same as cop vs. robber, that is the number of moves up to and including the capture.
gamble- the gamblers probability distribution, for example if a graph has 5 vertices labeled $v_{1}, v_{2}, v_{3},v_{4}, v_{5}$, on choice of gamble for the gambler is $p_{1}$ = .05 $p_{2}$ = .25 $p_{3}$ =.40  $p_{4}$ = .15 $p_{5}$ =.15
value of the game - expected capture time with both players playing at their best.

There are two variations of cop vs.gambler: 1) cop knows the gamble and 2)cop doesn't know the gamble. I am going to focus mainly on when the cop does know the gamble.

We know;
The cop can capture the gambler in expected time less than or equal to n on $P_{n}$
proof:
Strategy: cop moves from $v_{1}$ towards $v_{n}$ stopping when $p_{i}$ is large enough to allow it.
Now, Suppose cop is at $v_{i}$:
- let $m_{i}$ = n-i +1, be the total number of vertices "ahead" of the cop, including the one she is occupying
-let $c_{i}$ = $p_{i}+...+p_{n}$, be the sum of probabilities of vertices that are ahead
-let T_{i} be expected time from now (current position) until capture time

Claim: $T_{i} < m_{i}/c_{i}$ for all i /in {i....n} proceed by induction
when $m_{i}$=1, i = n, so the cop is at $v_{n}$, hence $C_{n} = P_{n}$ therefore
$T_{n} = 1/P_{n} = M_{n}/C_{n}$
Suppose this holds for all $m_{j}$ for j > 1, and cop has arrived at v_{i}
if $p_{i} >= c_{i}/m_{i}$ we are done since $T_{i} = i/p_{i} <= m_{i}/c_{i}$
suppose $p_{i}<c_{i}/m_{i}$ with probability $p_{i}$, the cop captures the gambler at $v_{i}$
(which takes one) and with probabiltity 1-p; she moves to vertex v_{i+1},
Now: $m_{i+1}=m_{i}-1<m$; so expected capture time from this new position is bounded by $m_{i+1}/c_{i+1}=m_{i}-1/c_{i}-p_{i}$. This yields the following inequality:
$T_{i}$ ≤ 1 + (1 − $p_i$) $m_i$−1 $c_{i}−p_{i}$
We have (for i > 1):
$p_{i} < c_{i}/ m_{i}$
⇒ $c_{i}(c_{i} − 1) < m_{i}p_{i}(c_{i} − 1)$
⇒ $c_{i}(c_{i} − m_{i}p_{i} + m_{i} − 1 + p_{i} − p_{i}) < m_{i}(c_{i} − p_{i})$
⇒ $c_{i} c_{i} − p_{i} (c_{i} − p_{i} + m_{i}(1−p_{i}) − (1−p_{i})) < m_{i }$
⇒ $c_{i} + c_{i}(1−p_{i}) c_{i} − p_{i} (m_{i} − 1) < m_{i}$
⇒ $1 + 1−p_{i} c_{i} − p_{i} (m_{i} − 1) < m_{i} c_{i}$
Therefore $T-{i} < m_{i} c_{i}$ whenever $p_{i} < c_{i} m_{i}$.

Lemma 2.1:  The cop can capture the gambler in expected time at most n on any tree of order n.

as well as:
Lemma 3.1: The cop and the gambler game played against a uniform gamble has expected capture time exactly n.

and:
Theorem 3.2: The value of the cop vs. gambler game on any connected n-vertex graph is n.

all of which I will discuss in class tomorrow.

It turns out the game value is n regardless of the graphs structure, whether the cop picks her initial position or not, or  whether the cop chooses her initial position before or after the gambler makes his strategy known.

We know a few different things about the unknown gambler (when the gamblers gamble is not known). One I found most interesting was Lemma 4.4 because it allows us to compare it directly with the known gambler.
Lemma 4.4: The cop vs. unknown gambler has expected capture time of less then 2n, on any connected n-vertex graph.
Since this is only any upper bound this does not hold true for every case but in most cases the unknown gambler is stronger compared to the known gambler.

Food for thought:
Imagine an anit-incursion program (or a program to prevent an attack) has to navigate a linked list of ports, trying to minimize the time to intercept an enemy packet as it arrives.; if the enemies' port choice is known we a get a version of the known gambler, otherwise the unknown gambler.

Hunter vs. Mole

Cops and Robbers

So by now we have an understanding of Cops and Robbers, we know graphs that are Cop win, we can understand capture time, and we even know how to catch drunks! The next variation of Cops and Robbers is called Hunter Vs. Mole.  While similar to Cops and Robbers, there are some big changes to the rules that have been made. I am going to do my best at explaining the rules and the quick proof. Luckily if we have any questions that I cannot answer, we have the local expert on Hunter Vs. Mole in the classroom!

Rules

Hunter:

Not constrained by edges

            Plays in the dark

Mole:

Constrained by edges

            Must move

            Can see the hunter

Players move simultaneously

Who wins?

The graphs are categorized in two different ways, the graph can be Hunter win, where the Hunter captures the Mole within a bounded time, and Mole win, if the Mole survives past the bounded time.

This leads to the question of, what graphs can the hunter guarantee capture of the mole in the bounded time. We assume that the mole is making the best possible moves to maximize capture time.

And so the theorem is that graphs are hunter win only if it is a lobster.

Yes, a lobster, the graph has to be in the shape of a lobster for the hunter to win!

As awesome as this would be, a lobster is something other than a delicious summer dinner. A lobster is a tree containing a path P, where are vertices are within distance 2 of path P.

This is an example of a lobster, AKA Hunter win graph.

But how? (A simple proof)

Start with the hunter on the orange dot, and place the mole at possible locations on the graph.  For this, we will say the mole is at the vertices that are spaced 2n moves away from the hunter. We will place multiple moles down, to show all the possible different locations, as shown below.

While the hunter is allowed to move to any location on the graph that she would like, we will take a different approach.

We will play this out just moving the hunter one move at a time.  The mole will react by moving to the best location that will maximize capture time. The lobster graph forces the mole to move back and forth in the legs of the lobster, hopefully to avoid capture.  The hunter works her way across the graph, moving down legs where need be.  The hunter will ultimately catch the mole going from left to graph in this graph, but lets cook a lobster in class and see if we can prove it on our own graph!

Now that we know what Hunter win graphs look like, we will take a quick look at graphs that are Mole win.  First looking at graphs, we will look at spiders!!

Three legged spiders instead of eight legged ones, as seen below.

                                  

Upon further examination, the sequences of locations will repeat, and the hunter will not make any progress to catching the mole, and thus is a Mole win graph.

So we can state that a graph is Hunter win if and only if it is a lobster!

Variation

What is a game like cops and robbers without a variation? What if the mole can stay put? We see that if there are two or more vertices that the mole can stay put, means that the graph is Mole win.

But what about if the mole can stay put at exactly one endpoint? This is still Mole win if and only if the graph is a lobster and the end point is on the main pathway.

As you could probably assume, the variations can go on and on, different locations for the loops, more than one hunter, etc.

Please let me know if you have any questions, and I can answer them during the presentation.

Thank you,

Sam Horan

http://myslu.stlawu.edu/~nkomarov/450/HunterMolePaper.pdf
http://myslu.stlawu.edu/~nkomarov/450/HunterMole-BeamerStLaw.pdf