Главная
5 в ряд

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

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

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

Здесь возникают два вопроса:

  • как оценивать вероятность выигрыша для класса
  • как выбирать классы

Оценка вероятности выигрыша

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

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

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

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

Формирование классов

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

Есть один простой вариант - сформировать список классов со слов самих игроков. А уж за оценкой их дело не станет. Как вариант, наверное, неплохо. Но уж очень как-то неинтересно :).

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

Классы формируются по признакам. Признак - некоторое логическое утверждение о ситуации. Набор признаков определяет класс. В качестве примера, можно привести такую ситуацию: у нас стоят три незакрытых фигуры, а у противника - четыре, закрытые с одной стороны, ход наш. Первый признак - у нас есть длинная атака (название из прошлой реализации алгоритма - для выигрыша надо 2 хода). Второй признак - у противника есть короткая атака (1 ход). Третий признак - наш ход. Вывод - надо закрывать его атаку, а не развивать свою. В общем случае можно сказать, что если мы имеем N признаков, то у нас получается максимум 2^N классов. Возможно, для уменьшения сложности обработки придётся уменьшать их количество с помощью объединения (на самом деле, например, при наличии короткой атаки у противника остальные признаки не так уж и важны).

Признаки типа "длинная атака", "короткая атака" основываются на паттернах. Паттерн - тоже логическое утверждение о ситуации, но, в некотором смысле, локальное. Представить его можно в виде двумерного массива - маски, элементы которого могут принимать 4 значения: крестик, нолик, пустое поле и *(звёздочка). Паттерн смещается по полю и проверяется соответствие ситуации ему. Звёздочка подходит под любое значение, все остальные должны точно совпадать. Таким образом, в результате применения паттерна к ситуации является набор смещений, при которых ситуация удовлетворяет паттерну.

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

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

Так или иначе, все эти три типа объекта нужно уметь генерировать: классы на основе признаков, признаки на основе паттернов, паттерны на основе выигрышных и проигрышных ситуаций.

Предполагается такая процедура: каждый тип объектов генерируется путём рассмотрения различных пересечений объектов нижнего уровня. Паттерны ищутся рассмотрением пересечений выигрышных ситуаций с различными смещениями (клетки, которые отличаются, заменяются на звёздочки). Из сформированных паттернов остаются только полезные - те, которые хорошо коррелируют с результатом игры. На их основе строятся признаки: сначала всевозможные, потом - те, которые себя хорошо зарекомендовали. И на этих признаках уже выписываются классы. Сначала 2^N, потом (возможно, на основе корреляций) происходит объединение некоторых классов.

Тема это, пожалуй, - самая интересная и самая недоработанная. Наверное, потому что объект её рассмотрения наиболее сдвинут от технических вопросов в стороны попыток описания интеллектуальных задач...

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

05.05.2006

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