Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 65
Текст из файла (страница 65)
Задача устранения 'а. эффекта горизонта является более сложной. Этот эффект возникает, если программа сталкивается с каким-то ходом противника, который причиняет серьезный ущерб и в конечном итоге является неизбежным. Рассмотрим шахматную позицию, приведенную на рис. 6.7. Черные превосходят белых по количеству материала, но если белые смогут продвинуть свою пешку с седьмой горизонтали на восьмую, то пешка станет ферзем и обеспечит легкую победу белых. Черные могут отсрочить этот итог на 14 полуходов, объявляя шах белым с помощью ладьи, но пешка неизбежно станет ферзем. Одним из недостатков поиска на фиксированную глубину является то, что применяемый при Глава 6.
Поиск в условиях противодействия 257 без дальнейшего рассмотрения. Очевидно, что большинство людей, играющих в шахматы, рассматривают лишь несколько ходов из каждой позиции (по крайней мере, сознательно). К сожалению, этот подход является довольно опасным, поскольку нет никакой гарантии того, что не произойдет отсечение лучшего хода. А если отсечение применяется недалеко от корня, результат может оказаться катастрофическим, поскольку слишком часто возникают такие ситуации, что программа пропускает некоторые "очевидные'* ходы. Предварительное отсечение может использоваться безопасно в особых ситуациях (например, если два хода являются симметричными или эквивалентными по каким-то другим признаками, то необходимо рассматривать только один из них) или при анализе узлов, которые находятся глубоко в дереве поиска.
В результате совместного использования всех методов, описанных выше, появляется возможность создать программу, которая неплохо играет в шахматы (или другие игры). Предположим, что реализована функция оценки для шахмат, предусмотрена разумная проверка останова в сочетании с поиском спокойной позиции, а также предусмотрена большая таблица транспозиций. Кроме того, предположим, что, затратив целые месяцы на скрупулезную разработку программ, функционирующих на уровне битов, мы получили возможность формировать и оценивать примерно миллион узлов в секунду на новейшем персональном компьютере, что позволяет выполнять поиск приблизительно среди 200 миллионов узлов в расчете на каждый ход при стандартном контроле времени (три минуты на каждый ход).
Коэффициент ветвления для шахмат составляет в среднем примерно 35, а 35' равно приблизительно 50 миллионам, поэтому прн использовании минимаксного поиска мы получим возможность заглядывать вперед лишь приблизительно на пять полуходов. Такая программа, хотя и не совсем некомпетентная, может быть легко обманута человеком, игроком в шахматы среднего уровня, который иногда способен планировать на шесть илн восемь полуходов вперед.
Альфа- бета-поиск позволяет достичь глубины приблизительно в 10 полуходов, что приводит к усилению игры до уровня мастера. В разделе 6.7 описаны дополнительные методы отсечения, которые позволяют увеличить эффективную глубину поиска примерно до 14 полуходов. Чтобы достичь уровня гроссмейстера, требуется тщательно настроенная функция оценки и большая база данных с записями оптимальных ходов в дебюте и эндшпиле.
Не мешало бы также иметь суперкомпьютер для эксплуатации на нем такой программы! 6.5. ИГРЫ, КОТОРЫЕ ВКЛЮЧАЮТ ЭЛЕМЕНТ СЛУЧАЙНОСТИ В реальной жизни происходит много непредсказуемых внешних событий, из-за которых люди попадают в непредвиденные ситуации. Эта непредсказуемость отражается во многих играх за счет включения элемента случайности, такого как метание жребия. Таким образом, игры с элементов случайности позволяют нам на один шаг приблизиться к реальности и поэтому имеет смысл рассмотреть, как это отражается на процессе принятия решений. Одной из типичных игр, в которых сочетается удача и искусство, являются нарды. Перед каждым своим ходом игрок бросает кубики для определения допустимых и~'~а ~1, и "-." Глава 6.
Поиск в условиях противодействия 261 Сложность оценки ожцдаемьгх мннимаксных значений Если бы в программе были заранее известны все выпадения жребия, которые должны произойти в течение остальной части игры, то поиск решения в игре с жеребьевкой был бы полностью аналогичным поиску решения в игре без жеребьевки, который осушествляется минимаксным алгоритмом поиска за время о(Ь ) . Но поскольку в алгоритме, использующем ожидаемые минимаксные значения, рассматриваются также все возможные последовательности выпадения жребия, для его работы требуется время о(.Ь и ), где и — количество различных вариантов выпадения жребия.
Даже если глубина поиска ограничена некоторой небольшой величиной с), из-за таких дополнительных затрат времени, намного более значительных по сравнению с минимаксным алгоритмом, в большинстве игр с элементами случайности становится неосушествимым стремление заглянуть в дерево поиска на очень большую глубину. В нардах п равно 21, а Ь обычно составляет приблизительно 20, но в некоторых ситуациях может достигать величины 4000 для выпадений жребия, включающих повторяющиеся очки. По-видимому, все, на что можно рассчитывать, — это заглянуть вперед на три полухода. Еше один способ размышления об этой проблеме состоит в следующем: преимушеством альфа-бета-поиска является то, что в нем игнорируются будущие направления развития игры, которые просто не должны быть реализованы, если в игре всегда выбирается наилучший ход.
Поэтому альфа-бета-поиск сосредоточивается на наиболее вероятных событиях. В играх с жеребьевкой вероятных последовательностей ходов не может быть, поскольку, для того, чтобы были сделаны данные ходы, вначале должен выпасть правильный жребий, который сделал бы их допустимыми. В этом заключается общая проблема, возникаюшая в любой такой ситуации, когда в картину мира вмешивается неопределенность: количество вариантов дальнейших действий умножается в чрезвычайной степени, а формирование подробных планов действий становится бессмысленным, поскольку мир, скорее всего, будет играть совсем в другую игру. Несомненно, читателю уже приходила в голову мысль, что к деревьям игр с узлами жеребьевки, по-видимому, можно было бы применить какой-то метод, подобный альфа-бета-отсечению. Как оказалась, такая возможность действительно сушествует.
Анализ узлов М1М и М))х остается неизменным, но можно также обеспечить отсечение узлов жеребьевки с использованием некоторой доли изобретательности. Рассмотрим узел жеребьевки с, приведенный на рис. 6.9, и определим, что будет происходить со значением этого узла по мере исследования и оценки его дочерних узлов. Можно ли найти верхний предел значения С до того, как будут проверены все его дочерние узлы? (Напомним, что именно это требуется в альфа-бета-поиске для того, чтобы можно было выполнить отсечение узла и его поддерева.) На первый взгляд такое требование может показаться невыполнимым, поскольку значение узла С представляет собой среднее значение его дочерних узлов.
А до тех пор пока не будут рассмотрены все выпадения жребия, это среднее может представлять собой что угодно, поскольку сами неисследованные дочерние узлы могут иметь вообше любое значение. Тем не менее, если будут установлены пределы допустимых значений функции полезности, то появится возможность определять пределы и этого среднего. Например, если будет установлено, что все значения полезности находятся в пределах от 262 Часть 11. Решение проблем + 3 до -3, то значения листовых узлов становятся ограниченными, а это, в свою очередь, позволяет установить верхний предел значения узла жеребьевки, не рассматривая все его дочерние узлы.
Карточные игры Карточные игры интересны не только тем, что они часто бывают связаны с денежными ставками, но и по многим другим причинам. Количество различных вариантов карточных игр чрезвычайно велико, но в данной главе мы сосредоточимся на таких вариантах, в которых карты тасуют случайным образом в начале игры и каждый игрок получает на руки карты, которые он не показывает другим игрокам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
