Функция оценки , также известная как эвристическая функция оценки или статическая функция оценки , — это функция, используемая игровыми компьютерными программами для оценки ценности или качества позиции (обычно в листовом или конечном узле) в дереве игры. [1] В большинстве случаев значение представляет собой либо действительное число , либо квантованное целое число , часто в n-ных долях от стоимости игровой фигуры, такой как камень в го или пешка в шахматах, где n может быть десятыми, сотыми или другой удобной дробью, но иногда значение представляет собой массив из трех значений в единичном интервале , представляющих проценты выигрыша, ничьи и проигрыша позиции.
Не существует аналитических или теоретических моделей для функций оценки для нерешенных игр, и такие функции не являются полностью ad hoc. Состав функций оценки определяется эмпирически путем вставки функции-кандидата в автомат и оценки его последующей производительности. В настоящее время существует значительный объем доказательств для нескольких игр, таких как шахматы, сёги и го, относительно общего состава функций оценки для них.
Игры, в которых игровые компьютерные программы используют функции оценки, включают шахматы , [2] го , [2] сёги (японские шахматы), [2] отелло , гексагон , нарды , [3] и шашки . [4] [5] Кроме того, с появлением таких программ, как MuZero , компьютерные программы также используют функции оценки для видеоигр , например, от Atari 2600. [6] Некоторые игры, такие как крестики -нолики , решаются строго и не требуют поиска или оценки, поскольку доступно дискретное дерево решений.
Дерево таких оценок обычно является частью алгоритма поиска, такого как поиск по дереву Монте-Карло или минимаксный алгоритм , такой как альфа-бета-поиск . Предполагается, что значение представляет собой относительную вероятность выигрыша, если игровое дерево было бы расширено от этого узла до конца игры. Функция смотрит только на текущую позицию (т. е. на каких клетках находятся фигуры и их взаимосвязь друг с другом) и не учитывает историю позиции или исследует возможные ходы вперед узла (следовательно, статическая). Это означает, что для динамических позиций, где существуют тактические угрозы, функция оценки не будет точной оценкой позиции. Такие позиции называются не- покоящимися ; они требуют по крайней мере ограниченного вида расширения поиска, называемого поиском покоя, для разрешения угроз перед оценкой. Некоторые значения, возвращаемые функциями оценки, являются абсолютными, а не эвристическими, если в узле происходит выигрыш, проигрыш или ничья.
Существует сложная связь между поиском и знаниями в функции оценки. Более глубокий поиск благоприятствует менее краткосрочным тактическим факторам и более тонким позиционным мотивам дальнего горизонта в оценке. Существует также компромисс между эффективностью закодированных знаний и вычислительной сложностью: вычисление подробных знаний может занять так много времени, что производительность снижается, поэтому приближения к точным знаниям часто лучше. Поскольку функция оценки зависит от номинальной глубины поиска, а также от расширений и сокращений, используемых в поиске, не существует общей или автономной формулировки для функции оценки. Функция оценки, которая хорошо работает в одном приложении, обычно должна быть существенно перенастроена или переобучена для эффективной работы в другом приложении.
В компьютерных шахматах выход функции оценки обычно является целым числом , а единицы функции оценки обычно называются пешками . Термин «пешка» относится к значению, когда у игрока на одну пешку больше, чем у противника в позиции, как объяснено в Относительная стоимость шахматной фигуры . Целое число 1 обычно представляет некоторую долю пешки, и в компьютерных шахматах обычно используются сентипешки , которые являются сотой частью пешки. Большие оценки указывают на материальный дисбаланс или позиционное преимущество или на то, что выигрыш материала обычно неизбежен. Очень большие оценки могут указывать на то, что мат неизбежен. Функция оценки также неявно кодирует значение права на ход, которое может варьироваться от небольшой доли пешки до выигрыша или проигрыша.
Исторически в компьютерных шахматах члены функции оценки конструируются (т. е. создаются вручную) разработчиком движка, а не обнаруживаются посредством обучения нейронных сетей . Общий подход к построению функций оценки вручную заключается в линейной комбинации различных взвешенных членов, определенных для влияния на ценность позиции. Однако не все члены в функции оценки вручную являются линейными, некоторые, такие как безопасность короля и структура пешек, являются нелинейными. Каждый член можно считать состоящим из факторов первого порядка (тех, которые зависят только от пространства и любой фигуры на нем), факторов второго порядка (пространство по отношению к другим пространствам) и факторов n-го порядка (зависимости от истории позиции).
Вручную созданная функция оценки обычно имеет термин материального баланса, который обычно доминирует в оценке. Обычные значения, используемые для материала, следующие: ферзь = 9, ладья = 5; конь или слон = 3; пешка = 1; королю присваивается произвольно большое значение, обычно большее, чем общее значение всех остальных фигур. [1] Кроме того, она обычно имеет набор позиционных терминов, которые обычно в сумме не превышают значение пешки, хотя в некоторых позициях позиционные термины могут быть намного больше, например, когда мат неизбежен. Вручную созданные функции оценки обычно содержат от десятков до сотен отдельных терминов.
На практике эффективные функции оценки, созданные вручную, создаются не путем расширения списка оцениваемых параметров, а путем тщательной настройки или обучения весов относительно друг друга, скромного набора параметров, таких как описанные выше. С этой целью используются позиции из различных баз данных, таких как из мастер-игр, игр движка, игр Lichess или даже из самостоятельной игры, как в обучении с подкреплением .
Пример функции оценки для шахмат, созданной вручную, может выглядеть следующим образом:
Каждый из членов представляет собой вес, умноженный на коэффициент разности: значение материальных или позиционных членов белого цвета за вычетом материальных или позиционных членов черного цвета.
Хотя нейронные сети использовались в функциях оценки шахматных движков с конца 1980-х годов, [7] [8] они не стали популярными в компьютерных шахматах до конца 2010-х годов, поскольку необходимое для обучения нейронных сетей оборудование в то время было недостаточно мощным, а быстрые алгоритмы обучения, топология и архитектура сетей еще не были разработаны. Первоначально функции оценки на основе нейронных сетей обычно состояли из одной нейронной сети для всей функции оценки с входными признаками, выбранными с доски, и чьи выходные данные представляли собой целое число , нормализованное по шкале сентипешек, так что значение 100 примерно эквивалентно материальному преимуществу пешки. Параметры в нейронных сетях обычно обучаются с использованием обучения с подкреплением или контролируемого обучения . Совсем недавно функции оценки в компьютерных шахматах начали использовать несколько нейронных сетей, причем каждая нейронная сеть обучалась для определенной части оценки, такой как структура пешек или эндшпиля. Это позволяет использовать гибридные подходы, где функция оценки состоит как из нейронных сетей, так и из вручную созданных терминов.
Глубокие нейронные сети использовались, хотя и нечасто, в компьютерных шахматах после того, как Giraffe Мэтью Лэя [9] в 2015 году и AlphaZero Deepmind в 2017 году продемонстрировали осуществимость глубоких нейронных сетей в оценочных функциях. Проект распределенных вычислений Leela Chess Zero был начат вскоре после этого, чтобы попытаться повторить результаты статьи AlphaZero Deepmind. Помимо размера сетей, нейронные сети, используемые в AlphaZero и Leela Chess Zero, также отличаются от тех, которые используются в традиционных шахматных движках, поскольку у них есть два выхода, один для оценки ( головка значения ) и один для упорядочивания ходов ( головка политики ), а не только один выход для оценки. [10] Кроме того, хотя можно установить вывод значения заголовка нейронной сети Лилы в виде действительного числа , чтобы приблизиться к шкале сентипешек, используемой в традиционных шахматных движках, по умолчанию вывод представляет собой проценты выигрыша-ничьи-проигрыша, вектор из трех значений каждое из единичного интервала . [10] Поскольку глубокие нейронные сети очень большие, движки, использующие глубокие нейронные сети в своей оценочной функции, обычно требуют графического процессора для эффективного вычисления оценочной функции.
Важной методикой оценки, по крайней мере с начала 1990-х годов, является использование таблиц фигур-квадратов (также называемых таблицами стоимости фигур) для оценки. [11] [12] Каждая таблица представляет собой набор из 64 значений, соответствующих клеткам шахматной доски. Самая базовая реализация таблицы фигур-квадратов состоит из отдельных таблиц для каждого типа фигур на игрока, что в шахматах приводит к 12 таблицам фигур-квадратов в общей сложности. Более сложные варианты таблиц фигур-квадратов используются в компьютерных шахматах, одним из самых известных является таблица король-фигура-квадратов, используемая в Stockfish , Komodo Dragon , Ethereal и многих других движках, где каждая таблица учитывает положение каждого типа фигуры по отношению к королю игрока, а не положение каждого типа фигуры в отдельности. Значения в таблицах являются бонусами/штрафами за расположение каждой фигуры на каждой клетке и кодируют совокупность многих тонких факторов, которые трудно количественно оценить аналитически. В функциях оценки, созданных вручную, иногда есть два набора таблиц: один для дебюта/миттельшпиля и один для эндшпиля; позиции миттельшпиля интерполируются между ними. [13]
Первоначально разработанная в компьютерных сёги в 2018 году Ю Насу, [14] [15] наиболее распространенной функцией оценки, используемой сегодня в компьютерных шахматах [ требуется ссылка ], является эффективно обновляемая нейронная сеть , или сокращенно NNUE , разреженная и неглубокая нейронная сеть , которая имеет только таблицы фигур-квадратов в качестве входных данных для нейронной сети. [16] Фактически, самая базовая архитектура NNUE - это просто 12 таблиц фигур-квадратов, описанных выше, нейронная сеть только с одним слоем и без функций активации . Эффективно обновляемая архитектура нейронной сети, использующая таблицы короля-фигуры-квадратов в качестве входных данных, была впервые перенесена в шахматы в производной от Stockfish под названием Stockfish NNUE, публично выпущенной 30 мая 2020 года, [17] и была принята многими другими движками, прежде чем в конечном итоге была включена в официальный движок Stockfish 6 августа 2020 года. [18] [19]
Шахматные движки часто используют таблицы эндшпиля в своей оценочной функции, поскольку это позволяет движку идеально играть в эндшпиле.
Исторически функции оценки в Computer Go учитывали как контролируемую территорию, так и влияние камней, количество заключенных и жизнь и смерть групп на доске. Однако современные компьютерные программы для игры в го в основном используют глубокие нейронные сети в своих функциях оценки, например AlphaGo , Leela Zero , Fine Art и KataGo , и выводят процент выигрышей/ничей/проигрышей, а не значение в количестве камней.