Разработка алгоритма и реализация игры "Реверси" (стр. 1 из 2)
Федеральное агентство по образованию Российской Федерации
Брянский Государственный Технический Университет
Кафедра «Информатика и программное обеспечение»
Курсовая работа
по предмету: «Интеллектуальные системы»
на тему: «Разработка алгоритма и реализация игры “реверси”»
Выполнил:
студент гр. 07-ПО3
Черкесов М.В.
Преподаватель:
Булатицкий Д.И.
Брянск
2010
Введение
1. Алгоритм
1.1 Алгоритм альфа-бета отсечения
2. Описание программного средства
2.1 Руководство пользователя
2.2 Листинг программы
Заключение
Список литературы
Введение
В игре используется квадратная доска размером 8 × 8 клеток (все клетки могут быть одного цвета) и 64 специальные фишки, окрашенные с разных сторон в контрастные цвета, например, в белый и чёрный. Клетки доски нумеруются от верхнего левого угла: вертикали — латинскими буквами, горизонтали — цифрами. Один из игроков играет белыми, другой — чёрными. Делая ход, игрок ставит фишку на клетку доски «своим» цветом вверх.
В начале игры в центр доски выставляются 4 фишки: чёрные на d5 и e4, белые на d4 и e5.
Первый ход делают чёрные. Далее игроки ходят по очереди.
Делая ход, игрок должен поставить свою фишку на одну из клеток доски таким образом, чтобы между этой поставленной фишкой и одной из имеющихся уже на доске фишек его цвета находился непрерывный ряд фишек соперника, горизонтальный, вертикальный или диагональный (другими словами, чтобы непрерывный ряд фишек соперника оказался «закрыт» фишками игрока с двух сторон). Все фишки соперника, входящие в «закрытый» на этом ходу ряд, переворачиваются на другую сторону (меняют цвет) и переходят к ходившему игроку.
Если в результате одного хода «закрывается» одновременно более одного ряда фишек противника, то переворачиваются все фишки, оказавшиеся на всех «закрытых» рядах.
Игрок вправе выбирать любой из возможных для него ходов. Если игрок имеет возможные ходы, он не может отказаться от хода. Если игрок не имеет допустимых ходов, то ход передаётся сопернику.
Игра прекращается, когда на доску выставлены все фишки или когда ни один из игроков не может сделать хода. По окончании игры проводится подсчёт фишек каждого цвета, и игрок, чьих фишек на доске выставлено больше, объявляется победителем. В случае равенства количества фишек засчитывается ничья.
Игра была изобретена в Великобритании в 1880 году и пользовалась большой популярностью, но впоследствии была забыта. Возродили её в Японии, где она в 1971 году под названием отелло вновь стала популярна. С 1977 года регулярно проводятся чемпионаты мира по игре в реверси.
Реверси является стратегической игрой, схожей с шашками и шахматами. Так же как и в шахматах, принято разделять партию на три части: дебют (начало), миттельшпиль (середина игры) и эндшпиль (концовка). Однако, в отличие от шахмат, количество возможных дебютов здесь намного меньше, и все они легко запоминаются. Все сколько-либо серьёзные игроки знают дебюты на 5-6 ходов вперёд, чтобы избежать заведомо проигрышных ходов на данной стадии. Миттельшпиль, пожалуй, является наиболее «свободной» и одновременно сложной частью игры, когда положение можно либо упрочить, либо изменить в свою пользу. Несмотря на это, многие, казалось бы, проигранные в миттельшпиле партии обретают новые качества при вступлении в конечную стадию игры — эндшпиль. Золотое правило концовки — не спешить и считать. Считать принято фишки, которые результируют конечный исход игры для конкретной тактики. Естественно, количество исходов зависит от того, с какого хода начинать считать, и именно поэтому компьютеры играют намного лучше людей — они могут позволить себе просчитать все возможные варианты (их, по компьютерным меркам, немного) и всегда выбирают тот, при котором минимизируется результат человека и максимизируются очки компьютера.
Существует достаточно много различных стратегий игры в реверси[1], и выбор определяется уровнем подготовки и наклонностями игрока. Простейшей для новичков может быть игра за захват угловых клеток доски, которые впоследствии уже невозможно «перекрасить» в другой цвет, и последовательное занятие доски от углов. Более продвинутой тактикой считается ограничение возможных ходов противника: создаётся позиция, в которой противнику остаются только устраивающие игрока ходы, и игра проходит в удобном для игрока русле. Как правило, большинство японских мастеров отличается именно этой, отточенной до совершенства, тактикой. Ещё более продвинутой тактикой является тактика «темпов» (англ. temp), которую можно охарактеризовать правилом «отними у противника его самые выгодные ходы и сделай их своими». Данная стратегия требует, однако, чрезвычайно сильного «чувства позиции».
Варианты реверси:
· Реверси n × n
Игра на поле n × n клеток. От игры 8 × 8 отличается тем, что фишки одного цвета в начале игры ставятся не в шахматном порядке, а рядом. Существуют варианты реверси с размером поля 10 × 10 и больше. Они не отличаются от обычных ничем, кроме размера поля. В целом, варианты размером меньше 8 × 8 не представляют интереса, поскольку являются детерминированными и при идеальной стратегии всегда выигрывает второй игрок (тот, кто ходит вторым).
· Антиреверси
Отличается только тем, что при подведении результатов игры выигрывает тот, у кого фишек меньше.
· Реверси с чёрной дырой
Отличается только тем, что одна из клеток доски (случайно выбирается в начале игры) помечается как «черная дыра». При этом на неё нельзя сделать ход, и фишки с одной стороны такой клетки не могут захватить фишки с другой.
Компьютерные программы реверси уже с середины 1990-х годов играют намного сильнее людей. Программа Logistello в 1997 году обыграла чемпиона мира Такэси Мураками 6:0.[4]
Как и многие игры, реверси довольно распространены в Интернете. Однако, отсутствие «культового» статуса, позволяет наткнуться в онлайне на игроков мирового уровня (так, например, на сайте рамблер.ру, одно время играл основатель Ассоциации реверси в СССР Олег Степанов, а трёхкратный чемпион мира Хидеси Таменори до сих пор играет на www.kurnik.pl под ником becky2002jan). Практически все уважающие себя гейм-порталы имеют раздел реверси, однако вследствие того, что компьютеры играют намного лучше людей, в Интернете считается хорошим тоном играть только блицы (обычно до двух минут на каждого игрока).
разработка алгоритм программа листинг
Для компьютера эта игра является достаточно простой и хорошие программы без особого труда обыгрывают даже чемпионов среди людей. Данное качество достигается на данном этапе развития техники алгоритмом альфа-бета отсечения, с использованием большой базы данных уже прошедших партий. В игре существует порядка 10^28 позиций, и около 10^58 возможных партий.
1.1 Алгоритм альфа-бета отсечения
Альфа-бета отсечение (англ. Alpha-beta pruning) — это алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом минимакс. Этот алгоритм предназначен для антагонистических игр и используется для машинной игры (в шахматах, го и других). В основе алгоритма лежит идея, что оценивание ветви дерева поиска может быть досрочно прекращено (без вычисления всех значений оценивающей функции), если было найдено, что для этой ветви значение оценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви. (Рис.1) Альфа-бета отсечение является оптимизацией, так как результаты работы оптимизируемого алгоритма не изменяются.
Рис.1 Алгоритм альфа-бета отсечения
Преимущество альфа-бета отсечения фактически заключается в том, что некоторые из ветвей подуровней дерева поиска могут быть исключены после того, как хотя бы одна из ветвей уровня рассмотрена полностью. Так как отсечения происходят на каждом уровне вложенности (кроме последнего), эффект может быть весьма значительным. На эффективность метода существенно влияет предварительная сортировка вариантов (без перебора или с перебором на меньшую глубину) — при сортировке чем больше в начале рассмотрено «хороших» вариантов, тем больше «плохих» ветвей может быть отсечено без исчерпывающего анализа. минимаксный поиск осуществляется в глубину, поэтому в любой момент времени достаточно рассматривать узлы вдоль единственного пути в дереве. Алгоритм альфа-бета-отсечения получил свое название по следующим двум параметрам, которые представляют пределы в зарезервированных значениях, присутствующих во всех узлах вдоль этого пути: а = значение наилучшего варианта (т.е. варианта с самым высоким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока МАХ; Р = значение наилучшего варианта (т.е. варианта с самым низким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока MIN. Алгоритм альфа-бета-поиска в процессе своей работы обновляет значения а и Р, а также отсекает оставшиеся ветви в узле (т.е. прекращает рекурсивные вызовы), как только становится известно, что значение текущего узла хуже по сравнению с текущим значением а или Р для игрока МАХ или MIN соответственно.
2. Описание программного средства
2.1 Руководство пользователя
Для работы с программой необходимо активизировать её. Для этого нужно на рабочем столе двойным кликом мыши щелкнуть по ярлыку «Reversi»: Спустя мгновение перед вами откроется рабочее окно приложения (Pиc.2).
Оно состоит из элементов:
· Игровое поле, где находятся фишки игрока и противника.
· Поле подсчёта очков (количества фишек).
· Кнопка начала новой игры.