Programming & Problem Solving

Cats & Dogs

"Cats & Dogs" is a two-player board game similar to "Three Musketeers" and based on the gaming principle of unequal forces: the two players move by different rules and have different conditions for winning.

The board is a 7-by-7 grid in which the four corners and center square are all initially occupied by Cats, and the remaining squares are initially occupied by Dogs.

The Cat player moves first. It can move one of the Cats to any orthogonally (non-diagonal) adjacent space occupied by a Dog, which is then removed from the board. Poor doggie.

The Dog player moves next. It can move one of the Dogs to any orthogonally adjacent unoccupied space. The Dog player then moves again; it is okay to move the first Dog back to its original spot.

The Dog player wins if it can force three or more of the Cats to all be in the same row or same column. The Cat player wins if no Cat can move because there are no orthogonally adjacent squares occupied by a Dog (assuming there are no rows or columns containing three or more Cats).

In this project, you will implement strategies for both the Cat and Dog players; we will decide as a group which one to start with.

Although you are free to use any approach you like, of course, you should at least be aware of (if not familiar with) the "minimax" game playing strategy, which is typically taught in AI courses and involves looking ahead at possible board states based on the current game state. Depending on how far ahead you look, it may take a very long time for a player to decide on its next move. To make gameplay tractable, there is currently a time limit of 5 seconds on each player's move, but we can change that if necessary.