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

Ответ 1

EDITED: Этот ответ путал приемлемость и последовательность. Я исправил это, чтобы ссылаться на допустимость, но исходный вопрос касался согласованности, и этот ответ не полностью отвечает на вопрос.

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

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

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

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

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

Ответ 2

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

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

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