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

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.