阿尔法-贝塔用一个愚蠢的举动修剪

Question

在学习了一段时间的alpha-beta修剪算法后，我决定编写一个简单的国际象棋程序。然而，当运行程序时，计算机决定做出一个愚蠢的举动。我不知道函数哪里写错了。

我必须修复什么才能使程序正常工作。

这是我的静态评估函数，其中m_turn是依次的边，m_xturn是尚未转向的边

int CChess::Evaluate()
{
int score = 0;
for (int r = 0; r < CHEIGHT; r++)
for (int c = 0; c < CWIDTH; c++)
if (m_color[r][c] == m_turn)
score += PIECE_VALUE[m_piece[r][c]];
else if (m_color[r][c] == m_xturn)
score -= PIECE_VALUE[m_piece[r][c]];
return score;
}

阿尔法-贝塔修剪功能：

int CChess::AlphaBeta(int depth, int alpha, int beta, bool isMaxPlayer)
{
if (depth == 0)
return Evaluate();
std::vector<CChessMove> move_list = GenMove();
size_t n = move_list.size();
if (isMaxPlayer)
{
for (size_t i = 0; i < n; i++)
{
CChessPiece piece = Move(move_list[i]);
int value = AlphaBeta(depth - 1, alpha, beta, false);
UnMove(move_list[i], piece);
if (value > alpha)
alpha = value;
if (alpha >= beta)
break;
}
return alpha;
}
for (size_t i = 0; i < n; i++)
{
CChessPiece piece = Move(move_list[i]);
int value = AlphaBeta(depth - 1, alpha, beta, true);
UnMove(move_list[i], piece);
if (value < beta)
beta = value;
if (alpha >= beta)
break;
}
return beta;
}

查找最佳移动的功能。

CChessMove CChess::ComputerThinks()
{
int best_value = -CCHESS_INFINITY;
CChessMove best_move = { {-1, -1}, {-1, -1 } };
std::vector<CChessMove> move_list = GenMove();
size_t n = move_list.size();
for (size_t i = 0; i < n; i++)
{
CChessPiece piece = Move(move_list[i]);
int value = AlphaBeta(CCHESS_DEPTH, -CCHESS_INFINITY, CCHESS_INFINITY, false);
UnMove(move_list[i], piece);
if (value > best_value)
{
best_value = value;
best_move = move_list[i];
}
}
return best_move;
}

Answer 1

这真正意味着你的引擎认为它找到了反驳。例如，也许它分析了深度1处的QxP。它会认为自己刚刚赢得了一枚棋子，这太棒了！但是，一个举动后，它意识到它将失去女王。即使在更高的深度，这也是一个问题——QxP引擎可能会导致一系列捕获，最终成为一个棋子，但事实上，在它没有看到的最后一次捕获时，它失去了一辆车。我建议像评论中其他人所建议的那样实现quiescence搜索，它会贯穿所有捕获，而不是直接评估。由于在给定位置上，与正常移动相比，捕获次数很少，因此这比尝试增加一些额外深度更便宜。

我还强烈建议将其放在Negamax框架中，而不是标准的Alpha Beta。它要简单得多。