We had to program a board game using a 32-bit computer and Lisp in an Artificial Intelligence elective course I attended. Tic-tac-toe (5x5) was the easiest game to select, while checkers was the most difficult. We realized that most teams who choose checkers would not accomplish anything worthwhile in time due to the time limit, but tic-tac-toe was too basic, so we tried something in the center.
Nine Men’s Morris was the game we chose. It is made out of a twenty-four-point grid. Each player starts with nine pieces and must strive to form ‘mills’ (three pieces lined up horizontally or vertically) in order to eliminate an opponent’s pieces from the game until only two remain. The game features three stages in which the laws of movement change: in the first, the pieces can be put in any vacant spot; in the second, the pieces can only move to nearby locations; and in the third, the losing player (with just three pieces remaining) can ‘fly’ the pieces to any unoccupied position.
We utilized the Alpha-beta pruning algorithm, which performed well. For fun, we tried it against the one in the Assassin’s Creed game.