Оценка позиции в играх с узлами жеребьевки
По аналогии с минимаксными значениями, очевидный подход к использованию ожидаемых минимаксных значений состоит в том, чтобы останавливать поиск в некоторой точке и применять функцию оценки к каждому листу. На первый взгляд может показаться, что функции оценки для таких игр, как нарды, должны быть полностью подобными функциям оценки для шахмат, ведь от них требуется лишь то, чтобы они присваивали более высокие оценки лучшим позициям. Но в действительности наличие узлов жеребьевки означает, что требуется более тщательный анализ смысла таких оценочных значений. На рис. 6.10 показано, что происходит в играх с элементами случайности — при использовании функции оценки, которая присваивает листьям значения [1,2,3,4], наилучшим является ход Аи а если присваиваются значения [1,20,30,400], наилучшим становится ход А2. Поэтому программа ведет себя полностью по-разному, если вносятся изменения в шкалу некоторых оценочных значений! Как оказалось, такой чувствительности к изменению шкалы можно избежать при условии, что функция оценки представляет собой положительную линейную трансформацию вероятности выигрыша из некоторой позиции (или, в более общем смысле, ожидаемой полезности данной позиции). В этом состоит важное и общее свойство ситуаций, связанных с наличием неопределенности, и это свойство дополнительно рассматривается в главе 16.
Сложность оценки ожидаемых минимаксных значений
Если бы в программе были заранее известны все выпадения жребия, которые должны произойти в течение остальной части игры, то поиск решения в игре с жеребьевкой был бы полностью аналогичным поиску решения в игре без жеребьевки, который осуществляется минимаксным алгоритмом поиска за время 0(Ьт). Но поскольку в алгоритме, использующем ожидаемые минимаксные значения, рассматриваются также все возможные последовательности выпадения жребия, для его работы требуется время 0( JbW1), где п — количество различных вариантов выпадения жребия.
Даже если глубина поиска ограничена некоторой небольшой величиной d, из-за таких дополнительных затрат времени, намного более значительных по сравнению с минимаксным алгоритмом, в большинстве игр с элементами случайности становится неосуществимым стремление заглянуть в дерево поиска на очень большую глубину. В нардах п равно 21, а Ь обычно составляет приблизительно 20, но в некоторых ситуациях может достигать величины 4000 для выпадений жребия, включающих повторяющиеся очки. По-видимому, все, на что можно рассчитывать, — это заглянуть вперед на три полухода.
Еще один способ размышления об этой проблеме состоит в следующем: преимуществом альфа-бета-поиска является то, что в нем игнорируются будущие направления развития игры, которые просто не должны быть реализованы, если в игре всегда выбирается наилучший ход. Поэтому альфа-бета-поиск сосредоточивается на наиболее вероятных событиях. В играх с жеребьевкой вероятных последовательностей ходов не может быть, поскольку, для того, чтобы были сделаны данные ходы, вначале должен выпасть правильный жребий, который сделал бы их допустимыми. В этом заключается общая проблема, возникающая в любой такой ситуации, когда в картину мира вмешивается неопределенность: количество вариантов дальнейших действий умножается в чрезвычайной степени, а формирование подробных планов действий становится бессмысленным, поскольку мир, скорее всего, будет играть совсем в другую игру.
Несомненно, читателю уже приходила в голову мысль, что к деревьям игр с узлами жеребьевки, по-видимому, можно было бы применить какой-то метод, подобный альфа-бета-отсечению. Как оказалась, такая возможность действительно существует. Анализ узлов MIN и МАХ остается неизменным, но можно также обеспечить отсечение узлов жеребьевки с использованием некоторой доли изобретательности. Рассмотрим узел жеребьевки С, приведенный на рис. 6.9, и определим, что будет происходить со значением этого узла по мере исследования и оценки его дочерних узлов. Можно ли найти верхний предел значения С до того, как будут проверены все его дочерние узлы? (Напомним, что именно это требуется в альфа-бета-поиске для того, чтобы можно было выполнить отсечение узла и его поддерева.) На первый взгляд такое требование может показаться невыполнимым, поскольку значение узла С представляет собой среднее значение его дочерних узлов. А до тех пор пока не будут рассмотрены все выпадения жребия, это среднее может представлять собой что угодно, поскольку сами неисследованные дочерние узлы могут иметь вообще любое значение. Тем не менее, если будут установлены пределы допустимых значений функции полезности, то появится возможность определять пределы и этого среднего. Например, если будет установлено, что все значения полезности находятся в пределах от
+3 до -3, то значения листовых узлов становятся ограниченными, а это, в свою очередь, позволяет установить верхний предел значения узла жеребьевки, не рассматривая все его дочерние узлы.