0

JavaでNine Men's MorrisというゲームのNegamax検索を実装しようとしています。

プレーヤーが 3 つの駒を続けて持っている場合 (ここではミルと呼ばれます)、ターンを切り替える前に相手の駒を取り除きます (「追加の」移動)。

さらに、すべての最初の駒が配置された後、セット ピースフェーズとムーブ ピースフェーズがあります。

私の実装は次のようになります。

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

基本的なネガマックス アルゴリズムを変更せず、石の設定と石の移動を 1 つの操作でカプセル化して、アルゴリズム自体で 2 つを区別しないようにすることをお勧めしますが、私の理解では、それでもこのように機能するはずです。

関数 negamaxRemove は、基本的には negamaxSet と同じですが、ミル (不可能) をチェックせず、削除する部分を探しません。

呼び出し元の関数と同じパラメーターを使用して negamaxRemove を呼び出し、符号を切り替えない (それによって再び最大化する) のは正しいですか?

どういうわけか、AI プレイヤーは対戦相手がミルを形成するのを妨げません (ただし、可能であれば自分でミルを形成します)。

アルゴリズムはこのように正しいのでしょうか?コードの他の場所でエラーを探す必要がありますか? それとも、ネガマックスの仕組みを誤解したのでしょうか? (alpha-beta pruning をコメントアウトしたので、alpha または beta を間違って設定しても、ここでは違いはありません)

いくつかの指針を本当に感謝します！

4

1 に答える 1

0

このゲームを実装しました。移動の定義を「アクションを実行し、別の移動を与えられる」から「マルチパート アクションを実行する」に変更します。from: 3, to: 0, remove: 17次に、2 つの「移動」を行う代わりに、 、 などのように移動するだけです。from: 3, to: 0, remove 19ピースを削除しない移動については、削除を に設定するだけです-1。

于 2016-08-19T14:36:16.827 に答える