Функция оценки полезности игры

Привет, мой друг, тебе интересно узнать все про функция оценки полезности игры, тогда с вдохновением прочти до конца. Для того чтобы лучше понимать что такое функция оценки полезности игры , настоятельно рекомендую прочитать все из категории Математические методы исследования операций .Теория игр и расписаний..

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

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

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

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

Рассмотрим эту идею немного более конкретно. Функции оценки чаще всего действуют по принципу вычисления различных характеристик данного состояния, например, в шахматах одной из таких характеристик является количество пешек, принадлежащих каждой из сторон. Об этом говорит сайт https://intellect.icu . Эти характеристики, вместе взятые, определяют различные категории, или классы эквивалентности состояний: состояния из каждой категории имеют одни и те же значения для всех своих характеристик.

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

Например, предположим, полученный опыт показывает, что 72% состояний, встретившихся в данной категории, едут к победе (полезность +1); 20% — к поражению (-1) и 8% к ничьей (0). В таком случае приемлемой оценкой для состояний этой категории становится взвешенное среднее, или дожидаемое значение: (0.72x + 1) + (0.20x - 1) + (0.08x0) = 0.52

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

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

Например, в учебниках по шахматам для начинающих можно найти приближенные оценки стоимости материала для каждой фигуры: например, такие, что пешка имеет стоимость 1, конь или слон— 3, ладья— 5, а ферзь— 9. Другие характеристики, такие как "хорошая пешечная структура" и "безопасность короля", могут оцениваться как равные, скажем, половине стоимости пешки. После этого стоимости таких характеристик просто складываются для получения оценки позиции. Надежное преимущество, эквивалентное стоимости пешки, расценивается как значительная вероятность выигрыша, а надежное преимущество в три пешки должно почти наверняка обеспечить победу, как показано на рисунке.

В математике функция оценки такого типа называется взвешенной линейной функцией, поскольку она может быть представлена следующим образом:

где каждый коэффициент w_i представляет собой вес, а каждая функция f_i оценивает некоторую характеристику позиции. В шахматах функция f_i может определять количество на доске фигур каждого вида, а коэффициент w_i — оценивать стоимости этих фигур A за пешку, 3 за слона и т.д.).

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

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

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

Если я не полностью рассказал про функция оценки полезности игры? Напиши в комментариях Надеюсь, что теперь ты понял что такое функция оценки полезности игры и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Математические методы исследования операций .Теория игр и расписаний.