Эффект горизонта

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

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

В 1973 году Ганс Берлинер назвал это явление, которое он и другие исследователи наблюдали, «Эффектом горизонта». ^[1] Он разделил эффект на две части: эффект негативного горизонта «приводит к созданию отвлечений, которые неэффективно откладывают неизбежные последствия или заставляют недостижимое казаться достижимым». Что касается «эффекта положительного горизонта», который «в значительной степени игнорируется», «программа слишком рано улавливает последствия, которые можно навязать противнику на досуге, часто в более эффективной форме».

Жадные алгоритмы, как правило, страдают от эффекта горизонта.

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

Переписывание функции оценки для конечных узлов и/или анализ большего количества узлов решит многие проблемы эффекта горизонта.

Пример

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

См. также

Ссылки

^ Берлинер, Ганс Дж. (20–23 августа 1973 г.). «Некоторые необходимые условия для магистерской программы по шахматам» . Материалы 3-й Международной совместной конференции по искусственному интеллекту. Стэнфорд, Калифорния, США, 20–23 августа 1973 г .: 77–85.

Рассел, Стюарт Дж .; Норвиг, Питер (2003), Искусственный интеллект: современный подход (2-е изд.), Аппер-Сэддл-Ривер, Нью-Джерси: Прентис-Холл, стр. 174, ISBN 0-13-790395-2

Внешние ссылки

Эффект горизонта в WIKI по шахматному программированию (CPW)

[1] Берлинер, Ганс Дж. (20–23 августа 1973 г.). «Некоторые необходимые условия для магистерской программы по шахматам» . Материалы 3-й Международной совместной конференции по искусственному интеллекту. Стэнфорд, Калифорния, США, 20–23 августа 1973 г .: 77–85.

[1]