我想为一个类似跳棋的游戏实现一个AI（人工智能）
我已经编写了以下方法：
-方法
public List<Move> allMoves(){ ... }该方法返回所有有效移动的列表，按权重排序，其中权重是根据移动类型和位置计算的
-方法
public int apply(Move m){ ...}用于将移动应用到棋盘上，如果有棋子被吃掉则返回1
-方法
public void undo(){ ...}用于恢复棋盘的先前状态。
这是一个零和游戏，因此AI应该最大化玩家颜色的棋子数量，并最小化对手的棋子数量。
为此，最好的方法似乎是使用带有Alpha-Beta剪枝的MinMax算法。以下是其伪代码：
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 functionprivate Integer evaluateBoard(Board board, Color player) { return board.pawns(player) - board.pawns(player.other());}如何编辑以实现Alpha-Beta剪枝？
回答：
这是我过去编写的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是特定于游戏的。你可以在这里找到完整的代码这里。它不是超级优化的，因为我尽量使它尽可能易读
添加：所以移除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从不改变；所以你最好使用布尔值 for (Move m : board.getPossibleMoves(maximizingPlayer))) { board.apply(m); val = minimax(board, depth - 1, Boolean.FALSE, minPlayerBestVal, maxPlayerBestVal); // 在这里交换 bestValue = Math.max(bestValue, val); board.revert(m); if (bestValue >= minPlayerBestVal) // 对minPlayer来说太好了 return bestValue; // 因此在这里剪枝 } return bestValue;最后，你需要用一个最大化窗口来调用该算法：
minimax(board, 3, true, Integer.MinInt, Integer.MaxInt);… 这意味着这是最大化玩家的回合，他从最差的可能值（Integer.MinInt）开始
