Главная страница « Информация « 4 курс « курс ФПScheme «

Варианты задания «Создание игровой программы на основе минимаксного алгоритма». 2019-20 учебный год


«...писать программы на Лиспе -- громадное удовольствие.»
Х. Абельсон, Дж. Дж. Сассман, Д. Сассман «Структура и интерпретация компьютерных программ»

Общие сведения о задании


Создайте игровую программу, используя минимаксный алгоритм. Максимальный балл -- 35. При решении второго задания можно использовать обычные библиотеки racket, мутируемые структуры, средства ООП Racket, присваивание. Использование этих средств должно быть обосновано. При оценке игровой программы учитывается «сила» её игры, сложность выбранной игры, сложность реализации. Код второго задания должен быть оформлен как следует и должен содержать содержательные комментарии на русском языке. В них следует указать, как представлена игровая ситуация, какой способ решения игры (поиска хода) реализован, каковы его параметры. Как отправную точку в написании кода решающей части игровой программы можно рассматривать реализацию крестиков-ноликов на Racket (адаптированный код выложен в ВК-группе). Этапы сдачи:
1й -- создание основы игры. Следует придумать внутреннее представление для игровой ситуации. Реализовать основные функции: перейти в новую ситуацию из текущей согласно некоторому ходу игрока; проверить, окончена ли игра (победой, поражением, ничьей); вывести игровую ситуацию в текстовом виде. Следует реализовать двух "игроков", делающих ходы по вводу пользователя. Максимальный балл -- 15. Сдача без штрафа до 26 ноября.
2й -- создание итоговой версии. Следует реализовать решающие функции: эвристически оценить позицию; построить дерево с оценками, выбрать оптимальный ход по минимаксу (с альфа-бета-отсечением). Следует реализовать двух "игроков", делающих оптимальные ходы. Максимальный балл -- 15. Сдача без штрафа до 17 декабря. Не рассматриваются «реализации», в которых под видом поиска по минимаксу с альфа-бета-отсечением осуществляется ординарный поиск и/или генерация случайных ходов.
3й -- сдача отчёта в электронном виде (в формате PDF). Максимальный балл -- 5. Сдача без штрафа до даты проведения экзамена. Позже баллы за отчёт не начисляются, но отчёт должен быть сдан.

Для сдачи онлайн следует направить код лектору по электронной почте. Сдача может быть осуществлена офлайн, но если по истечении 7 дней после сдачи код не прислан, то отметка о сдаче аннулируется, баллы обнуляются.

Для зарабатывания дополнительных баллов предлагается реализовать GUI для удобной игры против "человека"/"машины" и/или просмотра поединка двух "машин". Максимальная сумма баллов за GUI -- 15. Решения по этой части принимаются до истечения астрономического 2019го года. Позже зарабатывание дополнительных баллов невозможно. Если Вас не привлекает создание GUI, то можно, используя версию языка slideshow хотя бы выводить игровую позицию в более наглядном виде, чем псевдографика. 15 баллов за такое не заработаете, но сколько-то можете получить.

Требования к отчёту

Отчёт пишется на русском языке. Вёрстку можете осуществлять в любой подходящей для Вас системе. Текст отчёта должен быть разбит на следующие части:

  • Титульный лист, с «шапкой» – «Московский государственный университет имени М. В. Ломоносова, факультет Вычислительной математики и кибернетики». Далее следует заголовок: «Отчёт по второму заданию», номер и тема варианта задания, сведения об исполнителе (фамилия, имя и отчество полностью, номер группы). Внизу титульного листа указывается город и год. Нелишне обратить внимание на то, что точки после заголовков не ставятся.

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

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

  • Вторая глава, названная «Создание основы игры», содержит описание структур данных для представления игровой ситуации и основных функций.

  • Третья глава, названная «Создание итоговой версии», содержит описания: выбранной эвристической функции и её обоснование; параметров поискового алгоритма (глубины раскрытия дерева, усовершенствование выбора ходов, улучшение минимакса и т. п.); реализаций решающих функций. Эти дополнительно был реализован GUI, то в текст главы следует включить его описание. Должно быть описано, как протекает одна игровая партия, должны быть приложены скриншоты, поясняющие особенности дизайна GUI.

  • Четвёртая глава, названная «Результаты», содержит анализ результатов работы программы. Следует охарактеризовать результаты, полученные на тестовых прогонах программы, оценить «силу» игры программы. Если доступны другие реализации выбранной игры, следует сравнить результаты их работы с результатами, демонстрируемыми Вашей программой.

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

  • Список использованной литературы приводится, если в ходе работы над заданием были использованы статьи и/или книги. Библиографические записи в списке следует оформлять по рекомендациям ГОСТ. Сделать это можно при помощи Google.Schollar, который умеет импортировать по ГОСТ. На каждую запись списка в тексте отчёта должна быть ссылка. Пожалуйста, не указывайте статьи из Википедии как источники. Они не проходят такой же цикл проверки как научная публикация, как книга. Явное указание в Вашем тексте ссылки в Викидедию или любую другую энциклопедию равнозначно явно высказанной гипотезе о том, что Ваш читатель не догадается / не сможет самостоятельно искать в википедии или любой другой энциклопедии. Это дурной тон.

  • Приложение, которое содержит Ваш код.

На всякий случай, приведён вид страницы с содержанием (без указания номеров страниц для 2 главы и последующих частей отчёта)
Содержание
1. Постановка задачи .........................3
2. Создание основы игры ...................
3. Создание итоговой версии ...
4. Результаты ................................
Заключение ...................................
Список литературы ............................
Приложение. Код программы.....................


Список вариантов

  1. Калах

  2. Четыре в ряд

  3. Крестики-нолики 3D

  4. Шашки

  5. Миниуголки

  6. Реверси

  7. Шахматы 5х5

  8. Му-торере

  9. Рэндзю

  10. Четыре в ряд 3D

  11. Пятипольное коно

  12. Семь цветов

  13. Точки и квадраты

  14. L-игра

  15. 8 пешек

  16. Qubic

  17. Если доставшаяся Вам игра чем-то не подходит, то предлагайте свои варианты («Крестики-нолики», Ним, Точки, и другие игры, для которых легко найти реализацию на Racket или Scheme, не рассматриваются).

Вариант 1. Калах


Сведения об игре см. тут. Реализуйте вариант с 72 камнями.

Вариант 2. Четыре в ряд


Сведения об игре см. тут. Реализуйте вариант с полем 7x6.

Вариант 3. Крестики-нолики 3D


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

Вариант 4. Шашки


Вариант игры "английские" шашки на поле 8х8. Сведения об игре см. тут. Можно по согласованию с лектором рассмотреть доску меньшего размера и/или игру с меньшим количеством шашек (например, решение окончания шашечной партии с 4-5 шашками/дамками).

Вариант 5. Миниуголки


Вариант на поле 6х6 с начальным размещением 2х3. Правила осуществления ходов можно уточнить. Сведения об обычном варианте игры см. тут.

Вариант 6. Реверси


Можно реализовать только "дебют", т. е. фактически, рассматривать доску 6х6 вместо 8х8. Сведения об игре см. тут.

Вариант 7. Шахматы 5х5


Игра известна под названием «Мини-шахматы Гарднера». Сведения об игре см. тут. Можно по согласованию с лектором рассмотреть игру с меньшим количеством фигур и пешек (например, решение окончания шахматной партии с 4-5 фигурами: король и ладья против короля и 2х пешек и т. п.).

Вариант 8. Му-торере


Вариант уголков на особом поле, придуманный инками. Сведения об игре см. тут.

Вариант 9. Рэндзю


Простой вариант с полем 15х15, без фолов и пасов. Сведения об игре см. тут.

Вариант 10. Четыре в ряд 3D


Плоский вариант игры дан в варианте 2. Следует реализовать 3D-разновидность, в которой используется поле 4х4х4 и выигрывает игрок первым собравший ряд и своих символов (крестиков или ноликов). Сведения об игре см. тут.

Вариант 11. Пятипольное коно


Корейский вариант уголков на доске 5х5 с 7 фишками. Ходы только по диагонали. Сведения об игре см. тут.

Вариант 12. Семь цветов


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

Вариант 13. Точки и квадраты


Вариант на поле 5х5. Сведения об игре см. тут.

Вариант 14. L-игра


Сведения об игре см. тут.

Вариант 15. Восемь пешек


Игра 4 белых пешек против 4 чёрных пешек на поле 4х4. Сведения о схожей игре шестью пешками на доске 3х3 см. тут.

Вариант 16. Qubic


Трехмерный вариант крестиков-ноликов в кубе 4х4х4. Сведения об игре см. тут. Реализуйте вариант игры, в котором победа достигается при построении ряда из четырёх крестиков, либо из четырёх ноликов.

Предупреждение


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

  

© Кафедра системного программирования ВМК МГУ.

Обновлено: 1.IX.2019