C 语言下的国际象棋 : Negamax implementation works but sometimes doesn't spot mates in 1

Question

我用 alpha beta 剪枝和 quiscence 搜索实现了 negamax，它似乎有效......除了有时计算机让我在 1 中交配，尽管它可以采取一些措施来阻止它(这种情况发生了)在深度 4，它绝对应该被发现)。如果更有经验的人可以查看我的代码，也许会看到我没有看到的东西，我将非常感激:

static double alphaBetaMax(double alpha, double beta, int depthleft, game_t game, bool player)
{
move_t *cur;
move_t *tmp;
double score = 0;
    bool did_move = false;

cur = getAllMoves(game, player); //getAllMoves initilizes a global list of moves, firstMove
if(cur == NULL) /*  check mate*/
    return -9999999*(player*2-1);
tmp = firstMove;
firstMove = 0;

while (cur != NULL)
{
    game_t copy;
    if(depthleft<=0 && !isCapture(game, cur)) { /* Quiescence search */
            cur = cur->next;
                continue;
    }
            did_move = true;
    copyGame(game, &copy);
    makeMove(&copy, *cur);
    firstMove = NULL;
    score = -alphaBetaMax(-beta, -alpha, depthleft - 1, copy, !player);
    if(board_count > MAX_BOARDS)
      break;

    freeGame(copy);
    if(score > alpha)
      alpha = score;

    if (beta <= alpha)
      break;
    cur = cur->next;
}
firstMove=tmp;
freeMoves();

    if(!did_move)
       alpha = evaluate(game)*(player*2-1);
return alpha;
}

move_t* getBestMove(game_t game, int player, unsigned int depth) // initial call
{
move_t *cur = NULL, *best = NULL;
move_t *tmp;
double alpha = -DBL_MAX, score = 0;
freeMoves();
firstMove = NULL;
cur =  getAllMoves(game, player);
tmp = firstMove;
firstMove = 0;

while (cur != NULL)
{
    game_t copy;
    copyGame(game, &copy);
    makeMove(&copy, *cur);
    firstMove = NULL;
    score = -alphaBetaMax(-DBL_MAX, -alpha, depth-1, copy, !player);
#ifdef PRINT_SCORES
    printf(" <%c,%d> to ", cur->x1 + 'a', cur->y1 + 1);
    printf("<%c,%d>", cur->x2 + 'a', cur->y2 + 1);
    printf(" - score %f\n", score);
#endif
    freeGame(copy);

    if(board_count > MAX_BOARDS)
      break;

    if (score > alpha) {
      alpha = score;

      if (best != NULL) {
        best->next = NULL;
        free(best);
      }
      best = copyMove(*cur);
    }
    cur = cur->next;
}
firstMove = tmp;
freeMoves();

if(board_count > MAX_BOARDS) {
  free(best);
  return 0;
}
return best;

}

Answer 1

您的代码在许多方面执行不正确，例如 q-search、评估和搜索算法本身。例如，您的 qsearch 不正确。你应该得到一个标准分数，然后生成所有捕获和非完全移动。将这些移动递归地使用到 qsearch 中。

但最重要的是，您为将死返回的分数是错误的。在 nega-max 中，将死分数必须且必须相对于该回合的玩家返回。也就是说，您必须为配合返回负值。

你的代码

return -9999999*(player*2-1);

如果玩家为假(假== 0)，则返回正值。阅读 http://en.wikipedia.org/wiki/Negamax 中的负最大。你看到了吗

bestValue := -∞

在算法中？你不在乎轮到谁，你必须为队友返回一个负值。