樹的實現在MINMAX與α-β剪枝

Question

我想要實現的AI（人工智能）的跳棋類遊戲

我已經寫了如下方法：

-the方法

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

返回我所有按重量排序的有效移動列表，其中根據移動的類型和位置計算權重

- 方法

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

應用移動登機，並返回1，如果一些典當行已被殺害

-the方法

public void undo(){ 
    ... 
} 

恢復板的以前的狀態。

這是一個零和遊戲，所以AI應該最大化玩家顏色的棋子，並儘量減少對手的棋子。

爲此，最好的方法似乎使用最小 - 最大與alpha-beta修剪。 這有後續的僞代碼

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) 

但我不明白如何將這個適應我的問題。」 有人可以幫助我嗎？

編輯

我有這個極小極大，但未經修剪

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

如何編輯獲得α+β剪枝？

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; 

只有GenerateMoves，EvaluatePosition和MoveForward/Back是特定的。你可以找到完整的代碼here。這不是超級優化，因爲試圖使它儘可能地易讀

添加：所以刪除current，因爲它是不是真的需要。添加兩個參數的搜索窗口，並添加修剪：

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）