Hunter V.S. Mole

The Hunter & The Mole

As an alternate version of "Cops and Robbers",  Hunter V.S. Mole involves the Hunter, who acts similarly to the Cop, and the Mole, who acts similarly to the Robber.  However, the rules of the game are tweaked a bit and provide (in my opinion) a much more interesting pursuit.

Let's get it going.

Set Up and Rules

1. The Hunter:  Not constrained by edges, but is also not able to see where the mole moves.  The Hunter plays in the dark.
2. The Mole:  Constrained by the edges of the graph and must move (can't stay in one place like the Robber).  The Mole has the advantage of being able to see the Hunter.  
3. Both players move simultaneously.
4. A graph where the Hunter wins is called "Hunter-Win".  Similarly, a graph where the Mole can win is called "Mole-Win"

Types of Graphs

So, what types of graphs are Hunter-Win, and what types of graphs are Mole-Win?  Well...lucky for you guys, I am going to tell you :D.  

The Graph we are going to be utilizing to describe Hunter v Mole is called a "Lobster".  I am not sure why these types of graphs are named after a crustacean, but I do know what it means to be a lobster (the graph that is).  

Lobster

A Lobster graph is a tree graph containing 

a path P such that all vertices are within distance 2 of P.

Example:

Here is an example of a Lobster graph taken from Dr. Komarov's presentation in Q-Club 2015.

As you can see, there is a path P that goes from left to right where each vertex is no greater than 2 moves away from P.   There are also a few other important pieces of vocabulary associated with a Lobster graph.

• A Knee in a Lobster graph is, with respect to P, a non-leaf vertex at distance exactly 1 from P. A knee must also contain feet in order for the edge to be considered a knee.  Therefore we only have 1 knee in the Lobster graph above.
• A Foot in a Lobster graph is any leaf vertex adjacent to a knee.  There are 3 feet in this graph.
• A Hip in a Lobster is the vertex where the knee originates from.  There is one hip in this graph.

Theorem: "Lobsters are Hunter-Win"

Ok, so.  I feel it is best I go over this in class as it involves inserting many pictures into this blog post. However, feel free to take a look at the proof here, or on page 3 in this paper.  I have provided a general outline below as this will help when I explain it in class.

1. Essentially, the proof states that the Mole can either be an odd or even Mole.  This means that the Mole is either an odd number of vertices away from the Hunter or an even number of vertices away from the hunter. 
2. The hunter starts at one end of the path P, assuming the Mole is either odd or even.  Let's assume the Hunter chooses the Mole to be odd. 
3. The Hunter then moves across path P one vertex at a time, while the mole moves simultaneously, trying to maximize capture time. 
4. If the hunter gets to the other side of the graph and finds that he has not captured the Mole yet, then he can deduce that the Mole is actually even, instead of odd. 
5. Therefore, in optimal play, the Hunter moves back across path P, eventually capturing the Mole.  
6. The reason this works is because each vertex straying from path P is no more than 2 edges away.  

This might be a bit confusing, but I will go over it in class.  Keep in mind that the Hunter does not know where the Mole is and that the hunter is not constrained by the edges...so the proof is comparable to the process of elimination.  All in all, Lobsters are Hunter-Win.

Mole-Win Graphs

We have seen that Lobsters are Hunter-Win, and to come full circle, I will exemplify that no graphs other than Lobsters can be Hunter-Win.  

Let's just assume these two Lemmas have been proven true, no questions asked.  

Lemma 1

Let H be any mole-win graph. Then any graph G containing H as a subgraph is also mole-win. 

 Lemma 2 

The cycle Cn is mole-win for all n ≥ 3.

These are both very similar to the properties of the Cops and Robbers graphs we learned about last Thursday.  To recall: If there is a cycle Cn with n≥4, stand alone or serving as a subgraph, then the Robber wins.  

So if there is a cycle Cn with n≥3, then it is Mole-Win...as seen in this diagram below.  

The loop to the right of the graph illustrates how the Hunter can move wherever she wants, but since the Mole can move simultaneously with the robber, and also have eyes on her...the Mole wins.  Those "+" signs are indicators of each possible move the mole can make.

Corollary 1

Any graph containing a cycle is mole-win.

This next graph is referred to as the dreaded Three Legged Spider graph!  Not really all that "dreaded", but I had to capitalize on that opportunity.  Anywho... the last graph we looked at was a cycle with n≥3, so we already know that those are Mole-Win.  Now, we are going to look at tree graphs, and if they too can ever be Mole-Win.  (Hint: they can)

Behold...the Three Legged Spider graph.

This graph is, in fact, Mole-Win.   Again, the best way for me to explain this is to go over it in class. However, I will provide a brief scenario to show how it can be Mole-Win.

Scenario:

1. Let's Assume that the Hunter starts at vertex 0, and that she believes the Mole to choose either a2, b2, or c2 at the start (making it an even Mole).  Therefore, on his next turn, the Mole can move to a1, a3, b1, b3, c1, or c3.
2. In optimal play, the Hunter would move to any one of a1, a3, b1, b3, c1, or c3.  This is in an attempt to anticipate the Mole's move from a2, b2, or c2.  
3. Assume the Hunter moves to a1 or to a3. In both cases, the mole will be at one of the vertices 0, a2, b2, c2 on the next turn after that, and we have repeated the position we started with, showing that the hunter cannot guarantee capture of the even Mole by starting at vertex 0.  

This is but one scenario of many with a Three Legged Spider tree, that works towards proving this graph, as a Mole-Win graph.

Here is a nice diagram that illustrates all the possible scenarios, while simultaneously illustrating why it is best for me to go over this in class.

Conclusion

With the Three Legged Spider graph, let's denote it as "S3,3", we can deduce a Lemma, and a Corollary about Mole-Win graphs.

Lemma 3

S3,3 is a Mole-Win Graph

Corollary 2

Any tree containing S3,3 as a subgraph is mole-win.

And, based on Corollary 2 and what we saw about cycle graphs with n≥3, we can now provide a forbidden subgraph characterization of Lobsters.

Lemma 4 

A tree is a lobster if and only if it does not contain S3,3 as a subgraph.

Lemma 5 

A loop-free graph is hunter-win if and only if it is a lobster.

The proofs for all of these and more can be found in this paper.  This blog post is meant to give you guys a solid understanding about the basics of Hunter V.S. Mole, and my presentation in class will go into more depth about optimal strategy for both players.

Please feel free to ask questions or comment below.  See you all in class Thursday.

Work Cited

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

file:///Users/JackPeacock/Downloads/HunterMolePaper%20(1).pdf