Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 64
Текст из файла (страница 64)
А если бы в первую очередь был сформирован третий преемник, то была бы возможность отсечь двух остальных. На основании этого можно сделать вывод, что имеет смысл стремиться исследовать в первую очередь таких преемников, которые, по всей вероятности, могут стать наилучшими. Если принять допущение, что это может быть сделано', то окажется, что в алгоритме альфа-бета-отсечения для определения наилучшего хода достаточно исследовать только 0(.Ь"") узлов, а не 0(Ь ) узлов, как при использовании минимаксного алгоритма. Это означает, что эффективный коэффициент ветвления становится равнымз)Ь, а не Ь; например, для шахмат он равен б, а не 35. Иными словами, за такое же время альфа-бета-поиск позволяет заглянуть в дерево игры примерно в лва раза дальше по сравнению с минимаксным поиском.
А если исследование преемников происходит в случайном порядке, а не по принципу первоочередного выбора наилучших вариантов, то при умеренных значениях Ь общее количество исследованных узлов будет составлять примерно 0(Ь' м) . В случае шахмат применение довольно простой функции упорядочения (например, такой, в которой в первую очередь рассматриваются взятия фигур, затем угрозы, затем ходы вперед, а после этого ходы назад) позволяет оставаться в пределах, не превышаюших удвоенное значение результата 0(Ы"гз), который может быть получен в наилучшем случае. Добавление динамических схем упорядочения ходов, в частности, таких, в которых в первую очередь проверяются ходы, обозначенные как наилучшие на предыдушем этапе, позволяют подойти совсем близко к этому теоретическому пределу. Как было отмечено в главе 3, наличие повторяющихся состояний в дереве поиска может вызвать экспоненциапьное увеличение стоимости поиска.
В играх повторяющиеся состояния встречаются часто из-за возникновения Ъ.транспозиций— различных перестановок последовательностей ходов, которые оканчиваются в одной и той же позиции. Например, если белые имеют в своем распоряжении ход см на который черные могут ответить ходом Ь„а также еше один не связанный с ним ход аз на другой стороне доски, на который может быть дан ответ Ь„то обе последовательности, [аз, Ь„, аз, Ь,) и (аз, Ь„аз, Ь„1, оканчиваются водной и той же позиции (как и перестановки, начинающиеся с аз).
Поэтому целесообразно сохранять оценку каждой конкретной позиции в хэш-таблице при первом ее возникновении, чтобы не приходилось вычислять ее повторно при последующих возникновениях. По традиции хэштаблица с ранее встретившимися позициями называется ',ъ.таблицей траиспозипий; она по сути идентична списку с1овос) в алгоритме 0кар)з-ЯеаксЬ (см. с.!39). Использование таблицы транспозиций может оказать чрезвычайно эффективное воздействие, которое иногда выражается в удваивании достижимой глубины поиска в шахматах.
С другой стороны, если существует возможность вычислять оценки со скоростью в несколько миллионов узлов в секунду, то практически нет смысла хранить данные обо всех этих узлах в таблице транспозиций. Для выбора наиболее ценных из этих узлов были опробованы различные стратегии. ' Очевидно, что при этом невозможно постичь идеальных результатов, поскольку в противном случае функцию упорядочения можно было бы использовать для ведения идеальной игры! Часть 11. Решение проблем 252 6.4. НЕИДЕАЛЬНЫЕ РЕШЕНИЯ, ПРИНИМАЕМЫЕ В РЕАЛЬНОМ ВРЕМЕНИ Минимаксный алгоритм формирует все пространство поиска игры, а алгоритм альфа-бета-отсечения позволяет отсекать значительные его части.
Тем не менее при использовании алгоритма альфа-бета-отсечения все еше приходится выполнять поиск вплоть до терминальных состояний, по крайней мере, в некоторой области пространства поиска. Обычно задача достижения такой глубины на практике не осуществима, поскольку ходы должны быть сделаны за какое-то приемлемое время, как правило, не больше чем за несколько минут. Вместо этого в статье Шеннона Ргоягатття а сотригег Гог р!ау1щ слезз от 1950 года было предложено, чтобы программы прекращали поиск раньше времени и применяли к состояниям какую-то эвристическую функцию оценки, по сути, преобразуя нетерминальные узлы в терминальные листья.
Другими словами, в этой статье было предложено модифицировать минимаксный поиск или альфа-бета-поиск в двух отношениях: заменить функцию полезности эвристической функцией оценки кча1, которая дает оценку полезности данной позиции, а проверку терминальной позиции заменить Ж проверкой останова, которая позволяет решить, когда следует применять функцию кча1. Функции оценки Функция оценки возвращает прогноз ожидаемой полезности игры из данной конкретной позиции по аналогии с тем, как эвристические функции, описанные в главе 4, возврашают прогнозируемое значение расстояния до цели.
Идея такого "оценщика" в то время, когда Шеннон предложил ею воспользоваться, была не нова. В течение многих столетий шахматисты (и поклонники других игр) разработали способы выработки суждений о стоимости позиции, поскольку люди еше более ограничены в обьемах поиска, который может быть ими выполнен, чем компьютерные программы. Должно быть очевидно, что производительность любой программы ведения игры зависит от качества применяемой функции оценки. Неточная функция оценки приведет агента к позициям, которые окажугся проигрышными.
Поэтому возникает важный вопрос — как именно следует проектировать хорошие функции оценки? Во-первых, функция оценки должна упорядочивать терминальные состояния таким же образом, как и настоящая функция полезности; в противном случае используюгций ее агент может выбрать неоптимальные ходы, даже обладая способностью просчитывать все ходы до конца игры. Во-вторых, вычисления не должны занимать слишком много времени! (В функции оценки можно было бы вызывать мйпйгаахгзесйв1оп в качестве процедуры и вычислять точную стоимость данной позиции, но это поставило бы под сомнение то, к чему мы стремимся, — экономию времени.) В-третьих, для нетерминальных состояний значения этой функции оценки должны строго коррелировать с фактическими шансами на выигрыш.
Выражение "шансы на выигрыш" на первый взгляд может показаться странным. В конце концов, шахматы — это же не игра с элементами случайности: в ней безусловно известно текущее состояние и для определения следующего хода не нужно бросать жребий. Но если поиск должен прекращаться в нетерминальных состояниях, то в данном алгоритме будет обязательно оставаться неопределенность в отно- Глава 6.
Поиск в условиях противодействия 253 шении окончательных исходов для этих состояний. Неопределенность такого рода вызвана вычислительными, а не информационными ограничениями. Из-за ограниченного объема вычислений, которые разрешено выполнить в функции оценки для данного конкретного состояния, лучшее, что она может сделать, — это принять какое-то предположение в отношении конечного результата. Рассмотрим эту идею немного более конкретно. Функции оценки чаще всего действуют по принципу вычисления различных 'в. характеристик данного состояния, например, в шахматах одной из таких характеристик является количество пешек, принадлежащих каждой из сторон.
Эти характеристики, вместе взятые, определяют различные категории, или классы эквивалентности состояний: состояния из каждой категории имеют одни и те же значения для всех своих характеристик. Вообще говоря, любая конкретная категория включает некоторые состояния, которые ведут к победе, к ничьей или поражению. Функция оценки не позволяет определить, какими являются те или иные состояния, но способна вернуть единственное значение, которое отражает процентную далю этих состояний в каждом результате. Например, предположим, полученный опыт показывает, что 72% состояний, встретившихся в данной категории, ведут к победе (полезность +1); 20% — к поражению (-1) и 8% к ничьей (О). В таком случае приемлемой оценкой для состояний этой категории становится взвешенное среднее, или ~з,ожидаемое значение: (0.72х+1)+(0.20х-1)+(0.08х0) =0.52.
В принципе, ожидаемое значение можно определить для каждой категории, получив в итоге функцию оценки, применимую для любого состояния. Как и в случае терминальных состояний, функция оценки не обязана возвращать фактические ожидаемые значения, при условии, что упорядочение состояний остается тем же самым. На практике для проведения анализа такого рода требуется учитывать слишком много категорий и поэтому накопить слишком много опыта, чтобы можно было оценить все вероятности выигрыша.
Вместо этого в большинстве функций оценки вычисляются отдельные представленные в числовом виде значения вклада, зависящего от каждой характеристики, после чего эти значения комбинируются для поиска суммарного значения. Например, в учебниках по шахматам для начинающих можно найти приближенные оценки Ж стоимости материала для каждой фигуры: например, такие, что пешка имеет стоимость 1, конь или слон — 3, ладья — 5, аферзь — 9. Другие характеристики, такие как "хорошая пешечная структура" и "безопасность короля", могут оцениваться как равные, скажем, половине стоимости пешки. После этого стоимости таких характеристик просто складываются для получения оценки позиции.
Надежное преимущество, эквивалентное стоимости пешки, расценивается как значительная вероятность выигрыша, а надежное преимушество в три пешки должно почти наверняка обеспечить победу, как показано на рис. 6.6, а. В математике функция оценки такого типа называется 'а. взвешенной линейной функцией, поскольку она может быть представлена следующим образом: п Вча1(в) = ьаЕ,(а) ь н~Ег(я) + ... + и Е (а) = ~~) ьа Ег(в) Гсь где каждый коэффициент ь; представляет собой вес, а каждая функция Е, оценивает некоторую характеристику позиции. В шахматах функция Е, может определять количество на доске фигур каждого вида, а коэффициент ьз — оценивать стоимости этих фигур (! за пешку, 3 за слона и т.д.).
Глава 6. Поиск в условиях противодействия 255 заменить две строки в листинге 6.2, в которых упоминается функция техта1па1- теэс, следующей строкой: 1х сиеохх-теас(эсаее, дереЛ) ецеп хвечец Ена1(веаее) Необходимо также предусмотреть выполнение определенных технических операций для того, чтобы текущее значение глубины пере)з наращивалось при каждом рекурсивном вызове. Наиболее прямолинейный подход к управлению объемом поиска состоит в том, что должен устанавливаться фиксированный предел глубины, чтобы функция сисойй-тевс (эсасе, с)ерс)з) возвращала значение ехие при всех значениях с)ере)з, превышающих некоторую фиксированную глубину г1 (Она должна также возвращать елие для всех терминальных состояний, как было предусмотрено и в функции гехтвдпа1-теэс.) Глубина с) выбрана таким образом, чтобы используемое время не превышало допустимое по правилам игры.
Более надежный подход состоит в использовании метода итеративного углубления, который определен в главе 3. По окончании отведенного времени программа возвращает ход, выбранный по итогам наиболее глубокого завершенного поиска. Однако подобные подходы могут приводить к ошибкам, обусловленным приближенным характером функции оценки. Еше раз рассмотрим простую функцию оценки для шахмат, основанную на учете преимущества в материале.
Предположим, что программа выполняет поиск до предела глубины, достигая позиции, приведенной на рис. 6.6, б, где черные имеют перевес на одного коня и две пешки. Программа сообьцила бы об этом как об эвристическом значении данного состояния, объявив тем самым, что это состояние, по всей вероятности, приведет к победе черных. Но на следующем ходу белые берут ферзя черных без компенсации. Поэтому в действительности данная позиция является выигрышной для белых, но об этом можно было бы узнать, только заглянув вперед еше на один полуход.
Очевидно, что требуется более сложная проверка останова. Функция оценки должна применяться только к позициям, которые являются Ж спокойными, т.е. характеризующимися низкой вероятностью того, что в них в ближайшем будущем произойдут резкие изменения в стоимости. Например, в шахматах такие позиции, в которых могут быть сделаны желательные взятия фигур, не являются спокойными для такой функции оценки, в которой учитывается лишь материал. Неспокойные позиции могут быть дополнительно развернуты до тех пор, пока не будут достигнуты спокойные позиции. Подобный дополнительный поиск называется ъ. поиском спокойных позиций; иногда он ограничивается тем, что в нем рассматриваются только ходы определенных типов, такие как ходы со взятием фигур, что позволяет быстро устранять все неопределенности в этой позиции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
