c - Minimax 算法并检查每个选项/跟踪 C 中的最佳移动

Question

我尝试使用极小极大算法制作井字棋游戏，但我在递归和跟踪最佳移动方面遇到了困难。 现在，我的函数在出现获胜者时返回分数，然后从棋盘上删除该移动。我的问题是，如何防止它再次搜索同一个子节点？

int minimax(Board *board, int depth, char player, Position lastPosition)
{
    Position avMoves;
    int score = -2;

    if (didTheGameEnd(*board, (player == 'X') ? 'O' : 'X', lastPosition) == 1) {
        return (depth % 2 != 0) ? -10 : 10;
    } else if (didTheGameEnd(*board, (player == 'X') ? 'O' : 'X', lastPosition) == -1) {
        return 0;
    }

    if (board->numberOfBlanks != 0) {
        avMoves = getAvaliableMoves(*board);
    }

    for (int i = 0; i < board->numberOfBlanks; i++) {
        int newScore;
        placeMark(board, player, avMoves);
        newScore = minimax(board, depth+1, changePlayer(player), avMoves);
        if (depth % 2 != 0) {
            if (newScore > score) {
                score = newScore;
            }
        } else {
            if (newScore < score) {
                score = newScore;
            }
        }
        board->boardArr[avMoves.y][avMoves.x] = '-';
        board->numberOfBlanks++;
        board->numberOfOccupied--;
    }
    return score;
}

如何返回最佳棋步？ 编辑我忘了添加，我尝试在 N 尺寸板上制作这个

Answer 1

查看下面 Tom Kerrigan 的“简单国际象棋程序”的源代码可能会有所帮助

基本上，以下代码是 alpha-beta (minmax) 函数的一部分。它生成移动并在 for 循环中检查移动中是否有任何合法移动(这是必要的，因为国际象棋使用伪合法移动生成器)，返回最佳变化的关键部分是使用“三角数组”收集 pv[0][0..pv_length[0]] 中的最佳变化。 pv_length 跟踪博弈树不同深度的最佳变体的长度。这是一个乏味的索引方案，但完成了工作。

gen();
    if (follow_pv)  /* are we following the PV? */
        sort_pv();
    f = FALSE;

    /* loop through the moves */
    for (i = first_move[ply]; i < first_move[ply + 1]; ++i) {
        sort(i);
        if (!makemove(gen_dat[i].m.b))
            continue;
        f = TRUE;
        x = -search(-beta, -alpha, depth - 1);
        takeback();
        if (x > alpha) {

            /* this move caused a cutoff, so increase the history
               value so it gets ordered high next time we can
               search it */
            history[(int)gen_dat[i].m.b.from][(int)gen_dat[i].m.b.to] += depth;
            if (x >= beta)
                return beta;
            alpha = x;

            /* update the PV */
            pv[ply][ply] = gen_dat[i].m;
            for (j = ply + 1; j < pv_length[ply + 1]; ++j)
                pv[ply][j] = pv[ply + 1][j];
            pv_length[ply] = pv_length[ply + 1];
        }
    }

    /* no legal moves? then we're in checkmate or stalemate */
    if (!f) {
        if (c)
            return -10000 + ply;
        else
            return 0;
    }

    /* fifty move draw rule */
    if (fifty >= 100)
        return 0;
    return alpha;
}