Программирование игр и головоломок

 

1.5 Позиционные игры

 

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

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

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

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

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

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

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

 

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

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

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

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

Каждая вершина определяет единственную цепь (последовательность идущих друг за другом звеньев), связывающую начальную позицию с данной вершиной (рисунок 1). Такая цепь называется партией. На рисунке 1 одна из партий выделена жирными линиями. Число различных партий ровно числу вершин. В каждой вершине задан числовой выигрыш игрока А.

Рисунок 1. – Модель позиционной игры

Различают позиционные игры с неполной и полной информацией.

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

Игра в развернутой форме, в которой все информационные множества содержат ровно по одному узлу, называется игрой с полной информацией. В позиционных играх с полной информацией (например – шашки, шахматы) каждый игрок при своем ходе знает ту позицию дерева игры, в которой он находится.

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

 

1.6 Кооперативные и некооперативные игры

 

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

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

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

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

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

Некооперативная игра в нормальной форме предполагает следующий порядок разыгрывания.

1. Игроки  одновременно и независимо друг  от друга выбирают из множеств свои стратегии. Вектор стратегий  всех игроков представляет собой ситуацию в игре.

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

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

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

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

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

Начальная и промежуточные позиции образуют множество нетерминальных позиций.

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

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

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

Игра предполагает следующий порядок разыгрывания:

1. Игра  начинается из начальной позиции.

2. В любой  нетерминальной позиции игрок, имеющий в ней право хода, выбирает ход s , в результате чего игра попадает в следующую позицию, в которую входит ребро, соответствующее ходу S. Если эта позиция является нетерминальной, то повторяется п. 2.

3. Если  игра попадает в терминальную  позицию υ, то все игроки получают выигрыши , и игра завершается.

Принципы оптимальности

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

• равновесие дрожащей руки;
• собственное равновесие;
• сильное равновесие.

Менее универсальными, используемыми в отдельных классах некооперативных игр, являются следующие принципы:

• ε-равновесие;
• равновесие в доминирующих стратегиях;
• решение игры по доминированию;
• равновесие в осторожных стратегиях.

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

• равновесие, совершенное по под-играм;
• секвенциальное равновесие;
• сильное секвенциальное равновесие.

 

 

2. Реализация логической игры

 

2.1 Обоснование программных средств реализации

 

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

Для реализации программы была выбрана среда Borland C++, так как она предоставляет наиболее оптимальные возможности для программирования несложной логической игры.

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

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

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

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

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

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

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

2.2 Описание выигрышной стратегии логической игры

 

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

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