2

チェッカーのようなゲームに AI (人工知能) を実装したい

私は次のメソッドを書きました：

-方法

   public List<Move> allMoves(){
       ...
    }

これは、重みでソートされたすべての有効な動きのリストを返します。重みは、動きの種類と位置に従って計算されます

-方法

public int apply(Move m){
       ...
}

移動をボードに適用し、ポーンが殺された場合は 1 を返します

-方法

public void undo(){
     ...
}

ボードの以前の状態を復元します。

これはゼロサム ゲームであるため、AI はプレイヤーの色のポーンを最大化し、対戦相手のポーンを最小化する必要があります。

このための最良の方法は、アルファベータ剪定で最小最大を使用するようです。これには次の疑似コードがあります

function alphabeta(node, depth, α, β, maximizingPlayer)

           if depth = 0 or node is a terminal node
                return the heuristic value of node
            if maximizingPlayer
                v := -∞
                for each child of node
                    v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
                    α := max(α, v)
                    if β ≤ α
                        break (* β cut-off *)
                return v
            else
                v := ∞
                for each child of node
                    v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
                    β := min(β, v)
                    if β ≤ α
                        break (* α cut-off *)
                return v

    (* Initial call *)
    alphabeta(origin, depth, -∞, +∞, TRUE)

しかし、これを自分の問題に適応させる方法がわかりません。誰かが私を助けることができますか？

編集

私はこのMinMaxを持っていますが、刈り込みはありません

private Integer minimax(Board board, Integer depth, Color current, Boolean maximizingPlayer) {
    Integer bestValue;
    if (0 == depth)
        return ((current == selfColor) ? 1 : -1) * this.evaluateBoard(board, current);

    Integer val;
    if (maximizingPlayer) {
        bestValue = -INF;
        for (Move m : board.getPossibleMoves(current)) {
            board.apply(m);
            val = minimax(board, depth - 1, current, Boolean.FALSE);
            bestValue = Math.max(bestValue, val);
            board.revert(m);
        }
        return bestValue;
    } else {
        bestValue = INF;
        for (Move m : board.getPossibleMoves(current)) {
            board.apply(m);
            val = minimax(board, depth - 1, current, Boolean.TRUE);
            bestValue = Math.min(bestValue, val);
            board.revert(m);
        }
        return bestValue;
    }
}

the evaluate function

private Integer evaluateBoard(Board board, Color player) {
    return board.pawns(player) - board.pawns(player.other());
}

アルファ ベータ プルーニングを取得するために編集する方法は?

4

1 に答える 1

2

これは、私が過去に書いたアルファ ベータ チェス プログラムの疑似コードです。まあ、チェッカーでもチェスでも - この部分に大きな違いはありません。

  Const White      =      1;
        Black      =     -1;

        MaxInteger =  32767;
        MinInteger = -32768;

  Function AlphaBeta (Color, Alpha, Beta, 
                             Depth, MaxDepth : Integer) : Integer; 
  var Value : Integer;

  begin
    if Depth = MaxDepth then 
       AlphaBeta := EvaluatePosition (Color)

    end else
    begin
       GenerateMoves(Color, MoveList);

       For Each Move in MoveList do
       begin
           MoveForward (Move);

               Value := AlphaBeta (-Color, Beta, Alpha,
                                           Depth +1, MaxDepth);

               if Color = White then
                  if Value > Alpha then Alpha := Value;

               if Color = Black then
                  if Value < Alpha then Alpha := Value;

           MoveBack (Move);

               if Color = White then
                  if Alpha >= Beta then Return Alpha;

               if Color = Black then
                  if Alpha <= Beta then Return Alpha;
       end;

       AlphaBeta := Alpha;
    end;
  end;

GenerateMoves、EvaluatePositionおよびMoveForward/のみBackが固有です。完全なコードはここにあります。できるだけ読みやすくしようとしたため、最適化されていません

addedcurrent :実際には必要ないので削除検索ウィンドウに 2 つのパラメーターを追加し、プルーニングを追加します。

private Integer minimax(Board board, Integer depth, Boolean maximizingPlayer, 
                        Integer maxPlayerBestVal, Integer minPlayerBestVal) {
    Integer bestValue;
    if (0 == depth)
        return this.evaluateBoard(board);

    Integer val;
    if (maximizingPlayer) {
        bestValue = -INF;
        // current never changed in your case; so you better use the bool
        for (Move m : board.getPossibleMoves(maximizingPlayer))) {
            board.apply(m);
            val = minimax(board, depth - 1, Boolean.FALSE, 
                          minPlayerBestVal, maxPlayerBestVal); // swap here 
            bestValue = Math.max(bestValue, val);
            board.revert(m);
            if (bestValue >= minPlayerBestVal) // too good for the minPlayer
                return bestValue;              // so cut here (pruning)
        }
        return bestValue;

最後に、最大化されたウィンドウでアルゴリズムを呼び出す必要があります。

minimax(board, 3, true, Integer.MinInt, Integer.MaxInt);

...その最大を意味します。可能な限り最悪の値から始めるプレーヤーのターン ( Integer.MinInt)

于 2015-02-11T21:47:51.723 に答える