用MinMax实现Alpha
我想为类似跳棋的游戏实施AI（人工智能）
我写了以下方法：
-方法
public List<Move> allMoves(){
...
}
它返回按重量排序的所有有效移动的列表，其中权重根据移动的种类和位置计算
-方法
public int apply(Move m){
...
}
如果某些棋子已经被杀死，则将棋子应用于棋盘并返回1
-方法
public void undo(){
...
}
恢复董事会以前的状态。
这是一个零和游戏，所以AI应该最大化玩家颜色的棋子并且尽量减少对手的棋子。
为此，最好的方法似乎是使用alpha-beta修剪的min-max。 这具有下面的伪码
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修剪？
这是我过去写的一个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 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 ）