Функция оценки - Evaluation function

Для функции оценки строки см. Eval .

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

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

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

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

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

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

В шахматы

См. Также: Эффективно обновляемая нейронная сеть.

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

Оценочная функция для шахмат может иметь вид

  • c 1 * материал + c 2 * мобильность + c 3 * безопасность короля + c 4 * контроль над центром + c 5 * пешечная структура + c 6 * тропизм короля + ...

Каждый член представляет собой вес, умноженный на коэффициент различия: значение материала или позиционного балла белых минус баллы черных. Счет материала определяется путем присвоения каждой фишке стоимости в пешечных единицах. Стандартные значения: Ферзь = 9, Ладья = 5; Рыцарь или Слон = 3; Пешка = 1; королю присваивается произвольно большое значение, обычно превышающее общую стоимость всех остальных фигур. Имеет значение не только абсолютная ценность материала, но и соотношение материального материала белых и черных: жертва пешки в дебюте может дать позиционное преимущество (соотношение материалов практически не затронуто), но плюс пешки в короле и Для победы обычно достаточно пешечного эндшпиля (большое соотношение материала). Это соотношение обычно реализуется как бонус за размен в соответствии с практическим правилом: «разменивайте фигуры, но не пешки, когда впереди, и наоборот, когда позади». Показатель мобильности - это количество доступных игроку допустимых ходов или, альтернативно, сумма количества областей, атакованных или защищаемых каждой фигурой, включая области, занятые дружественными или противостоящими фигурами. Эффективная мобильность или количество «безопасных» мест, в которые может переместиться фигура, также могут быть приняты во внимание. Эффективная мобильность королевы часто очень мала, хотя количество ее допустимых ходов может быть довольно большим. Оценка безопасности короля - это набор бонусов и штрафов, оцениваемых в зависимости от местоположения короля и расположения пешек и фигур, прилегающих к королю или перед ним, а также противостоящих фигур, расположенных на пространствах вокруг короля. Контроль за центром определяется тем, сколько пешек и фигур занимают или несут на четырех центральных клетках, а иногда и на 12 клетках расширенного центра. Пешечная структура - это набор штрафов и бонусов за различные сильные и слабые стороны пешечной структуры, например, штрафы за сдвоенные и изолированные пешки. Тропизм короля - это бонус за близость (или штраф за расстояние) определенных фигур, особенно ферзей и рыцарей, к противостоящему королю.

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

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

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

Термины, составляющие некоторые факторы, такие как безопасность короля, комбинируются нелинейно - одна слабость в безопасности короля, такая как открытая линия рядом с королем, может быть оштрафована, например, пешкой 1/4, но может потребоваться штраф за две слабости. одна или даже две полные пешки и три слабости по фигуре, ладье или даже больше, потому что мат становится вероятной возможностью. Факторы, связанные с продвижением пешки и повышением, также сочетаются нелинейно.

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

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

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

Штучно-квадратные столы

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

Оценка в поиске по дереву монте-карло

У шахматных машин, таких как Leela Chess Zero , парадигма поиска и оценки существенно отличается от традиционной схемы алфавита / минимакса с вычислением листовых узлов. При поиске по дереву Монте-Карло пространство поиска для всех вариантов узла выбирается путем развертывания или до конца игры, поочередно выбирая случайный ход для каждой стороны. Результат (выигрыш, проигрыш или ничья) сохраняется в стартовом узле. Выбранный ход - это тот, который приводит к позиции с наибольшим количеством побед или наивысшим средним баллом, хотя с этим ходом не связано никакой конкретной линии игры. Аналогичная ситуация - это процент выигрышей / ничьих / проигрышей, накопленных для различных дебютов, используемых в основных играх. Если кто-то выбирает дебют, он будет склонен выбирать из тех, у которых наибольший процент выигрышей или самый большой процент выигрышей + ничьи. И аналогично для каждого варианта в дебюте, если есть статистика. Слабость такой схемы в том, что самая сильная линия (линии) игры для каждой стороны может не быть частью этого дебюта - они могут быть узкими возможностями в дебюте, который в противном случае является слабым.

Таким образом, «оценка» в реализациях monte-carlo - это вероятность выигрыша, а не числовая оценка позиции.

In Go

Функции оценки в Go учитывают как контролируемую территорию, так и влияние камней, количество заключенных, а также жизнь и смерть групп на доске.

Смотрите также

Рекомендации

  • Шеннон, Клод, 1950, "Программирование компьютера для игры в шахматы", Philosophical Magazine, Ser.7, Vol. 41, № 314.
  • Слейт, Д. и Аткин, Л., 1983, «Шахматы 4.5, шахматная программа Северо-Западного университета» в книге «Шахматные навыки человека и машины», 2-е изд., Стр. 93–100. Спрингер-Верлаг, Нью-Йорк, штат Нью-Йорк.
  • Эбелинг, Карл, 1987, Все правильные ходы: архитектура СБИС для шахмат (выдающаяся диссертация ACM), стр. 56–86. MIT Press, Кембридж, Массачусетс
  • Руководство по оценке Stockfish, [1]

Внешние ссылки