从递归 Alpha Beta 剪枝到迭代剪枝，以及其他优化 AI 玩 connect 4

Question

AI 可以玩 Connect4，这里是 compute 方法的当前代码：

std::pair<int, int>
MinimaxAI::compute(const Board &board, unsigned int depth, int player, int alpha, int beta) {
    std::pair<int, int> best;
    if(player == static_cast<int>(this->get_type()))
        best = std::make_pair(-1, std::numeric_limits<int>::min());
    else
        best = std::make_pair(-1, std::numeric_limits<int>::max());

    if(depth == 0 || board.is_terminal())
        return std::make_pair(-1, this->evaluate(board));

    std::vector<int> possible_moves = board.get_possible_moves();

    for(auto &move: possible_moves) {
        Board new_board = board;

        // Simulate the move (I say simulate because it's not actually played, it will be undone later...)
        new_board.place(move, static_cast<PlayerColor>(player));

        if(new_board.get_winner() == this->get_type()) {
            best = std::make_pair(move, std::numeric_limits<int>::max());
            return best;
        }

        // Recursively compute the best move
        std::pair<int, int> result = this->compute(new_board, depth - 1, -player, alpha, beta);

        // Undo the move
        new_board.remove(move);

        // Update the result
        result = std::make_pair(move, result.second);

        if(player == static_cast<int>(this->get_type())) {
            if(result.second > best.second)
                best = result;
            alpha = std::max(alpha, best.second);
            if(beta <= alpha)
                break;
        } else {
            if(result.second < best.second)
                best = result;
            beta = std::min(beta, best.second);
            if(beta <= alpha)
                break;
        }
    }
    return best;
}

标题是：

std::pair<int, int>
    compute(const Board &board, unsigned int depth, int player, int alpha = std::numeric_limits<int>::min(),
            int beta = std::numeric_limits<int>::max());

如果你愿意，我的evaluate方法：

int MinimaxAI::evaluate(const Board &board) {
    PlayerColor opponent = this->get_type() == PlayerColor::RED ? PlayerColor::YELLOW : PlayerColor::RED;
    int score = 0;
    int opponent_score = 0;

    if(board.get_winner() == this->get_type())
        return 100000000;
    else if(board.get_winner() == opponent)
        return -100000000;

    score = 1 * board.count_adjacent_discs(2, this->get_type());
    opponent_score = 3 * board.count_adjacent_discs(2, opponent);

    score += 3 * board.count_adjacent_discs(3, this->get_type());
    opponent_score += 10 * board.count_adjacent_discs(3, opponent);

    score += 10 * board.count_adjacent_discs(4, this->get_type());
    opponent_score += 1000 * board.count_adjacent_discs(4, opponent);

    return score - opponent_score;
}

当前，默认深度为7。

我可以去 8，但 AI 在它之后变得非常迟钝。

我希望尽可能地优化它。

我知道据称可以提高性能的位串，但我并不真正熟悉它，它需要我重写几乎所有东西。所以这是我宁愿避免的事情，除非真的需要它（最终我会在最后做，但不是现在）。

我还尝试实现了一个转置表（没有成功，AI比以往任何时候都更滞后，我想这是因为我自己实现不好）。

如果您有任何可以提高性能的解决方案，请随时告诉我。

您可以在这里找到完整的源代码：https://github.com/marcpinet/connect4-ai