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
http://myslu.stlawu.edu/~nkomarov/450/HunterMolePaper.pdf
http://myslu.stlawu.edu/~nkomarov/450/HunterMole-BeamerStLaw.pdf
Hi Sam - Thank you for your post. This is a very interesting variation of cop vs. robber games. It's interesting to see the dynamic between the mole and the hunter since they both have very different moves available but the mole also has an information advantage. I am a little confused about the difference between hunter win and mole win graphs. It seems like if it was not for the number of moves being restricted, all graphs would be hunter win, since eventually the hunter who is unconstrained in his moves would get to the same vertex as the mole. What determines the number of moves allowed to win, and if we increase the amount of possible moves, could a spider graph that is initially mole win become hunter win? Thanks again for your post. Now I want to eat lobster.
ReplyDeleteI think im right there with you Sam, the difference of Mole win vs Hunter win seems a bit confusing. I feel as if they two graphs are one in the same in some ways as they both share some characteristics, but I think the main difference is the fact that the Mole win graph contains spots that repeat in sequence. Not sure as to why that is still however but im sure itll make alot more sense after todays presentation.
DeleteGreat post and presentation Sam! I really liked all the visuals. After playing around in class I was curious if there was any strategy the mole could follow to be a "genius" mole? We kept saying the mole was a genius but when I played the mole I don't quite think I did the genius part justice haha
ReplyDeleteIn this context, I think that the mole being a genius simply means the mole not only knows where the hunter is going to go next, but where the hunter is going to go on every single move till the end of the game. Somewhat difficult when actually playing 1v1 with a piece of paper, but possible in theory. Still, giving such an advantage to the mole will not save him if the game is played on a lobster, assuming the hunter plays perfectly.
DeleteYep, Bayard is right! One way to imitate this prescient mole is for the hunter to announce his upcoming move out loud BEFORE the mole commits to his move. This simulates giving the mole future information so he never makes the wrong move.
DeleteThis is an excellent post Sam. And you did a great presentation in class too! I feel the material makes more sense to me, especially the hunter-win type graph, when you go over some examples in class and we actually play several rounds with our classmates! However, I'm a little bit confused about the mole-win type of graph. The spider graph you mentioned earlier, let's say the hunter is at b_1 and the mole is either at b_2 or b_3, then the hunter can just wait at b_1 to catch the mole since the mole always has to move, is it right? Or is there a rule-change or a different way when looking at the mole-win type of graph?
ReplyDeleteSam, I am so glad we got to play Hunter vs Mole in class. I was curious as to how two players could play this game with imperfect information... I was anticipating something like Battleship. I wasn't too far off! The hunter doesn't know the mole's location until the mole is captured.
ReplyDeleteMy presentation tomorrow will focus on another version of cops and robbers with imperfect information: Cops, Robbers and Alarms. The logistics of the game are pretty similar; however, the cop receives some information regarding the robber's location. Stay tuned!!
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteHi Sam, great post and presentation. I think playing the game in class was really helpful in understanding a little bit more how the games. We played with the Lobster set up of the game, so it was easier for the hunter to catch the mole, and it was easy to apply the strategy that you discussed in your presentation. However, I think it would have be interesting to also play with a game set up that wasn't a lobster. Overall, I really enjoyed this presentation!
ReplyDeleteGood suggestion, Dani. We ended up seeing that the lobster was hunter-win, but we never saw the other half of the theorem: that any graph that isn't a lobster is mole-win. Hopefully that started to become a little more clear when everyone was playing on non-lobster graphs (like cycles or things containing the 3-legged spider). But to really understand why the mole can always win on anything that isn't a lobster, we'd want to look at something called finite state diagrams. You can learn more about these in both of the links that Sam provided in his references!
Delete