Описание алгоритма компьютерного игрока

Переход к урезанному дереву

Раз не получается хранить всё дерево, придётся хранить его часть. Какие-то узлы просчитывать, на какие-то не обращать внимания (как это и человек делает). Это создаёт возможность пропустить что-то, но для того, чтобы учесть всё, нужно строить дерево полностью, а это нам "не по карману".

В случае полного дерева было два типа узлов: с потомками и конечные. Конечные узлы соответствуют ситуациям, когда игра закончилась. Результатов может быть три: выигрыш крестиков, выигрыш ноликов, ничья (поле-то ограниченное). В остальных узлах есть какой-то набор возможных ходов, а значит, и соответствующие потомки. Конечные узлы можно пометить в соответствии с результатом: +1/0/-1. Узлы с потомками тоже можно пометить: если ход крестиков и среди потомков есть узел, выигрышный для крестиков - этот узел сам помечается выигрышным для крестиков, если все узлы проигрышные - узел помечается проигрышным. То же самое для ноликов. Ну ещё учесть ничейные ситуации. Так можно разметить всё дерево и выбирать абсолютно оптимальные ходы.

Другое дело с урезанным деревом - той частью полного, которую мы можем позволить себе хранить в памяти. Если рассмотреть процедуру разметки полного дерева, то её пришлось бы делать с конечных узлом и распространять в направлении корня. При отсечении частей дерева появляется третий вид узлов, назовём их недостроенными. Совсем непонятно, какую метку им присваивать: выигрыш, проигрыш или ничья, ведь потомков, которые несли необходимую информацию, нет, а сама ситуация соответствует незаконченной игре, т.е. результата нет.

Всё, что у нас есть в недостроенных узлах - это ситуация - расположение крестиков и ноликов на поле. В принципе, она содержит достаточно информации, чтобы всё просчитать, но для этого надо строить полное дерево, а этого мы не можем. Потому нужно сознательно потерять часть информации о ситуации - просто потому, что столько мы обработать не можем. Один из путей такой:

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

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

28.04.2006

Дальше - Вычисление качества узлов с потомками

Предложения, отзывы...