НЕИДЕАЛЬНЫЕ РЕШЕНИЯ, ПРИНИМАЕМЫЕ В РЕАЛЬНОМ ВРЕМЕНИ
Минимаксный алгоритм формирует все пространство поиска игры, а алгоритм альфа-бета-отсечения позволяет отсекать значительные его части. Тем не менее при использовании алгоритма альфа-бета-отсечения все еще приходится выполнять поиск вплоть до терминальных состояний, по крайней мере, в некоторой области пространства поиска. Обычно задача достижения такой глубины на практике не осуществима, поскольку ходы должны быть сделаны за какое-то приемлемое время, как правило, не больше чем за несколько минут. Вместо этого в статье Шеннона Programming a computer for playing chess от 1950 года было предложено, чтобы программы прекращали поиск раньше времени и применяли к состояниям какую-то эвристическую функцию оценки, по сути, преобразуя нетерминальные узлы в терминальные листья. Другими словами, в этой статье было предложено модифицировать минимаксный поиск или альфа-бета-поиск в двух отношениях: заменить функцию полезности эвристической функцией оценки Eval, которая дает оценку полезности данной позиции, а проверку терминальной позиции заменить проверкой останова, которая позволяет решить, когда следует применять функцию Eval.
Функции оценки
Функция оценки возвращает прогноз ожидаемой полезности игры из данной конкретной позиции по аналогии с тем, как эвристические функции, описанные в главе 4, возвращают прогнозируемое значение расстояния до цели. Идея такого "оценщика" в то время, когда Шеннон предложил ею воспользоваться, была не нова. В течение многих столетий шахматисты (и поклонники других игр) разработали способы выработки суждений о стоимости позиции, поскольку люди еще более ограничены в объемах поиска, который может быть ими выполнен, чем компьютерные программы. Должно быть очевидно, что производительность любой программы ведения игры зависит от качества применяемой функции оценки. Неточная функция оценки приведет агента к позициям, которые окажутся проигрышными. Поэтому возникает важный вопрос — как именно следует проектировать хорошие функции оценки?
Во-первых, функция оценки должна упорядочивать терминальные состояния таким же образом, как и настоящая функция полезности; в противном случае использующий ее агент может выбрать неоптимальные ходы, даже обладая способностью просчитывать все ходы до конца игры. Во-вторых, вычисления не должны занимать слишком много времени! (В функции оценки можно было бы вызывать Minimax-Decision в качестве процедуры и вычислять точную стоимость данной позиции, но это поставило бы под сомнение то, к чему мы стремимся, — экономию времени.) В-третьих, для нетерминальных состояний значения этой функции оценки должны строго коррелировать с фактическими шансами на выигрыш.
Выражение "шансы на выигрыш" на первый взгляд может показаться странным. В конце концов, шахматы — это же не игра с элементами случайности: в ней безусловно известно текущее состояние и для определения следующего хода не нужно бросать жребий. Но если поиск должен прекращаться в нетерминальных состояниях, то в данном алгоритме будет обязательно оставаться неопределенность в отношении окончательных исходов для этих состояний. Неопределенность такого рода вызвана вычислительными, а не информационными ограничениями. Из-за ограниченного объема вычислений, которые разрешено выполнить в функции оценки для данного конкретного состояния, лучшее, что она может сделать, — это принять какое-то предположение в отношении конечного результата.
Рассмотрим эту идею немного более конкретно. Функции оценки чаще всего действуют по принципу вычисления различных характеристик данного состояния, например, в шахматах одной из таких характеристик является количество пешек, принадлежащих каждой из сторон. Эти характеристики, вместе взятые, определяют различные категории, или классы эквивалентности состояний: состояния из каждой категории имеют одни и те же значения для всех своих характеристик. Вообще говоря, любая конкретная категория включает некоторые состояния, которые ведут к победе, к ничьей или поражению. Функция оценки не позволяет определить, какими являются те или иные состояния, но способна вернуть единственное значение, которое отражает процентную долю этих состояний в каждом результате. Например, предположим, полученный опыт показывает, что 72% состояний, встретившихся в данной категории, ведут к победе (полезность +1); 20% — к поражению (-1) и 8% к ничьей (0). В таком случае приемлемой оценкой для состояний этой категории становится взвешенное среднее, или дожидаемое значение: (0 .72х+1) + (0 .20х-1) + (0 . 08x0) =0 . 52. В принципе, ожидаемое значение можно определить для каждой категории, получив в итоге функцию оценки, применимую для любого состояния. Как и в случае терминальных состояний, функция оценки не обязана возвращать фактические ожидаемые значения, при условии, что упорядочение состояний остается тем же самым.
На практике для проведения анализа такого рода требуется учитывать слишком много категорий и поэтому накопить слишком много опыта, чтобы можно было оценить все вероятности выигрыша. Вместо этого в большинстве функций оценки вычисляются отдельные представленные в числовом виде значения вклада, зависящего от каждой характеристики, после чего эти значения комбинируются для поиска суммарного значения. Например, в учебниках по шахматам для начинающих можно найти приближенные оценки стоимости материала для каждой фигуры: например, такие, что пешка имеет стоимость 1, конь или слон— 3, ладья— 5, а ферзь — 9. Другие характеристики, такие как "хорошая пешечная структура" и "безопасность короля", могут оцениваться как равные, скажем, половине стоимости пешки. После этого стоимости таких характеристик просто складываются для получения оценки позиции. Надежное преимущество, эквивалентное стоимости пешки, расценивается как значительная вероятность выигрыша, а надежное преимущество в три пешки должно почти наверняка обеспечить победу, как показано на рис. 6.6, а. В математике функция оценки такого типа называется взвешенной линейной функцией.
В шахматах функция fi может определять количество на доске фигур каждого вида, а коэффициент wL — оценивать стоимости этих фигур (1 за пешку, 3 за слона и т.д.).
На первый взгляд метод вычисления суммы стоимостей характеристик может показаться приемлемым, но в действительности он основан на очень радикальном допущении, что вклад каждой характеристики не зависит от стоимости других характеристик. Например, присваивая слону стоимость 3, мы игнорируем тот факт, что слоны становятся более мощными в конце игры, когда имеют большой объем пространства для маневра. По этой причине в современных программах для шахмат и других игр используются также нелинейные комбинации характеристик. Например, пара слонов может стоить немного больше по сравнению с удвоенной стоимостью одного слона, а слон стоит немного больше в конце игры, чем в начале.
Внимательный читатель должен был заметить, что все эти характеристики и веса не входят в состав шахматных правил! Они были выработаны в течение столетий на основе опыта игры людей в шахматы. Применение этих характеристик и весов на основе описанной линейной формы оценки позволяет добиться наилучшей аппроксимации по отношению к истинному упорядочению состояний по стоимости. В частности, опыт показывает, что надежное материальное преимущество больше чем в один пункт, по всей вероятности, приводит к выигрышу при всех прочих равных условиях; преимущество в три пункта является достаточным почти для безусловной победы. В таких играх, где опыт указанного вида отсутствует, веса функции оценки могут быть получены с помощью методов машинного обучения, приведенных в главе 18. Является обнадеживающим тот факт, что применение указанных методов к шахматам подтвердило, что слон действительно имеет стоимость, примерно равную трем пешкам.