Finding an Algorithm for the HAPPY-CAT problem

Question

I'm trying to develop an the algorithm for the problem:

The cat-and-mouse game is played by two players, “Cat” and “Mouse,” on an arbitrary undirected graph. At a given point, each player occupies a node of the graph. The players take turns moving to a node adjacent to the one that they currently occupy. A special node of the graph is called “Hole.” Cat wins if the two players ever occupy the same node. Mouse wins if it reaches the Hole before the preceding happens. The game is a draw if a situation repeats (i.e., the two players simultaneously occupy positions that they simultaneously occupied previously, and it is the same player’s turn to move).

In other words, we have to decide: HAPPY-CAT = {<G, c, m, h> | G, c, m, h are respectively a graph, and positions of the Cat, Mouse, and Hole, such that Cat has a winning strategy if Cat moves first}.

I came across this algorithm:

1. Mark all nodes (a, a, x) where a is a node in G, and x is turn {cat, mouse} for whoever goes next.
2. If for a node u = (a, b, cat), there is a node v = (c, b, mouse) which is marked and (u, v) is an edge then mark u.
3. If for a node u = (a, b, mouse), all nodes v = (a, c, cat) are marked and (u, v) is an edge then mark u.
4. Repeat steps 2 and 3 until no new nodes are marked.
5. Accept if start node s = (c, m, cat) is marked.

But I'm having difficulty envisioning the first step. For example, in the picture below (where cat starts at 1, mouse starts at 5, and the hole is at 10), cat wins at vertex 4 in two ways:

1. c -> 12, m -> 4, c -> 6, m -> 2, c -> 4, m -> 4
2. c -> 12, m -> 4, c -> 3, m -> 2, c -> 12, m -> 4, c -> 4

So then at step 1 of the algorithm, would node 4 in our new marked set contain (4, 4, cat) or (4, 4, mouse)?

Answer 1

Alike kotu in the comments, I do not fully understand what you want to achieve with your algorithm, but I'm sure that when playing the game you must assume perfect play, and thus the mouse will win in your example by simply moving to the hole.

Determining the game's outcome is not so trivial, so here are my observations:

Proposition 1: If the cat reaches the hole before the mouse, the game is not won for the mouse.

Proof: By a simple case distinction. If the cat is on the hole and the cat has to move, do one of the following: If the mouse is adjacent to the cat, catch it. Otherwise, move somewhere else. If the cat is adjacent to the hole and the cat has to move, move onto the hole.

Note, that the mouse cannot 'sneak by' while the cat is away, that's an easy exercise. This gives that the game is only lost for the cat whenever the mouse is too quick and we can proceed in analysing only drawn or winning scenarios.

Proposition 2: If the graph contains a cycle of proper length at least 5 (i.e. no chords, etc.) and the mouse can reach the cycle before the cat, the game is not won for the cat.

Proof idea: If the mouse is on the cycle and the cat is as well, the mouse can always 'run away' from the cat. If the cat is not on the cycle, then the mouse can keep its distance by strategically moving along the cycle.

This gives us quite a strong criterion on when the game is drawn. So in the following, we can assume that there is no proper 5 cycle that the mouse can reach without getting caught. However, proper 4 cycles are relatively hard to handle.

Proposition 3: If the mouse cannot reach any proper 4 cycle, then the cat will win.

Proof idea: Such a reachability graph only contains areas of triangles and simple paths between them (shrinking these areas gives a tree). In an area of triangles the cat can always catch the mouse. Inbetween areas the cat can chase the mouse. By induction, such a game is won for the cat.

This leaves us with the issue of proper 4 cycles occurring in the reachability graph.

Proposition 4: If the graph contains a cylce of proper length at least 4, the mouse and the cat are opposing each other, the cat has to move and there is no way for the cat to triangulate (cf. chess endgames), it's a draw.

Proposition 5: If in the above situation the cat can triangulate(*), the mouse needs to leave the cycle, or it will loose.

You can visualize these two propositions by drawing a square (4 vertices, 4 edges as cyle) and extending it with triangles that share 1 edge and 2 vertices with the square each. The drawn graphs are the square without attached triangles, the square with 4 attached triangles and the square with 2 attached triangles on opposite sides.

(*) The cat cannot triangulate if by doing so it let's the mouse sneak by. It also isn't able to 'triangulate' if the mouse can do so as well.

This way, you can determine for each proper 4 cycle, if it's a drawn or lost cycle for the mouse. We can focus on the games in which between the cat and the mouse there are no cycles but proper 3 cycles and lost proper 4 cycles. However, in such a graph the same argument as above holds and it's lost for the mouse.