Оценки позиций

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

Если всем вершинам дерева приписать цвета, выбирая из черного и белого, а всем листьям F - числа оц(F), то такое дерево будем называть деревом игры двух противников.

Именно такое дерево рассмотрено в "Г.М.Адельсон-Вельский, В.Л.Арлазаров, М.В.Донской. Программирование игр. - М.: Наука, 1978" при определении оценок и доказательстве некоторых утверждений относительно этих оценок. Далее авторы "Г.М.Адельсон-Вельский, В.Л.Арлазаров, М.В.Донской. Программирование игр. - М.: Наука, 1978" применяют этот аппарат для описания методов сокращения перебора в играх, подобных шахматам. Однако для нард такое дерево не может быть деревом игры, так как в них ход игрока не определяется лишь его выбором из возможных вариантов. На самом деле ход в нардах происходит в два этапа - сначала бросаются кубики, затем в зависимости от выпавших чисел выбирается ход. Таким образом, сам ход имеет двухступенчатую иерархическую структуру.

Для упрощения модели будем считать, что кубики за обоих игроков бросает третья сторона, интересы которой не противоречат интересам ни белых ни черных, а стратегия выбирается случайно (при помощи кубиков). Эту сторону договоримся называть "серыми". Серые ходят вдвое чаще, чем любая из двух других сторон, они никогда не ходят дважды подряд (среди ходов белых и черных есть пустой ход). Ход серых не изменяет расположения шашек на доске, но изменяет другую составляющую позиции - выпавшие на кубиках числа. Теперь определим некий объект, пригодный для моделирования игр типа нард, и докажем для него утверждения, аналогичные доказанным в "Г.М.Адельсон-Вельский, В.Л.Арлазаров, М.В.Донской. Программирование игр. - М.: Наука, 1978" для дерева игры двух противников.

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

Заметим, что дерево нард, во-первых, не является частным случаем дерева игры двух противников, а во-вторых, дерево игры в нарды является частным случаем дерева нард. Конечно, при этом нужно чтобы из игры в нарды была исключена возможность повторения игровых позиций с ходом одного цвета. Кстати, дерево игры в шахматы тоже есть лишь частный случай дерева игры двух противников, причем в шахматах при моделировании также исключают возможность повторения позиций. Это оправдано, так как зацикленная игра ни в коем случае не может считаться оптимальной.

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

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

Пусть A - дерево нард. Назовем B(А) б-усеченным деревом (относительно A), если: 1) B(А) получается из А-поддерева исключением некоторого числа открытых В-поддеревьев; 2) все заключительные позиции B(А) являются заключительными позициями дерева A, то есть в результате исключения не появилось новых. Ч-усеченное дерево определяется аналогично.

Мы будем употреблять символическое неравенство (пока как иероглиф): оц(А)>m, когда существует конечное б-усеченное дерево с корнем A, все заключительные позиции которого имеют оценки, и все они больше m. Аналогично, если m больше всех заключительных оценок некоторого ч-усеченного дерева с корнем А, мы будем писать: оц(А)<m. Для случая нестрогих неравенств изменение определений очевидно.

Пусть A - дерево нард и B - б-усеченное дерево. Тогда для каждой позиции А дерева B с ходом черных или серых в B содержатся все ходы, выходящие из А в дереве A, и хотя бы один ход, выходящий из А в дереве A, если А - незаключительная позиция с ходом белых. Справедливо также аналогичное утверждение, в котором белый и черный цвета поменялись местами.

Лемма. Если B₁(А) - б-усеченное дерево дерева нард A и B₂(А) - ч-усеченное дерево, то B=B₁(А)?B₂(А) - дерево и все его заключительные позиции являются заключительными позициями дерева A.

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

Теорема о непротиворечивости. Если A - дерево нард, то нельзя одновременно считать верными символические неравенства оц(А)>m, оц(А)?m.

Доказательство: Символическое неравенство оц(А)>m означает, что существует б-усеченное дерево B₁ с начальной позицией А и оценками всех заключительных позиций >m; неравенство оц(А)?m - что существует ч-усеченное дерево с той же начальной позицией и оценками заключительных позиций ?m. Их пересечение содержит хотя бы одну заключительную позицию F, оценка которой должна быть как >m, так и ?m.

Определение. Если для позиции А дерева нард A выполняется оц(А)?m, причем m₀ - верхняя граница таких чисел m, а M₀ - нижняя граница таких чисел М, тогда число M₀ называется верхней оценкой (обозначим как оц^*(А)), а число m₀ - нижней оценкой (обозначим как оц_*(А)) позиции А. Заметим, что для любой заключительной позиции F: оц^*(А)=оц_*(F)=оц(F).

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

Лемма. Пусть А - позиция дерева нард A с ходом белых и B - выходящий из нее ход, причем оц(В)?m (>m). Тогда оц(А)?m (>m).

Доказательство: Так как оц(В)?m, то существует б-усеченное дерево B с корнем В, у которого оценки всех заключительных позиций ?m. Тогда B+А также является б-усеченным поддеревом с корнем А и теми же заключительными позициями, что и у B.

Лемма. Пусть А - позиция дерева нард A с ходом белых и АА₁, АА₂, ..., АА_n - все ходы из этой позиции. Если для всех позиций А_s (s=1,2,...,n) верно, что оц(А_s)?m (<m), то и оц(А)?m (<m).

Доказательство: Каждое неравенство оц(А_s)?m следует из существования ч-усеченного дерева B_s с корнем А_s и оценками заключительных позиций ?m. Тогда А+B₁+B₂+...+B_n - ч-усеченное дерево с корнем А, у которого оценки всех заключительных позиций ?m.

Лемма. Пусть А - позиция дерева нард A с ходом серых и АА₁, АА₂, ..., АА_n - все ходы из этой позиции. Если для всех позиций А_s (s=1,2,...,n) верно, что оц(А_s)?m (<m) и оц(А_s)?M (>M), тогда оц(А)?M (>M) и оц(А)?m (<m).

Доказательство: Каждое неравенство оц(А_s)?m (оц(А_s)?M) следует из существования ч-усеченного (б-усеченного) дерева B_s с корнем А_s и оценками заключительных позиций ?m. Тогда А+B₁+B₂+...+B_n - ч-усеченное (б-усеченное) дерево с корнем А, у которого оценки всех заключительных позиций ?m (?M).

Теорема о переносе верхней и нижней оценок. Пусть А - вершина дерева нард A. Пусть также АА₁, АА₂, ..., АА_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 оц^*(B), (Вm(А)), если в позиции А ход белых; оц^*(А)=min оц^*(B), (Вm(А)), если в позиции А ход черных; оц^*(А)=max оц^*(B), (Вm(А)), если в позиции А ход серых; оц_*(А)=max оц_*(B), (Вm(А)), если в позиции А ход белых; оц_*(А)=min оц_*(B), (Вm(А)), если в позиции А ход черных; оц_*(А)=min оц_*(B), (Вm(А)), если в позиции А ход серых; где m(А) - множество позиций В, непосредственно следующих за А, то есть тех, в которые ведут ходы АВ из позиции А. Вслед за авторами "Г.М.Адельсон-Вельский, В.Л.Арлазаров, М.В.Донской. Программирование игр. - М.: Наука, 1978" будем называть эти условия формулами Цермело, так как последний в работе "Э.О.Цермело. Применение теории множеств к теории шахматной игры. - В книге: Матричные игры. М.: Физматгиз, 1961, с.167-172" предложил аналогичную формулу в качестве определения оценок незаключительных позиций.

Дж.фон Нейману принадлежит другое определение оценки "Дж.фон Нейман. Теория игр и экономическое поведение. - М.: Наука, 1970". Оно основано на понятии стратегии, то есть заранее произведенного выбора хода в каждой позиции игры с ходом своего цвета. Если белые выбрали некоторую стратегию s из своего множества стратегий S_б, черные - стратегию s' из S_ч, а серые s'' из S_с, то партия, которая будет сыграна, определяется однозначно. Если считать, что эта партия приводит в заключительную позицию F, имеющую оценку оц(F), тогда ее результатом r(s,s',s'') называется оц(F).

Дж.фон Нейман предлагает выбирать такую стратегию, которая при наиболее злостном выборе стратегий противников дает лучший результат. Его он и называет оценкой начальной позиции. Таким образом определяются две оценки начальной позиции A₀ дерева игры A (в нашем случае - дерева нард): оц_б(A₀)=max(min r(s,s',s''),(s'S_ч,s''S_с)),(sS_б), оц_ч(A₀)=min(max r(s,s',s''),(sS_б,s''S_с)),(s'S_ч), оценки произвольной позиции В определяются из В-поддерева аналогичным образом.

Если дерево нард конечно, и каждая заключительная позиция имеет оценку, то для любой позиции В: оц_б(B)=оц^*(B), оц_ч(B)=оц_*(B) (где оц^*(B), оц_*(B) - определенные нами оценки).

Здесь обнаруживается различие результатов данной работы с аналогичными из "Г.М.Адельсон-Вельский, В.Л.Арлазаров, М.В.Донской. Программирование игр. - М.: Наука, 1978". Это различие заключается в том, что для дерева нард не удалось построить единой оценки незаключительной позиции, которая была бы эквивалентна оценке по Дж.фон Нейману. Другими словами применение чистого метода максимина в случае с деревом нард не дает удовлетворительного результата. В случае с двумя противниками оц_б(A)=оц_ч(A), и если один из участников игры выбрал стратегию s, оптимальную по Дж.фон Нейману, и сообщил свой выбор противнику, то последний, заранее зная, каковы будут ответы на любые его ходы, все равно не смог бы улучшить для себя результат партии.

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

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

Теория игр в случае отсутствия седловой точки игры в чистых стратегиях предлагает поиск решения в смешанных стратегиях. Это значит, что каждой чистой стратегии нужно приписать некоторую вероятность, с которой она может быть выбрана. Решение нашей задачи при таком подходе очевидно - для серых выбирается такая смешанная стратегия, в которой все чистые имеют равные вероятности. Это соответствует фактическому случайному поведению серых. При этом появляется седловая точка, верхняя и нижняя оценки совпадают. Единую оценку в таком случае нужно считать так же, как раньше, только в позициях с ходом серых вычислять ее как среднее арифметическое оценок позиций, в которые есть ход из данной. Заметим, что в любом случае все изменения должны происходить только при вычислении оценок в позициях с ходом серых, так как неопределенность именно их действий вызывает разночтения в методе вычисления оценок.

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