search implementation not working when player can move twice in a row
I'm trying to implement Negamax search for a game called Nine Men's Morris in Java.
If a player has three pieces in a row (here called a mill), he removes a opponent's piece (the 'additional' move) before switching turns.
Additionally, there is a set piece phase and a move piece phase, after all initial pieces have been placed.
My implementation looks like this:
public int[] negamaxSet(int depth, int alpha, int beta, int color) {
if (depth == 0 || board.isGameOver()) {
return new int[] { color * evaluateBoard(color};
}
int stonesSet = color == -1 ? board.blackStonesSet : board.whiteStonesSet;
// set piece phase
if (stonesSet < Game.initialPieces) {
List<Piece> moves = board.getEmpty();
int bestValue = Integer.MIN_VALUE;
int bestMoveX = -1;
int bestMoveY = -1;
for (Piece piece : moves) {
Piece move = new Piece(color, piece.x, piece.y);
board.setPiece(move);
int value[] = null;
//Player made Mill, move again
if(board.checkMill(move)){
value = negamaxRemove(depth - 1, alpha, beta, color);
}
//normal move, switch turn
else {
value = negamaxSet(depth - 1, -beta, -alpha, -color);
value[0] = -value[0];
}
if (value[0] > bestValue) {
bestValue = value[0];
bestMoveX = move.x;
bestMoveY = move.y;
}
if (value[0] > alpha) {
alpha = value[0];
}
board.revertLastMove();
// if (alpha >= beta)
// break;
}
return new int[] { bestValue, bestMoveX, bestMoveY };
} else {
//move phase
List<Piece> moves = board.getPiecesByColor(color);
int bestValue = Integer.MIN_VALUE;
int bestMoveX = -1;
int bestMoveY = -1;
int bestMoveX2 = -1;
int bestMoveY2 = -1;
for (Piece piece : moves) {
List<Piece> adjPieces = board.getAdjacentEmtpy(piece);
for(Piece adjPiece : adjPieces){
Piece newFrom = new Piece(color, piece.x, piece.y);
Piece newTo = new Piece(color, adjPiece.x, adjPiece.y);
board.movePiece(newFrom, newTo);
int[] value = null;
//Player made Mill, move again
if(board.checkMill(newTo, false)){
value = negamaxRemove(depth - 1, alpha, beta, color);
} else {
value = negamaxSet(depth - 1, -beta, -alpha, -color);
value[0] = -value[0];
}
if (value[0] > bestValue) {
bestValue = value[0];
bestMoveX = newFrom.x;
bestMoveY = newFrom.y;
bestMoveX2 = newTo.x;
bestMoveY2 = newTo.y;
}
if (value[0] > alpha) {
alpha = value[0];
}
board.revertLastMove();
// if (alpha >= beta)
// break;
}
}
return new int[] { bestValue, bestMoveX, bestMoveY, bestMoveX2, bestMoveY2 };
}
}
It is probably advisable to not change the basic Negamax algorithm and encapsulate setting a stone and moving a stone in one operation to not distinguish between the two in the algorithm itself, but from my understanding it should still work like this.
The function negamaxRemove is basically the same as negamaxSet but without checking for a mill (not possible) and looking for a piece to remove.
Is it correct to call negamaxRemove with the same parameters as the calling function and not switching the sign (thereby maximizing again)?
Somehow the AI player does not prevent the opponent from forming a mill (but forms one himself if possible).
Is the algorithm correct like this and I should look for the error elsewhere in the code? Or did I misinterpreted how Negamax should work? (I commented out alpha-beta pruning so setting alpha or beta wrongly wouldn't make a difference here)
I would really appreciate some pointers!
I've implemented this game. Change your definition of a move from "performs action, awarded another move" to "performs multipart action". Then instead of having to make 2 "moves", you just end up with moves looking like from: 3, to: 0, remove: 17 , from: 3, to: 0, remove 19 , etc. For moves that do not remove a piece, you simply set remove to -1 .
上一篇: 双人棋盘游戏的Quiscence搜索实现