Эффект горизонта в игровом искусственном интеллекте
Horizon effect
Эффект горизонта в AI: проблема поиска в играх с огромным количеством состояний. Компьютеры не видят долгосрочные последствия ходов из-за ограниченной глубины поиска.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Слабость игрового искусственного интеллекта
Weakness of game playing artificial intelligence
Эффект горизонта, также известный как проблема горизонта, — это проблема в искусственном интеллекте, заключающаяся в том, что во многих играх количество возможных состояний или позиций огромно, и компьютеры могут практически исследовать лишь небольшую их часть, обычно на несколько ходов вглубь по дереву игры. Таким образом, для компьютера, осуществляющего поиск только на фиксированную глубину, существует вероятность совершения невыгодного хода, но этот эффект остаётся незамеченным, поскольку компьютер не анализирует позицию на глубину, на которой его оценочная функция выявляет истинную ценность варианта (то есть за пределами его «горизонта»). При оценке обширного дерева игры с использованием таких методов, как минимакс с альфа-бета отсечением, глубина поиска ограничена из соображений вычислительной целесообразности. Однако оценка частичного дерева может привести к ошибочным результатам. Если существенное изменение происходит непосредственно за горизонтом глубины поиска, вычислительное устройство становится жертвой эффекта горизонта. В 1973 году Ханс Берлинер назвал это явление, которое он и другие исследователи наблюдали, «эффектом горизонта». Он разделил его на два типа: эффект отрицательного горизонта «приводит к созданию отвлекающих манёвров, которые неэффективно откладывают неизбежные последствия или делают недостижимые цели кажущимися достижимыми». Для «в значительной степени упускаемого из виду» эффекта положительного горизонта «программа слишком рано стремится к реализации последствий, которые можно навязать противнику в удобное для него время, часто в более эффективной форме». Жадные алгоритмы склонны страдать от эффекта горизонта. Эффект горизонта можно смягчить, расширив алгоритм поиска поиском спокойных позиций. Это позволяет алгоритму поиска заглядывать за свой горизонт для определённого класса ходов, имеющих важное значение для состояния игры, например, взятий в шахматах. Пересмотр оценочной функции для конечных узлов и/или анализ большего количества узлов поможет решить многие проблемы, связанные с эффектом горизонта.
The horizon effect, also known as the horizon problem, is a problem in artificial intelligence whereby, in many games, the number of possible states or positions is immense and computers can only feasibly search a small portion of them, typically a few plies down the game tree. Thus, for a computer searching only a fixed number of plies, there is a possibility that it will make a detrimental move, but the effect is not visible because the computer does not search to the depth at which its evaluation function reveals the true evaluation of the line (i. e., beyond its "horizon"). When evaluating a large game tree using techniques such as minimax with alpha beta pruning, search depth is limited for feasibility reasons. However, evaluating a partial tree may give a misleading result. When a significant change exists just over the horizon of the search depth, the computational device falls victim to the horizon effect. In 1973 Hans Berliner named this phenomenon, which he and other researchers had observed, the "Horizon Effect." He split the effect into two: the Negative Horizon Effect "results in creating diversions which ineffectively delay an unavoidable consequence or make an unachievable one appear achievable." For the "largely overlooked" Positive Horizon Effect, "the program grabs much too soon at a consequence that can be imposed on an opponent at leisure, frequently in a more effective form." Greedy algorithms tend to suffer from the horizon effect. The horizon effect can be mitigated by extending the search algorithm with a quiescence search. This gives the search algorithm ability to look beyond its horizon for a certain class of moves of major importance to the game state, such as captures in chess. Rewriting the evaluation function for leaf nodes and/or analyzing more nodes will solve many horizon effect problems.
Пример
Например, в шахматах, представим ситуацию, когда компьютер просматривает дерево игры только на шесть ходов вперед и, исходя из текущей позиции, определяет, что ферзь будет потерян на шестом ходу. Предположим, в процессе поиска есть ход, при котором компьютер может пожертвовать ладью, отодвигая потерю ферзя на восьмой ход. Этот ход, конечно, хуже, чем немедленная жертва ферзя, поскольку он приводит к потере и ферзя, и ладьи. Однако, поскольку потеря ферзя оказалась за горизонтом поиска, она не была обнаружена и оценена. Потеря ладьи кажется предпочтительнее потери ферзя, поэтому жертва ладьи возвращается как лучший вариант, в то время как отсрочка жертвы ферзя на самом деле еще больше ослабила позицию компьютера.
For example, in chess, assume a situation where the computer only searches the game tree to six plies and from the current position determines that the queen is lost in the sixth ply; and suppose there is a move in the search depth where it may sacrifice a rook, and the loss of the queen is pushed to the eighth ply. This is, of course, a worse move than sacrificing the queen because it leads to losing both a queen and a rook. However, because the loss of the queen was pushed over the horizon of search, it is not discovered and evaluated by the search. Losing the rook seems to be better than losing the queen, so the sacrifice is returned as the best option whereas delaying the sacrifice of the queen has in fact additionally weakened the computer's position.