Методы поиска на игровых деревьях
Создание игровых программ является одной из классических задач искусственного интеллекта. Попытки их создания начались практически вместе с появлением первых вычислительных машин, и сыграли огромную роль в развитии теории и искусственного интеллекта и интеллектуальных технологий.
Помимо того, что производство игр является мощной отраслью индустрии (по данным InteractiveDigitalSoftwareAssociation(IDSA,Washington,D.C.), объем продаж игр в США в 2001 г. составил 225 миллионов единиц на сумму около 6.35 миллиардов долларов), игры являются подходящей моделью для многих ситуаций, возникающих в ходе человеческой деятельности. Примерами здесь могут служить переговоры, торги на бирже, военные столкновения, ситуации типа преследователь-жертва и т.п.
В настоящее время компьютерные программы достигли
уровня чемпионов мира в шашках (программа Chinook), нардах илиBackgrammon(программа BKG), шахматах (программаDeepFritz),
хороших результатов в бридж,
слабых результатов в го и китайских шахматах.
Для анализа игр можно использовать системы во многом похожие на систему продукции. Игры двух лиц, а только с ними мы и имеем здесь дело, обычно описывают множеством "позиций" и совокупностью правил перехода из одной позиции в другую, причем предполагают, что игроки ходят по очереди. Будем считать, что правилами разрешены лишь конечные последовательности позиций и что в каждой позиции имеется лишь конечное число разрешенных ходов. Например, в шахматах или шашках глобальная база данных должна содержать информацию о расположении фигур на доске, а правила продукции соответствуют ходам, разрешенным правилами.. Применение этих правил к исходной и результирующей базам данных приводят к игровому графу или дереву.
Мы будем далее класс игр двух лиц с полной информацией. В таких играх участвуют два игрока, которые поочередно делают свои ходы. В любой момент игры каждому игроку известно все, что произошло в игре к этому моменту и что может быть сделано в настоящий момент. Игра заканчивается либо выигрышем одного игрока (и проигрышем другого), либо ничьей (шахматы, шашки, "крестики-нолики", реверси, го, рэндзю и др.). В данный класс задач не попадают игры, исход которых определяется, хотя бы в некоторой степени, случаем (карточные игры, кости, домино и др.), хотя рассматриваемые методы допускают некоторое обобщение и на этот случай.
Рассмотрим пример игры с полной информацией.
Перед двумя игроками сложены некоторые предметы (монеты), первый игрок делит исходную пачку на две обязательно неравные части, затем игроки по очереди делят какую-нибудь из получившихся кучек, выбирая её по своему усмотрению. Игра продолжается до тех пор, пока во всех кучках не останется по одной или по две монеты. Проигрывает тот, кто первым не сможет образовать очередную кучку.
Назовем игроков Макс и Мин. Пусть Мин ходит первым. В исходной пачке семь монет. База данных для этой игры состоит из неупорядоченной последовательности чисел, обозначающих число монет в кучках и указания того, чей ход следующий. Исходной конфигурацией является (7, Мин). В ней Мин имеет три различных хода, приводящих к конфигурациям (6, 1, Макс), (5, 2, Макс) и (4, 3, Макс). Полный граф игры показан на рисунке 1. С помощью этого игрового графа можно показать, что независимо от поведения игрока Мин, игрок Макс всегда может выиграть.
С точки зрения одного из игроков, например Макс, граф игры очень похож на граф типа И/ИЛИ. У вершин, соответствующих следующему ходу игрока Мин, есть потомки, подобные вершине типа И. Решение (выигрыш) должно быть достижимо из всех дочерних вершин, то есть при любом ответном ходе противника. Вершины, соответствующие следующему ходу игрока Макс, имеют потомков, схожих с вершинами ИЛИ. С позиции интересов игрока Макс выигрыш должен быть достижим хотя бы из одной из вершин. Терминальные вершины на графе - вершины, соответствующие победе игрока Макс.
Рисунок 1. Пример игрового графа