Переславль-Залесский, 2006 год.
В проекте участвовали:
Атаманов Андрей,
Воронцов Илья,
Иванов Денис,
Ким Оля.
Лоскутов Алексей,
Овчинников Михаил,
Соколов Иван,
Хромов Алексей,
Руководитель: Неретин И.С.
Основной задачей проекта было моделирование стратегий поведения искусственного интелекта в различных играх и задачах. Первыми такими моделями стали "крестики-нолики" и "Идеализированная дилема заключенного".
Для решения первой задачи было разработано три различных движка (cross.pas, krnol.pas, krnol2.pas, плюс юзерский интерфейс - userint.pas), оптимизированных под конкретные задачи и тактики. Под эти движки было написано 7 стратегий по принципу приоритетов клеток и были проведены перекрестные тесты по системе каждый с каждым. Суть данного принципа заключается в том, что компьютер, последовательно пробегая по всем клеткам поля, смотрит на совпадение позиций фигур по всем направлениям, сравнивает их с базой данных, где описанно количество балов за ту или иную позицию, суммирует полученные результаты и записывает их в массив. После чего выбирает клетку с наибольшей суммой и ходит в нее. Разница между стратегиями в базах данных, то есть, они используют разные приоритеты на одни и теже ситуации, в одной из стратегий реализованна идея мнимых приоритетов, где компьютер смотрит не только на реальную позицию, но и на позицию после ближайщего хода противника. Ниже приведены сводные таблицы игр компов друг с другом, Лоскутовым и Соколовым.
Мнимые | Реал Ат1 | Реал Ат2 | Презент | Деф. реал | Лоскутов | Соколов | |
Мнимые | 0 | 0 | 0 | 0 | 0 | 1 | 3 |
Реал Ат1 | 3 | 0 | 3 | 0 | 1 | 3 | 3 |
Реал Ат2 | 3 | 0 | 0 | 0 | 1 | 1 | 3 |
Презент. | 3 | 3 | 3 | 0 | 1 | 3 | 3 |
Деф. реал | 3 | 1 | 1 | 1 | 0 | 1 | 3 |
Лоскутов | 1 | 0 | 1 | 1 | 1 | 0 | 3 |
Соколов | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Сумма | 13 | 4 | 8 | 2 | 4 | 9 | 18 |
Второй программой написанной на проекте стала Идеализированная дилема заключенного (zekz_ful.pas, zekz_tbl.pas). Перед ней ставилась задача - смоделировать дилему заключенного и выявить наилучшую стратегию игры. Программа моделирует следующую ситуацию, в тюрьме находится пара заключенных, имееющих возможность сдать своего подельника, в случае их обоюдной дачи показаний оба садятся на большой срок, в случае обоюдной не подачи срок для обоих минимален, если же один идет на сделку со следствием, а другой нет, то cговорчивого отпускают, а его подельник садится на максимальный срок.
Было написанно несколько стратегий: сдающая, не сдающая, периодичная, случайная, повторяющая предыдущий ход соперника и анализирущая. Суть анализирущей заключалась в том, что она отыскивала периодичность и соотношение ответов противостоящей ей стратегии, то есть как бы распознавала врага и подстраивалась под его действия, с неким случайным элементом, чтобы не быть распознанной самой.
Скрещивания проводились по схеме каждый с каждым с учетом численности выживших заключенных тех или иных стратегий, в результате выяснилось, что единственными жизнеспособными стратегиями являются анализирующая и повторяющая. Анализирующая несколько отставала от повторяющей по той причине, что ей каждый раз, чтобы перестроиться нужно было несколько анализируемых ходов, а повторяющей нет, как следствие при игре с такой же стратегией, она несколько вырывалась вперед, так как не имела анализирующих элементов.
Ниже приведена таблица с популяциями каждой стратегии к номеру хода.
№ хода | Анализрующая | Повторяющая | Заклад. | Незаклад. | Случайная |
1 | 100 | 100 | 100 | 100 | 100 |
100 | 178 | 85 | 207 | 10 | 21 |
1000 | 178 | 131 | 172 | 6 | 12 |
2000 | 177 | 153 | 149 | 6 | 11 |
5000 | 174 | 178 | 122 | 5 | 9 |
10000 | 171 | 197 | 116 | 4 | 8 |
Lim | 208 | 260 | 28 | 1 | 3 |
Еще одной программой, созданой участниками проекта были шашки (Vavki.rar), на данный момент эта программа не закончена, создан и протесирован рабочий движок, который полностью соблюдает правила, как шашек так и поддавков, позволяет играть пвп или против копьютера, скрещивать компы друг с другом, но исскуственный интелект пока что отстутствует, он заменен тем, что машина делает случайные возможные ходы.
Реверси моделирует средневековую европейскую игру. На поле расположены фишки двух различных цветов, каждый игрок за ход может поставить одну фишку своего цвета, но только так чтоб обратить фишку противника. Фишки обращаются только, если они находятся между клетками противника, стоящими с обоих концов вплотную к ряду обращаемых фишек.
Программа была разбита на несколько частей, а именно модуль с правилами - движок, игровой интерфейс - мод позволяющий играть с машиной или игрок против игрока (rev_user.pas), и компьютерного искусственного интеллекта, после чего к ней было дописано несколько модулей (rev_cpu2.pas, rev_cpu3.pas), позволяющих скрещивать разные компьютерные стратегии друг с другом, запуская разные комбинации в бат файлах.
Иван Соколов
06.08.06
История происхождения.
Изначально эта программа была создана для того, чтобы показать одному ученику, что же такое ReadKey и как им пользоваться. Тогда мы имели стандартное поле 80х23, где при помощи Random ставились четыре объекта: игрок, клад и два монстра. Каждый монстр имел свой шанс на этом ходу сходить в сторону игрока. Было два типа монстров: один атаковал по вертикали, а второй по горизонтали. Задача игрока состояла в том, чтобы добраться до клада прежде, чем до него доберутся монстры. Спустя некоторое время была выдвинута идея улучшить эту программу до полноценной игры лабиринт.
Путь развития.
Первым шагом стало создание игрового поля. Немного постаравшись, мы получили поле 80х23,на котором кроме монстров, клада и игрока были ещё и стены. В начале игры вам надо было ввести название файла, в котором был записан уровень. На данном этапе была выдвинута идея создать программу, которая сама могла создавать лабиринты. Эта идея не увенчалась успехом по причине неспособности автоматически созданных карт конкурировать с авторскими произведениями. Далее были созданы несколько уровней, для удобства соединённых в файле Default.clv, в результате чего мы получили игру в которой при прохождении лабиринта, игрока отправляли на прохождение следующего.
Дальнейшей идеей улучшения Colobka было улучшение монстров. Первым шагом было улучшение вертикального и горизонтального монстров. Начиная с этого момента они застревали, только тогда, когда были зажаты тремя стенками. Но ,по мнению руководителя проекта, это было мало. Тогда был создан третий монстр, который не охотился за игроком, а просто ходил по лабиринту, залезая почти во все углы. Примерно двумя днями раньше были доделаны последние уровни игры.
Достижения.
На сегодня мы имеем следующие достижения:
1)Игру colobok.pas, которую собственно и надо запускать для игры.
2)Систему уровней объединённых в файле Default.clv (см. colobok.rar). Сейчас там 9 авторских уровней, которые при желании можно менять местами. Правило записи файлов простое. Сначала пишется полное имя уровня (расширение clv), на следующей строчке два числа от 0 до 100, которые показывают шанс хода 1 и 2 монстров. Если уровень последний, то на строчке выше названия пишется слово last. Для прохождения этих уровней после запуска Colobok.exe надо ввести 1 и нажать Enter.
3) 3 типа монстров: # (атакует по вертикали), @ (атакует по горизонтали) и * (ходит по карте по правилу левого поворота)
4) Возможность использовать функции Save (в игре нажмите s и введите имя для сохранения) и Load (в игре нажмите l и введите имя сохранённого файла).
5) Возможность использовать коды, для прохождения игры.
Для ввода кода нажмите y (скорее всего два раза). После этого внизу появиться курсор и можно вводить читы. Вот один из них: Svarog.
Что делает этот код и какие есть ещё, вы узнаете, если захотите.
Михаил Овчинников, Алексей Лоскутов