0

我正在尝试实现 Negamax 搜索，以在 Java 中搜索名为Nine Men's Morris的游戏。

如果玩家连续拥有三个棋子（这里称为磨），他会在切换回合之前移除对手的棋子（“额外”移动）。

此外，在放置所有初始棋子之后，还有一个定位棋子阶段和一个移动棋子阶段。

我的实现如下所示：

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 };       
    }
}

可能建议不要更改基本的 Negamax 算法并将放置石头和移动石头封装在一个操作中，以便在算法本身中不区分两者，但根据我的理解，它应该仍然像这样工作。

函数 negamaxRemove 与 negamaxSet 基本相同，但不检查磨机（不可能）并寻找要移除的部件。

使用与调用函数相同的参数调用 negamaxRemove 并且不切换符号（从而再次最大化）是否正确？

不知何故，人工智能玩家并没有阻止对手形成一个磨坊（但如果可能的话，他自己形成一个）。

这样的算法是否正确，我应该在代码的其他地方查找错误？还是我误解了 Negamax 应该如何工作？（我注释掉了 alpha-beta 修剪，因此错误地设置 alpha 或 beta 在这里不会产生影响）

我真的很感激一些指示！

4

1 回答 1

0

我已经实现了这个游戏。将您对动作的定义从“执行动作，授予另一个动作”更改为“执行多部分动作”。然后，您不必进行 2 个“移动”，而最终得到的移动看起来像from: 3, to: 0, remove: 17,from: 3, to: 0, remove 19等。对于不删除棋子的移动，您只需将 remove 设置为-1。

于 2016-08-19T14:36:16.827 回答