What is a good algorithm to trap the cat in the game “circle the cat”?

I did the cat algorithm based on Breadth-First Search - BFS (because I read about it in another topic here). But now I would like to know if there is a good strategy to CATCH the cat.

For those who do not know, the game is this:
Game Circle the Cat

1 Answer

Nice game. I hadn't seen it before today. I played it for a while, and I've tried to document my algorithm if I was going to code it... Disclaimer: these are just my ideas, while I'm away from my computer, no mathematical proofs that it works or anything like that.

I wanted to start by giving values to each square (I know they're not square-shaped, I'm using 'square' to mean each position in the board). These values will help to indicate which might be the best choice for the cat. For each of the following steps, ignore squares that have been filled in.

Firstly, allocate a DistanceToWin value for each square showing how far to the edge of the board, as follows...

1. Give each square next to the edge of the board a DistanceToWin value of 1.
2. Each square adjacent to a 1 gets a value of 2; next to a 2 gets a 3; etc. Keep going until no new values are set. Notice that some squares may not have values set: these have no route to the edge, so if the cat is on one of these squares, it is trapped, and sooner or later, you are going to win.

Now we need to give an indication of HowManyRoutes are possible for each square, as follows... (this could be done at the same time as the assigning of DistanceToWin)

1. Each square with DistanceToWin=1 gets a HowManyRoutes value of 2. (My thinking here is that this represents that the escape cannot be blocked: one more step, and you can't block two routes in one turn.)
2. Every other square with a DistanceToWin value has HowManyRoutes set to the sum of HowManyRoutes of the neighbours with a smaller DistanceToWin value.

The square which is the best choice for the cat is the square neighbouring the cat's square which has the highest value of HowManyRoutes divided by DistanceToWin (which I will call Score). If the Score is >= 2, then the cat can/should escape. Each time a square is filled, these values need recalculating across the whole board, unless you feel like working out which squares are impacted.

The algorithm to trap the cat seems to fall into 3 categories:

1. The cat is encircled (DistanceToWin is not set for the cat's square), and just needs to be finally trapped.
2. The cat's best escape route needs to be blocked this move (the best Score of a cat's neighbour=1, and the worst Score of any next step on that route is >1)
3. The cat has loads of escape routes, and you need to limit its options.

For category 1, I'd suggest filling any square next to the cat.

Category 2, fill the square which needs filling.

Category 3: fill in a square which reduces the total Score for the whole board by the largest amount.