beta修剪产生错误的结果
我试图用alpha beta修剪实现抽象minimax算法。 minimax部分很好，但只要我添加alpha beta修剪，内联就开始表现得很愚蠢，甚至跳过明显的动作。 我不确定发生了什么事。
这是我的递归函数的样子：
- (id<MMGameMove>)getBestMove:(id<MMGame>)game player:(MMPlayerSeed)player depth:(NSInteger)depth alpha:(NSInteger)alpha beta:(NSInteger)beta
{
id<MMGameMove> bestMove = nil;
NSArray *allMoves = [game allMoves];
for (id<MMGameMove> move in allMoves)
{
//Take the move and evaluate the game's score
id<MMGame> gameBoard = [game clone];
move.player = player;
[gameBoard saveMove:move];
self.count++;
if (depth == 0 || gameBoard.isOver)
{
move.rank = [gameBoard scoreForPlayer:self.playerId depth:depth];
}
else
{
MMPlayerSeed opponent = (player == self.playerId) ? self.opponentId : self.playerId;
move.rank = [self getBestMove:gameBoard player:opponent depth:depth-1 alpha:alpha beta:beta].rank;
}
//If the new move is better than our previous move, take it
BOOL minMove = (player == self.opponentId && move.rank <= beta);
BOOL maxMove = (player == self.playerId && move.rank >= alpha);
if (minMove || maxMove)
{
BOOL shouldPrune = NO;
if (minMove)
{
beta = move.rank;
if (alpha >= beta) {
shouldPrune = YES;
}
}
else if (maxMove)
{
alpha = move.rank;
if (alpha <= beta) {
shouldPrune = YES;
}
}
bestMove = move;
if (shouldPrune && depth < self.maxDepth) {
break;
}
}
}
return bestMove;
}
我最初的电话是这样的：
[self getBestMove:game player:self.playerId depth:self.maxDepth alpha:INT_MIN beta:INT_MAX];
据我所知，对于相同的游戏状态，alpha-beta修剪应该给予与minimax没有的修改相同的举动，但是在这种实现中，显然不是这种情况。
编辑1
在建议的修改之后，出现了另一个错误，那就是我正在修剪根节点。 我编辑了代码以反映正确的答案。 在完成这个并且运行两个minimax以及不使用alpha-beta修剪的情况下，我现在可以看到，两者都产生了相同的结果，并且我能够检查您从alpha beta增加中获得的更好性能。
编辑2
上面贴出的代码实际上并不像预期的那样工作。 我遵循xXliolauXx的建议，但我仍然无法正常工作。 我在深度= 0或游戏结束时获得了正确的值，但似乎它们不是递归地传递回相应的根移动。 例如，我可以看到，我的启发式为第一个根移动的孩子返回-3，其余孩子为0。 所以我期望第一个根移动报告-3而不是0，因为这是计算机可能发现的最糟糕的情况，如果它这样做的话。
这是我的新代码：
- (NSInteger)alphabeta:(id<MMGame>)game player:(MMPlayerSeed)player depth:(NSInteger)depth alpha:(NSInteger)alpha beta:(NSInteger)beta
{
if (depth == 0 || game.isOver)
{
return [game scoreForPlayer:self.playerId depth:depth];
}
MMPlayerSeed opponent = (player == self.playerId) ? self.opponentId : self.playerId;
for (id<MMGameMove> move in game.allMoves)
{
id<MMGame> gameCopy = [game clone];
move.player = player;
[gameCopy saveMove:move];
self.count++;
NSInteger score = [self alphabeta:gameCopy player:opponent depth:depth-1 alpha:alpha beta:beta];
if (player == self.playerId)
{
if (depth == self.maxDepth)
{
move.rank = @(score);
[self.rootMoves addObject:move];
}
alpha = MAX(alpha, score);
if (beta < alpha)
{
break;
}
}
else
{
beta = MIN(beta, score);
if (beta < alpha)
{
break;
}
}
}
return (player == self.playerId) ? alpha : beta;
}
请注意，我在修改beta <alpha的同时最大化修剪。 否则，在扫描第一个根移动之后，它总是会剪掉。
这是我如何启动递归：
[self alphabeta:game player:self.playerId depth:self.maxDepth alpha:-INFINITY beta:INFINITY];
编辑3
我想我明白了。 我不是返回alpha或beta，而是返回最佳（或最差）分数。 我需要清理我的代码以使其更具可读性，但现在看起来如此：
- (NSInteger)alphabeta:(id<MMGame>)game player:(MMPlayerSeed)player depth:(NSInteger)depth alpha:(NSInteger)alpha beta:(NSInteger)beta
{
if (depth == 0 || game.isOver)
{
return [game scoreForPlayer:self.playerId depth:depth];
}
MMPlayerSeed opponent;
NSInteger bestScore;
if (player == self.playerId)
{
opponent = self.opponentId;
bestScore = -INFINITY;
}
else
{
opponent = self.playerId;
bestScore = INFINITY;
}
for (id<MMGameMove> move in game.allMoves)
{
id<MMGame> gameCopy = [game clone];
move.player = player;
[gameCopy saveMove:move];
self.count++;
NSInteger score = [self alphabeta:gameCopy player:opponent depth:depth-1 alpha:alpha beta:beta];
if (player == self.playerId)
{
bestScore = MAX(bestScore, score);
alpha = MAX(alpha, bestScore);
if (depth == self.maxDepth)
{
move.rank = @(score);
[self.rootMoves addObject:move];
}
if (beta < alpha)
{
break;
}
}
else
{
bestScore = MIN(bestScore, score);
beta = MIN(beta, bestScore);
if (beta < alpha)
{
break;
}
}
}
return bestScore;
}
这个错误似乎是在你修剪可能的部分（这是一个negamax-alpha beta的实现，而你正在使用minimax-alphabeta）。
要解决这个问题，只需添加一个if，不管你目前是最大化还是最小化（就像你在更改alpha或beta时所做的那样）。
当你最小化时，每当alpha> = beta时修剪，反之则最大化。
之后，代码应该正常工作（如果没有其他错误;））。
链接地址: http://www.djcxy.com/p/56345.html