Функция оценки
| Эта статья является частью серии, посвящённой |
| Шахматное программирование |
|---|
 |
Функция оценки , также известная как эвристическая функция оценки или статическая функция оценки , представляет собой функцию, используемую игровыми компьютерными программами для оценки значения или качества позиции (обычно на листе или конечном узле) в дереве игры. [1] В большинстве случаев значение представляет собой либо действительное число , либо квантованное целое число , часто в n-ных долях от стоимости игровой фигуры, такой как камень в го или пешка в шахматах, где n может быть десятыми, сотыми или другими удобными долями. дробь, но иногда значение представляет собой массив из трех значений в единичном интервале , представляющих проценты выигрыша, ничьи и проигрыша позиции.
Не существует аналитических или теоретических моделей функций оценки нерешенных игр, и такие функции не являются полностью специальными. Состав оценочных функций определяется эмпирически путем помещения функции-кандидата в автомат и оценки ее последующего выполнения. В настоящее время существует значительный объем данных по некоторым играм, таким как шахматы, сёги и го, относительно общего состава функций оценки для них.
Игры, в которых игровые компьютерные программы используют функции оценки, включают шахматы , [2] идти , [2] сёги (японские шахматы), [2] Отелло , шестигранник , нарды , [3] и шашки . [4] [5] Кроме того, с появлением таких программ, как MuZero , компьютерные программы также используют функции оценки для видеоигр , например, от Atari 2600 . [6] Некоторые игры, такие как «крестики-нолики» , имеют строгое решение и не требуют поиска или оценки, поскольку доступно дискретное дерево решений.
Отношение к поиску
[ редактировать ]Дерево таких оценок обычно является частью алгоритма поиска, такого как поиск по дереву Монте-Карло , или минимаксного алгоритма, такого как альфа-бета-поиск . Предполагается, что это значение представляет относительную вероятность выигрыша, если дерево игры было расширено от этого узла до конца игры. Функция смотрит только на текущую позицию (т.е. на каких пространствах находятся фигуры и их отношение друг к другу) и не учитывает историю позиции и не исследует возможные ходы вперед от узла (поэтому статические). Это означает, что для динамичных позиций, где существуют тактические угрозы, функция оценки не будет точной оценкой позиции. Эти позиции называются непостоянными ; им требуется, по крайней мере, ограниченный вид расширения поиска, называемый поиском покоя, для устранения угроз перед оценкой. Некоторые значения, возвращаемые функциями оценки, являются абсолютными, а не эвристическими, если в узле происходит выигрыш, проигрыш или ничья.
В функции оценки существует сложная взаимосвязь между поиском и знаниями. Более глубокий поиск отдает предпочтение меньшему количеству краткосрочных тактических факторов и более тонким долгосрочным позиционным мотивам в оценке. Существует также компромисс между эффективностью закодированных знаний и вычислительной сложностью: вычисление детальных знаний может занять так много времени, что производительность снижается, поэтому приближения к точным знаниям часто оказываются лучше. Поскольку функция оценки зависит от номинальной глубины поиска, а также от расширений и сокращений, используемых при поиске, не существует общей или отдельной формулировки функции оценки. Функция оценки, которая хорошо работает в одном приложении, обычно требует существенной перенастройки или переобучения для эффективной работы в другом приложении.
В шахматах
[ редактировать ]В компьютерных шахматах результат оценочной функции обычно представляет собой целое число , а единицы оценочной функции обычно называются пешками . Термин «пешка» относится к значению, когда у игрока в позиции на одну пешку больше, чем у противника, как объяснено в разделе « Относительная ценность шахматной фигуры» . Целое число 1 обычно представляет собой некоторую долю пешки, а в компьютерных шахматах обычно используются , которые сантипешки составляют сотую часть пешки. Более крупные оценки указывают на материальный дисбаланс или позиционное преимущество или на то, что материальный выигрыш обычно неизбежен. Очень большие оценки могут указывать на то, что мат неизбежен. Функция оценки также неявно кодирует значение права на ход, которое может варьироваться от небольшой доли пешки до победы или поражения.
Созданные вручную функции оценки
[ редактировать ]Исторически сложилось так, что в компьютерных шахматах члены оценочной функции конструируются (то есть создаются вручную) разработчиком движка, а не обнаруживаются посредством обучения нейронных сетей . Общий подход к построению вручную оценочных функций представляет собой линейную комбинацию различных взвешенных условий, которые призваны влиять на стоимость позиции. Однако не все члены созданной вручную функции оценки являются линейными, некоторые, такие как безопасность короля и пешечная структура, являются нелинейными. Каждый терм можно рассматривать как состоящий из факторов первого порядка (тех, которые зависят только от пространства и любой его части), факторов второго порядка (пространства по отношению к другим пространствам) и факторов n-го порядка (зависимости от истории позиция).
Созданная вручную функция оценки обычно имеет элемент материального баланса, который обычно доминирует в оценке. Обычные значения, используемые для материала: ферзь=9, ладья=5; Рыцарь или Слон=3; Пешка=1; королю присваивается сколь угодно большая стоимость, обычно превышающая общую стоимость всех остальных фигур. [1] Кроме того, он обычно имеет набор позиционных условий, обычно общая сумма которых не превышает стоимости пешки, хотя в некоторых позициях позиционные условия могут быть намного больше, например, когда мат неизбежен. Созданные вручную функции оценки обычно содержат от десятков до сотен отдельных терминов.
На практике эффективные функции оценки, созданные вручную, создаются не путем расширения списка оцениваемых параметров, а путем тщательной настройки или тренировки весов относительно друг друга для скромного набора параметров, таких как описанные выше. С этой целью используются позиции из различных баз данных, например, из мастер-игр, движковых игр, игр Lichess или даже из самостоятельной игры, как при обучении с подкреплением .
Пример
[ редактировать ]Пример функции оценки, созданной вручную для шахмат, может выглядеть следующим образом:
- c 1 * материал + c 2 * подвижность + c 3 * безопасность короля + c 4 * контроль центра + c 5 * пешечная структура + c 6 * тропизм короля + ...
Каждое из слагаемых представляет собой вес, умноженный на разностный коэффициент: значение материальных или позиционных слагаемых белых минус значение черных.
- Материальный термин получается путем присвоения стоимости в пешковых единицах каждой из фигур.
- Мобильность — это количество разрешенных ходов, доступных игроку, или, альтернативно, сумма количества мест, атакованных или защищаемых каждой фигурой, включая места, занятые дружественными или противостоящими фигурами. Также может быть принята во внимание эффективная мобильность или количество «безопасных» мест, на которые может переместиться фигура.
- Безопасность короля - это набор бонусов и штрафов, начисляемых за расположение короля и конфигурацию пешек и фигур, прилегающих к королю или перед ним, а также противостоящих фигур, опирающихся на пространства вокруг короля.
- Контроль центра зависит от того, сколько пешек и фигур занимают или занимают четыре центральных поля, а иногда и 12 мест расширенного центра.
- Пешечная структура — это набор штрафов и бонусов за различные сильные и слабые стороны пешечной структуры, например штрафы за сдвоенные и изолированные пешки.
- Тропизм короля — это бонус за близость (или штраф за расстояние) определенных фигур, особенно ферзей и коней, к королю противника.
Нейронные сети
[ редактировать ]Хотя нейронные сети используются в функциях оценки шахматных движков с конца 1980-х годов, [7] [8] они не стали популярными в компьютерных шахматах до конца 2010-х годов, поскольку оборудование, необходимое для обучения нейронных сетей, в то время было недостаточно мощным, а алгоритмы быстрого обучения, топология и архитектура сети еще не были разработаны. Первоначально функции оценки на основе нейронных сетей обычно состояли из одной нейронной сети для всей функции оценки, входные параметры которой выбирались с доски, а выходные данные представляли собой целое число , нормализованное по шкале сантипа, так что значение 100 примерно эквивалентно материалу. преимущество пешки. Параметры нейронных сетей обычно обучаются с использованием обучения с подкреплением или обучения с учителем . Совсем недавно функции оценки в компьютерных шахматах начали использовать несколько нейронных сетей, каждая из которых обучена для определенной части оценки, такой как пешечная структура или эндшпиль. Это позволяет использовать гибридные подходы, в которых функция оценки состоит как из нейронных сетей, так и из созданных вручную терминов.
Глубокие нейронные сети использовались, хотя и нечасто, в компьютерных шахматах после «Жирафа» Мэтью Лая. [9] в 2015 году и Deepmind от AlphaZero в 2017 году продемонстрировали возможность использования глубоких нейронных сетей в функциях оценки. Проект распределенных вычислений был запущен вскоре после этого с Leela Chess Zero целью попытаться воспроизвести результаты статьи Deepmind AlphaZero. Помимо размера сетей, нейронные сети, используемые в AlphaZero и Leela Chess Zero, также отличаются от сетей, используемых в традиционных шахматных движках, поскольку они имеют два выхода: один для оценки ( значение head ) и один для упорядочивания ходов ( головка политики). ), а не только один выход для оценки. [10] Кроме того, хотя на выходе значения head нейронной сети Лилы можно установить действительное число , чтобы аппроксимировать шкалу центипешек, используемую в традиционных шахматных движках, по умолчанию выходными данными являются проценты выигрышей, ничьих и проигрышей, вектор по три значения каждого из единичного интервала . [10] Поскольку глубокие нейронные сети очень велики, механизмам, использующим глубокие нейронные сети в своей функции оценки, обычно требуется графический процессор для эффективного расчета функции оценки.
Кусковые столы
[ редактировать ]Важным методом оценки, по крайней мере, с начала 1990-х годов, является использование для оценки таблиц сдельных квадратов (также называемых таблицами сдельной стоимости). [11] [12] Каждая таблица представляет собой набор из 64 значений, соответствующих клеткам шахматной доски. Самая базовая реализация таблицы «фигура-квадрат» состоит из отдельных таблиц для каждого типа фигур на каждого игрока, что в шахматах дает всего 12 таблиц «фигура-квадрат». Более сложные варианты таблиц «фигура-квадрат» используются в компьютерных шахматах, одним из наиболее известных из которых является таблица «король-фигура-квадрат», используемая в Stockfish , Komodo Dragon , Ethereal и многих других движках, где каждая таблица учитывает положение каждой фигуры. тип фигуры по отношению к королю игрока, а не позиция каждого типа фигуры в отдельности. Значения в таблицах представляют собой бонусы/штрафы за расположение каждой фигуры на каждом поле и отражают совокупность многих тонких факторов, которые трудно измерить аналитически. В функциях оценки, созданных вручную, иногда имеется два набора таблиц: один для дебюта/миттельшпиля и один для эндшпиля; позиции миттельшпиля интерполируются между ними. [13]
Первоначально разработанный в компьютерных сёги в 2018 году. Ю Насу [14] [15] наиболее распространенная функция оценки, используемая сегодня в компьютерных шахматах [ нужна ссылка ] — это эффективно обновляемая нейронная сеть , или NNUE сокращенно , разреженная и неглубокая нейронная сеть , которая имеет только таблицы кусков-квадратов в качестве входных данных для нейронной сети. [16] Фактически, самая базовая архитектура NNUE — это просто описанные выше таблицы из 12 квадратных частей, нейронная сеть только с одним слоем и без функций активации . Эффективно обновляемая архитектура нейронной сети, использующая в качестве входных данных таблицы «король-фигура-квадрат», была впервые перенесена на шахматы в производной версии Stockfish под названием Stockfish NNUE, публично выпущенной 30 мая 2020 года. [17] и был принят многими другими движками, прежде чем 6 августа 2020 года был включен в официальный движок Stockfish. [18] [19]
Табличные базы эндшпиля
[ редактировать ]Шахматные движки часто используют базы таблиц эндшпиля в своей функции оценки, поскольку это позволяет движку идеально играть в эндшпиле.
В Го
[ редактировать ]Исторически функции оценки в Computer Go учитывали как контролируемую территорию, влияние камней, количество заключенных, так и жизнь и смерть групп на доске. Однако современные компьютерные программы для игры в го в своих функциях оценки в основном используют глубокие нейронные сети, такие как AlphaGo , Leela Zero , Fine Art и KataGo , и выводят процент выигрыша/ничей/проигрыша, а не значение в количестве камней.
Ссылки
[ редактировать ]- ^ Jump up to: а б Шеннон, Клод (1950), Программирование компьютера для игры в шахматы (PDF) , сер. 7, том. 41, Philosophical Magazine , получено 12 декабря 2021 г.
- ^ Jump up to: а б с Сильвер, Дэвид ; Юбер, Томас; Шритвизер, Джулиан; Антоноглу, Иоаннис; Лай, Мэтью; Гез, Артур; Ланкто, Марк; Сифре, Лоран; Кумаран, Дхаршан; Грепель, Торе; Лилликрап, Тимоти; Симонян, Карен; Хассабис, Демис (7 декабря 2018 г.). «Общий алгоритм обучения с подкреплением, позволяющий освоить шахматы, сёги и самостоятельную игру» . Наука . 362 (6419): 1140–1144. Бибкод : 2018Sci...362.1140S . дои : 10.1126/science.aar6404 . ПМИД 30523106 .
- ^ Тезауро, Джеральд (март 1995 г.). «Обучение временным разницам и TD-гаммон» . Коммуникации АКМ . 38 (3): 58–68. дои : 10.1145/203330.203343 . S2CID 8763243 . Проверено 1 ноября 2013 г.
- ^ Шеффер, Дж.; Берч, Н.; Ю. Бьернссон; Кишимото, А.; Мюллер, М.; Лейк, Р.; Лу, П.; Сатфен, С. (2007). «Шашки решены» (PDF) . Наука . 317 (5844): 1518–22. дои : 10.1126/science.1144079 . ПМИД 17641166 . S2CID 10274228 .
- ^ Шеффер, Дж.; Бьернссон, Ю.; Берч, Н.; Кишимото, А.; Мюллер, М.; Лейк, Р.; Лу, П.; Сатфен, С. «Решение шашек» (PDF) . Материалы Международной совместной конференции по организации искусственного интеллекта 2005 г.
- ^ Шритвизер, Джулиан; Антоноглу, Иоаннис; Юбер, Томас; Симонян, Карен; Сифре, Лоран; Шмитт, Саймон; Гез, Артур; Локхарт, Эдвард; Хассабис, Демис; Грепель, Торе; Лилликрап, Тимоти (2020). «Освоение Atari, го, шахмат и сёги путем планирования с использованием изученной модели». Природа . 588 (7839): 604–609. arXiv : 1911.08265 . Бибкод : 2020Natur.588..604S . дои : 10.1038/s41586-020-03051-4 . ПМИД 33361790 . S2CID 208158225 .
- ^ Турн, Себастьян (1995), Учимся играть в шахматы (PDF) , MIT Press , получено 12 декабря 2021 г.
- ^ Левинсон, Роберт (1989), Самообучающаяся шахматная программа, ориентированная на шаблоны , том. 12, Журнал ICCA
- ^ Лай, Мэтью (4 сентября 2015 г.), Жираф: использование глубокого обучения игре в шахматы с подкреплением , arXiv : 1509.01549v1
- ^ Jump up to: а б «Топология нейронной сети» . lczero.org . Проверено 12 декабря 2021 г.
- ^ Бил, Дон; Смит, Мартин К., Изучение значений «кусок-квадрат» с использованием временных различий , том. 22, Журнал ICCA
- ^ Дзюн Нагасима Такетоши; Ёитиро Кадзихара; Хироюки Иида (2002), «Эффективное использование кусочных таблиц в компьютерных сёги» , Японское общество обработки информации.
- ^ Руководство по оценке вяленой рыбы , получено 12 декабря 2021 г.
- ^ Ю Насу (28 апреля 2018 г.). «Эффективно обновляемая функция оценки на основе нейронных сетей для компьютерных сёги» (PDF) (на японском языке).
- ^ Ю Насу (28 апреля 2018 г.). «Эффективно обновляемая функция оценки на основе нейронных сетей для компьютерных сёги (неофициальный английский перевод)» (PDF) . Гитхаб .
- ^ Гэри Линскотт (30 апреля 2021 г.). «ННЭУ» . Гитхаб . Проверено 12 декабря 2020 г.
- ^ Нода, Хисаёри (30 мая 2020 г.). "Выпуск вяленой рыбы-nue- 3 мая 2020 г. Гитхаб . Получено 12 декабря.
- ^ «Введение в оценку ННЭУ» . 6 августа 2020 г.
- ^ Йост ВандеВонделе (25 июля 2020 г.). "official-stockfish / Stockfish, слияние ННЭУ" . Гитхаб .
- Слейт Д. и Аткин Л., 1983, «Шахматы 4.5, шахматная программа Северо-Западного университета» в книге «Шахматные навыки человека и машины», 2-е изд., стр. 93–100. Спрингер-Верлаг, Нью-Йорк, штат Нью-Йорк.
- Эбелинг, Карл, 1987, Все правильные ходы: архитектура СБИС для шахмат (выдающаяся диссертация ACM), стр. 56–86. MIT Press, Кембридж, Массачусетс