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

Дисбаланс дерева

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

Вот и появляется вопрос: как распределять узлы по направлениям, кому давать больше, кому меньше. Здесь можно выработать ряд критериев:

1. Польза для игры

В рамках отдельной игры это - самый "правильный" критерий. Расширять нужно только те узлы, которые дают нам полезную для игры информацию, которая, в следствие более глубокого просчёта какого-то направления, может уберечь нас от неправильного хода или подсказать выгодный ход. Критерий хороший, но неформализованный. И не очень-то понятно, как его формализовать. Можно вводить понятия "интересности" направления, "надёжности его оценки", "пользы от его углубления". Можно привлекать статистику, чтобы оценивать эти показатели уже после того, как решение было принято, чтобы потом в такой же или похожей ситуации поступить правильнее. Эти показатели сами не очень-то формализованы, и даже после получения результата не всегда можно сказать что-либо конкретное об их значениях.

2. Максимум полезных узлов

Когда мы или соперник делаем ход, совсем необязательно полностью пересчитывать всё дерево. Можно выбрать ту его часть, которая соответствует сделаному ходу, а всё остальное удалить. Получится, что на начало хода у нас уже есть часть дерева, которую можно просто углубить, насколько позволяют ресурсы, и не тратить время на повторную генерацию тех узлов, которые уже есть. Это подводит к следующей мысли: хорошо, когда много узлов сохраняется при переходе на следующий шаг, и нам надо тратить меньше времени. Однако, критерий получается довольно-таки радикальный: он приводит к тому, что расширять нужно только узлы с самым высоким качеством. Это может привести к тому, что глубоко будет просчитано только одно направление. Хотя это и не значит, что он плохой - это уже вопрос практики.

3. Наиболее глубокий просчёт вероятных ходов

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

4. Максимум отсечений

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

5. Комбинированный критерий

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

6. Польза для игрока

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

30.04.2006

Дальше - Оценка ситуаций в недостроенных узлах

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