Heuristic/Evaluation Function for Nine Men’s Morris

Nine Men’s Morris is a two-player strategy board game. The game has three clearly delimited phases:

Phase 1: Placing pieces
Players alternatively place their pieces on the board. If a player closes a morris (or mill), she will grab one of her opponent’s piece. Strategically placing the pieces is more important than closing a morris in this phase.
Phase 2: Moving pieces
Players alternatively move their pieces one at a time to an adjacent empty point, close morrises and grab pieces.
Phase 3: Flying pieces
A player reaches phase 3 when she is left with only 3 pieces. She can now move any of her piece to any empty point on the board.

A player wins by reducing her opponent to two pieces, or by leaving her without a legal move.

Continue reading