Программирование логических игр

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Ижевский государственный технический университет имени М. Т. Калашникова»

Кафедра «Программное обеспечение»

Отчет по курсовой работе

«Программирование логических игр»

«Ним»

Выполнил:

студент гр. Б06−191−2

Э.Ф. Ахмерова Принял:

А.В. Коробейников Ижевск — 2015

1. ПОСТАНОВКА ЗАДАЧИ

2. ОПИСАНИЕ ИГРЫ

3. ФОРМАЛИЗАЦИЯ ДЕРЕВА СОСТОЯНИЙ

4. ОПИСАНИЕ ПРЕДЛОЖЕННЫХ ЭВРИСТИК

5. КРАТКОЕ ОПИСАНИЕ ИСПОЛЬЗОВАННЫХ АЛГОРИТМОВ

6. ОПИСАНИЕ АДАПТАЦИИ АЛГОРИТМОВ К ВАШЕЙ ЗАДАЧЕ

7. СТРУКТУРА ПРОГРАММЫ ИЛИ АЛГОРИТМОВ

7.1 Иерархическая схема программы

7.2 Блок-схемы программы

8. ИСХОДНЫЕ ТЕКСТЫ ПРОГРАММЫ

9. ПРИМЕР РАБОТЫ ПРОГРАММЫ

10. ПРИМЕР ДЕРЕВА СОСТОЯНИЙ ВЫВОДЫ ПО ДОСТИГНУТЫМ РЕЗУЛЬТАТАМ СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. ПОСТАНОВКА ЗАДАЧИ В настоящее время теория искусственного интеллекта активно развивается. Одним из направлений является решение логических игр. Это позволяет разработчику формализовать поиск в пространстве состояний, что является ключевым методом искусственного интеллекта. Игровые задачи легко представимы в компьютерной программе, поэтому разработка не сильно затруднена.

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

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

2. ОПИСАНИЕ ИГРЫ Ним — математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет.

В классическом варианте игры число кучек равняется трём.

Игра Ним попала в Европу в XVI веке из Китая. Имя «ним» было дано игре американским математиком Чарльзом Бутоном (англ. Charles Bouton), описавшим в 1901 году выигрышную стратегию игры.

Существует несколько вариантов происхождения названия игры:

— от немецкого глагола Nimm или старо-английского глагола Nim, имеющих значение «брать»;

— от английского глагола WIN («побеждать»), переворачиванием слова;

3. ФОРМАЛИЗАЦИЯ ДЕРЕВА СОСТОЯНИЙ Для данной игры Ним зададим 3 кучки с количеством камней i = [3;5]. Пространство состояний — это граф из множества вершин и дуг, соединяющих пары вершин. В модели пространства состояний решаемой задачи вершины графа представляют дискретные состояния процесса решения, например различные сочетания размеров кучек. Дуги графа описывают переходы между состояниями. Эти переходы соответствуют логическим заключениям или допустимым ходам в игре. Фрагмент пространства состояний для игры Ним представлен на рис. 1.

Рис. 1. Фрагмент пространства состояний Поиск в пространстве состояний предполагает нахождение пути от исходного состояния к целевому. Цель может описывать выигрышное состояние. Эвристический поиск определяется как выбор ветвей из пространства состояний на основе определенных правил, которые с наибольшей вероятностью приведут к приемлемому решению проблемы.

Для игры Ним с размерами кучек в 5 камней количество состояний всего составляет 6*6*6 = 216. Так как пространство состояний для данной игры очень велико, я использую минимаксный алгоритм на ограниченную глубину. При этом поиск осуществляется вглубь на определенное число уровней.

4. ОПИСАНИЕ ПРЕДЛОЖЕННЫХ ЭВРИСТИК Эвристикой может считаться оптимальное состояние игры, требуемое для выигрыша. Так как мы не можем просматривать граф состояний полностью, каждой вершине присваивается значение, определяемое эвристической функцией. Алгоритм поиска затем использует эти значения, чтобы выбрать наилучший среди возможных ходов из очередной корневой вершины.

Для игры Ним выбор выигрышного состояния определяется функцией Шпрага-Гранди. Следствие этой функции: для текущего игрока стратегия является выигрышной тогда и только тогда, когда xor-сумма размеров кучек положительна. Состояние любой «равноправной» игры можно изобразить в виде ним-кучки. Если размер кучки равен нулю, то состояние проигрышное. Если не равен — выигрышное.

Рассмотрим пример игры с состоянием 3−2-4 (рис. 2).

В скобках указаны xor-суммы размеров кучек. Max должен сделать такой ход, чтобы состояние для Min было проигрышным, поэтому выбирается состояние 3−2-1, где xor-сумма равна 0.

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

5. КРАТКОЕ ОПИСАНИЕ ИСПОЛЬЗОВАННЫХ АЛГОРИТМОВ Алгоритм минимаксной стратегии на ограниченную глубину:

1. Построение дерева игровых состояний из текущего состояния (корневой вершины) на заданное число уровней.

2. Определение эвристических оценок для состояний на последнем (горизонтном) уровне дерева состояний (листья).

3. Минимаксный перенос результатов игры от листьев графа вверх по графу к корню в соответствии с минимаксным правилом.

4. Принятие решения об очередном ходе в соответствии со значениями минимаксного переноса: Max ходит в сторону максимального из детей, Min? в сторону минимального.

5. Для принятия решения по следующему ходу игрока необходимо повторное построение дерева состояний из новой текущей (корневой) вершины.

6. ОПИСАНИЕ АДАПТАЦИИ АЛГОРИТМОВ К ВАШЕЙ ЗАДАЧЕ Смысл игр Ним таков, что при правильном алгоритме можно после первого хода определить победителя. Поэтому достаточно просматривать пространство состояний на 1 уровень вперед для определения наилучшего хода.

Алгоритм минимаксной стратегии на ограниченную глубину для игры Ним:

1. Построение дерева игровых состояний из текущего состояния на 1 уровень вперед.

2. Определение эвристической оценки для каждого состояния уровня.

3. Если ходит Max, то перейти к пункту 4, иначе перейти к пункту 6.

4. Если среди оценок есть нулевая, то вернуть номер этого состояния, иначе переход к пункту 5.

5. Присвоить ход к Min и перейти к пункту 1.

6. Если среди оценок нет нулевых, то вернуть номер состояния, иначе выход.

7. СТРУКТУРА ПРОГРАММЫ ИЛИ АЛГОРИТМОВ

7.1 Иерархическая схема программы Рис. 3

Form1_Load запускает функцию DrawStones, получает начальное состояние игры.

DrawStones генерирует начальное состояние игры с помощью генератора случайных чисел, инициализирует поля для изображений, выводит на экран изображения камней.

button1_Click — процедура при нажатии на кнопку. Устанавливает новое текущее состояние, запускает функцию RemoveStones, выводит сообщение в случае выигрыша пользователя.

RemoveStones удаляет необходимое количество камней с экрана.

CompTurn выполняет ход компьютера, запускает функцию GetPossibleStates, затем GetProfitState и RemoveStones, выводит сообщение в случае выигрыша компьютера.

GetPossibleStates формирует список состояний из текущего состояния.

GetProfitState находит выигрышное состояния, вычисляя xor-суммы.

7.2 Блок-схемы программы

8. ИСХОДНЫЕ ТЕКСТЫ ПРОГРАММЫ

using System;

using System.Collections.Generic;

using System. ComponentModel;

using System. Data;

using System. Drawing;

using System. Linq;

using System. Text;

using System.Threading.Tasks;

using System.Windows.Forms;

using System. Threading;

namespace Nim

{

public partial class Form1: Form

{

public struct State

{

public int x;

public int y;

public int z;

}

private State currentState;

PictureBox[] imgBox1;

PictureBox[] imgBox2;

PictureBox[] imgBox3;

List box1;

List box2;

List box3;

Image[] img1;

Image[] img2;

Image[] img3;

private bool max = false;

private bool handup = false;

String path;

public Form1()

{

InitializeComponent ();

}

private void Form1_Load (object sender, EventArgs e)

{

path = Environment. CurrentDirectory;

int index = path. IndexOf («bin»);

path = path. Substring (0, index);

//first state

currentState = DrawStones ();

num1.Maximum = currentState. x;

num2.Maximum = currentState. y;

num3.Maximum = currentState. z;

var possibleStates = new List ();

possibleStates = GetPossibleStates (currentState);

var lines2 = new List ();

for (var i = 0; i < possibleStates. Count; i++)

{

lines2.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 (@path + «PosssibleStates.txt», lines2);

timer1.Start ();

}

public List GetPossibleStates (State currentState)

{

var stateList = new List ();

State state;

for (var i = 0; i < currentState. x; i++)

{

state.x = i;

state.y = currentState. y;

state.z = currentState. z;

stateList.Add (state);

}

for (var i = 0; i < currentState. y; i++)

{

state.x = currentState. x;

state.y = i;

state.z = currentState. z;

stateList.Add (state);

}

for (var i = 0; i < currentState. z; i++)

{

state.x = currentState. x;

state.y = currentState. y;

state.z = i;

stateList.Add (state);

}

return stateList;

}

private void button1_Click (object sender, EventArgs e)

{

label1.Text = «Мой ход» ;

//remove stones

if (num1.Value ≠ 0)

{

currentState.x -= (int)num1.Value;

RemoveStones (box1, (int)num1.Value);

}

else if (num2.Value ≠ 0)

{

currentState.y -= (int)num2.Value;

RemoveStones (box2, (int)num2.Value);

}

else

{

currentState.z -= (int)num3.Value;

RemoveStones (box3, (int)num3.Value);

}

if (currentState.x == 0 && currentState. y == 0 && currentState. z == 0)

{

timer.Stop ();

timer1.Stop ();

label1.Text = «Вы выиграли» ;

//new game?

if (MessageBox.Show («Ещё раз?», «Поздравляем!», MessageBoxButtons. YesNo, MessageBoxIcon. Exclamation)

== DialogResult. Yes)

{

Application.Restart ();

}

else

Application.Exit ();

}

timer.Enabled = true;

timer.Start ();

}

private State DrawStones ()

{

Random rand = new Random ();

State st;

st.x = rand. Next (3, 6);

st.y = rand. Next (3, 6);

st.z = rand. Next (3, 6);

imgBox1 = new PictureBox[st.x];

imgBox2 = new PictureBox[st.y];

imgBox3 = new PictureBox[st.z];

box1 = new List ();

box2 = new List ();

box3 = new List ();

img1 = new Image[st.x];

img2 = new Image[st.y];

img3 = new Image[st.z];

for (var i = 0; i < st. x; i++)

{

imgBox1[i] = new PictureBox ();

imgBox1[i]. Height = 40;

imgBox1[i]. Width = 40;

imgBox1[i]. Top = 90;

imgBox1[i]. Left = 17 + 68 * i;

var randImg = rand. Next (1, 10);

img1[i] = Image. FromFile (path + «img» + Convert. ToString (randImg) + «.png»);

imgBox1[i]. Image = img1[i];

imgBox1[i].BackColor = Color. Transparent;

box1.Add (imgBox1[i]);

this.Controls.Add (box1[i]);

imgBox1[i]. BringToFront ();

}

for (var i = 0; i < st. y; i++)

{

imgBox2[i] = new PictureBox ();

imgBox2[i]. Height = 40;

imgBox2[i]. Width = 40;

imgBox2[i]. Top = 145;

imgBox2[i]. Left = 17 + 68 * i;

var randImg = rand. Next (1, 10);

img2[i] = Image. FromFile (path + «img» + Convert. ToString (randImg) + «.png»);

imgBox2[i]. Image = img2[i];

box2.Add (imgBox2[i]);

this.Controls.Add (box2[i]);

imgBox2[i].BringToFront ();

}

for (var i = 0; i < st. z; i++)

{

imgBox3[i] = new PictureBox ();

imgBox3[i]. Height = 40;

imgBox3[i]. Width = 40;

imgBox3[i]. Top = 200;

imgBox3[i]. Left = 17 + 68 * i;

var randImg = rand. Next (1, 10);

img3[i] = Image. FromFile (path + «img» + Convert. ToString (randImg) + «.png»);

imgBox3[i]. Image = img3[i];

box3.Add (imgBox3[i]);

this.Controls.Add (box3[i]);

imgBox3[i].BringToFront ();

}

return st;

}

private State GetProfitState (List states)

{

State profitState;

State err;

err.x = -1;

err.y = -1;

err.z = -1;

int num = -1;

if (!max)

max = true;

else

max = false;

for (var i = 0; i < states. Count; i++)

{

if ((states[i]. x ^ states[i]. y ^ states[i]. z) == 0)

{

num = i;

break;

}

}

if (max)

{

if (num >= 0)

{

profitState.x = states[num]. x;

profitState.y = states[num]. y;

profitState.z = states[num]. z;

return profitState;

}

else

{

for (var i = 0; i < states. Count; i++)

{

var states2 = GetPossibleStates (states[i]);

if (GetProfitState (states2).x ≠ err. x)

{

profitState.x = states[i]. x;

profitState.y = states[i]. y;

profitState.z = states[i]. z;

return profitState;

}

max = true;

}

profitState.x = states[0]. x;

profitState.y = states[0]. y;

profitState.z = states[0]. z;

return profitState;

}

}

else

if (num >= 0)

{

profitState.x = -1;

profitState.y = -1;

profitState.z = -1;

return profitState;

}

else

{

profitState.x = 0;

profitState.y = 0;

profitState.z = 0;

return profitState;

}

}

private void num1_ValueChanged (object sender, EventArgs e)

{

if (num1.Value > 0)

{

button1.Enabled = true;

num2.Enabled = false;

num3.Enabled = false;

}

else

{

button1.Enabled = false;

num2.Enabled = true;

num3.Enabled = true;

}

}

private void num2_ValueChanged (object sender, EventArgs e)

{

if (num2.Value > 0)

{

button1.Enabled = true;

num1.Enabled = false;

num3.Enabled = false;

}

else

{

button1.Enabled = false;

num1.Enabled = true;

num3.Enabled = true;

}

}

private void num3_ValueChanged (object sender, EventArgs e)

{

if (num3.Value > 0)

{

button1.Enabled = true;

num1.Enabled = false;

num2.Enabled = false;

}

else

{

button1.Enabled = false;

num1.Enabled = true;

num2.Enabled = true;

}

}

private void RemoveStones (List box, int num)

{

int count = box. Count;

//remove stones

for (var i = 0; i < num; i++)

{

this.Controls.Remove (box[count — i — 1]);

box.RemoveAt (count — i — 1);

}

}

private void CompTurn (object sender, EventArgs e)

{

//get possible states from current state

var possibleStates = new List ();

possibleStates = GetPossibleStates (currentState);

var lines2 = new List ();

for (var i = 0; i < possibleStates. Count; i++)

{

lines2.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: UsersasusDocumentsVisual Studio 2013ProjectsNimPosssibleStates. txt", lines2);

State turnState = GetProfitState (possibleStates);

if (turnState.x ≠ currentState. x)

{

RemoveStones (box1, currentState. x — turnState. x);

currentState.x = turnState. x;

}

else if (turnState.y ≠ currentState. y)

{

RemoveStones (box2, currentState. y — turnState. y);

currentState.y = turnState. y;

}

else

if (turnState.z ≠ currentState. z)

{

RemoveStones (box3, currentState. z — turnState. z);

currentState.z = turnState. z;

}

num1.Value = 0;

num2.Value = 0;

num3.Value = 0;

if (currentState.x == 0 && currentState. y == 0 && currentState. z == 0)

{

timer.Stop ();

timer1.Stop ();

label1.Text = «Вы проиграли» ;

//new game?

if (MessageBox.Show («Ещё раз?», «Проигрыш», MessageBoxButtons. YesNo, MessageBoxIcon. Error)

== DialogResult. Yes)

{

Application.Restart ();

}

else

Application.Exit ();

}

else

label1.Text = «Ваш ход» ;

num1.Maximum = currentState. x;

num2.Maximum = currentState. y;

num3.Maximum = currentState. z;

max = false;

timer.Stop ();

}

private void timer1_Tick (object sender, EventArgs e)

{

if (!handup)

{

handup = true;

for (var i = 0; i < 5; i++)

{

button1.Top = button1. Top + i;

}

}

else

{

handup = false;

for (var i = 0; i < 5; i++)

{

button1.Top = button1. Top — i;

}

}

}

private void button1_MouseHover (object sender, EventArgs e)

{

this.Cursor = Cursors. Hand;

timer1.Stop ();

}

private void button1_MouseLeave (object sender, EventArgs e)

{

this.Cursor = Cursors. Default;

timer1.Start ();

}

}

}

9. ПРИМЕР РАБОТЫ ПРОГРАММЫ Программа запускается открытием файла Nim.exe. Появляется главное окно программы (рис. 4).

Рис. 4

Для хода необходимо выбрать положительное количество камней из одного ряда и нажать на изображение руки. При этом выбранные камни исчезнут (рис. 5). Спустя секунду компьютер производит свой ход (рис.6). Остальные ходы представлены на рис. 7,8.

Рис. 5

Рис. 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) Википедия. Ним (игра)

3. 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 Википедия. Функция Шпрага-Гранди.

4. http://habrahabr.ru/post/124 856/ Теория игр и функция Шпрага-Гранди.

5. http://e-maxx.ru/algo/sprague_grundy Теория Шпрага-Гранди. Ним.

6. https://msdn.microsoft.com/en-US/ Руководство по программированию на C#.