具有 alpha beta 算法的国际象棋 AI
Chess AI with alpha beta algorithm
我已经为我的国际象棋游戏实现了 alpha beta 算法,但是它需要很多时间(4 层的分钟)才能最终做出一个相当愚蠢的举动。
2 天来我一直在努力寻找错误(我想我犯了一个错误),非常感谢对我的代码提供一些外部输入。
getMove 函数:为根节点调用,它为它的所有子节点(可能的移动)调用 alphaBeta 函数,然后选择得分最高的移动。
Move AIPlayer::getMove(Board b, MoveGenerator& gen)
{
// defined constants: ALPHA=-20000 and BETA= 20000
int alpha = ALPHA;
Board bTemp(false); // test Board
Move BestMov;
int i = -1; int temp;
int len = gen.moves.getLength(); // moves is a linked list holding all legal moves
BoardCounter++; // private attribute of AIPlayer object, counts analyzed boards
Move mTemp; // mTemp is used to apply the nextmove in the list to the temporary test Board
gen.mouvements.Begin(); // sets the list counter to the first element in the list
while (++i < len && alpha < BETA){
mTemp = gen.moves.nextElement();
bTemp.cloneBoard(b);
bTemp.applyMove(mTemp);
temp = MAX(alpha, alphaBeta(bTemp, alpha, BETA, depth, MIN_NODE));
if (temp > alpha){
alpha = temp;
BestMov = mTemp;
}
}
return BestMov;
}
alphaBeta 函数:
int AIPlayer::alphaBeta(Board b, int alpha, int beta, char depth, bool nodeType)
{
Move m;
b.changeSide();
compteurBoards++;
MoveGenerator genMoves(b); // when the constructor is given a board, it automatically generates possible moves
// the Board object has a player attribute that holds the current player
if (genMoves.checkMate(b, b.getSide(), moves)){ // if the current player is in checkmate
return 100000;
}
else if (genMoves.checkMate(b, ((b.getSide() == BLACK) ? BLACK : WHITE), moves)){ // if the other player is in checkmate
return -100000;
}
else if (!depth){
return b.evaluateBoard(nodeType);
}
else{
int scoreMove = alpha;
int best;
genMoves.moves.Begin();
short i = -1, len = genMoves.moves.getLength();
Board bTemp(false);
if (nodeType == MAX_NODE){
best = ALPHA;
while (++i < len){
bTemp.cloneBoard(b);
if (bTemp.applyMove(genMoves.moves.nextElement())){
scoreMove = alphaBeta(bTemp, alpha, beta, depth - 1, !nodeType);
best = MAX(best, scoreMove);
alpha = MAX(alpha, best);
if (beta <= alpha){
std::cout << "max cutoff" << std::endl;
break;
}
}
}
return scoreMove;
//return alpha;
}
else{
best = BETA;
while (++i < len){
bTemp.cloneBoard(b);
if (bTemp.applyMove(genMoves.moves.nextElement())){
scoreMove = alphaBeta(bTemp, alpha, beta, depth - 1, !nodeType);
best = MIN(best, scoreMove);
beta = MIN(beta, best);
if (beta <= alpha){
std::cout << "min cutoff" << std::endl;
break;
}
}
}
return scoreMove;
//return beta;
}
return meilleur;
}
}
编辑:我应该注意,评估板只评估棋子的移动性(可能移动的数量,捕获移动根据捕获的棋子获得更高的分数)
谢谢。
我只是解决你的算法的runtime cost问题,因为我不知道你的板子评估函数的实现细节。
为了让事情尽可能简单,我将假设算法的最坏情况。
getMove 函数对 alphaBeta 函数进行 len1 调用,而 alphaBeta 函数又对自身进行 len2 调用,后者又对自身进行 len3 调用,依此类推,直到深度达到 0 并且递归停止。
由于最坏情况假设,假设 n = max(len1, len2, ...),所以您有
n * n * n * ... * n 调用 alphaBeta,乘法次数取决于深度 d,这会导致 n^d 调用 alphaBeta,这意味着您具有指数运行时行为。这是超慢的,只有阶乘运行时行为才能打败它。
我认为您应该为此目的查看 Big O 表示法,并尝试相应地优化您的算法以获得更快的结果。
此致,
OPM
我看到您正在尝试实现一个 mini-max 算法。但是,代码中有些东西让我怀疑。我们会将代码与开源 Stockfish 国际象棋引擎进行比较。请参考https://github.com/mcostalba/Stockfish/blob/master/src/search.cpp
处的搜索算法
1.通过值
你的代码中有这个:
alphaBeta(Board b, int alpha, int beta, char depth, bool nodeType)
我不知道 "Board" 到底是什么。但这对我来说不合适。让我们看看 Stockfish:
Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth
depth, bool cutNode)
位置对象在 Stockfish 中通过引用传递。如果 "Board" 是 class,程序将需要在每次调用 alpha-beta 函数时创建一个新副本。在国际象棋中,当我们要评估很多节点时,这显然是不可接受的。
2。无散列
哈希是在 Stockfish 中完成的:
ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
如果不进行散列,您将需要一次又一次地评估相同的位置。如果不实施散列,你哪儿也去不了。
3。检查将死
可能不是最明显的减速,但我们永远不应该在每个节点中检查将死。在干鱼中:
// All legal moves have been searched. A special case: If we're in check
// and no legal moves were found, it is checkmate.
if (InCheck && bestValue == -VALUE_INFINITE)
return mated_in(ss->ply); // Plies to mate from the root
完成在所有可能的着法都被搜索之后。我们这样做是因为我们通常有比将死节点更多的非将死节点。
4.电路板 bTemp(false);
这看起来像是一个重大的放缓。让我们来看看 Stockfish:
// Step 14. Make the move
pos.do_move(move, st, ci, givesCheck);
你不应该在每个节点中创建一个临时对象(创建一个bTemp对象)。机器需要分配一些堆栈 space 来保存 bTemp。这可能是一个严重的性能损失,特别是如果 bTemp 不是主变量(即,不太可能被处理器缓存)。 Stockfish 只是修改内部数据结构而不创建新结构。
5. bTemp.cloneBoard(b);
与 4 类似,更糟糕的是,节点中的每一步都这样做。
6. std::cout << "max cutoff" << std::endl;
也许很难相信,打印到终端比处理要慢得多。在这里,您正在创建一个潜在的减速,因为字符串需要保存到 IO 缓冲区中。该功能可能(我不是 100% 确定)甚至会阻止您的程序,直到文本显示在终端上。 Stockfish 仅用于统计汇总,绝对不是每次出现 fail-high 或 fail-low 时。
7.不对 PV move
排序
在解决其他问题之前,您可能不想做这件事。在 Stockfish,他们有:
std::stable_sort(RootMoves.begin() + PVIdx, RootMoves.end());
这是针对迭代深化框架中的每次迭代完成的。
我已经为我的国际象棋游戏实现了 alpha beta 算法,但是它需要很多时间(4 层的分钟)才能最终做出一个相当愚蠢的举动。
2 天来我一直在努力寻找错误(我想我犯了一个错误),非常感谢对我的代码提供一些外部输入。
getMove 函数:为根节点调用,它为它的所有子节点(可能的移动)调用 alphaBeta 函数,然后选择得分最高的移动。
Move AIPlayer::getMove(Board b, MoveGenerator& gen)
{
// defined constants: ALPHA=-20000 and BETA= 20000
int alpha = ALPHA;
Board bTemp(false); // test Board
Move BestMov;
int i = -1; int temp;
int len = gen.moves.getLength(); // moves is a linked list holding all legal moves
BoardCounter++; // private attribute of AIPlayer object, counts analyzed boards
Move mTemp; // mTemp is used to apply the nextmove in the list to the temporary test Board
gen.mouvements.Begin(); // sets the list counter to the first element in the list
while (++i < len && alpha < BETA){
mTemp = gen.moves.nextElement();
bTemp.cloneBoard(b);
bTemp.applyMove(mTemp);
temp = MAX(alpha, alphaBeta(bTemp, alpha, BETA, depth, MIN_NODE));
if (temp > alpha){
alpha = temp;
BestMov = mTemp;
}
}
return BestMov;
}
alphaBeta 函数:
int AIPlayer::alphaBeta(Board b, int alpha, int beta, char depth, bool nodeType)
{
Move m;
b.changeSide();
compteurBoards++;
MoveGenerator genMoves(b); // when the constructor is given a board, it automatically generates possible moves
// the Board object has a player attribute that holds the current player
if (genMoves.checkMate(b, b.getSide(), moves)){ // if the current player is in checkmate
return 100000;
}
else if (genMoves.checkMate(b, ((b.getSide() == BLACK) ? BLACK : WHITE), moves)){ // if the other player is in checkmate
return -100000;
}
else if (!depth){
return b.evaluateBoard(nodeType);
}
else{
int scoreMove = alpha;
int best;
genMoves.moves.Begin();
short i = -1, len = genMoves.moves.getLength();
Board bTemp(false);
if (nodeType == MAX_NODE){
best = ALPHA;
while (++i < len){
bTemp.cloneBoard(b);
if (bTemp.applyMove(genMoves.moves.nextElement())){
scoreMove = alphaBeta(bTemp, alpha, beta, depth - 1, !nodeType);
best = MAX(best, scoreMove);
alpha = MAX(alpha, best);
if (beta <= alpha){
std::cout << "max cutoff" << std::endl;
break;
}
}
}
return scoreMove;
//return alpha;
}
else{
best = BETA;
while (++i < len){
bTemp.cloneBoard(b);
if (bTemp.applyMove(genMoves.moves.nextElement())){
scoreMove = alphaBeta(bTemp, alpha, beta, depth - 1, !nodeType);
best = MIN(best, scoreMove);
beta = MIN(beta, best);
if (beta <= alpha){
std::cout << "min cutoff" << std::endl;
break;
}
}
}
return scoreMove;
//return beta;
}
return meilleur;
}
}
编辑:我应该注意,评估板只评估棋子的移动性(可能移动的数量,捕获移动根据捕获的棋子获得更高的分数)
谢谢。
我只是解决你的算法的runtime cost问题,因为我不知道你的板子评估函数的实现细节。
为了让事情尽可能简单,我将假设算法的最坏情况。
getMove 函数对 alphaBeta 函数进行 len1 调用,而 alphaBeta 函数又对自身进行 len2 调用,后者又对自身进行 len3 调用,依此类推,直到深度达到 0 并且递归停止。 由于最坏情况假设,假设 n = max(len1, len2, ...),所以您有
n * n * n * ... * n 调用 alphaBeta,乘法次数取决于深度 d,这会导致 n^d 调用 alphaBeta,这意味着您具有指数运行时行为。这是超慢的,只有阶乘运行时行为才能打败它。
我认为您应该为此目的查看 Big O 表示法,并尝试相应地优化您的算法以获得更快的结果。
此致, OPM
我看到您正在尝试实现一个 mini-max 算法。但是,代码中有些东西让我怀疑。我们会将代码与开源 Stockfish 国际象棋引擎进行比较。请参考https://github.com/mcostalba/Stockfish/blob/master/src/search.cpp
处的搜索算法1.通过值
你的代码中有这个:
alphaBeta(Board b, int alpha, int beta, char depth, bool nodeType)
我不知道 "Board" 到底是什么。但这对我来说不合适。让我们看看 Stockfish:
Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode)
位置对象在 Stockfish 中通过引用传递。如果 "Board" 是 class,程序将需要在每次调用 alpha-beta 函数时创建一个新副本。在国际象棋中,当我们要评估很多节点时,这显然是不可接受的。
2。无散列
哈希是在 Stockfish 中完成的:
ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
如果不进行散列,您将需要一次又一次地评估相同的位置。如果不实施散列,你哪儿也去不了。
3。检查将死
可能不是最明显的减速,但我们永远不应该在每个节点中检查将死。在干鱼中:
// All legal moves have been searched. A special case: If we're in check
// and no legal moves were found, it is checkmate.
if (InCheck && bestValue == -VALUE_INFINITE)
return mated_in(ss->ply); // Plies to mate from the root
完成在所有可能的着法都被搜索之后。我们这样做是因为我们通常有比将死节点更多的非将死节点。
4.电路板 bTemp(false);
这看起来像是一个重大的放缓。让我们来看看 Stockfish:
// Step 14. Make the move pos.do_move(move, st, ci, givesCheck);
你不应该在每个节点中创建一个临时对象(创建一个bTemp对象)。机器需要分配一些堆栈 space 来保存 bTemp。这可能是一个严重的性能损失,特别是如果 bTemp 不是主变量(即,不太可能被处理器缓存)。 Stockfish 只是修改内部数据结构而不创建新结构。
5. bTemp.cloneBoard(b);
与 4 类似,更糟糕的是,节点中的每一步都这样做。
6. std::cout << "max cutoff" << std::endl;
也许很难相信,打印到终端比处理要慢得多。在这里,您正在创建一个潜在的减速,因为字符串需要保存到 IO 缓冲区中。该功能可能(我不是 100% 确定)甚至会阻止您的程序,直到文本显示在终端上。 Stockfish 仅用于统计汇总,绝对不是每次出现 fail-high 或 fail-low 时。
7.不对 PV move
排序在解决其他问题之前,您可能不想做这件事。在 Stockfish,他们有:
std::stable_sort(RootMoves.begin() + PVIdx, RootMoves.end());
这是针对迭代深化框架中的每次迭代完成的。