Cat and Mice – Part 5: Really implementing the AI

In this blog series about Cat and Mice, I will discuss the whole process, from design to implementation, from publishing to artificial intelligence. Cat and Mice is a game that is played on a checkers board. One player plays the cat and has only one piece. The piece of this player starts at one side of the checker’s board. On the other side are four pieces of the mice. The goal for the cat is to reach the other side of the checker’s board. The goal for the mice is to prevent this. This fifth article will discuss the implementation of the move calculator for the computer.

About this blog series

This blog series will follow me along in the making of a simple game with Flutter. Not just the technical parts but also everything that happens around the implementation. I started off with a weekly series but after another Flutter project, I am back to finish the series.

  1. The Goal
  2. CI/CD
  3. The Architecture
  4. Implementing the Game
  5. Implementing the AI

Using a heuristic approach

In the last blog post, I have discussed the mini-max approach for the AI of the game. However, there were two problems. First, the computation time became too long. There are different ways to speed this up. However, due to the second problem, I decided to spend no time improving the computation time. The second problem is that if the mice player plays the game perfectly from the beginning, that player will always win the game. So, I have decided to go with a heuristic approach.

Implementation of the cat AI

For both the cat player and the mice player, there are two different difficulties. Let’s start with the normal difficulty of the cat player. The heuristic approach of the cat player is pretty straightforward. The cat player will move forward if possible. Otherwise, the cat player will move backward.

 MoveCommand computeMove(List<Checker> checkers) {
    final catChecker = checkers.firstWhere((element) => element.type == PlayerType.CAT);
    final possibleMoves = GameLogic.possibleMoves(catChecker, checkers);
    possibleMoves.shuffle();
    final movesForward = possibleMoves.where((element) => element.y < catChecker.coordinate.y).toList();
    if (movesForward.isNotEmpty) {
      return MoveCommand(catChecker.id, catChecker.coordinate, movesForward.first);
    }
    return MoveCommand(catChecker.id, catChecker.coordinate, possibleMoves.first);
  }

To make the AI a bit smarter, there are two things that can be improved. In this position, both moves are forward, but one can be defended by the mice and the other position not.

Two possible moves forward, one side is blocked by the mice, the other is not.

If the cat can move towards both forward positions, the ai will check if one of those is blocked or can be blocked by the mice. If not, the AI will choose that position. Otherwise, the AI will move towards the middle, since it is more dangerous to get trapped at the sides of the board.

MoveCommand computeMove(List<Checker> checkers) {
    final catChecker = checkers.firstWhere((element) => element.type == PlayerType.CAT);
    final possibleMoves = GameLogic.possibleMoves(catChecker, checkers);
    possibleMoves.shuffle();
    final movesForward = possibleMoves.where((element) => element.y < catChecker.coordinate.y).toList();
    if (movesForward.length == 2) {
      //check if any position is blocked by mice
      for (Coordinate move in movesForward) {
        if (!coordinateIsBlockedByMice(move, checkers)) {
          return MoveCommand(catChecker.id, catChecker.coordinate, move);
        }
      }
      return moveToTheMiddle(movesForward.first, movesForward.last, catChecker);
    }
    if (movesForward.isNotEmpty) {
      return MoveCommand(catChecker.id, catChecker.coordinate, movesForward.first);
    }
    if (possibleMoves.length == 2) {
      return moveToTheMiddle(possibleMoves.first, possibleMoves.last, catChecker);
    }
    return MoveCommand(catChecker.id, catChecker.coordinate, possibleMoves.first);
  }

Implementation of the mice AI

The implementation of the AI of the mice proved to be a bit more difficult. However, there is a simple move that can be played by the mice without danger. These are moves where the mice can move forward without creating a new gap. For example, during the game start, the upper left corner mice can move forward without creating a gap.

There are situations in which the mice cannot perform that move. This happens when the cat is in the position that was the next move that could happen. In this case, the checker that is the farthest away will move forward. There is one important situation that is missing, that I will solve in the hard difficulty. That is when a gap arises, due to the cat being in a position that is next for closing the gap. The hard difficulty mice will close the gap.

The smartest move for the mice is to close the gap

By closing the gap, the AI has already become pretty smart! However, it is possible to improve AI further. This can be done, by improving the option of moving the mice that are furthest away from the cat. This now moves randomly forward. If these mice would move towards the cat, the AI would become (almost?) impossible to beat, since the mice can enforce a win by playing the perfect moves. If you want to look at the implementation ( needs a bit more polishing), check the Github project!

In the next post, I will improve the UI/UX and add some sounds! This will be in two weeks (really this time). If you want to follow along, you can see my progress on the code on Github. 

Leave a Reply