|
Главная 5 в ряд
|
Описание алгоритма компьютерного игрока
Вычисление качества узлов с потомкамиТеперь под качеством будем понимать просто вероятность нашего выигрыша. Вопрос с качеством конечных узлов не стоит - либо 0, либо 1, в зависимости от результата игры в сложившейся ситуации. Один из возможных подходов к оценке качества недостроенных узлов описан выше. Остаются узлы с потомками. В случае полного дерева (и соответственно только нулевых и единичных вероятностей) вопрос даже не возникает - выше была описана простая процедура, распространяющая оценку от узлов с известной вероятностью в направлении корня. Но теперь у нас большинство узлов "немножко выигрышные и немножко проигрышные". Здесь возникает вопрос, как игрок выбирает ход. 1. Оптимальный игрокПредположим, что мы играем с игроком, у которого идеальная интуиция. Или у него суперкомпьютер, и он смог построить полное дерево и разметить его (тут нужен даже не супер, а супер-пупер компьютер). Это означает, что если в какой-нибудь ситуации есть выигрышный ход, он его обязательно сделает. А это означает, что вероятность его проигрыша в ситуации, соответствующей обрабатываемому узлу (когда его ход), равна произведению вероятностей его проигрыша в ситуациях, соответсвующих узлам-потомкам. 2. Равный игрокЕсли у игрока нет полного дерева и нет идеальной интуиции, ему приходится довольствоваться тем, что есть. И выбирает он не всегда лучшие в глобальном смысле ходы. Он просто как-то их оценивает, наверное, просчитывает на какую-то глубину и выбирает лучший в каком-то своём локальном смысле. Если предположить, что он использует такое же дерево (или, по крайней мере, такие же оценки вероятностей), как и у нас, то вероятность выигрыша для какого-то узла (опять же, когда его ход) будет равна максимуму вероятности выигрыша у всех его потомков. В принципе, может оказаться более продуктивным комбинированный подход: берём выпуклую комбинацию этих двух значений. Коэффициент можно выбирать на основании "оценки игры" соперника. Если он часто выигрывает, то он будет близок к оптимальному. Если приблизительно на равне - ближе к равному. Если часто проигрывает... Неважно, наверное. Раз проигрывает, значит, всё неплохо работает, и лучше ничего не трогать :) . Но есть у первого подхода одно преимущество: он учитывает способность соперника к непонятным для нас действиям (которые он просчитал дальше). В случае первого подхода ситуации, которые дают сопернику меньше выбора (например, длинные серии атак), оцениваются выше. Это имеет некоторый смысл - он не может планировать никаких действий, только защита. 29.04.2006 |