ИГРЫ, КОТОРЫЕ ВКЛЮЧАЮТ ЭЛЕМЕНТ СЛУЧАЙНОСТИ
В реальной жизни происходит много непредсказуемых внешних событий, из-за которых люди попадают в непредвиденные ситуации. Эта непредсказуемость отражается во многих играх за счет включения элемента случайности, такого как метание жребия. Таким образом, игры с элементов случайности позволяют нам на один шаг приблизиться к реальности и поэтому имеет смысл рассмотреть, как это отражается на процессе принятия решений.
Одной из типичных игр, в которых сочетается удача и искусство, являются нарды. Перед каждым своим ходом игрок бросает кубики для определения допустимых ходов. Например, в позиции игры в нарды, приведенной на рис. 6.8, белым выпали очки 6-5 и они имеют четыре возможных хода.
Хотя белым известно, каковы их допустимые ходы, они не знают, какие очки принесет метание жребия черным, и поэтому не могут определить, какими будут допустимые ходы черных. Это означает, что белые не имеют возможности сформировать стандартное дерево игры такого типа, которое встретилось нам в шахматах, а также крестиках-ноликах. Дерево игры в нарды, кроме узлов МАХ и MIN, должно включать узлы жеребьевки. Узлы жеребьевки обозначены на рис. 6.9 кружками. Ветви, ведущие от каждого узла жеребьевки, обозначают возможные результаты метания жребия, поэтому каждая из них отмечена надписью с указанием количества очков и вероятности, с которой могут быть получены эти очки. Существуют 36 различных сочетаний очков на двух кубиках, и все они являются равновероятными; но поскольку такие сочетания очков, как 6-5 и 5-6, являются одинаковыми, имеется только 21 различимое сочетание очков. Вероятность появления шести дублей (от 1-1 до 6-6) равна 1/36, а каждое из 15 остальных различных сочетаний очков имеет вероятность 1/18.
Следующий этап состоит в том, чтобы понять, как следует принимать правильные решения. Безусловно, и в этом случае требуется найти такой ход, который ведет к наилучшей позиции. Однако результирующие позиции не имеют определенных минимаксных значений. Вместо этого существует возможность вычислить только ожидаемое значение, в котором ожидаемый результат устанавливается с учетом всех возможных выпадений жребия, которые могут произойти. Это приводит к обобщению минимаксного значения для детерминированных игр до ожидаемого минимаксного значения (expectiminimax value) для игр с узлами жеребьевки. Терминальные узлы и узлы МАХ и MIN (для которых известны результаты жеребьевки) применяются точно так же, как и прежде, а узлы жеребьевки оцениваются путем получения взвешенного среднего значений, полученных в результате всех возможных выпадений жребия.
Результаты вычисления этих уравнений могут резервироваться рекурсивно во всех узлах вплоть до корня дерева точно так же, как и в минимаксном алгоритме. Оставляем читателю проработку всех деталей этого алгоритма в качестве упражнения.