Программирование логических игр
Министерство
образования и науки Российской Федерации
Федеральное
государственное бюджетное образовательное учреждение
высшего
профессионального образования
«Ижевский
государственный технический университет имени
М. Т. Калашникова»
Кафедра
«Программное обеспечение»
Отчет
по курсовой работе
«Программирование
логических игр»
«Ним»
Выполнил:
студент гр. Б06-191-2
Э.Ф. Ахмерова
Принял:
А.В. Коробейников
Ижевск
-
2015
СОДЕРЖАНИЕ
1. ПОСТАНОВКА
ЗАДАЧИ
2. ОПИСАНИЕ
ИГРЫ
3. ФОРМАЛИЗАЦИЯ
ДЕРЕВА СОСТОЯНИЙ
4. ОПИСАНИЕ
ПРЕДЛОЖЕННЫХ ЭВРИСТИК
5. КРАТКОЕ
ОПИСАНИЕ ИСПОЛЬЗОВАННЫХ АЛГОРИТМОВ
6. ОПИСАНИЕ
АДАПТАЦИИ АЛГОРИТМОВ К ВАШЕЙ ЗАДАЧЕ
7. СТРУКТУРА
ПРОГРАММЫ ИЛИ АЛГОРИТМОВ
7.1 Иерархическая
схема программы
7.2 Блок-схемы
программы
8. ИСХОДНЫЕ
ТЕКСТЫ ПРОГРАММЫ
9. ПРИМЕР
РАБОТЫ ПРОГРАММЫ
10. ПРИМЕР
ДЕРЕВА СОСТОЯНИЙ
ВЫВОДЫ ПО ДОСТИГНУТЫМ РЕЗУЛЬТАТАМ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
. ПОСТАНОВКА ЗАДАЧИ
В настоящее время теория
искусственного интеллекта активно развивается. Одним из направлений является
решение логических игр. Это позволяет разработчику формализовать поиск в
пространстве состояний, что является ключевым методом искусственного
интеллекта. Игровые задачи легко представимы в компьютерной программе, поэтому
разработка не сильно затруднена.
Целью работы является получение
практических навыков решения сложных задач на примере логических игр с помощью
подходов СИИ и закрепление теоретических знаний методам поиска по дереву
состояний.
Необходимо проанализировать
пространство состояний и дерево решений игры Ним, разработать программу на
языке высокого уровня, моделирующую данную игру.
. ОПИСАНИЕ ИГРЫ
Ним - математическая игра, в
которой два игрока по очереди берут предметы, разложенные на несколько кучек.
За один ход может быть взято любое количество предметов (большее нуля) из одной
кучки. Выигрывает игрок, взявший последний предмет.
В классическом варианте игры
число кучек равняется трём.
Игра Ним попала в Европу в XVI
веке из Китая. Имя «ним» было дано игре американским математиком Чарльзом
Бутоном (англ. Charles Bouton), описавшим в 1901 году выигрышную стратегию
игры.
Существует несколько вариантов
происхождения названия игры:
- от немецкого
глагола Nimm или старо-английского глагола Nim, имеющих значение «брать»;
- от английского
глагола WIN («побеждать»), переворачиванием слова;
. ФОРМАЛИЗАЦИЯ ДЕРЕВА
СОСТОЯНИЙ
Для данной игры Ним зададим 3
кучки с количеством камней i
= [3;5]. Пространство состояний - это граф из множества вершин и дуг,
соединяющих пары вершин. В модели пространства состояний решаемой задачи
вершины графа представляют дискретные состояния процесса решения, например
различные сочетания размеров кучек. Дуги графа описывают переходы между
состояниями. Эти переходы соответствуют логическим заключениям или допустимым
ходам в игре. Фрагмент пространства состояний для игры Ним представлен на рис.
1.
Рис. 1. Фрагмент пространства
состояний
Поиск в пространстве состояний
предполагает нахождение пути от исходного состояния к целевому. Цель может
описывать выигрышное состояние. Эвристический поиск определяется как выбор
ветвей из пространства состояний на основе определенных правил, которые с
наибольшей вероятностью приведут к приемлемому решению проблемы.
Для игры Ним с размерами кучек
в 5 камней количество состояний всего составляет 6*6*6 = 216. Так как
пространство состояний для данной игры очень велико, я использую минимаксный
алгоритм на ограниченную глубину. При этом поиск осуществляется вглубь на
определенное число уровней.
. ОПИСАНИЕ ПРЕДЛОЖЕННЫХ
ЭВРИСТИК
Эвристикой может считаться
оптимальное состояние игры, требуемое для выигрыша. Так как мы не можем
просматривать граф состояний полностью, каждой вершине присваивается значение,
определяемое эвристической функцией. Алгоритм поиска затем использует эти
значения, чтобы выбрать наилучший среди возможных ходов из очередной корневой
вершины.
Для игры Ним выбор выигрышного
состояния определяется функцией Шпрага-Гранди. Следствие этой функции: для
текущего игрока стратегия является выигрышной тогда и только тогда, когда
xor-сумма размеров кучек положительна. Состояние любой «равноправной» игры
можно изобразить в виде ним-кучки. Если размер кучки равен нулю, то состояние
проигрышное. Если не равен - выигрышное.
Рассмотрим пример игры с
состоянием 3-2-4 (рис. 2).
В скобках указаны xor-суммы
размеров кучек. Max должен сделать такой ход, чтобы состояние для Min было
проигрышным, поэтому выбирается состояние 3-2-1, где xor-сумма равна 0.
Если среди возможных ходов не
будет состояния с xor-суммой, то производится поиск на еще один уровень для
определения наилучшего пути.
. КРАТКОЕ ОПИСАНИЕ
ИСПОЛЬЗОВАННЫХ АЛГОРИТМОВ
Алгоритм минимаксной стратегии
на ограниченную глубину:
. Построение дерева игровых
состояний из текущего состояния (корневой вершины) на заданное число уровней.
. Определение эвристических
оценок для состояний на последнем (горизонтном) уровне дерева состояний
(листья).
. Минимаксный перенос
результатов игры от листьев графа вверх по графу к корню в соответствии с
минимаксным правилом.
. Принятие решения об очередном
ходе в соответствии со значениями минимаксного переноса: Max ходит в сторону
максимального из детей, Min − в сторону минимального.
. Для принятия решения по
следующему ходу игрока необходимо повторное построение дерева состояний из
новой текущей (корневой) вершины.
. ОПИСАНИЕ АДАПТАЦИИ
АЛГОРИТМОВ К ВАШЕЙ ЗАДАЧЕ
Смысл игр Ним таков, что при
правильном алгоритме можно после первого хода определить победителя. Поэтому
достаточно просматривать пространство состояний на 1 уровень вперед для
определения наилучшего хода.
Алгоритм минимаксной стратегии
на ограниченную глубину для игры Ним:
. Построение дерева
игровых состояний из текущего состояния на 1 уровень вперед.
. Определение
эвристической оценки для каждого состояния уровня.
. Если ходит Max,
то перейти к пункту 4, иначе перейти к пункту 6.
. Если среди оценок есть
нулевая, то вернуть номер этого состояния, иначе переход к пункту 5.
. Присвоить ход к Min
и перейти к пункту 1.
. Если среди оценок нет
нулевых, то вернуть номер состояния, иначе выход.
. СТРУКТУРА ПРОГРАММЫ
ИЛИ АЛГОРИТМОВ
Рис. 3
_Load запускает функцию DrawStones,
получает начальное состояние игры.генерирует начальное состояние игры с помощью
генератора случайных чисел, инициализирует поля для изображений, выводит на
экран изображения камней._Click - процедура при нажатии на кнопку.
Устанавливает новое текущее состояние, запускает функцию RemoveStones, выводит
сообщение в случае выигрыша пользователя.удаляет необходимое количество камней
с экрана.выполняет ход компьютера, запускает функцию GetPossibleStates, затем
GetProfitState и RemoveStones, выводит сообщение в случае выигрыша
компьютера.формирует список состояний из текущего состояния.находит выигрышное
состояния, вычисляя xor-суммы.
7.2 Блок-схемы
программы
8. ИСХОДНЫЕ
ТЕКСТЫ ПРОГРАММЫ
using
System;
using
System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Threading.Tasks;System.Windows.Forms;System.Threading;Nim
{partial class
Form1 : Form
{struct State
{int x;int y;int z;
}State
currentState;[] imgBox1;[] imgBox2;[] imgBox3;<PictureBox>
box1;<PictureBox> box2;<PictureBox> box3;
Image[] img1;[]
img2;[] img3;
private bool max =
false;bool handup = false;path;Form1()
{();
}void
Form1_Load(object sender, EventArgs e)
{=
Environment.CurrentDirectory;index = path.IndexOf("bin");=
path.Substring(0, index);
//first state=
DrawStones();.Maximum = currentState.x;.Maximum = currentState.y;.Maximum =
currentState.z;possibleStates = new List<State>();=
GetPossibleStates(currentState);lines2 = new List<String>();(var i = 0; i
< possibleStates.Count; i++)
{.Add(String.Format("{0}-{1}-{2}
= {3}", Convert.ToString(possibleStates[i].x),
Convert.ToString(possibleStates[i].y), Convert.ToString(possibleStates[i].z),
Convert.ToString(possibleStates[i].x ^ possibleStates[i].y ^
possibleStates[i].z)));
}.IO.File.WriteAllLines(@path
+ "PosssibleStates.txt", lines2);.Start();
}List<State>
GetPossibleStates(State currentState)
{stateList = new
List<State>();state;(var i = 0; i < currentState.x; i++)
{.x = i;.y =
currentState.y;.z = currentState.z;.Add(state);
}(var i = 0; i <
currentState.y; i++)
{.x =
currentState.x;.y = i;.z = currentState.z;.Add(state);
}(var i = 0; i <
currentState.z; i++)
{.x =
currentState.x;.y = currentState.y;.z = i;.Add(state);
}stateList;
}void button1_Click(object
sender, EventArgs e)
{.Text = "Мой
ход";
//remove
stones(num1.Value != 0)
{.x -=
(int)num1.Value;(box1, (int)num1.Value);
}if (num2.Value !=
0)
{.y -=
(int)num2.Value;(box2, (int)num2.Value);
}
{.z -=
(int)num3.Value;(box3, (int)num3.Value);
}(currentState.x ==
0 && currentState.y == 0 && currentState.z == 0)
{.Stop();.Stop();.Text
= "Вы
выиграли";
//new
game?(MessageBox.Show("Ещё
раз?",
"Поздравляем!",
MessageBoxButtons.YesNo, MessageBoxIcon.Exclamation)
==
DialogResult.Yes)
{.Restart();
}.Exit();
}.Enabled =
true;.Start();
}State DrawStones()
{rand = new
Random();st;.x = rand.Next(3, 6);.y = rand.Next(3, 6);.z = rand.Next(3, 6);=
new PictureBox[st.x];= new PictureBox[st.y];= new PictureBox[st.z];= new List<PictureBox>();=
new List<PictureBox>();= new List<PictureBox>();= new Image[st.x];=
new Image[st.y];= new Image[st.z];(var i = 0; i < st.x; i++)
{[i] = new
PictureBox();[i].Height = 40;[i].Width = 40;[i].Top = 90;[i].Left = 17 + 68 *
i;randImg = rand.Next(1, 10);[i] = Image.FromFile(path + "img\\" +
Convert.ToString(randImg) + ".png");[i].Image = img1[i];[i].BackColor
= Color.Transparent;.Add(imgBox1[i]);.Controls.Add(box1[i]);[i].BringToFront();
}(var i = 0; i <
st.y; i++)
{[i] = new
PictureBox();[i].Height = 40;[i].Width = 40;[i].Top = 145;[i].Left = 17 + 68 *
i;randImg = rand.Next(1, 10);[i] = Image.FromFile(path + "img\\" +
Convert.ToString(randImg) + ".png");[i].Image =
img2[i];.Add(imgBox2[i]);.Controls.Add(box2[i]);[i].BringToFront();
}(var i = 0; i <
st.z; i++)
{[i] = new
PictureBox();[i].Height = 40;[i].Width = 40;[i].Top = 200;[i].Left = 17 + 68 *
i;randImg = rand.Next(1, 10);[i] = Image.FromFile(path + "img\\" +
Convert.ToString(randImg) + ".png");[i].Image =
img3[i];.Add(imgBox3[i]);.Controls.Add(box3[i]);[i].BringToFront();
}st;
}State
GetProfitState(List<State> states)
{profitState;err;.x
= -1;
err.y = -1;.z =
-1;num = -1;
if (!max)= true;=
false;(var i = 0; i < states.Count; i++)
{((states[i].x ^
states[i].y ^ states[i].z) == 0)
{= i;;
}
}(max)
{(num >= 0)
{.x =
states[num].x;.y = states[num].y;.z = states[num].z;profitState;
}
{(var i = 0; i <
states.Count; i++)
{states2 =
GetPossibleStates(states[i]);(GetProfitState(states2).x != err.x)
{.x =
states[i].x;.y = states[i].y;.z = states[i].z;profitState;
}= true;
}
}(num >= 0)
{.x = -1;.y = -1;.z
= -1;profitState;
}
{.x = 0;.y = 0;.z =
0;profitState;
}
}void
num1_ValueChanged(object sender, EventArgs e)
{(num1.Value >
0)
{.Enabled =
true;.Enabled = false;.Enabled = false;
}
{.Enabled =
false;.Enabled = true;.Enabled = true;
}
}void
num2_ValueChanged(object sender, EventArgs e)
{(num2.Value >
0)
{.Enabled =
true;.Enabled = false;.Enabled = false;
}
{.Enabled =
false;.Enabled = true;.Enabled = true;
}
}void
num3_ValueChanged(object sender, EventArgs e)
{(num3.Value >
0)
{.Enabled =
true;.Enabled = false;.Enabled = false;
}
{.Enabled =
false;.Enabled = true;.Enabled = true;
}
}void
RemoveStones(List<PictureBox> box, int num)
{count = box.Count;
//remove stones(var
i = 0; i < num; i++)
{.Controls.Remove(box[count
- i - 1]);.RemoveAt(count - i - 1);
}
}void
CompTurn(object sender, EventArgs e)
{
//get possible
states from current statepossibleStates = new List<State>();=
GetPossibleStates(currentState);lines2 = new List<String>();(var i = 0; i
< possibleStates.Count; i++)
{.Add(String.Format("{0}-{1}-{2}
= {3}", Convert.ToString(possibleStates[i].x),
Convert.ToString(possibleStates[i].y), Convert.ToString(possibleStates[i].z),
Convert.ToString(possibleStates[i].x ^ possibleStates[i].y ^
possibleStates[i].z)));
}
System.IO.File.WriteAllLines(@"C:\Users\asus\Documents\Visual
Studio 2013\Projects\Nim\PosssibleStates.txt", lines2);turnState =
GetProfitState(possibleStates);(turnState.x != currentState.x)
{(box1,
currentState.x - turnState.x);.x = turnState.x;
}if (turnState.y !=
currentState.y)
{(box2,
currentState.y - turnState.y);.y = turnState.y;
}(turnState.z !=
currentState.z)
{(box3,
currentState.z - turnState.z);.z = turnState.z;
}.Value = 0;.Value
= 0;.Value = 0;(currentState.x == 0 && currentState.y == 0 &&
currentState.z == 0)
{.Stop();.Stop();.Text
= "Вы
проиграли";
//new
game?(MessageBox.Show("Ещё
раз?",
"Проигрыш",
MessageBoxButtons.YesNo, MessageBoxIcon.Error)
==
DialogResult.Yes)
{.Restart();
}.Exit();
}.Text = "Ваш
ход";.Maximum
= currentState.x;.Maximum = currentState.y;.Maximum = currentState.z;=
false;.Stop();
}void
timer1_Tick(object sender, EventArgs e)
{(!handup)
{= true;(var i = 0;
i < 5; i++)
{.Top = button1.Top
+ i;
}
}
{= false;(var i =
0; i < 5; i++)
{.Top = button1.Top
- i;
}
}
}void
button1_MouseHover(object sender, EventArgs e)
{.Cursor =
Cursors.Hand;.Stop();
}void
button1_MouseLeave(object sender, EventArgs e)
{.Cursor =
Cursors.Default;.Start();
}
}
}
9. ПРИМЕР
РАБОТЫ ПРОГРАММЫ
Программа запускается открытием
файла Nim.exe.
Появляется главное окно программы (рис. 4).
Рис. 4
Для хода необходимо выбрать
положительное количество камней из одного ряда и нажать на изображение руки.
При этом выбранные камни исчезнут (рис. 5). Спустя секунду компьютер производит
свой ход (рис.6). Остальные ходы представлены на рис. 7,8.
Рис. 6
Рис. 7
Рис. 8
В случае проигрыша или выигрыша
появится сообщение об этом и предложение продолжить игру (рис. 9, 10).
Рис. 9
Рис. 10
10. ПРИМЕР
ДЕРЕВА СОСТОЯНИЙ
Рис. 11. Дерево состояний
контрольного примера
ВЫВОДЫ ПО ДОСТИГНУТЫМ
РЕЗУЛЬТАТАМ
Цель данной курсовой работы -
получение практических навыков в СИИ - была выполнена. Для этого была
разработана программа-игра Ним, реализующая минимаксный алгоритм поиска на
определенную глубину. Подобные программы позволяют изучить математические
методы искусственного интеллекта, в частности поиск в пространстве состояний и
эвристический поиск.
Результаты контрольных примеров
совпали с ожидаемыми, значит программа работает корректно.
При выполнении данной курсовой
работы мной были изучены методы работы с Windows Forms в языке С#, а также
минимаксный алгоритм поиска в пространстве состояний.
программирование
логический игра алгоритм
СПИСОК ИСПОЛЬЗОВАННЫХ
ИСТОЧНИКОВ
1. Дж.Ф.Люгер, Искусственный интеллект.
Стратегии и методы решения сложных проблем, 2003 г.
2. <https://ru.wikipedia.org/wiki/%D0%9D%D0%B8%D0%BC_(%D0%B8%D0%B3%D1%80%D0%B0)>
Википедия. Ним (игра)
. <https://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%A8%D0%BF%D1%80%D0%B0%D0%B3%D0%B0-%D0%93%D1%80%D0%B0%D0%BD%D0%B4%D0%B8>
Википедия. Функция Шпрага-Гранди.
. <http://habrahabr.ru/post/124856/>
Теория игр и функция Шпрага-Гранди.
. <http://e-maxx.ru/algo/sprague_grundy>
Теория Шпрага-Гранди. Ним.
. <https://msdn.microsoft.com/en-US/>
Руководство по программированию на C#.