В игровом программировании, как я могу проверить, является ли используемая эвристика последовательной или нет?

Question

Я думал о некоторой эвристике для большой (более высокой размерности) игры в крестики-нолики. Как проверить, какие из них на самом деле согласованы ?

Что означает согласованность в любом случае?

Answer 1

Эвристика производит какую-то стоимость стоимости для данного состояния. Согласованность в этом контексте означает, что оценка состояния плюс стоимость перехода в следующее состояние меньше или равна оценке для этого нового состояния. Если это не так, то это будет означать, что - если эвристика была точной - что переход из одного состояния в другое может повлечь за собой отрицательные издержки, что, как правило, невозможно или неправильно.

Это интуитивно понятно, когда дело доходит до поиска пути, поскольку вы ожидаете, что каждый шаг вдоль пути займет некоторое время, поэтому оценка на шаге 1 должна быть ниже, чем оценка на любом шаге 2. Возможно, она немного сложнее для крестики-нолики, так как вы, вероятно, должны произвольно решить, что представляет собой «стоимость» в вашей системе. Если ваша эвристика может увеличиваться или уменьшаться в результате выполнения хода - например, потому что вы кодируете хорошие ходы с положительными числами и плохие ходы с отрицательными числами - тогда ваша эвристика не может быть последовательной.

Однако отсутствие последовательной эвристики не всегда является проблемой. Возможно, вам не гарантировано достижение оптимального решения без него, но оно все равно может ускорить поиск по сравнению с перебором с использованием грубой силы.

Answer 2

РЕДАКТИРОВАНИЕ: Этот ответ спутал допустимость и последовательность. Я исправил это, чтобы отнести к приемлемости, но оригинальный вопрос был о последовательности, и этот ответ не полностью отвечает на вопрос.

Вы можете сделать это аналитически, различая все различные случаи и тем самым доказывая , что ваша эвристика действительно допустима.

Для информированного поиска допустима эвристика с проблемой поиска (скажем, поиск лучшего хода в игре) тогда и только тогда, когда она недооценивает «расстояние» до подходящего состояния.

ПРИМЕР: поиск кратчайшего маршрута к целевому городу через сеть автомагистралей между городами. Здесь можно использовать евклидово расстояние как эвристику: длина прямой линии до цели всегда короче или одинаково длиннее, чем наилучший возможный путь.

Приемлемость требуется для таких алгоритмов, как A *, которые затем гарантируют вам оптимальность (т. Е. Они найдут лучший «путь» к целевому состоянию, если таковое существует).

Я бы порекомендовал поискать тему в AI учебнике .