29

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ” Кафедра “Системного аналізу та управління” Курсова робота Дисципліна “Дискретна математика" Тема „Ігри класу Нім на графах”(Варіант №11-20) Керівник роботи: доц. каф. САіУ, канд.техн.наук Волдеморт Л.М. Виконавець: студент групи ІФ-50в Поттер Г.В. Харків – 2007

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Кафедра “Системного аналізу та управління”

Оцінка

________________________

голова комісії

доц. каф.САиУ

____________ /Кащеєв Л.Б./

« » ___________ 200 _ р.

КУРСОВА РОБОТА

Дисципліна: „Дискретна математика”

Тема: „Ігри класу Нім на графах”(Варіант №11-20)

Виконавець: ст. гр. ИФ-50^в Г.В.Поттер

“ ” 200 р.

Керівник роботи: доц., канд. техн. наук Л.М.Волдеморт

“ ” 200 р.

Харків 2007

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Кафедра “Системного аналізу та управління”

Студент Поттер Г.В. Група ИФ-50^в

ЗАВДАННЯ на науково-дослідну курсову роботу

Дисципліна: “Дискретна математика”

Тема: „Ігри класу Нім на графах”(Варіант №11-20)

Короткий зміст роботи:

а) теоретична частина

Розробка методики розв’язання задачі гри в Ним:

Ілюстрація на графі «простій ігри Ним» на дві купки предметів

- 11 і 5 (ходить гравець, супротивник, що програє, завжди бере 1 предмет з першої купки)

- 7 і 7 (ходить гравець, супротивник відповідає оптимальним чином, не менш 4 кроків)

Ілюстрація на графі «Цзяньшизци» на дві купки предметів

- 11 і 5 (ходить гравець, супротивник, що програє, завжди бере 1 предмет з першої купки).

Покрокове рішення гри Зірковий ним з ходом супротивника – супротивник завжди ходить оптимальним чином або від безвихідності бере один предметів з будь-якого «променю».

Покрокове рішення гри Марієнбад (ним на купки 1,3,5,7, узяти останній предмет) з ходом супротивника і гравця – супротивник завжди ходить оптимальним чином або від безвихідності бере один предмет з «наймолодшої купки».

б) програмно-розрахункова частина

Розробка програмного забезпечення, яке дозволяє грати у гру Нім на 2..4 купки, гру Цзяньшицзи на 2 кучки та Марієнбад.

Дата видачі завдання: 15.03.2007 Термін захисту: 21.05.2006

Керівник курсової роботи: / канд. техн. наук, доц. САіУ Л.М.Волдеморт/

СОДЕРЖАНИЕ

Введение …….………..………………………………………………………..5

1 Расчетная часть работы ……………………………………………………..8

1.1 «Простая игра Ним». ……………………………………………………...8

1.1.1 Правила игры Ним, стратегия выигрыша …………....................8

1.1.2 Изображение игры Ним на графе ………………………………..8

1.1.3 Пример игры Ним со стартовой точкой в «окружении» графа ..9

1.1.4 Пример игры Ним со стартовой точкой в «ядре» графа …….....10

1.2 Игра Звездный Ним ………………………………………………………..11

1.3 Игра Цзяншицзы ………..……………………………………………….....13

1.3.1 Правила игры Цзяншицзы, стратегия выигрыша ..………...........13

1.3.2 Изображение игры Цзяншицзы на графе ………………………..14

1.3.3 Цзяншицзы со стартовой точкой в «окружении» графа ………..16

1.4 Игра Мариенбад ……………………………………………………………17

1.4.1 Правила игры Мариенбад, стратегия выигрыша .......………......17

1.4.2 Пример игры в Мариенбад ...…………….…………………….....18

2. Постановка задачи на программирование …………………………………20

2.1. Постановка задачи ………………………………………………………..20

2.2. Описание разработанного объекта ………………………………………21

2.2.1. Иерархия наследования …………………………………………21

2.2.2. Организация объекта ……………………..……………………..22

2.3. Интерфейс программы ………………………………………………….23

Заключение …………………………………………………………………...25

Список использованных источников ……………………………………….26

ВВЕДЕНИЕ

Это очень древний класс математических игр. Отнимать что-либо друг у друга люди начали с незапамятных времен. Обычно в этих играх используются так или иначе сложенные кучки камешков, спичек или других фишек, которые игроки по очереди разбирают. Но если у вас есть бумага и карандаш, то удобнее камешки рисовать, просто обводя клетки, а снимать фишки, перечеркивая клетки. Недостатком этих игр, с точки зрения настоящих игроков, является то, что почти для каждой (но не для всех!) можно найти выигрышную стратегию. Если ваш друг не математик, то с ним вполне можно сразиться в любую из этих игр. Кстати, название этим играм "nim" (в переводе с английского "взять", "стянуть") придумал один английский профессор математики.

Перечисли кратко наиболее известные игры Ним.

Ним (или «Простая игра Ним»).

Имеется несколько кучек, в каждой из которой определенное число фишек. Обычно фишек кучках в общей сумме не менее 15. За ход можно брать сколько угодно фишек из любой кучки, но только из одной. Кто взял последнюю, тот выиграл. Существует выигрышная стратегия.

Обратная игра Ним.

Правила совпадают с «Простой игрой Ним», но, кто не взял последнюю, тот выиграл. Существует выигрышная стратегия.

Мариенбад.

Частный случай игры Ним. 16 фишек расставляются в четыре ряда: в первом - одна, во втором - три, в третьем - пять, в четвертом - семь. Кто взял последнею, тот проиграл. Можно наоборот играть: кто взял последнею, тот выиграл. Существует выигрышная стратегия.

Баше.

Эту игру исследовал французский математик Баше еще в начале XVII века, а сколько ей лет на самом деле никто не знает. Из одной кучи берут не менее одной, но не более заранее обусловленного количества. Кто взял последнею, тот выиграл. Существует выигрышная стратегия.

Дюма.

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

Цзяньшицзы.

Очень древняя китайская игра. Две кучки. Допускается брать сколько угодно из любой или поровну из двух сразу. Кто взял последнюю, тот выиграл. Существует выигрышная стратегия.

Кейлс.

Придумана в начале XX века. Двенадцать клеток располагают в ряд и одну рядом. За ход можно перечеркнуть одну или две клетки расположенные рядом. Выигрывает тот, кто перечеркнет последнюю фишку.

Рассада.

Игру придумал Дж. Конвей и М. Петерсон в 1967 году. В начале рисуется несколько точек (не стоит рисовать больше 7). Каждым ходом игрок, может или нарисовать петлю из какой либо точки или соединить две точки кривой, при этом на этой петле или кривой рисуется новая точка. Нельзя пересекать линии и точки. Из одной точки не должно быть более трех линий ("ростков"). Кто не сможет сделать очередного хода, тот проиграл.

Сим.

Игру придумал специалист по теории графов Г.Симмонс. На окружности расставляется несколько точек (меньше 6 не интересно). При каждом ходе игроки соединяют любые две точки прямой линией своего цвета. Кто вынужден первым построить треугольник своего цвета, тот проиграл.

Усадьба Хакенбуш.

Эту замечательную игру придумал математик Джон Конвей. Для игры используется картинка с "усадьбой Хакенбуш" (смотри ниже) или другая нарисованная в таком же стиле. А именно: картинка должна быть в рамке; все ее элементы должны быть связаны с рамкой; все соединения линий ограничиваются точками.

За один ход игрок стирает одну любой отрезок картинки, ограниченный точками или одной точкой если отрезок это петля.

Если после удаление этой линии, часть линий оказывается не связанной с рамкой, то она удалятся тоже.

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

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

Рисунок В.1 - Усадьба Хакенбуш

1 Расчетная часть работы

1.1 «Простая игра Ним»

1.1.1 Правила игры Ним, стратегия выигрыша

Правила игры Ним – имеет определенное количество предметов в N кучках (N ≥ 2). Игроки по очереди берут любое ненулевое количество предметов из любой кучки. Выигравшим считается тот игрок, который взял последний предмет.

Простая игра Ним имеет относительно несложный алгоритм выигрыша. По имени математика, нашедшего этот алгоритм, выигрышные точки на графе состояния игры называются точками Гранди. Точки Гранди делят множество вершин графа состояния на два подмножества – «ядро» и «окружение». Ядром называются те вершины графа, в которых функция Гранди имеет нулевые значения. Для простой игры Ним функция Гранди представляет собой «сумму по модулю два» для количества предметов в каждой из кучек, записанных в двоичном коде.

1.1.2 Изображение игры Ним на графе

Для игры, заданной в моем варианте (11 и 5 предметов) граф представлен на рис.1.1.

Рисунок 1.1 – Исходная позиция для игры Ним на две кучки 11 и 5

1.1.3 Пример игры Ним со стартовой точкой в «окружении» графа

Очевидно, что для двух кучек равенство нулю суммы по модулю 2 чисел, выраженных в двоичном коде достигается, когда количество предметов в кучках равно. Эти точки на графе выделены двойной обводкой. Осуществляя ход, мы должны из окружения перейти в ядро – берем из первой кучки 6 предметов, попадая в точку (5,5), рис.1.2.

Рисунок 1.2 – Первый ход, в точку с нулевым значением функции Гранди

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

Рисунок 1.3 – Изображение на графе игры ним на две кучки

Представленные на графе коды можно представить в табличном виде, табл.1.1.

Таблица 1.1

Ход игры Ним на две кучки из стартовой позиции 11 и 5

(число предметов оставшихся в кучках после хода игроков)

Номер хода	Игрок 1		Игрок 2
	Кучка 1	Кучка 2	Кучка 1	Кучка 2
1	5	5	4	5
2	4	4	3	4
3	3	3	2	3
4	2	2	1	2
5	1	1	0	1
6	0	0	Первый игрок победил, второй проиграл

1.1.4 Игра Ним со стартовой точкой в «ядре» графа

Второй пример моего задания, к сожалению, начинает игру из точки ядра (7,7), потому при правильной игре второго игрока первый игрок всегда проиграет. Чтобы не затягивать игру (а заодно проверить, умеет ли играть второй игрок) я буду брать из произвольных кучек 3,2 и 1 предмет, рис.1.4.

Рисунок 1.4 – Первый ход, в точку с нулевым значением функции Гранди

Аналогично предыдущей игре, игровой процесс можно представить таблицей, табл.1.2.

Таблица 1.2

Ход игры Ним на две кучки из стартовой позиции 7 и 7

(число предметов оставшихся в кучках после хода игроков)

Номер хода	Игрок 1		Игрок 2
	Кучка 1	Кучка 2	Кучка 1	Кучка 2
1	7	4	4	4
2	2	4	2	2
3	2	1	1	1
4	0	1	0	0
	Первый игрок проиграл, второй победил