The AI uses the Minimax algorithm with Alpha-Beta pruning.
*Rules The board consists of a grid with twenty-four intersections or points. Each player has nine pieces, or "men", usually coloured black and white. Players try to form 'mills'—three of their own men lined horizontally or vertically—allowing a player to remove an opponent's man from the game. A player wins by reducing the opponent to two pieces (where they could no longer form mills and thus be unable to win), or by leaving them without a legal move.
*The game proceeds in three phases:
Placing men on vacant points Moving men to adjacent points (optional phase) Moving men to any vacant point when the player has been reduced to three men
*Phase 1: Placing pieces
Nine men's morris starts on an empty board. The game begins with an empty board. The players determine who plays first, then take turns placing their men one per play on empty points. If a player is able to place three of their pieces on contiguous points in a straight line, vertically or horizontally, they have formed a mill and may remove one of their opponent's pieces from the board and the game, with the caveat that a piece in an opponent's mill can only be removed if no other pieces are available. After all men have been placed, phase two begins.
*Phase 2: Moving pieces
Players continue to alternate moves, this time moving a man to an adjacent point. A piece may not "jump" another piece. Players continue to try to form mills and remove their opponent's pieces as in phase one. A player can "break" a mill by moving one of his pieces out of an existing mill, then moving it back to form the same mill a second time (or any number of times), each time removing one of his opponent's men. The act of removing an opponent's man is sometimes called "pounding" the opponent. When one player has been reduced to three men, phase three begins.
*Phase 3: "Flying"
When a player is reduced to three pieces, there is no longer a limitation on that player of moving to only adjacent points: The player's men may "fly" (or "hop",[4][5] or "jump"[6]) from any point to any vacant point.
Some rules sources say this is the way the game is played,[5][6] some treat it as a variation,[4][7][8][9] and some do not mention it at all.[10] A 19th-century games manual calls this the "truly rustic mode of playing the game".[4] Flying was introduced to compensate when the weaker side is one man away from losing the game.
*Strategy
At the beginning of the game, it is more important to place pieces in versatile locations rather than to try to form mills immediately and make the mistake of concentrating one's pieces in one area of the board.[11] An ideal position, which typically results in a win, allows a player to shuttle one piece back and forth between two mills, removing a piece every turn.
FEUP - IART 2018/2019
group 59
António Costa
Luis Oliveira
Ricardo Silva