Mühle explained

“Mühle” is a turn-based board game in which two players face off against each other and try to eliminate the opposing pieces until only two are left. The first player receives the white pieces and can start, while the second player gets the black pieces, respectively.

Setup phase

The players take turns placing down nine of their pieces on any free crossing or corner.

Move phase

Pieces can be moved over the marked lines, if the next crossing or corner isn’t already occupied. Whenever three pieces are in line horizontally or vertically, a mill has been created. Now that player can remove one piece of the opponent.

End phase

If a player has only three pieces left, they are not restricted to moving only in single steps on the board, but can instead jump around to any free spot.

Win phase

The player loses, if they have just 2 pieces left, or they cannot make any move.

extra: When creating two mills at the same time, only one piece can be taken. A piece normally cannot be taken out of an existing mill, but if all pieces are part of mills, this rule does not apply anymore.

Description

You can play against someone else locally, against my AI in 3-difficulties and even watch how two AI’s play against each another. Good luck!

AI explained

The AI is using a minimax algorithm with alpha-beta-pruning and a simple evaluation function to determine the best next move.

Minimax

The algorithm simply tries to maximize the score for itself and minimize it for the opponent. By introducing depth, the algorithm can try a couple of moves and only then evaluate the out coming score, to come to a better result. The easy difficulty restricts this algorithm to the basic form without any depth; the medium difficulty has a maximum depth of 6, and the hard difficulty only has a time restriction of exactly one second and no depth restriction. On average, the depth of the hard-AI reaches between 9 and 12.

Evaluation

When comparing multiple possible moves, the algorithm has to tell if one move is better than another. The evaluation function can do just that, giving a score to any board. A high positive score, indicates that white is in a better position and a high negative score does the same but for black. The function only considers the token counts and the possible moves.

Data structure

The board with all its pieces is saved in one u64. A white piece is 0b11, black piece 0b10 and an empty piece 0b00. By having 24 positions, we can save the pieces in 48 bits total. Through easy bit manipulation, we can move and count pieces. Because we have 16 free bits and the slowest functions are counting all pieces and the total possible move count, we save the piece count and possible move count in those 16 bits. More on the data structure can be seen in src/core/position.rs

Download

Use the browser version for simplicity. If you want to benchmark and test how deep the minimax algorithm goes, run it locally with cargo.