Прекращение поиска

Привет, мой друг, тебе интересно узнать все про прекращение поиска, тогда с вдохновением прочти до конца. Для того чтобы лучше понимать что такое прекращение поиска , настоятельно рекомендую прочитать все из категории Математические методы исследования операций .Теория игр и расписаний..

Следующий этап состоит в том что алгоритм Alpha-Beta-Search должен быть модифицирован так, чтобы он вызывал эвристическую функцию Eval, когда возникает необходимость остановить поиск. С точки зрения реализации необходимо заменить две строки в листинге, в которых упоминается функция Terminal-Test, следующей строкой:

if Cutoff-Test(state, depth) then return Eval(state)

Необходимо также предусмотреть выполнение определенных технических операций для того, чтобы текущее значение глубины depth наращивалось при каждом рекурсивном вызове. Наиболее прямолинейный подход к управлению объемом поиска состоит в том, что должен устанавливаться фиксированный предел глубины, чтобы функция Cutoff-Test (state, depth) возвращала значение true при всех значениях depth, превышающих некоторую фиксированную глубину d. (Она должна также возвращать true для всех терминальных состояний, как было предусмотрено и в функции Terminal-Test.) Глубина d выбрана таким образом, чтобы используемое время не превышало допустимое по правилам игры.

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

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

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

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

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

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

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

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

А если отсечение применяется недалеко от корня, результат может оказаться катастрофическим, поскольку слишком часто возникают такие ситуации, что программа пропускает некоторые "очевидные" ходы. Предварительное отсечение может использоваться безопасно в особых ситуациях (например, если два хода являются симметричными или эквивалентными по каким-то другим признаками, то необходимо рассматривать только один из них) или при анализе узлов, которые находятся глубоко в дереве поиска.

В результате совместного использования всех методов, описанных выше, появляется возможность создать программу, которая неплохо играет в шахматы (или другие игры). Предположим, что реализована функция оценки для шахмат, предусмотрена разумная проверка останова в сочетании с поиском спокойной позиции, а также предусмотрена большая таблица транспозиций. Кроме того, предположим, что, затратив целые месяцы на скрупулезную разработку программ, функционирующих на уровне битов, мы получили возможность формировать и оценивать примерно миллион узлов в секунду на новейшем персональном компьютере, что позволяет выполнять поиск приблизительно среди 200 миллионов узлов в расчете на каждый ход при стандартном контроле времени (три минуты на каждый ход). Коэффициент ветвления для шахмат составляет в среднем примерно 35, а 35⁵ равно приблизительно 50 миллионам, поэтому при использовании минимаксного поиска мы получим возможность заглядывать вперед лишь приблизительно на пять полуходов.

Такая программа, хотя и не совсем некомпетентная, может быть легко обманута человеком, игроком в шахматы среднего уровня, который иногда способен планировать на шесть или восемь полуходов вперед. Альфа-бета-поиск позволяет достичь глубины приблизительно в 10 полуходов, что приводит к усилению игры до уровня мастера. В разделе 6.7 описаны дополнительные методы отсечения, которые позволяют увеличить эффективную глубину поиска примерно до 14 полуходов. Чтобы достичь уровня гроссмейстера, требуется тщательно настроенная функция оценки и большая база данных с записями оптимальных ходов в дебюте и эндшпиле. Не мешало бы также иметь суперкомпьютер для эксплуатации на нем такой программы!

Если я не полностью рассказал про прекращение поиска? Напиши в комментариях Надеюсь, что теперь ты понял что такое прекращение поиска и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Математические методы исследования операций .Теория игр и расписаний.