Mill – the board game – including an AI using Alpha-beta pruning (Java)

mill board

General Description of Mill Game

Mill is a two person board game. The goal is to remove the stones of the enemy from the board while keeping once own stones on the board. This is done by producing a line of three stones by moving the stones across the board. If this is achieved, a stone of the enemy may be taken of the board. With this program it is possible to play against an artificial intelligence or against a real person. You may play with the standard rules, or try the advanced version in which diagonal moves are allowed as well. Also, the number of stones one starts with is adjustable, so you can decide to play a very short, or a long game.

Notes on code quality

The code base is the same as for the Connect4 game, which I do not think was a good choice (but it really was no choice as it is a university project and we were supposed to do it this way). In parts, the code is quite messy, this is mainly because the interfaces we received changed and we had to adapt the code in a very short time, and also because new requirements were added from time to time which also had to be added in a short time.
All in all, the code works, but it could use some refactoring.

Notes on Mill AI

The AI uses Alpha-beta pruning with iterative deepening (which allows to specify a time in which the ai must decide on a move). It also saves a list of moves that resulted in a cutoff in sibling nodes, as it is likely that these produce a cutoff as well.

Iterative deepening is used, but only to allow for a time limit. If the results were saved, it would allow for early cutoffs as well (which I might include in the future), but they are not at the moment, so iterative deepening produces an overhead.

The ai that is responsible for the moves is quite good, but the one that calculates the set moves at the beginning of a game is not (I am not that good of a mill player myself and was unsure as to what strategy to apply).

Alpha-beta pruning in a nutshell

Here is the general structure of the alpha beta algorithm, it is executed for every possible move the ai can take this turn.
The rating is an accumulation of ratings of the single moves, the heuristic for these ratings only includes mills and Catch22s (which already produces a good result). It is important that the rating is always from the point of view of the ai; if the ai closes a mill, a positive amount will be added to the current value, if the enemy does, a negative.
    public int alphaBeta(Node node, int depth, int alpha, int beta) {
        if (win()) {
            return playerWin ? winRating : -winRating;
        } else if (depth <= 0) {
            return nodeRating;

        List<Node> children = generateChildren(); // generates children. also rates them and applies move to copy of field.

        if (currentPlayer == ai) { // ai tries to maximize the score
            for (Node child : children) {
                alpha = Math.max(alpha, alphaBeta(child, depth - 1, alpha, beta));

                if (beta <= alpha) {
                    break; // cutoff
            return alpha;
        } else { // enemy tries to minimize the score
            for (Node child : children) {
                beta = Math.min(beta, alphaBeta(child, depth - 1, alpha, beta));
                if (beta <= alpha) {
                    break; // cutoff
            return beta;
The optimization over the MiniMax algorithm results from the early cutoffs (which eliminate parts of the tree).

the Wikipedia article on Alpha-Beta pruning explains this part quite nicely:
The algorithm maintains two values, alpha and beta, which represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively. Initially alpha is negative infinity and beta is positive infinity. As the recursion progresses the “window” becomes smaller. When beta becomes less than alpha, it means that the current position cannot be the result of best play by both players and hence need not be explored further.
So it is important to achieve cutoffs as early as possible. To do so, it is a good idea to always sort the children of a node, so that those which probably result in a cutoff are at the beginning of the list.

Screenshots Mill

Download Mill Game and Java Source Code

Mill Game [102.54 kB]

Mill Game Java Source Code [80.6 kB]


Thanks go out to fiv again, who designed the user interface, wrote the controller and also helped with the game logic as well as the ai.

4 thoughts on “Mill – the board game – including an AI using Alpha-beta pruning (Java)

  1. Mate i am going to make a game with MiniMax and AlphaBeta, as a dissertation for my univercity as well, i am trying to find implementation of the alphaBeta, though i found minimax from connect4 game, from your download i can see only jar files, if it is not a big deal for you, please senf me on my e-mail adress the whole game (implementation) or the implementation of the AlphaBeta only. Thank you.

  2. I added the mill source code to the post, sorry about that. Normally it is always included in the jar files, here I must have forgotten. I hope it helps and good luck on your project :)

  3. good day. Can i ask a favor? I’m having my project now in my subject in AI. I’m going to learn and present the Mill game because it has a nice approach in AI and uses alpha beta pruning. I downloaded the two files above and when I tried running it , the jar file in the “Mill Game” seems cool and really gives me what I want and thanks for that. I tried to study the code so I run the other file “Mill Game Java Source Code” in netBeans and it turns out not okay. I run the “” and it pop out different User interface compare to the jar file? the language also is not English, i think it is Russian. Can you help me for this? How can I get the source code that have user interface the same with the jar file? Looking forward for your reply. It is much appreciated :)

  4. @Clent: its german^^ the interfaces where given to us later in the development circle, thats where the mix-up comes from. I seem to have misplaced my earlier (english) interfaces, so I am afraid that I cannot help you. But most of the comments are not really relevant as the method names are self-descriptive.
    Just a couple of thinks regarding the Playerinterface:
    In Mill, you have different kinds of moves. You have the “set” moves in the first phase (when both players place their stones on the mill board) and then you have the normal moves in the second phase (when players move their stones that are on the board from phase 1). In addition players can do “remove” moves in case they created a mill. Thats what the three methods getNextSetMove, getNextMove, and getRemoveMove do respectively.
    I think the other interfaces should be clear in context, but if you have any specific questions please fell free to ask.

Leave a Reply

Your email address will not be published.