Аспекты задачи сокращения перебора при анализе сложных позиционных игр

• Введение
• 1. Подходы к реализации AI в логических играх
• 1.1 Понятие поиска
• 1.2 Позиционная игра
• 1.3 Подходы к решению задач выбора хода в позиционных играх
• 1.4 Особенности игры нарды
• 1.5 Правила игры в нарды
• 1.6 Оценочная функция
• 1.7 Самообучение
• 1.8 Нетранзитивность игр
• 1.9 Обзор литературы и существующих программ
• 1.10 Игровые деревья
• 1.11 Дерево игры в нарды
• 2. Построение эвристических оценочных функций
• 2.1 Выделение параметров
• 2.2 Определение более сильного игрока из двух
• 2.3 Настройка весовых коэффициентов
• 2.4 Линейная модель из 3-х параметров. Вид поверхности
• 2.5 Таблицы вероятностей
• 2.6 Снижение размерности. Гипергаммон
• 2.7 Разделение игрового процесса на фазы
• 3. Построение оценочных функций на основе нейронных сетей
• 3.1 Теория нейронных сетей
• 3.2 Использование нейронных сетей в качестве оценочной функции
• 3.3 Использование MatLab для обучения нейронных сетей
• 3.4 Экспериментальные данные
• 4. Реализация версии для мобильных устройств
• 4.1 Особенности программирования портативных устройств
• 4.1.1 Размер экрана
• 4.1.2 Быстрый отклик
• 4.1.3 Ввод данных
• 4.1.4 Питание
• 4.1.5 Память
• 4.1.6 Файловая система
• 4.2 Выбор средств разработки
• 4.3 Реализация игры
• Заключение
• Список литературы

В настоящее время мобильная связь имеет широкое распространение в мире. При этом и без того немалое число пользователей мобильных телефонов продолжает расти. Сами же мобильные телефоны больше не являются просто средством связи. Благодаря поддержке сторонних приложений они получают новые возможности. Соответственно возрастает спрос на софт для мобильных телефонов. В том числе и на игры. Многие пользователи воспринимают телефон как мобильный центр развлечений, поэтому игровые возможности устройства являются для них наиболее приоритетными после его коммуникативных возможностей.

Еще несколько лет назад игровые возможности телефона полностью определялись набором игр, «вшитых» в него производителем: не существовало никакой возможности добавить новые игры. В настоящее же время большинство телефонов работающих как под управлением операционных систем (смартфоны), так и под управлением встроенного ПО (прошивки), поддерживают технологию Java. Благодаря этой технологии, совместимой с любыми приложениями созданными при помощи Java Micro Edition, появилась возможность написания любых программ для мобильных устройств, в том числе и игр.

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

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

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

Мобильная игра — игровая программа для мобильных устройств, например сотовых телефонов, смартфонов, коммуникаторов, КПК и прочих (за исключением ноутбуков).

На данный момент особенно распространены мобильные игры для платформы Java Micro Edition. Эту платформу поддерживают большинство современных мобильных устройств, в том числе большинство сотовых телефонов стандарта GSM, используемого в России.

Решения на машинном коде изначально ориентированы на определённую платформу. Поэтому такие игры показывают самый высокий уровень производительности и используют все мультимедийные возможности аппарата, но недоступны для других платформ.

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

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

Sun J2ME (Java 2 Micro Edition, в просторечии Java) — одно из самых распространённых средств для разработки игр для мобильных телефонов. Лёгкость портирования позволяет выпускать одну и ту же игру на большое число различных устройств. Использование виртуальной машины для выполнения промежуточных кодов позволяет ограничить доступ приложения к данным телефона для повышения безопасности, однако это же зачастую приводит к снижению функциональности.

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

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

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

1. Подходы к реализации AI в логических играх

1.1 Понятие поиска

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

Многие ранние исследования в области поиска в пространстве состояний совершались на основе таких распространенных настольных игр, как шашки, шахматы и пятнашки. Вдобавок к свойственному им интеллектуальному характеру такие игры имеют некоторые свойства, делающие их идеальным объектом для экспериментов. Большинство игр ведутся с использованием четко определенного набора правил: это позволяет легко строить пространство поиска и избавляет исследователя от неясности и путаницы, присущих менее структурированным проблемам. Позиции фигур легко представимы в компьютерной программе, они не требуют создания сложных формализмов, необходимых для передачи семантических тонкостей более сложных предметных областей. Тестирование игровых программ не порождает никаких финансовых или этических проблем. Поиск в пространстве состояний — принцип, лежащий в основе большинства исследований в области ведения игр.

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

1.2 Позиционная игра

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

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

При переходе к позиционной игре с бесконечным множеством информационных состояний (например, два игрока поочередно называют десятичные цифры a₁, а₂, a₃, a₄,. и если получающееся в результате число 0, a₁a₂a₃a₄. будет принадлежать некоторому множеству, то первый игрок выигрывает единицу; в противном случае единицу выигрывает второй игрок) это утверждение теряет силу, и могут наблюдаться явления парадоксального характера, математически весьма сложные.

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

К числу позиционных игр (с непрерывным множеством информационных состояний) можно отнести Дифференциальные игры. Как теорию одного из классов позиционной игры с одним игроком можно понимать Динамическое программирование. Естественно интерпретировать как П.И. задачи многошаговых (секвенциальных) статистических решений. Учёт получаемой или утрачиваемой игроком в П.И. информации обусловливает связь теории игр с информации теорией.

1.3 Подходы к решению задач выбора хода в позиционных играх

При создании программ, играющих в такие позиционные игры, как шахматы или нарды, в основном используется так называемая эвристическая схема Шеннона. Дерево игры исследуется на фиксированную глубину. Далее применяется метод максимина для выбора наилучшего хода. Существуют и другие подходы к созданию играющих программ, например метод горизонтов, но ни один из них не дал пока результатов, существенно лучше, чем у метода Шеннона.

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

1.4 Особенности игры нарды

Нарды по своей природе — случайная игра (для того, чтобы совершить ход, необходимо бросить игральные кости), что отличает ее от других логических игр типа шахмат, шашек, реверси и др. (ознакомиться с правилами можно в Приложении А) Эта особенность может быть использована для настройки весов линейной модели.

Существует две вариации правил игры в нарды: длинные нарды и короткие нарды. Короткие нарды — игра для двух игроков, на доске, состоящей из двадцати четырех узких треугольников, называемых пунктами. Треугольники чередуются по цвету и объединены в четыре группы по шесть треугольников в каждой. Пункты нумеруются для каждого игрока отдельно, начиная с дома данного игрока. Самый дальний пункт является 24-м пунктом, он также является первым пунктом для оппонента. Для белых (на диаграммах рисуется внизу) пункты нумеруются по часовой стрелке, для чёрных — против часовой стрелки.

Пункты объединены в группы. Эти группы называются — дом (1−6), двор (7−12), дом противника (19−24), двор противника (13−18). Дом и двор разделены между собой планкой, которая выступает над игровым полем и называется бар.

У каждого игрока имеется 15 шашек. Начальная расстановка шашек такова: у каждого из игроков по две шашки в двадцать четвертом пункте, пять в тринадцатом, три в восьмом и пять в шестом.

игра дерево позиционная перебор

1.5 Правила игры в нарды

· Игроки ходят по очереди.

· Направление перемещения шашек отличается в разных вариантах игры. Но в любом случае шашки движутся по кругу и для каждого игрока направление их движения фиксировано.

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

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

· За один ход делается от одного до четырёх передвижений шашки. В каждом из них игрок может передвинуть любую свою шашку на такое количество пунктов, которое выпало на одной из костей. Например, если выпало 2 и 4 очка, игрок может за этот ход передвинуть одну (любую) из шашек на 2 пункта, другую — на 4 пункта, либо передвинуть одну шашку сначала на 2, затем — на 4 пункта (или, наоборот, сначала на 4 потом на 2). Если на обеих костях выпадает одинаковое число очков (дубль, паш, куш, кошка), то выпавшие очки удваиваются, и игрок получает возможность сделать 4 перемещения. Каждое перемещение шашки должно делаться на полное количество очков, выпавшее на кости (если выпало 4 очка, то пойти шашкой на 1, 2 или 3 пункта нельзя — можно только на полные 4).

o В варианте игры «гюльбар» если у игрока нет возможности сделать какой-либо из этих ходов, то недоигранные ходы должен сделать соперник. При выпадении дубля если игрок смог сделать все 4 хода, то он бросает кости снова. ^[4]

o В варианте игры «бешеный гюльбар» при выпадении дубля игрок делает все ходы от выпавшего дубля до дубля шести (например, при выпадении дубля «четыре-четыре» игрок перемещает одну шашку на 4 пункта, затем другую на 4 пункта, затем ещё одну на 5, ещё одну на 5, одну на 6 пунктов и ещё одну на 6 пунктов). Если у игрока нет возможности сделать какой-либо из этих ходов, то недоигранные ходы должен сделать соперник ^[5] .

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

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

· Когда все шашки игрока в процессе движения по доске попадают в свой дом, следующими ходами игрок может начать выставлять их за доску. Шашка может быть выставлена за доску, когда номер пункта, на котором она стоит, равен числу очков, выпавших на одной из костей (то есть шашку, стоящую на крайнем пункте, можно выставлять, если выпала единица, на втором от края — если выпала двойка). Если все шашки в доме находятся ближе к краю доски, чем выпавшее число очков, то может выставляться за доску шашка из пункта с наибольшим номером.

· Начальное расположение шашек определяется правилами.

· Ничьих в нардах не бывает. Выигрывает тот, кто первым выставил все свои шашки за борт.

· Победитель получает за выигрыш от одного до трех очков. Правила начисления очков за выигрыш в разных вариантах нард могут отличаться.

1.6 Оценочная функция

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

Будем полагать, что оценочная функция — симметричная, т. е. если белые «думают», что они находятся в хорошей позиции, то черные «полагают», что они на столько же в плохой позиции.

ОФ - может быть более или менее сложная, в зависимости от встроенных в нее знаний. Соответственно, чем более сложная ОФ, тем дольше ее вычислять. Обычно производительность программы (т.е. насколько она хорошо играет) может быть оценена как произведение «скорости» на «знание».

Рис. 1. Оценочная функция.

В качестве оценочной функции используются линейные модели (линейная комбинация некоторых параметров).

В простейшей модели в качестве параметров можно взять просто количество фишек на каждом поле, получив в сумме 26 параметров. Реально же используют некоторые вычисляемые параметры, представляющие определенные стратегические аспекты игры.

Одним из основных параметров является подсчет пипсов — это число, которое нужно выбросить на игральных костях, чтобы вывести все свои фишки. По этому параметру определяют лидерство и близость победы.

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

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

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

Также считают число прямых возможностей взятия — это число одинарных фишек на расстоянии 6 или меньше полей. Есть схожий с этим параметр — число одинарных фишек на расстоянии меньшем 12. Схожим параметром является вероятность взятия одинарной фишки, которая в большинстве случаев рассчитывается по предварительно посчитанной таблице.

Равномерность распределения фишек по полям. Например, гораздо выгоднее иметь три фишки на одном поле и еще три на другом, чем две и четыре на тех же полях. В случае выпадения определенных костей может потребоваться сдвинуть фишку с первого поля и тем самым сделать как минимум одну одинарную фишку.

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

Также часто используется параметр коммуникации — нужно стремиться располагать свои фишки на расстоянии не более 6 пипсов друг от друга. Тем самым препятствовать разделению своих фишек.

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

Очень часто вводятся понятия контакта фишек — наличие хотя бы одной вражеской фишки в направлении движения. Наличие факта контакта влияет на используемую стратегию и может предполагать разные оценочные функции.

Эвристический метод, используемый для получения подобных оценок, в общем, заключается во введении некоторой числовой функции на множестве позиций, зависящей от ряда переменных, которую называют оценочной функцией (evaluation function). Переменными, обычно служат разного рода элементарные оценки позиции, такие как, например, материальный перевес, пешечные структуры, угрозы фигурам. Функция должна быть легко вычисляема, поэтому её обычно строят в виде линейной функции соответствующих переменных. Некоторые исследователи ищут развитие этого метода в усложнении вида оценочной функции путем введения в нее нелинейных элементов или использования булевых функций. Тем не менее, сложность расчета такой функции имеет критическое значение, так как должна быть оправдана отказом от исследования дальнейшего развития ситуации. Иными словами, время, потраченное на вычисление слишком сложной оценочной функции, может быть с гораздо большим успехом потрачено на просчет ходов из данной позиции, и расчет более простой оценочной функции в полученных позициях.

Так или иначе, оценочная функция определяется набором переменных, видом, и набором параметров. Выбор переменных производится путем анализа экспертных знаний. На этом этапе иногда есть возможность обратиться к литературе по теории данной игры, каковой в избытке можно найти по шахматам. Кроме того, на практике часто очень полезны даже самые элементарные соображения экспертов, имеющих опыт игры. Это очень важно в случае с играми, для которых не создано такой внушительной теоретической базы. В некоторых, достаточно простых играх хватает всего трех переменных, и такая функция делает игру программы сносной; в шахматах их число обычно достигает нескольких сотен. Вид функции, как уже говорилось, определяется сравнительной легкостью вычисления. Последним этапом построения оценочной функции, а зачастую и всей программы, является подбор параметров при переменных (нелинейных или булевых слагаемых), то есть весов соответствующих критериев оценки позиции. Здесь анализа экспертных знаний всегда недостаточно. Часто критерии кажутся несоотносимыми, хотя требуют точнейшей сравнительной оценки. Большое количество переменных, а соответственно и параметров, делает более-менее адекватный их априорный выбор просто невозможным. Еще одна проблема при выборе параметров — их нестабильность в том смысле, что в разных фазах игры, а иногда и в разных игровых ситуациях, наиболее сильной игре соответствуют разные оценочные функции. Может появиться необходимость в течение игры менять как параметры оценочной функции, так и её структуру. В случае с фазами игры можно заранее предусмотреть такую замену, а в случае с различными игровыми ситуациями (которых на практике может оказаться больше, чем в теории) потребуется в процессе игры выбирать адекватную программу. Причем существуют варианты: выбирать из готовых, и/или адаптировать существующую программу, получая новую. Эта частная задача относится к классу задач самообучения игровых программ, который подробнее рассматривается ниже.

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

1.7 Самообучение

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

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

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

Реально, нет никаких гарантий, что такая функция вообще существует, но часто удобно предполагать её существование, так как у исследуемого объекта иногда проявляются некоторые свойства функции. Главная проблема в такой постановке задачи заключается в заведомом отсутствии градиента и вообще каких бы то ни было частных производных этой функции. Точнее, частные производные и градиент вероятно существуют, но нет никаких подходов к их поиску. Таким образом, пойти в этом направлении дальше метода покоординатного спуска не представляется возможным. С другой стороны, такая аналогия приводит к выводу о том, что метод вскарабкивания на холм поможет нам найти лишь локальный экстремум нашей гипотетической функции. Учитывая, что о характере этой функции не известно практически ничего, можно предположить, что локальный экстремум в данной ситуации может находиться сколь угодно далеко от глобального. Если так, то мы найдем совсем не то, что искали. Предположим теперь, что рассматриваемая игра относится к сложным, и её оценочная функция имеет не меньше десятка параметров. Мы оптимизируем один из них, затем переходим к другому, оптимизируем его.

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

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

Итак, окончательный вывод выглядит так: при выборе очередного параметра для изменения невозможно учитывать предыдущий порядок выбора параметров. То есть каждый раз, выбирая очередной параметр, мы стоим на распутье, где неоткуда получить никакой априорной информации, куда идти. Два выхода из такой ситуации это: выбрать параметр случайно или попробовать все и остановиться на том, который дает лучший результат. Второй выход сопряжен с огромным расходом времени. Кроме того, что параметров много, неизвестно, на сколько надо их менять. Таким образом, количество проб в таком случае приблизительно равно произведению числа параметров на число предполагаемых вариантов длины шага. Учитывая то, что каждая проба подразумевает состязание двух программ, которое в свою очередь обычно заключается в проведении нескольких партий, делаем вывод, что перебор всех вариантов — задача трудновыполнимая. Кроме того, даже при таком подходе отнюдь не исключается возможность пропустить верную дорогу, так как она может оказаться «за поворотом», то есть необходимо исследовать все возможности на два шага вперед, на три и т. д. Первый выход по крайней мере выполним. В таком методе обучение программы отдаётся на волю случая. Этот подход называют также эволюцией в популяции из двух особей. «Особями» здесь выступают конкурирующие программы, из которых «выживает» сильнейшая, даёт «потомство», которое «мутирует», то есть изменяет один из параметров своей оценочной функции.

Преимуществом этого метода является сравнительная простота. Процесс обучения можно запускать несколько раз из одной стартовой точки и если программы забрались на разные холмы, то можно выбрать забравшуюся на высочайший. Правда не решается проблема зависимости от стартовой оценочной функции. Если стартовую точку и некий холм разделены «оврагом», то программа никогда не заберется на него. Чтобы взобраться на холм, нужно по крайней мере, чтобы стартовая оценочная функция попала на его склон. И даже это не дает гарантии, что программа на него все-таки поднимется вообще и если поднимется, то за конечное время. На практике использование подобных методов нередко приводило, например, к бесконечному кружению по спирали по подножию холма.

1.8 Нетранзитивность игр

Одна из проблем метода вскарабкивания связана с транзитивностью отношения «более сильный — более слабый» игровых программ. Если программа A чаще всего выигрывает у программы B, а та в свою очередь чаще всего выигрывает у программы C, то последняя может чаще всего выигрывать у программы A. То есть транзитивность этого отношения стоит под вопросом. Программа, играющая на среднем уровне, может в силу стечения обстоятельств иметь, скажем, всего одну, но очень эффективную стратегию против гораздо более сильной программы и постоянно её обыгрывать. При этом эта стратегия не действует против других более сильных программ. Такие примеры существуют в жизни. Так, величайшего шахматиста Александра Алёхина, очень часто обыгрывал шахматист значительно менее высокого уровня Лайош Асталош. Известны и другие случаи подобного «везения», в том числе и в командных играх, что говорит о том, что это свойство нетранзитивности не является результатом каких-то психологических феноменов, а присуще самим играм, в особенности сложным позиционным.

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

1.9 Обзор литературы и существующих программ

В последние годы в мире был опубликован ряд статей и монографий, посвященных применению искусственного интеллекта (AI) в логических играх, в частности в нардах.

В работе G. Tesauro «TD-Gammon, a self-teaching backgammon program» отмечается, что программа по игре в нарды (backgammon), реализованная с использованием нейронной сети, добилась высоких результатов при игре с лучшими игроками-людьми, используя параметры, полученные при игре сама с собой. Нейронная сеть использовалась для оценки качества позиций. Программа оценивала все доступные за один ход позиции и выбирала тот ход, который вел к наилучшей позиции. Параметры нейронной сети модифицировались с помощью алгоритма TD.

В работе J. Pollack & A. Blair «Co-Evolution in the successful learning of backgammon strategy» рассматривают эволюционный подход к настройке весов нейронной сети, оценивающей позиции в нардах. В работе предлагается использовать упрощенный вариант генетических алгоритмов. Констатируется достижение достаточно высоких результатов несмотря на некоторые огрехи в методике.

В работе M. Buro «Efficient approximation of backgammon race equities» предлагается использовать статистические методы и динамическое программирование для оценки вероятности выигрыша позиции в нардах. В работе сообщается об обоснованности применения данных методов.

Также в последнее время был выпущен ряд программ для PC и для мобильных устройств.

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

Также был выпущен ряд игр для телефонов, поддерживающих J2ME фирмами gameloft, ZingMagic. Их отличает хорошая графика и приемлемый уровень игры.

1.10 Игровые деревья

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

Также полагается, что дерево конечно, т. е. мы имеем дело с игрой которая не длится вечно или имеет бесконечно много ходов из одной позиции.

Рис. 2 Фрагмент игрового дерева

Многие сложные реальные задачи можно смоделировать с помощью деревьев решений (decision trees). Каждый узел в дереве представляет собой один шаг решения задачи. Ветвь в дереве соответствует решению, которое ведет к более полному решению. Листы представляют собой окончательное решение. Цель состоит в том, чтобы найти «наилучший» путь от корня до листа при выполнении некоторых условий. Естественно, что условия и «наилучший» путь зависят от сложности конкретной задачи.

На примере крестиков-ноликов показаны способы поиска в деревьях игры наилучшего возможного хода. Последующие разделы описывают более общие способы исследования деревьев решений. Для самых маленьких деревьев можно использовать метод полного перебора (exhaustive searching) всех возможных решений. Для работы с большими деревьями более подходит метод ветвей и границ (brunch-and-bound technique), позволяющий отыскивать лучшее возможное решение без поиска по всему дереву. Для огромных деревьев лучше использовать эвристический метод (heuristic). При этом найденное решение может и не быть наилучшим из возможных, но должно быть достаточно близким к нему.

1.11 Дерево игры в нарды

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

Игра описывается посредством дерева игры. Далее также по аналогии определяются оценки позиций, применяется а, b — эвристика. Кроме того, вводится такое новое понятие, как функция риска.

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

Учитывая то, что у нард очень большой коэффициент ветвления дерева игровых позиций (достигает 200−300 доступных ходов из одной позиции) и наличие случайности (броски костей) перебор в осложняется, вследствие ограниченности вычислительных ресурсов. Для примера, в шахматах коэффициент ветвления составляет порядка 40 ходов, а для шашек 8−15. Так например при глубине поиска два существует 1,296 ходов, глубина 3 — 46,656 ходов. Поэтому рассматриваются наиболее вероятные ходы, например выпадение дубля несколько раз подряд маловероятно. При таком подходе число учитываемых ходов сокращается до 900 и 27,000 соответственно. Но даже такой подход не позволяет осуществлять перебор ходов на большую глубину, т.к. их количество слишком велико, и время работы существенно увеличивается. В следствие этого расчет ходов более чем на глубину 2 не целесообразен. На рисунке 3. показана зависимость количества вариантов ходов от глубины.

Рисунок 3. Зависимость количества вариантов ходов от глубины.

Поэтому необходима качественная оценочная функция, дающая правдоподобную оценку вероятности победы игрока в данной позиции.

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

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

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

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

2. Построение эвристических оценочных функций

2.1 Выделение параметров

Реализованная программа игры за компьютер состоит из двух частей. Первая часть генерирует все возможные ходы (при текущем броске костей) доступные из текущей позиции. Вторая часть — оценочная функция, с помощью которой выбирается наилучший ход. Учитывая то, что у нард очень большой коэффициент ветвления дерева игровых позиций (достигает 200−300 доступных ходов из одной позиции) и наличие случайности (броски костей) перебор в глубину не представляется целесообразным, вследствие ограниченности вычислительных ресурсов. Для примера, в шахматах коэффициент ветвления составляет порядка 40 ходов, а для шашек 8−15. Таким образом, применение «грубой силы» («brute force») для нард неэффективно.

В качестве оценочной функции используются линейные модели (линейная комбинация некоторых параметров) и нейронные сети (трехслойная нейронная сеть).

В простейшей модели в качестве параметров можно взять просто количество фишек на каждом поле, получив в сумме 26 параметров. Реально же используют некоторые вычисляемые параметры, представляющие определенные стратегические аспекты игры.

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

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

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

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

Также считают число прямых возможностей взятия (direct shot) — это число одинарных фишек на расстоянии 6 или меньше полей. Есть схожий с этим параметр indirect shots — число одинарных фишек на расстоянии меньшем 12. Схожим параметром является вероятность взятия одинарной фишки, которая в большинстве случаев рассчитывается по предварительно посчитанной таблице.

Равномерность распределения фишек по полям. Например, гораздо выгоднее иметь три фишки на одном поле и еще три на другом, чем две и четыре на тех же полях. В случае выпадения определенных костей может потребоваться сдвинуть фишку с первого поля и тем самым сделать как минимум одну одинарную фишку.

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

Также часто используется параметр коммуникации — нужно стремиться располагать свои фишки на расстоянии не более 6 пипсов друг от друга. Тем самым препятствовать разделению своих фишек.

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

Очень часто вводятся понятия контакта фишек — наличие хотя одной вражеской фишки в направлении движения. Наличие факта контакта влияет на используемую стратегию и может предполагать разные оценочные функции.

В целом можно отметить, что с ростом числа параметров в модели росло и время обучения, но также росло и качество оценки позиции.

2.2 Определение более сильного игрока из двух

В силу того, что и в игре присутствует элемент везения возможна ситуация, когда слабый соперник может выиграть у более сильного, что ставит вопрос об определении более сильного игрока из двух. В случае, когда один соперник заведомо сильнее другого эффект везения практически не проявляется и выбрать сильнейшего можно сыграв незначительное число партий. К тому же данная ситуация случается не так часто. Когда же силы игроков примерно равны (такое часто случается при подборе весов оценочной функции) выбирать сложнее. Соответственно требуется оценить число партий, которые необходимо сыграть, чтобы достоверно определить победителя. Можно доказать, что число побед одного игрока над другим распределено по нормальному закону. В этом случае для получения доверительного интервала для оценки математического ожидания вероятности победы первого игрока можно воспользоваться следующим выражением:, гдевыборочное среднее, — «исправленное» среднее квадратическое отклонение, — коэффициент Стьюдента с надежностью , — объем выборки. Так как силы игроков примерно равны, можно считать, что вероятности выпадения 1 (победа белых) или 0 (победа черных) равны. Тогда задавшись, получим доверительный интервал для:. А для:. Основываясь на полученных данных, сравнивать силу двух игроков, примерно равных по силе, корректно только при числе сыгранных партий близком к тысяче и более.

2.3 Настройка весовых коэффициентов

Исходя из пункта 1.6 оценочная функция будет иметь вид:

f = - pip — one + group (x2 even if) + block + pos;

где pip — расстояние до конца доски,

one — количество одиночных фишек,

group — вхождение в группу фишек (умножается на два, если количество фишек в группе чётное),

block — если блокируется фишки противника,

pos — если занимается 4-я, 5-я, 20-я или 21-я клетка.

2.4 Линейная модель из 3-х параметров. Вид поверхности

При нынешнем уровне развития вычислительной техники, при большом числе параметров модели (например, если в качестве параметров использовать число фишек на каждом поле) перебрать все параметры для определения подходящих величин не представляется возможным. Но получить представление о виде поверхности количества побед модели над эталонным игроком, на примере коротких нард, можно, сведя количество параметров до трех: pips (сумма чисел, которые нужно выкинуть на кубиках, чтобы выиграть партию), blots (число одиночных фишек), hold (число удерживаемых позиций, т. е. с числом фишек больше двух). В результате были построены зависимости количества побед над эталонным игроком (выбирающим ходы случайным образом) от blots и hold при фиксированных значениях pips, выбранных равными +1, — 1, +5, — 5. Учитывается разница этих параметров для игроков, играющих белыми и черными фишками. Перебор этих параметров осуществлялся в диапазоне от — 10 до 10.