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

Алгоритм основан на переборе. Даже если понаблюдать за игрой человека, она тоже оказывается основанной на переборе. При наличии неограниченных ресурсов у комптьютера задача вообще не вызывает трудностей - перебираем все возможные варианты развития игры из текущей ситуации (получается дерево, где каждый узел соответствует ситуации, сложившейся на доске), выбираем тот, который в любом случае приводит нас к выигрышу, если есть такой, ну или хотя бы тот, который не приводит к проигрышу. В качестве примера можно рассмотреть крестики-нолики 3*3 - немного поперебирать и можно выбрать беспроигрышную стратегию (выигрышной нельзя), если исходить из начальной, а не какой-нибудь безнадёжной ситуации.

Основная проблема в том, что для данной игры полный перебор - слишком дорогое удовольствие. Когда большинство клеточек свободно (а обычно вся партия сосредоточена где-то около центра) сложность перебора растет экспоненциально с ростом его глубины.

Потому приходится просматривать только часть дерева и некоторые узлы, которые в полном дереве имели бы продолжение, делать конечными (листьями). Получается три типа узлов:

с потомками - тут все просто, мы предполагаем, что играем с умным противником, а это сводится к тому, что мы считаем, что он будет делать наилучшие для него ходы (правда, с использованием нашего же алгоритма оценки качества ходов, потому что другого у нас нет), потому мы присваиваем каждому узлу с потомками качество его наилучшего потомка (с точки зрения текущего игрока)
узлы, соответствующие ситуациям, когда один из игроков уже выиграл - тут тоже все просто - выиграл крестик - качество (+1), нолик - (-1), ничья - 0
то, что появляется из-за неполного просмотра дерева - узлы, которые должны бы иметь потомков, но нам не хватает памяти для их хранения (или времени для их обработки), с их качеством сложнее - нам нужно спрогнозировать результат или, другими словами, оценить ситуацию

Таким образом, построение алгоритма сводится к двум вопросам:

что делать с "обрезанными" узлами - как оценивать ситуацию
как выбирать ту часть дерева, которая будет просматриваться (ну и, соответственно, какую часть обрезать)

Оценка ситуации

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

Сами признаки берутся из опыта автора алгоритма (хотя было бы неплохо уметь выделять их, основываясь на своём опыте). На данный момент они такие:

количество коротких атак - когда для выигрыша не хватает одного хода
количество длинных атак - когда для выигрыша не хватает двух ходов, и есть не один вариант таких ходов, короче, чтобы в случае не закрытия этой атаки на следующем ходу получалось две коротких атаки

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

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

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

Отвлекает ли это его от планов или он и так собирался туда поставить крестик, это ещё вопрос. Но если проводить такой анализ, то это будет просто ещё один (или больше) уровень перебора, а перебором занимается другая часть алгоритма.

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

какие-то полезные параметры ситуации, которые можно будет "забить" в функцию оценки, как это получилось с длинными и короткими атаками
сдвинуться в сторону обучения программы - нейронные сети или что-нибудь в сторону теории вероятности

Выбор просматриваемой части дерева

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

При хранении дерева в памяти ее необходимое количество начинает расти экспоненциально. Добавляются операции работы с кучей (по сравнению с работой со стеком они медленнее). Вся последовательность уже не помещается в кеше процессора, а, может быть, и в оперативной памяти вообще, что приводит к обращениям к винчестеру (а это ужасно для скорости).

Что же дерево дает хорошего: оно позволяет хранить и использовать уже полученные результаты для "соседних" цепочек. Кроме того, дерево на следующий ход можно получить из дерева на предыдущем ходу, взяв соответствующую часть и углубив ее.

Самый простой способ - указать глубину и все, что глубже - отрезать. Но он не совсем соответствует нашей ситуации. Причина, по которой приходится урезать дерево, не в том, что нам не нравится большая глубина, а в том, что мы не хотим хранить/обрабатывать слишком большое количество элементов.

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

Таким образом, целесообразно вводить ограничения не на глубину просмотра, а на количество узлов (ограничение по памяти) и время работы. И кроме того вводить дисбаланс в дерево - просматривать разные направления с разной глубиной.

И ещё две оптимизации, связанных с тем, что некоторые узлы можно просто удалить. Они касаются тех ходов, которые были просчитаны до конца и относительно которых точно известен конец партии и, соответственно, точная оценка ситуации +1/0/-1.

если у нас есть точно проигрышный ход, то его можно просто удалить из списка возможных ходов (вместе со всем деревом)
если у нас есть точно выигрышный ход, можно удалить все остальные ходы: зачем они нам, если мы и так можем выиграть

Первая оптимизация позволяет только улучшить ситуацию с использованием памяти (ведь время мы все равно уже потратили на то, чтобы просчитать проигрышность).

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

Здесь пригодится вариант, при котором дерево хранится памяти: тогда можно использовать результаты предыдущего уровня перебора для упорядочивания узлов таким образом, чтобы наиболее хорошие ходы обрабатывать раньше (в надежде, что они окажутся выигрышными, и остальные узлы можно будет удалить).

Что касается использования информации от соседних цепочек ходов, на данный момент видно два варианта использования:

если у нас есть ход, который приводит к появлению выигрышной линии из пяти фигур, мы можем пройтись по соседним узлам, которые отличаются только предыдущим ходом противника, и проверить, возможен ли этот выигрышный ход, если да - значит, противник не закрыл его и не выиграл, и мы можем сразу пометить узел, как выигрышный для нас, что избавит от лишних проверок и расчетов (правда, большой пользы сейчас от этого анализа нет, т.к. использование усложненной функции оценки вообще не доводит дело до проверки на установку последней фигуры в линии, так это можно назвать лишь гипотетическим примером использования соседних цепочек)
ситуация на доске полностью определяет последующую игру, и неважно, в результате каких ходов эта ситуация сложилась, таким образом если у нас есть последовательность ходов (10,10)-(20,20)-(11,11), то она эквивалентна последовательности (11,11)-(20,20)-(10,10), а это значит, что можно объединить два поддерева (т.к. они точно будут одинаковы), к сожалению, это приводит к необходимости более сложного анализа всего дерева и усложнения самой его структуры (объединения узлов) и пока не реализовано

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

Этот подход лучше, чем равномерный перебор до какой-то глубины, но он все равно слишком "стихийный". Среди планов по модификации этой части алгоритма можно выделить следующие:

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

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

Общее описание алгоритма

Если все эти соображения подытожить, получается следующий алгоритм углубления анализа узла (он применяется к корневому):

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

В начале игры формируется дерево, при ходе человека просто выбирается соответствующий узел, при ходе компьютера - узел с наилучшим качеством. Он (выбранный узел) становится новым корнем, остальное дерево удаляется. Таким образом, дерево за один цикл "сворачивается" два раза: при ходе компьютера и при ходе человека. Это приводит уменьшению количества узлов. Углубление дерева делается перед ходом компьютерного игрока до тех пор, пока количество узлов не станет достаточно большим (как только перескочит максимально позволенное).

23.04.2006

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