2

这是我的五子棋 AI 代码。所以现在我的 AI 目前运行超过 5 秒，但时间限制是 5 秒。我正在尝试提高性能，所以我尝试移动订购，但它似乎不起作用。我首先在 getChildStates(int player) 函数中计算分数，然后将向量按降序排序。但它只是行不通。一些身体可以帮助我吗？

另外，我的深度是两个。转位表好像没什么用，所以没试过。

int minimax(int depth, GameState state, bool maximizingPlayer, int alpha, int beta)
{
if (depth == 2)
    return state.score;

if (maximizingPlayer)
{
    vector<GameState> children = state.getChildStates(1);
    sort(children.begin(), children.end(), greaterA());

    int best = MIN;

    for (auto& value : children) {



        int val = minimax(depth + 1, value,
            false, alpha, beta);


        int oldBest = best;

        best = max(best, val);
        alpha = max(alpha, best);

        if (depth == 0 && oldBest != best){
            bestMoveX = value.lastMove.x;
            bestMoveY = value.lastMove.y;

        }


        // Alpha Beta Pruning
        if (beta <= alpha)
            break;

    }
    return best;
}
else
{

    vector<GameState> children = state.getChildStates(2);

    sort(children.begin(), children.end(),greaterA());

    int best = MAX;
    // Recur for left and right children
    for (auto& value : children) {
        int val = minimax(depth + 1, value,
            true, alpha, beta);

        best = min(best, val);
        beta = min(beta, best);

        // Alpha Beta Pruning
        if (beta <= alpha)
            break;
    }
    return best;
}

}

4

1 回答 1

0

我不建议对游戏状态进行排序以优先考虑状态，从而根据设置的超时启用强制移动。即使使用 alpha-beta 修剪，极小极大树也可能太大。作为参考，您可以在 github 上查看GNU Chess 。以下是一些减少最佳移动搜索时间的选项：

1）降低搜索深度。

2）从可能的动作中剔除多余的动作。

3) 在第一层使用多线程来提高速度

4) 允许静止搜索模式，这样当人类对手还在思考时，minimax 树枝可以在后台继续生成。

5）您可以考虑可重用的极小极大树，而不是为每个动作生成极小极大树，在这种树中您只修剪已经做出的动作，并且每次迭代只继续生成一层（而不是整个树，请参阅本文）。

于 2018-04-26T08:06:03.697 回答