用Alpha-Beta剪枝实现最小最大树

Question

我想为一个类似跳棋的游戏实现一个人工智能

我写了以下方法:

-方法

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

这将返回所有按重量排序的有效移动的列表，其中重量是根据移动的类型和位置计算的

-方法

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

将移动应用于棋盘，如果有棋子被杀则返回1

-方法

public void undo(){
     ...
}

以恢复板的先前状态。

这是一个零和游戏，所以人工智能应该最大化玩家颜色的棋子，最小化对手的棋子。

为此，最好的方法似乎是使用最小-最大和α-β修剪。这有以下伪码

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

如何编辑获取alpha beta修剪？

Answer 1

这是我过去写的一个alpha beta国际象棋程序的伪代码。嗯，跳棋或者象棋——这部分没有太大区别:

  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;

只有DynamateMoves、E价值定位和MoveForwards/返回是特定的。您可以在此处找到完整的代码。它不是超级优化的，因为它试图使其尽可能具有可读性

添加：因此删除当前，因为它不是真正需要的。为搜索窗口添加两个参数并添加修剪：

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）