Mouse and Cheese Game Design

Design a turn-based simulation game where two AI-controlled mice compete on a rectangular board to find a hidden piece of cheese. The board is a matrix of cells; some are walls, some are empty, and exactly one contains cheese. Each turn both mice (starting at fixed opposite corners) simultaneously attempt one move: up, down, left, or right. After moves are resolved, if either mouse occupies the cheese cell it scores 1 point, the round ends, and the cheese is relocated randomly to another empty cell. The match runs for a fixed number of rounds (say 1000) and the mouse with the higher score wins. You must implement the game runner, the board, and a pluggable AI interface. The AI for a mouse must decide its next move given only its current position and the Manhattan distance to the cheese (an integer); it does NOT receive the cheese coordinates, the board layout, or the opponent’s state. Design the system so new AI strategies can be added without changing existing code (Strategy pattern expected). Provide two sample AIs: one that moves randomly and one that greedily steps toward the cheese using the supplied distance. The runner enforces turn order, collision rules (two mice cannot occupy the same cell; if they try, neither moves), and boundary/wall constraints. After each move the runner checks for a winner of the round, updates scores, and respawns the cheese. Your solution should be extensible for additional mice, larger boards, or new AI heuristics.