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

Задумано число 4356

Ходы программы:

1) 1234 Быков – 0, коров – 2

2) 5234 Быков – 0, коров – 3

3) 5634 Быков – 0, коров – 4

4) 6534 Быков – 0, коров – 4

5) 3654 Быков – 1, коров – 3

6) 6354 Быков – 2, коров – 2

7) 5364 Быков – 1, коров – 3

8) 6534 Быков – 0, коров – 4

9) 6345 Быков – 0, коров – 4

10) 4356 Быков – 4, коров – 0

Таким образом, компьютер отгадал загаданное число за 10 шагов.

Теперь рассмотрим выигрышную стратегию «Метод решета». Она заключается в том, что мы рассматриваем конечное множество всех возможных чисел, и каждый ход исключаем все элементы множества, не представляющие интереса. Например, для загаданного числа 5643 мы предположили 1234, и получили 0 быков и 2 коровы, затем вторым шагом проверяем оставшиеся два числа, предполагаем 1256, получаем 0 быков и 2 коровы, значит искомые числа это 3456, остаётся только узнать правильное расположение этих чисел:

1) 1234 Быков – 0, коров – 2

2) 1256 Быков – 0, коров – 2

Сперва проверяем числа 3456, получаем 0 быков и 4 коровы, затем попарно меняем каждое число друг с другом и проверяем до тех пор пока не получим хотя бы 2 быка:

3) 3456 Быков – 0, коров – 4

4) 4365 Быков – 0, коров – 4

5) 5634 Быков – 2, коров – 2

На 5-м ходу мы получили 2 быка, затем попарно меняем числа в этой комбинации до тех пор пока не найдём искомое:

6) 6534 Быков – 0, коров – 4

7) 5643 Быков – 4, коров – 0

Таким образом, число угадано за 7 шагов. В худшем случае с помощью этой стратегии число угадывается за 9-10 шагов.

 

2.3 Описание интерфейса программы и результатов тестирования

 

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

 

Рисунок 2. – Игровой процесс

Рисунок 3. – Игровой процесс  

Рисунок 4. – Игровой процесс

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

Разработан и реализован вариант игры «Быки и коровы». Игры бывают разные, и стратегии у них разные, у каждой игры она индивидуальная. Для игры «Быки и коровы» главной задачей компьютера является – отгадать число, которое загадал пользователь за минимально возможное количество ходов.

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

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

 

 

 

 

 

 

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

 

1. Колобашкина Л.В., Алюшин М.В. - Информационные технологии принятия решений в условиях конфликта, 2010 г. – 164 с.

2. Н. Н. Писарук – Введение в теорию игр, 2013 г. – 239 с.

3. Н. Н. Воробьева - Бесконечные антагонистические игры, 1963 г. – 195 с.

4. Джеймс Карс - Книга “Конечных и Бесконечных Игр” – 113 с.

5. Н. С. Садовин, Т. Н. Садовина – Основы теории игр, 2011 г. – 120 с.

6. Васин А. А., Морозов В. В. - Теория игр и модели математической экономики. — М., 2005г. – 127 с.

7. Петросян Л. А., Зенкевич Н.А., Семина Е.А. - Теория игр: Учеб. пособие для ун-тов, 1998 г. — 304 с.

8. Д. Андерхилл, С. Барретт, П. Бернелл, П. Бернем, и др. Общая редакция: д.э.н. Осадчая И.М. Политика. Толковый словарь. — М., 2001 г. – 235 с.

 

Приложение А

Текст программы

 

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

 

int GetCows(int n[4], int m[4])

{

int c = 0;

for (int i = 0; i < 4; i++)

for (int j = 0; j < 4; j++)

if (n[i] == m[j] && i != j) c++;

 

return c;

}

 

int GetBulls(int n[4], int m[4])

{

int b = 0;

for (int i = 0; i < 4; i++)

if (n[i] == m[i]) b++;

 

return b;

}

 

void main()

{

int m[4] = { 1, 2, 3, 4 };

int temp[4], n[4], number, bulls, cows, w, t, s, c, attempts = 1;

 

clrscr();

 

printf("Zagadayte chislo: ");

scanf("%d", &number);

 

n[0] = number / 1000;

n[1] = number % 1000 / 100;

n[2] = number % 100 / 10;

n[3] = number % 10;

 

bulls = GetBulls(n, m);

cows = GetCows(n, m);

 

printf("[%d%d%d%d]\t[bulls: %d]\t[cows: %d]\n", m[0], m[1], m[2], m[3], bulls, cows);

 

w = 0;

c = 5;

s = bulls + cows;

 

while (bulls + cows != 4)

{

attempts++;

 

if (w == 4)

{

w = 0;

c++;

}

 

temp[0] = m[0]; temp[1] = m[1]; temp[2] = m[2]; temp[3] = m[3];

temp[w] = c;

w++;

 

bulls = GetBulls(n, temp);

cows = GetCows(n, temp);

 

printf("[%d%d%d%d]\t[bulls: %d]\t[cows: %d]\n", temp[0], temp[1], temp[2], temp[3], bulls, cows);

 

if (bulls + cows > s)

{

m[w - 1] = c;

c++;

s = bulls + cows;

}

}

 

w = 0;

t = 0;

s = bulls;

 

while (bulls != 4)

{

attempts++;

 

if (t == 4)

{

w++;

t = 0;

}

 

if (w == t) t++;

 

temp[0] = m[0]; temp[1] = m[1]; temp[2] = m[2]; temp[3] = m[3];

c = temp[w];

temp[w] = temp[t];

temp[t] = c;

t++;

 

bulls = GetBulls(n, temp);

 

printf("[%d%d%d%d]\t[bulls: %d]\n", temp[0], temp[1], temp[2], temp[3], bulls, cows);

 

if (bulls > s)

{

c = m[w];

m[w] = m[t - 1];

m[t - 1] = c;

w++;

t = 0;

s = bulls;

}

}

 

printf("Chislo ugadano: %d%d%d%d\n", m[0], m[1], m[2], m[3]);

printf("Kolichestvo popytok: %d", attempts);

 

getch();

}