[Содержание] [Предыдущая глава] [Следующая глава]
Одной из сложных позиционных игр, исследуемых в настоящее время на предмет построения играющей программы, является игра в короткие нарды (backgammon), которую мы в дальнейшем будем называть просто нарды. Это игра двух противников. В нее играют шашками на одномерном поле с 26 игровыми полями. Начальная позиция заключается в некоторой исходной расстановке шашек на игровых полях. Ходом игрок передвигает какие-то из своих шашек в одном направлении. Направления движения шашек разных игроков противоположны. Цель игры - первым вывести свои шашки на заключительное поле или сгруппировать их поближе к этому полю. Возможность игрока передвигать шашки определяется броском двух кубиков. Существует 36 равновероятных комбинаций выпадения кубиков, из них 21 принципиально разная. В сети интернет можно найти большое количество материалов по нескольким различным подходам к программированию игрока в нарды. Некоторая систематизация этих материалов произведена авторами [10]. Среди описанных здесь подходов - реализация самообучения по методу взбирания на холм, подробное рассмотрение которого содержится в главе 3 данной работы.
В статье [6] подробно описан один из подходов к данной задаче. Его суть вкратце в следующем. Игра, по аналогии с подходом из книги [1], описывается посредством дерева игры. Далее также по аналогии определяются оценки позиций, применяется а,b - эвристика. Кроме того, вводится такое новое понятие, как функция риска. Программа, построенная авторами статьи, добилась реальных успехов.
Так как нарды в большой степени отличаются от игр, подобных шахматам, то некоторые подходы из [1] не применимы в отношении нард. Основным отличием нард от шахмат является недетерминированность. Её привносит в нарды стохастический фактор, обусловленный бросанием кубиков. Этот фактор значительно усложняет исследование нард, но в то же время делает его более актуальным. Ведь подавляющее большинство явлений и процессов в действительности так или иначе связано с явлениями случайными, описываемыми вероятностно. В результате, дерево игры в нарды - дерево недетерминированной игры. В связи с этим возникает потребность дополнительном анализе дерева игры в нарды.
В начале определим дерево (в индуктивной форме). Элементами дерева являются вершины и дуги, то есть направленные ребра. При этом одна из инцидентных дуге вершин называется её началом, а другая - концом. Деревом является:
а) одна вершина;
б) дерево с добавленными вершиной и дугой, начинающейся в старой и заканчивающейся в новой вершине. Если старая вершина обозначена как А, а новая - В, то дуга из первой во вторую обозначается АВ или.
Корнем дерева называется вершина, в которую не ведет ни одна дуга. Концевой вершиной (листом) называют такую, из которой не исходит ни одна дуга. Непустое подмножество дерева A, составляющее дерево, называют поддеревом дерева A. Если B и C - поддеревья дерева A, а D - их непустое пересечение, то D - поддерево дерева A.
Говорят, что вершина В подчинена вершине А если:
а) В?А;
б) В - конец дуги, выходящей из вершины, подчиненной А.
Если А - вершина дерева A, то А-поддеревом дерева A называют такое его поддерево которое содержит все подчиненные A вершины, и только их. Если А - не корневая вершина, то открытым поддеревом называют А-поддерево вместе с дугой .Если из дерева A выбросить открытое А-поддерево, то оставшееся будет деревом.
Будем считать корень вершиной ранга 0. Если вершина А имеет ранг n, а АВ - дуга дерева, то вершина В имеет ранг n+1.
Пусть А - вершина дерева, В вершина А-поддерева, тогда веткой W(A,B) будем называть последовательность дуг АА1, А1А2, … , АsВ, принадлежащих дереву, если она существует. При этом если ветка W(A,B) существует, то она единственна.
Если всем вершинам дерева приписать цвета, выбирая из черного и белого, а всем листьям F - числа оц(F), то такое дерево будем называть деревом игры двух противников.
Именно такое дерево рассмотрено в [1] при определении оценок и доказательстве некоторых утверждений относительно этих оценок. Далее авторы [1] применяют этот аппарат для описания методов сокращения перебора в играх, подобных шахматам. Однако для нард такое дерево не может быть деревом игры, так как в них ход игрока не определяется лишь его выбором из возможных вариантов. На самом деле ход в нардах происходит в два этапа - сначала бросаются кубики, затем в зависимости от выпавших чисел выбирается ход. Таким образом, сам ход имеет двухступенчатую иерархическую структуру. Для упрощения модели будем считать, что кубики за обоих игроков бросает третья сторона, интересы которой не противоречат интересам ни белых ни черных, а стратегия выбирается случайно (при помощи кубиков). Эту сторону договоримся называть "серыми". Серые ходят вдвое чаще, чем любая из двух других сторон, они никогда не ходят дважды подряд (среди ходов белых и черных есть пустой ход). Ход серых не изменяет расположения шашек на доске, но изменяет другую составляющую позиции - выпавшие на кубиках числа. Теперь определим некий объект, пригодный для моделирования игр типа нард, и докажем для него утверждения, аналогичные доказанным в [1] для дерева игры двух противников.
Если всем вершинам дерева приписать цвета, выбирая из белого, серого и черного, а всем листьям F - числа оц(F), то такое дерево будем называть деревом игры трех противников. Дерево игры трех противников, в котором все дуги, заканчивающиеся листьями, исходят из белых или черных вершин, назовем деревом игры двух противников и нейтральной стороны, либо просто деревом нард (см. рис. 1). Именно дерево нард будем рассматривать вместо дерева игры двух противников для доказательства аналогичных утверждений. Заметим, что дерево нард во-первых не является частным случаем дерева игры двух противников, а во-вторых дерево игры в нарды является частным случаем дерева нард. Конечно, при этом нужно чтобы из игры в нарды была исключена возможность повторения игровых позиций с ходом одного цвета. Кстати дерево игры в шахматы тоже есть лишь частный случай дерева игры двух противников, причем в шахматах при моделировании также исключают возможность повторения позиций. Это оправдано, так как зацикленная игра ни в коем случае не может считаться оптимальной. Заметим что в дереве игры в нарды, в частности, все листья и корень - серого цвета, цвет вершины определяется остатком от деления ранга вершины на четыре, ветка от белой вершины к черной (или наоборот) всегда содержит серую. Но от этих свойств дерева игры в нарды утверждения сделанные для дерева нард не будут зависеть. Итак, мы рассматриваем общий случай для дерева игры в нарды - дерево нард.
Так же как для дерева игры двух противников, определим вершины дерева нард как позиции, листья как заключительные позиции, дуги как ходы (белых, серых, черных), ветвь от корня до одного из листьев F как партию, а число оц(F) как результат этой партии. Также будем считать, что оценка позиции - это результат, на который рассчитывают черные или белые, если партия играется с данной позиции (как с начальной). В отличие от случая двух противников будем различать ходы: ходы белых и черных будем называть б-ч-ходами, ходы серых - с-ходами. Таким образом, в нардах б-ч-ходы выбирают сами игроки, а с-ходы определяются случайно при помощи кубиков. В дальнейшем будем рассуждать о дереве нард, параллели с деревом игры двух противников будут подразумеваться.
Пусть A - дерево нард. Назовем B(А) б-усеченным деревом (относительно A), если:
1) B(А) получается из А-поддерева исключением некоторого числа открытых В-поддеревьев, где - ход белых.
2) Все заключительные позиции B(А) являются заключительными позициями дерева A т. е. В результате исключения не появилось новых.
Ч-усеченное дерево определяется аналогично.
Мы будем употреблять символическое неравенство (пока как иероглиф)
Оц(А) > М,
когда существует конечное б-усеченное дерево с корнем A, все заключительные позиции которого имеют оценки, и все они больше М. Аналогично, если М больше всех заключительных оценок некоторого ч-усеченного дерева с корнем А, мы будем писать
Оц(А) < М.
Для случая нестрогих неравенств изменение определений очевидно.
Пусть A - дерево нард и B - б-усеченное дерево. Тогда для каждой позиции А дерева B с ходом черных или серых в B содержатся все ходы, выходящие из А в дереве A, и хотя бы один ход, выходящий из А в дереве A, если А - незаключительная позиция с ходом белых. Справедливо также аналогичное утверждение, в котором белый и черный цвета поменялись местами.
Лемма. Если B1(А) - б-усеченное дерево дерева нард A и B2(А) - ч-усеченное дерево, то B = B1(А)?B2(А) - дерево и все его заключительные позиции являются заключительными позициями дерева A.
Доказательство: B - не пусто, так как содержит корень А и, следовательно, B - дерево. Пусть В B - незаключительная вершина A. Если цвет В - серый, то все ходы из В содержатся как в B1(А), так и в B2(А). Если цвет В - белый (черный), тогда все ходы из В содержатся в B2(А) (B1(А)) и хотя бы один в B1(А)( B2(А)). Таким образом, в любом случае вершина В - незаключительная.
Теорема о непротиворечивости. Если A - дерево нард, А A, то нельзя одновременно считать верными символические неравенства
оц(А) > М,
оц(А) ? М.
Доказательство: Символическое неравенство оц(А) > М означает, что существует б-усеченное дерево B1 с начальной позицией А и оценками всех заключительных позиций > М; неравенство оц(А) ? М - что существует ч-усеченное дерево с той же начальной позицией и оценками заключительных позиций ? М. Их пересечение содержит хотя бы одну заключительную позицию F, оценка которой должна быть как > М, так и ? М.
Определение. Если для позиции А дерева нард A выполняется
оц(А) ? m,
оц(А) ? М,
причем m0 - верхняя граница таких чисел m, а М0 - нижняя граница таких чисел М тогда число М0 называется верхней оценкой (обозначим как оц*(А)), а число m0 - нижней оценкой (обозначим как оц*(А)) позиции А. Заметим, что для любой заключительной позиции F
оц*(F) = оц*(F) = оц(F).
Во всех дальнейших рассуждениях об усеченных деревьях, позициях и ходах можно менять местами белый и черный цвета, меняя при этом знаки неравенств на противоположные. Как правило это не будет специально оговариваться.
Лемма. Пусть А - позиция дерева нард A с ходом белых и - выходящий из неё ход, причем оц(В) ? М (> М). Тогда оц(А) ? М (> М).
Доказательство: Так как оц(В) ? М, то существует б-усеченное дерево B с корнем В, у которого оценки всех заключительных позиций ? М. Тогда B+А (см. рис. 2) также является б-усеченным поддеревом с корнем А и теми же заключительными позициями, что и у B.
Лемма. Пусть А - позиция дерева нард A с ходом белых и АА1, АА2, … , ААn - все ходы из этой позиции. Если для всех позиций Аs (s = 1, 2, … , n) верно, что оц(Аs) ? М (< М), то и оц(А) ? М (< М).
Доказательство: Каждое неравенство оц(Аs) ? М следует из существования ч-усеченного дерева Bs с корнем Аs и оценками заключительных позиций ? М. Тогда А+B1+B2+…+Bn (см рис. 3) - ч-усеченное дерево с корнем А, у которого оценки всех заключительных позиций ? М.
Лемма. Пусть А - позиция дерева нард A с ходом серых и АА1, АА2, … , ААn - все ходы из этой позиции. Если для всех позиций Аs (s = 1, 2, … , n) верно, что оц(Аs) ? М (< М) и оц(Аs) ? m (> m), тогда оц(А) ? m (> m) и оц(А) ? M (< M).
Доказательство: Каждое неравенство оц(Аs) ? М (оц(Аs) ? m) следует из существования ч-усеченного (б-усеченного) дерева Bs с корнем Аs и оценками заключительных позиций ? М. Тогда А+B1+B2+…+Bn - ч-усеченное (б-усеченное) дерево с корнем А, у которого оценки всех заключительных позиций ? М (? m).
Теорема о переносе верхней и нижней оценок. Пусть А - вершина дерева нард A. Пусть также АА1, АА2, … , ААn - все ходы из этой позиции. Если все вершины Аs имеют оценки оц*(Аs) и оц*(Аs), тогда вершина А также имеет оценки оц*(А) и оц*(А), причем:
а) если А - вершина с ходом белых, то
оц*(А) = max оц*(Аs), (s = 1, 2, … , n),
оц*(А) = max оц*(Аs), (s = 1, 2, … , n);
б) если А - вершина с ходом черных, то
оц*(А) = min оц*(Аs), (s = 1, 2, … , n),
оц*(А) = min оц*(Аs), (s = 1, 2, … , n);
и) если А - вершина с ходом серых, то
оц*(А) = max оц*(Аs), (s = 1, 2, … , n),
оц*(А) = min оц*(Аs), (s = 1, 2, … , n).
Теорема о существовании верхней и нижней оценок. Если A - конечное дерево нард, и все его заключительные позиции имеют оценку, то каждая его позиция А имеет верхнюю и нижнюю оценки. Эти оценки полностью определяются А-поддеревом.
Доказательство: Все позиции максимального ранга А-поддерева дерева нард A имеют верхнюю и нижнюю оценки (так как они заключительные). Если все позиции А ранга > n имеют верхнюю и нижнюю оценки, то по теореме о переносе оценки все позиции ранга n также имеют верхнюю и нижнюю оценки.
Итак, верхняя и нижняя оценки позиции А дерева нард A удовлетворяют условиям:
оц*(А) = max оц*(В), (В M(А)), если в позиции А ход белых;
оц*(А) = min оц*(В), (В M(А)), если в позиции А ход черных;
оц*(А) = max оц*(В), (В M(А)), если в позиции А ход серых;
оц*(А) = max оц*(В), (В M(А)), если в позиции А ход белых;
оц*(А) = min оц*(В), (В M(А)), если в позиции А ход черных;
оц*(А) = min оц*(В), (В M(А)), если в позиции А ход серых;
где M(А) - множество позиций В, непосредственно следующих за А, т. е. Тех в которые ведут ходы АВ из позиции А. В след за авторами [1] будем называть эти условия формулами Цермело, так как последний в работе [8] предложил аналогичную формулу в качестве определения оценок незаключительных позиций.
Дж. фон Нейману принадлежит другое определение оценки [7]. Оно основано на понятии стратегии, т. е. заранее произведенного выбора хода в каждой позиции игры с ходом своего цвета. Если белые выбрали некоторую стратегию s из своего множества стратегий Sб, черные - стратегию s' из Sч, а серые s'' из Sс, то партия, которая будет сыграна, определяется однозначно. Если считать, что эта партия приводит в заключительную позицию F, имеющую оценку оц(F), тогда её результатом r(s,s',s'') называется оц(F).
Дж. фон Нейман предлагает выбирать такую стратегию, которая при наиболее злостном выборе стратегий противников дает лучший результат. Его он и называет оценкой начальной позиции. Таким образом определяются две оценки начальной позиции А0 дерева игры A (в нашем случае - дерева нард):
оцб(А0) = max(min r(s,s',s''),(s' Sч, s'' Sс)),(s Sб),
оцч(А0) = min(max r(s,s',s''),(s Sб, s'' Sс)),(s' Sч),
Оценки произвольной позиции В определяются из В-поддерева аналогичным образом.
Если дерево нард конечно, и каждая заключительная позиция имеет оценку, то для любой позиции В оцб(В) = оц*(В), оцч(В) = оц*(В) (где оц*(В), оц*(В) - определенные нами оценки).
Здесь обнаруживается различие результатов данной работы с аналогичными из [1]. Это различие заключается в том, что для дерева нард не удалось построить единой оценки незаключительной позиции, которая была бы эквивалентна оценке по Дж. фон Нейману. Другими словами применение чистого метода максимина в случае с деревом нард не дает удовлетворительного результата. В случае с двумя противниками оцб(А) = оцч(А), и если один из участников игры выбрал стратегию s, оптимальную по Дж. фон Нейману, и сообщил свой выбор противнику, то последний, заранее зная, каковы будут ответы на любые его ходы, всё равно не смог бы улучшить для себя результат партии. В теории игр это соответствует существованию седловой точки игры (в чистых стратегиях). В нашем же случае такого благоприятного эффекта не наблюдается. Неравенство верхней и нижней оценок появляется в момент выбора этих оценок для позиций с с-ходом, в то время как вычисление верхней и нижней оценок в позициях с б-ч-ходом идентично. Дело в том, что и белые, и черные предполагают действия серых наиболее неблагоприятными для себя. В действительности этого не происходит, да и не может происходить, потому что сколь действия серых неблагоприятны для белых, столь благоприятны они для черных. Если к тому же учесть, что действия серых в рассматриваемых нами играх определяются случайным образом, то можно полагать, что они действуют на руку белым в той же мере, что и черным. Своих целей они преследовать не могут, и партия не может завершиться после их хода (т. е. их победой). Таким образом, верхняя оценка может служить критерием выбора хода черных, если они предполагают катастрофическое развитие ситуации. Аналогично работает нижняя оценка для белых. В то же время одновременная катастрофа для обеих сторон исключена. Даже более того, наихудшее стечение обстоятельств (постоянное неудачное бросание кубиков) для какой-либо из сторон просто маловероятно. Очевидно, требуется иной подход к прогнозу действий серых, нежели тот "абсолютно пессимистичный", что был описан ранее. Сразу следует исключить из рассмотрения прямо противоположный подход, как обладающий всеми теми же недостатками. Теперь от общих рассуждений перейдем к более конкретным.
Теория игр в случае отсутствия седловой точки игры в чистых стратегиях предлагает поиск решения в смешанных стратегиях. Это значит, что каждой чистой стратегии нужно приписать некоторую вероятность, с которой она может быть выбрана. Решение нашей задачи при таком подходе очевидно - для серых выбирается такая смешанная стратегия, в которой все чистые имеют равные вероятности. Это соответствует фактическому случайному поведению серых. При этом появляется седловая точка, верхняя и нижняя оценки совпадают. Единую оценку в таком случае нужно считать так же, как раньше, только в позициях с ходом серых вычислять её как среднее арифметическое оценок позиций, в которые есть ход из данной. Заметим, что в любом случае все изменения должны происходить только при вычислении оценок в позициях с ходом серых, так как неопределенность именно их действий вызывает разночтения в методе вычисления оценок.
Так как исследуемые игры не требуют от игроков раскрытия выбранных ими стратегий, то приемлемыми можно считать любые смешанные стратеги, предполагаемые для действий серых. В частности те чистые стратегии, которые были выбраны в начале ("катастрофические" для игроков), также подходят. Вопрос лишь в эффективности данного выбора смешанной стратегии серых. Далее мы будем вместо вопроса о выборе смешанных стратегий, предполагаемых для действий серых, рассматривать вопрос о методе вычисления верхней и нижней оценок в позициях с с-ходом, ввиду того, что эти вопросы эквивалентны.
Игрок вычисляет оценку позиции с с-ходом как некоторую функцию от оценок позиций, в которые ведут с-ходы из данной. Будем называть эту функцию функцией риска. Итак, задача сводится к поиску функции риска. Функции риска, выбранные разными игроками, могут быть различными, что обуславливает различность верхней и нижней оценок позиций. Если оценки заключительных позиций расставить так, что бы аналогичным победам разных игроков соответствовали одинаковые по модулю числа, но разные по знаку, то можно сделать следующий вывод о свойствах функций риска. Если игроки выбирают функции риска по одному принципу, то равенство верхней и нижней оценок позиции определяется четностью функции риска. Поэтому среднее арифметическое - приводит к равенству оценок, а экстремум - не приводит.
С учетом использования функций риска, теорема о переносе оценок может быть переформулирована в общем случае, при этом формулы Цермело приобретают следующий вид:
оц*(А) = max оц*(В), (В M(А)), если в позиции А ход белых;
оц*(А) = min оц*(В), (В M(А)), если в позиции А ход черных;
оц*(А) = f*(В1, B2, … , Вn), (Вi M(А), i = 1, 2, … , n), если в позиции А ход серых;
оц*(А) = max оц*(В), (В M(А)), если в позиции А ход белых;
оц*(А) = min оц*(В), (В M(А)), если в позиции А ход черных;
оц*(А) = f*( В1, B2, … , Вn), (Вi M(А), i = 1, 2, … , n), если в позиции А ход серых;
где M(А) - множество позиций В, непосредственно следующих за А, f*, f * - функции риска выбранные белыми и черными соответственно. Принимая во внимание теорию белой игры, описанную в предисловии к [2] можно рассматривать только последние три формулы, так как именно они существенны для выбора хода белых. Соответственно разговор может вестись только об одной функции риска - f*.
К описанию использования функций риска остается добавить, что сравнение эффективности различных функций риска в настоящее время - дело практики. Некоторые результаты по этому поводу опубликованы в [6].
Теперь уделим немного отдельного внимания вероятностным свойствам дерева нард. Конкретно, рассмотрим дерево игры в нарды, как некий абстрактный объект. В принципе его можно построить целиком, но на практике для этого не хватит мощности современной ЭВМ. Тем не менее, мы покажем некоторые его свойства.
Еще раз отметим некоторые частные особенности дерева игры в нарды (см. рис. 4), которые не были указаны для дерева нард. В дереве игры в нарды корневая вершина (ранга 0) - серая, вершины ранга 1 - белые, ранга 2 - серые, ранга 3 - черные, и т. д. Кроме того, количество с-ходов из одной вершины всегда равно 36. В таком случае их можно считать равновероятными. При этом действительно разных В-поддеревьев для вершин В, в которые ведут с-ходы, будет 21. Таким образом, дерево игры в нарды можно заменить на эквивалентное, в котором из одной серой вершины будет исходить 21 с-ход, и каждому из них будет приписан вес (соответствующий вероятности выпадения). Совпадение поддеревьев связано с тем, что в действительности с-ход - это бросок двух одинаковых кубиков, так что комбинации типа a-b и b-a считаются эквивалентными. Когда выбрана реализация дерева с 21 с-ходом, то с-ходам соответствующим комбинациям кубиков типа a-a приписывают вес 1, а всем остальным - вес 2.
Как следует из определения, дерево нард может быть бесконечным. Для дерева игры в нарды, можно построить такую модель, которая будет конечной. Для этого все позиции с с-ходом, для которых ветвь от начальной позиции до данной содержит позиции идентичные данной (в плане расположения шашек и очередности хода) пометим как повторные. Далее удалим из данного дерева открытые А-поддеревья для всех повторных позиций А. Если в полученном дереве появились заключительные позиции, которых не было в исходном, то удалим их вместе с б-ч-ходами, ведущими к ним. Последнюю операцию будем повторять, пока в полученном дереве будут оставаться заключительные позиции, которых нет в исходном. В итоге получим конечное дерево, которое можно рассматривать вместо исходного. Произведенная операция с деревом соответствует исключению в игре повторения позиций при выборе хода. Такое повторение не исключено в связи с тем, что ходя все шашки в нардах движутся каждая в своем одном направлении, движение шашки может быть прервано - ее могут сбить. В ситуации взаимного сбивания шашек, возможно повторение их расположения при одной очередности хода. В оптимальной игре такое недопустимо, чему и служит усечение дерева игры в нарды до конечного.
Введем новую оценку позиций и сразу назовем её вероятностной. Так же, как и другие оценки, эта будет равняться крайним значениям в листьях дерева. Заметим здесь, что все листья дерева игры в нарды суть вершины с ходом серых, то есть к ним ведут б-ч-ходы. Вероятностную оценку вершины с б-ч-ходом будем считать как среднее арифметическое оценок вершин с с-ходом, к которым ведут б-ч-ходы из данной вершины. Аналогично, оценка в незаключительной вершине с с-ходом равна среднему арифметическому оценок вершин с б-ч-ходом к которым ведут с-ходы из данной вершины (в случае с 21-бросковым вариантом дерева должны учитываться веса бросков). Итак, рекурсивно описана оценка любой вершины (соответственно и игровой позиции) в дереве игры. Возможность посчитать такую оценку на практике исключена в месте с возможностью построения полного дерева игры. Тем не менее, посмотрим, как ведет себя эта оценка. Очевидно, что она тем выше, чем больше среди потомков оцениваемой вершины листьев с победой белых, а так же чем ближе эти листья к данной вершине расположены. Расположение листьев с победой черных влияет на оценку с точностью до наоборот. Другими словами, вероятностная оценка показывает соотношение выигрышных позиций белых и черных среди потомков оцениваемой позиции. Причем это соотношение имеет как количественный, так и качественный (близость победы) аспекты. Практически, при крайних значениях 0 и 1 данная оценка соответствует вероятности победы белых при случайном выборе ходов обеими сторонами (при игре "в тяжелом цейтноте"). Это напрямую следует из рекурсивного построения оценки.
Возникает вопрос, насколько эта оценка полезна для выбора наилучшего хода. С одной стороны в этой оценке абсолютно не учитывается противоположность интересов игроков. В детерминированной игре, скажем в шахматах, такая оценка наверняка была бы практически бесполезной. Но в нашем случае детерминизм отсутствует. То есть ход игры лишь частично контролируется действиями игроков. На каждом втором шаге он определяется случайностью. Это заставляет сделать вывод, что вероятностная оценка, пусть не полностью, но отражает преимущества и недостатки позиций и, наряду с другими оценками, может приниматься во внимание в процессе выбора наилучшего хода. Кроме того, существует еще фактор цейтнота, то есть нехватки времени на обдумывание хода. Под влиянием этого фактора любой ход (не бросок) несет в себе некоторую стохастическую составляющую. Это также является доводом в пользу информативности вероятностной оценки.
Второй важный вопрос касается возможности, осуществимости практического использования вероятностной оценки. Этот вопрос отчасти остается открытым, но существует конкретное предложение, как посчитать эту оценку. Так же как и другие оценки, вероятностная оценка не может быть получена с абсолютной точностью, но может быть построено некоторое приближение к ней. Предлагаемый подход связан со свойством вероятностной оценки быть равной вероятности победы белых при неконтролируемой игроками игре. Если из данной позиции сыграть достаточное количество партий со случайным выбором ходов, то частота побед белых в таком случае даст представление о вероятностной оценке позиции. При этом придется выполнить работу по генерации ходов в количестве приблизительно равном среднему числу ходов в партии при данной начальной позиции умноженному на количество играемых партий. Объем расчетов в таком случае напрямую зависит от предполагаемой точности приближения. Отметим также, что с приближением к завершающей фазе партии, объем работ по нахождению приближения сокращается (так как остается лишь доигрывать партию), а точность при фиксированном количестве играемых случайных партий возрастает (так как сокращается общее количество листьев в поддереве, соответствующем оцениваемой позиции). Следовательно, даже если данный подход не оправдает себя при оценке позиций в начальной фазе игры, он может оправдать себя в конечной фазе. Так или иначе, этот подход требует дальнейшего исследования, которое уже планируется.
То, что вероятностная оценка отражает недетерминизм нард, может быть полезно для теоретического обоснования выбора функции риска, описанной выше. Дело в том, что функция риска - это именно та составляющая модернизированного метода максимина, которая призвана учитывать недетерминизм нард. Как сообщают авторы статьи [6], она успешно это делает. Но при этом отсутствуют какие бы то ни было теоретические предпосылки для процедуры её построения. Функция риска в этой работе - чистая эвристика, и её вид определяется лишь эмпирическими данными, в то время как исследование вероятностной оценки может дать какие-то подходы к систематизации её синтеза.
[Содержание] [Предыдущая глава] [Следующая глава]