使用 Alpha-Beta 修剪在 MinMax 中实现树
Tree Implementation in MinMax with Alpha-Beta Pruning
我想为类似跳棋的游戏实现 AI(人工智能)
我写了以下方法:
-方法
public List<Move> allMoves(){
...
}
那个returns我是所有有效动作的列表,按权重排序,其中权重是根据动作的种类和位置计算的
-方法
public int apply(Move m){
...
}
将移动应用到棋盘上,returns 1 如果一些棋子已被杀死
-方法
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)
但我还不明白如何使它适应我的问题。'
有人可以帮助我吗?
编辑
我有这个 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
是特定的。你可以找到完整的代码here。它不是超级优化,因为试图使其尽可能可读
添加:所以删除current
,因为它不是真正需要的。为搜索添加两个参数window并添加剪枝:
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;
最后你需要用最大化window调用算法:
minimax(board, 3, true, Integer.MinInt, Integer.MaxInt);
...意味着它的最大值。玩家轮流以最差值开始 (Integer.MinInt
)
我想为类似跳棋的游戏实现 AI(人工智能)
我写了以下方法:
-方法
public List<Move> allMoves(){
...
}
那个returns我是所有有效动作的列表,按权重排序,其中权重是根据动作的种类和位置计算的
-方法
public int apply(Move m){
...
}
将移动应用到棋盘上,returns 1 如果一些棋子已被杀死
-方法
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)
但我还不明白如何使它适应我的问题。' 有人可以帮助我吗?
编辑
我有这个 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
是特定的。你可以找到完整的代码here。它不是超级优化,因为试图使其尽可能可读
添加:所以删除current
,因为它不是真正需要的。为搜索添加两个参数window并添加剪枝:
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;
最后你需要用最大化window调用算法:
minimax(board, 3, true, Integer.MinInt, Integer.MaxInt);
...意味着它的最大值。玩家轮流以最差值开始 (Integer.MinInt
)