искусственный интеллект — C ++ Negamax альфа-бета неправильное отсечение?

Question

искусственный интеллект — C ++ Negamax альфа-бета неправильное отсечение?

Я использую Negamax, чтобы играть соединить четыре. Что я заметил, так это то, что если я добавляю альфа-бета-версию, она иногда дает «неправильные» результаты, так как, делая неудачный ход, я не верю, что он должен делать с той глубиной, на которой я ищу. Если я удаляю альфа-бета, она играет так, как и должна. Может ли альфа-бета отрезать некоторые действительно жизнеспособные ветви (особенно, когда глубина ограничена)? Вот код на всякий случай:

int negamax(const GameState& state, int depth, int alpha, int beta, int color)
{
//depth end reached? or we actually hit a win/lose condition?
if (depth == 0 || state.points != 0)
{

return color*state.points;
}

//get successors and optimize the ordering/trim maybe too
std::vector<GameState> childStates;
state.generate_successors(childStates);
state.order_successors(childStates);

//no possible moves - then it's a terminal state
if (childStates.empty())
{
return color*state.points;
}
int bestValue = -extremePoints;
int v;
for (GameState& child : childStates)
{
v = -negamax(child, depth - 1, -beta, -alpha, -color);
bestValue = std::max(bestValue, v);
alpha = std::max(alpha, v);
if (alpha >= beta)
break;
}
return bestValue;
}

1

alpha-beta-pruning artificial-intelligence c++negamax

Решение

Другие решения

Вопрос в том, как вы инициализируете свои альфа и бета в корневом узле. У меня была похожая ошибка, потому что я установил их в std :: numeric_limits :: min () и std :: numeric_limits :: max () соответственно и во время передачи альфа-параметра другому рекурсивному вызову negamax (… -a_beta, — a_alpha …) Я отрицал минимальное значение int, добавляя оператор минус, который по-прежнему возвращает минимальное значение int, потому что математическое отрицание минимального значения int находится за пределами диапазона int (-2147483648 против 2147483647).

Однако, если вы инициализируете альфа другим значением (например, std :: numeric_limits :: min () + 1), это не так.

0

Источник

Accepted Answer

Может ли альфа-бета отрезать некоторые действительно жизнеспособные ветви (особенно, когда глубина ограничена)?

Алфа-бета-алгоритм возвращает те же результаты, что и минимакс (оценка в корневом узле и игровой линии) но (часто) в более быстрое время сокращая ветви, которые не могут повлиять на окончательное решение (вы можете прочитать доказательство в Анализ алгоритма обрезки альфа-бета Самуэля Х. Фуллер — 1973).

Вы используете Negamax альфа-бета обрезка но это всего лишь вариант для упрощения реализации алгоритма.

Так же отказоустойчивость мягкий трюк не меняет ситуацию.

Конечно, поиск на малой глубине может выбрать плохие ходы, но то же самое можно сказать и о минимаксе.

Так что это должна быть ошибка реализации.

Показанный код кажется мне правильным. Вы должны проверить:

как вы называете Negamax в корневом узле. Это должно быть что-то вроде:
```
negamax(rootState, depth, −extremePoints, +extremePoints, color)
```
alpha / beta самые низкие и самые высокие возможные значения.

Если вы используете разные начальные значения для alpha / beta (например. окна устремления) и истинный счет находится за пределами начальных окон, вам необходимо выполнить повторный поиск.
как вы собираете / храните / управляете / распространяете ходы основного варианта (соответствующий код отсутствует). Такие техники, как PV-таблицы, связаны с изменениями bestValue, Если это проблема, вы должны получить тот же счет за позицию (относительно минимакса), но другой лучший ход.

2