Вероятностная оценка

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

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

Еще раз отметим некоторые частные особенности дерева игры в нарды, которые не были указаны для дерева нард. В дереве игры в нарды корневая вершина (ранга 0) - серая, вершины ранга 1 - белые, ранга 2 - серые, ранга 3 - черные, и так далее. Кроме того, количество с-ходов из одной вершины всегда равно 36. В таком случае их можно считать равновероятными. При этом действительно разных В-поддеревьев для вершин В, в которые ведут с-ходы, будет 21. Таким образом, дерево игры в нарды можно заменить на эквивалентное, в котором из одной серой вершины будет исходить 21 с-ход, и каждому из них будет приписан вес (соответствующий вероятности выпадения). Совпадение поддеревьев связано с тем, что в действительности с-ход - это бросок двух одинаковых кубиков, так что комбинации типа a-b и b-a считаются эквивалентными. Когда выбрана реализация дерева с 21 с-ходом, то с-ходам, соответствующим комбинациям кубиков типа a-a, приписывают вес 1, а всем остальным - вес 2.

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

Введем новую оценку позиций и сразу назовем ее вероятностной. Так же как и другие оценки, эта будет равняться крайним значениям в листьях дерева. Заметим здесь, что все листья дерева игры в нарды суть вершины с ходом серых, то есть к ним ведут б-ч-ходы. Вероятностную оценку вершины с б-ч-ходом будем считать как среднее арифметическое оценок вершин с с-ходом, к которым ведут б-ч-ходы из данной вершины. Аналогично, оценка в незаключительной вершине с с-ходом равна среднему арифметическому оценок вершин с б-ч-ходом, к которым ведут с-ходы из данной вершины (в случае с 21-бросковым вариантом дерева должны учитываться веса бросков). Итак, рекурсивно описана оценка любой вершины (соответственно и игровой позиции) в дереве игры. Возможность посчитать такую оценку на практике исключена в месте с возможностью построения полного дерева игры. Тем не менее, посмотрим, как ведет себя эта оценка. Очевидно, что она тем выше, чем больше среди потомков оцениваемой вершины листьев с победой белых, а также чем ближе эти листья к данной вершине расположены. Расположение листьев с победой черных влияет на оценку с точностью до наоборот. Другими словами, вероятностная оценка показывает соотношение выигрышных позиций белых и черных среди потомков оцениваемой позиции. Причем это соотношение имеет как количественный, так и качественный (близость победы) аспекты. Практически при крайних значениях 0 и 1 данная оценка соответствует вероятности победы белых при случайном выборе ходов обеими сторонами (при игре "в тяжелом цейтноте"). Это напрямую следует из рекурсивного построения оценки.

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

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

То, что вероятностная оценка отражает недетерминизм нард, может быть полезно для теоретического обоснования выбора функции риска, описанной выше. Дело в том, что функция риска - это именно та составляющая модернизированного метода максимина, которая призвана учитывать недетерминизм нард. Как сообщают авторы статьи "Б.Ф.Мельников, А.Н.Радионов. О выборе стратегии в недетерминированных антагонистических играх. - Программирование (РАН), 1998, N5, с.98-99", она успешно это делает. Но при этом отсутствуют какие бы то ни было теоретические предпосылки для процедуры ее построения. Функция риска в этой работе - чистая эвристика, и ее вид определяется лишь эмпирическими данными, в то время как исследование вероятностной оценки может дать какие-то подходы к систематизации ее синтеза.

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