Оценочная функция

Применение методов искусственного интеллекта в переборных алгоритмах

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

Так или иначе, оценочная функция определяется набором переменных, видом и набором параметров. Выбор переменных производится путем анализа экспертных знаний. На этом этапе иногда есть возможность обратиться к литературе по теории данной игры, каковой в избытке можно найти по шахматам. Кроме того, на практике часто очень полезны даже самые элементарные соображения экспертов, имеющих опыт игры. Это очень важно в случае с играми, для которых не создано такой внушительной теоретической базы. В некоторых, достаточно простых играх хватает всего трех переменных, и такая функция делает игру программы сносной; в шахматах их число обычно достигает нескольких сотен. Вид функции, как уже говорилось, определяется сравнительной легкостью вычисления. Последним этапом построения оценочной функции, а зачастую и всей программы, является подбор параметров при переменных (нелинейных или булевых слагаемых), то есть весов соответствующих критериев оценки позиции. Здесь анализа экспертных знаний всегда недостаточно. Часто критерии кажутся несоотносимыми, хотя требуют точнейшей сравнительной оценки. Большое количество переменных, а соответственно и параметров, делает более-менее адекватный их априорный выбор просто невозможным. Еще одна проблема при выборе параметров - их нестабильность в том смысле, что в разных фазах игры, а иногда и в разных игровых ситуациях, наиболее сильной игре соответствуют разные оценочные функции. Может появиться необходимость в течение игры менять как параметры оценочной функции, так и ее структуру. В случае с фазами игры можно заранее предусмотреть такую замену, а в случае с различными игровыми ситуациями (которых на практике может оказаться больше, чем в теории) потребуется в процессе игры выбирать адекватную программу. Причем существуют варианты: выбирать из готовых, и/или адаптировать существующую программу, получая новую. Эта частная задача относится к классу задач самообучения игровых программ, и этот класс задач подробнее рассматривается ниже.

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

А.В.Мосеев, underwood.narod.ru, 1999 год