我正在为国际象棋编写极大极小算法。
对于没有修剪的极大极小值和有修剪的极大极小值,我得到了不同的最终结果值。
我的伪代码如下。有人能帮我吗?
极大极小()
public int miniMax(int depth, Board b, boolean maxPlayer) {
if(depth == 0)
return evaluateBoard(b);
if(maxPlayer) {
int bestMoveVal = 0;
for( each Max player's moves) {
// make a move on a temp board
int eval = miniMax(depth - 1, tempBoard, false);
bestMoveVal = Math.max(bestMoveVal, eval);
}
return bestMoveVal;
}
else {
int bestMoveVal = 0;
for (each Min player's moves) {
// make a move on a temp board.
int eval = miniMax(depth - 1, tempBoard, true);
bestMoveVal = Math.max(bestMoveVal, eval);
}
return bestMoveVal;
}
}
alphabeta ()
public int alphabeta(int depth, Board b, int alpha, int beta, boolean maxPlayer) {
if(depth == 0)
return evaluateBoard(b);
if(maxPlayer) {
for(each max player's moves) {
// make a move on a temp board
int eval = alphabeta(depth - 1, temp, alpha, beta, false);
alpha = Math.max(alpha, eval);
if(beta <= alpha) //beta cut off;
break;
}
return alpha;
}
else {
for(each of min's moves) {
// make a move on a temp board
int eval = alphabeta(depth - 1, temp, alpha, beta, false);
beta = Math.min(beta, eval);
if(beta <= alpha)
break; // alpha cut off;
}
return beta;
}
}
Board表示a。对于每次移动,我在传递的Board对象的副本上移动,然后将这个临时Board传递给进一步的调用。
evaluateBoard(Board b)接收一个Board,并根据给定的Board场景计算一个分数。
代码中的一个大问题是alphabeta
不是递归的,而它应该是递归的。它叫miniMax
。
alphabeta
中的递归调用应该调用alphabeta
,否则从根本上是错误的。也就是说,在每个深度级别上都要进行修剪,而不仅仅是在顶层。
在minMax
函数中,bestMoveVal = Math.max(bestMoveVal, eval);
用于最小化和最大化玩家。