Как улучшить производительность обрезки альфа-бета

Question

Вот мой код для гомоку 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;
}

}

Answer 1

Я не буду рекомендовать сортировать игровые состояния, чтобы расставить приоритеты по состояниям, тем самым позволяя силовое движение в соответствии с установленным таймаутом. Даже при обрезке альфа-бета минимаксное дерево может быть слишком большим. Для справки вы можете посмотреть в GNU Chess на github. Вот несколько вариантов сокращения времени поиска лучшего хода:

1) Уменьшить глубину поиска.

2) Отсеять лишние ходы от возможных ходов.

3) Используйте многопоточность в первом слое, чтобы набрать скорость

4) Разрешите режим поиска покоя, чтобы минимаксные ветви деревьев могли продолжать генерироваться в фоновом режиме, когда оппонент все еще думает.

5) Вместо того, чтобы генерировать минимаксное дерево для каждого хода, вы можете подумать о многоразовом минимаксном дереве, где вы только сокращаете уже сделанные ходы и продолжаете генерировать только один слой за каждую итерацию (вместо всего дерева, см. Эту статью).