Рефетека.ру / Информатика и програм-ие

Курсовая работа: Игра в "Морской бой" с компьютером

СОДЕРЖАНИЕ


Введение

1 Постановка задачи

2 Математические и алгоритмические основы решения задачи

3 Функциональные модели и блок-схемы решения задачи

4 Программная реализация решения задачи

5 Пример выполнения программы

Заключение

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


Введение


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

Остановимся на некоторых основных правилах классического варианта игры. Первый игрок, игрок А, расставляет корабли на квадратном игровом поле из n клеток (обычно это поле Игра в "Морской бой" с компьютером клеток). Корабли делятся на классы: одноклеточные, двухклеточные, трехклеточные и четырехклеточные. Игрок В на своем поле расставляет свои корабли. Заметим, что корабли не должны касаться друг друга. Игра состоит в том, что игроки по очереди называют координаты клеток, в которых, как они предполагают, расположены корабли противника, то есть как бы производят выстрел по выбранной клетке. О попадании или промахе игроку сообщается после выстрела. Игра продолжается до тех пор, пока у одного из игроков не будут уничтожены все корабли.

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


Игра в "Морской бой" с компьютером

Рисунок 1


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

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

В дальнейшем будем рассматривать только одностороннюю игру: игрок А расставляет корабли, а игрок В ведет их поиск.

Математическую модель игры можно строить двумя способами. Первый способ состоит в том, что после каждого выстрела учитываются изменения поля игры и вероятности обнаружения кораблей. Такая форма игры называется развернутой, а сама игра представляется многошаговой. Сложность применения этого подхода связана с необходимостью определения вероятностей событий, которые являются комбинацией большого числа элементарных событий. При увеличении числа выстрелов k количество комбинаций растет пропорционально k! (факториалу k).

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


1. Постановка задачи


Задача заключается в разработке алгоритма, по которому компьютер сможет играть в «Морской бой» с максимальным качеством, и при этом не подглядывая расположение флота игрока.

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

Необходимо вспомнить правила игры: участники поединка делают ходы поочередно, причем, если один из игроков попадает по кораблю соперника, то он получает право следующего хода. Если реализовать поиск цели компьютером в виде отдельной процедуры, то надо как-то научить его запоминать исходы прошлых выстрелов, чтобы адекватно произвести следующий. Из этого факта вытекает, что самое простое и рациональное решение данной проблемы можно оформить в виде конечного автомата, наиболее точно описывающего последовательность действий.

Можно выделить три состояния:

прострел игрового поля по случайным координатам до попадания по кораблю, после чего переход во второе состояние;

обстрел вокруг подбитой ячейки поля для определения направления корабля (вертикальное или горизонтальное), после очередного попадания – переход в третье состояние;

расстрел корабля в полученном направлении до полного его уничтожения, после чего переход в первое состояние.

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

Прострел

На этом этапе компьютер должен поймать какой-либо из кораблей противника. Для этого он будет стрелять по произвольным незанятым клеткам поля игрока. Гораздо эффективнее сначала разделаться с большими кораблями, поэтому выбирая координаты для выстрела надо проверять, что бы в этой позиции мог разместиться самый большой из оставшихся кораблей. Процесс прекращается, как только произойдет попадание. Обозначим подбитую часть корабля значением «*», а промах «~» соответствующей ячейки поля. Если у игрока остались только однопалубные корабли, то этим попаданием корабль уничтожен полностью и обстреливать его нет смысла. В противном случае надо перейти ко второму состоянию.

Обстрел

На этом шаге задача заключается в определении направления пойманного корабля. Для этого надо обстрелять четыре ячейки (если они свободны), которые могут служить продолжением. В случае, когда все четыре клетки обстреляны, а попадания не произошло (однопалубный корабль), надо перейти к первому состоянию. Если в какой-то момент удалось подбить еще одну палубу противника, то можно переходит к расстрелу данного корабля, т. к. его направление стало известно. Аналогично первому состоянию, если у игрока остались корабли не более двух палуб, то этим попаданием корабль уничтожен полностью и надо вернуться к прострелу.

Расстрел

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


Пример

Поле кораблей

1 1 1 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 1 0 1 0 0 0
1 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 1 1 0 0 0 0
1 0 1 0 0 0 0 1 1 1

Стратегия игры компьютера.

Выбирается случайная клетка, рассматривается ее значение.

Если значение = 1 – попали в корабль, отмечаем удар «*»;

Если значение = 0 – промазали, отмечаем удар «~»;

Если значение = «*» или значение = «~», значит в эту клетку нами уже был произведен удар, возвращаемся к шагу 1.

После того как все корабли разбиты, прекращаем бой. Поле разбитых кораблей


* * * * ~ ~ * ~ ~ ~
~ ~ ~ ~ ~ ~ * ~ ~ ~
~ ~ ~ ~ * ~ * ~ ~ ~
* ~ ~ ~ * ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ 0 ~ ~ ~ ~ ~
~ ~ * ~ ~ ~ ~ ~ 0 *
~ ~ ~ ~ ~ ~ ~ ~ ~ *
~ ~ ~ ~ * * ~ ~ ~ ~
* ~ * ~ ~ ~ ~ * * *

Нулями обозначены те клетки, в которые мы не попали.

2. Математические и алгоритмические основы решения задачи


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

На поле из n клеток расположен одноклеточный корабль. Определим вероятность попадания в корабль k-ым выстрелом, то есть его уничтожение.

В качестве пространства элементарных исходов выбора игрока В рассмотрим множество стратегий обстрела игрового поля, каждая стратегия состоит из n выстрелов,


Игра в "Морской бой" с компьютером,


где Игра в "Морской бой" с компьютером – номер выбранной клетки, то есть рассмотрим множество всех выборок из n по n клеток. Очевидно, что это пространство содержит Игра в "Морской бой" с компьютером элементов и все эти стратегии равновозможны. Количество стратегий с благоприятным исходом, то есть количество выборок, содержащих на k-ом месте искомую клетку


Игра в "Морской бой" с компьютером.


Вероятность попадания


Игра в "Морской бой" с компьютером.


Определим вероятность уничтожения корабля за k выстрелов. Это событие состоит в том, что корабль может быть уничтожен либо первым выстрелом, либо вторым и т.д., то есть благоприятная выборка из k клеток содержит искомую клетку с кораблем. Количество благоприятных стратегий определится как число неупорядоченных выборок из множества n – 1 клеток по k – 1 (одна клетка, занятая кораблем не учитывается при выборке), умноженное на число перестановок в самой выборке k! и число перестановок клеток оставшихся за выборкой (n – k)!:)!. Вероятность попадания в одноклеточный корабль за k выстрелов


Игра в "Морской бой" с компьютером. (1)


Усложним задачу. На поле из n клеток расположен двухклеточный корабль. Определим вероятность первого попадания в корабль (в одну из его клеток) выстрелом с номером k. Полное число всевозможных стратегий, как и в предыдущем случае, равно Игра в "Морской бой" с компьютером, а число благоприятных стратегий определяется как сумма благоприятных стратегий попадания в одну клетку и попадания во вторую клетку, то есть Игра в "Морской бой" с компьютером. Вероятность попадания k-ым выстрелом равна Игра в "Морской бой" с компьютером.

Очевидно, что при обстреле m-клеточного корабля или m одноклеточных кораблей, вероятность попадания k-ым выстрелом равна


Игра в "Морской бой" с компьютером.


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


Игра в "Морской бой" с компьютером,

где Игра в "Морской бой" с компьютером – выборки, содержащие либо первую клетку, либо вторую клетку, Игра в "Морской бой" с компьютером – выборки, содержащие одновременно две клетки. Следовательно


Игра в "Морской бой" с компьютером


и после преобразований получим


Игра в "Морской бой" с компьютером. (2)


Заметим, что аналогичным образом можно определить вероятность попадания за k выстрелов в корабль из m клеток. Задача попадания за k выстрелов в многоклеточный корабль хотя бы один раз является задачей поиска корабля. Очевидно, что если учесть геометрию корабля, то можно предложить систему его поиска, при которой вероятность обнаружения становится выше. Действительно, при поиске двухклеточного корабля можно рассмотреть подмножество всех стратегий, содержащих обстрел, например, клеток только с четными или с нечетными номерами. Поиск двухклеточного корабля сведется к поиску одноклеточного корабля на этом подмножестве. Полагая n четным, для оптимальной вероятности попадания за k выстрелов получим


Игра в "Морской бой" с компьютером. (3)


Найденное значение вероятности больше вероятности, полученной выше

Игра в "Морской бой" с компьютером,


при всех значениях Игра в "Морской бой" с компьютером.

Оптимальная стратегия поиска трехклеточного и четырехклеточного корабля может быть получена аналогичным образом.

Вероятность попадания в игре «Морской бой»

Всего клеток 100

а) вероятность попасть в какой-нибудь корабль равна Игра в "Морской бой" с компьютером;

б) вероятность попасть в четырехпалубный равна Игра в "Морской бой" с компьютером;

в) вероятность попасть в однопалубный равна Игра в "Морской бой" с компьютером;

Всего кораблей 10, не однопалубных 6, «клеточек» 16.

а) вероятность попасть в четырехпалубный равна Игра в "Морской бой" с компьютером;

б) вероятность попасть в трехпалубный равна Игра в "Морской бой" с компьютером;

в) вероятность попасть в двухпалубный равна Игра в "Морской бой" с компьютером.


3. Функциональная модель решения задачи


Функциональная модель решения задачи представлены на рисунке 2.


Игра в "Морской бой" с компьютером

Рисунок 2 – Функциональная модель решения задачи для функции BLOW


4. Программная реализация решения задачи


; открываем файл для чтения

(setq input_stream (open «d:\\field.txt»:direction:input))

; считываем поле противника

(setq field (read input_stream))

; закрываем файл

(close input_stream)

; количество кораблей

(setq user_ship 10)


; убиваем корабль

(defunset_missing_comp (lst i j ip jp)

(setq k (if (>= (- i 1) 0) (- i 1) i))

(setq l (if (>= (- j 1) 0) (- j 1) j))


(loop

(do

()

((or (> k (+ i 1)) (>= k 10)))


(do

()

((or (> l (+ j 1)) (>= l 10)))


(if (eql (nth l (nth k lst)) 1)

(progn

(setq k 10)

(returnt)

)

)


(setq l (+ l 1))

)


(setq k (+ k 1))

)

(returnnil)

)


(setq k (if (>= (- i 1) 0) (- i 1) i))

(setq l (if (>= (- j 1) 0) (- j 1) j))


(loop

(do

()

((or (> k (+ i 1)) (>= k 10)))


(do

()

((or (> l (+ j 1)) (>= l 10)))


(if (not (eql (nth l (nth k lst)) '*)) (setf (nth l (nth k lst)) '~))


(setq l (+ l 1))

)


(setq k (+ k 1))

)

(returnnil)

)

t

)


; шагаем по направлению «креста»

(defunset_missing (lst i j ip jp)

(if (>= (- i 1) 0)

(if (and (/= (- i 1) ip) (eql (nth j (nth (- i 1) lst)) 1))

(set_missing lst (- i 1) j i j)

)

)


(if (>= (- j 1) 0)

(if (and (/= (- j 1) jp) (eql (nth (- j 1) (nth i lst)) 1))

(set_missing lst i (- j 1) i j)

)

)


(if (< (+ i 1) 10)

(if (and (/= (+ i 1) ip) (eql (nth j (nth (+ i 1) lst)) 1))

(set_missing lst (+ i 1) j i j)

)

)


(if (< (+ j 1) 10)

(if (and (/= (+ j 1) jp) (eql (nth (+ j 1) (nth i lst)) 1))

(set_missing lst i (+ j 1) i j)

)

)


(if (eql (nth j (nth i lst)) 1) (setf (nth j (nth i lst)) '*))

)


; функция, реализующая удар по полю

(defunblow(lst)

; выбираем случайную клетку

(setq i (random 10))

(setq j (random 10))

(setq n (nth j (nth i lst)))


(cond

((eql n 1)

(progn

; значение в клетке = 1

; убиваем корабль


(set_missing lst i j i j)

(set_missing_comp lst i j i j)


(setq user_ship ( user_ship 1))


(if (/= user_ship 0) (blow lst))

)

)


((eql n 0)

(progn

; значение в клетке 0

; промахнулись


(setf (nth j (nth i lst)) '~)


(blow lst)

)

)

; уже были в этой клетке – выбираем другую

((or (equal n '*) (equal n '~)) (blow lst))

)

lst

)


; убиваем противника!!!

(blow field)


; файл для записи

(setq output_stream (open «d:\\destroy_field.txt»:direction:output))


; записываем побитое поле противника

(print field output_stream)


; закрываем файл

(close output_stream)


5. Пример выполнения программы


Пример 1.


Игра в &amp;quot;Морской бой&amp;quot; с компьютером

Рисунок 3 – Поле кораблей

Игра в &amp;quot;Морской бой&amp;quot; с компьютером

Рисунок 4 – Расстрелянное поле кораблей


Пример 2.


Игра в &amp;quot;Морской бой&amp;quot; с компьютером

Рисунок 5 – Поле кораблей


Игра в &amp;quot;Морской бой&amp;quot; с компьютером

Рисунок 6 – Расстрелянное поле кораблей


Пример 3.

Игра в &amp;quot;Морской бой&amp;quot; с компьютером

Рисунок 7 – Поле кораблей


Игра в &amp;quot;Морской бой&amp;quot; с компьютером


Рисунок 8 – Расстрелянное поле кораблей


Заключение


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

Итогом работы можно считать созданную функциональную модель реализации стратегии игры «Морской бой». Созданная функциональная модель и ее программная реализация могут служить органической частью решения более сложных задач.


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


Бронштейн, И.Н. Справочник по математике для инженеров и учащихся втузов [Текст] / И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 2007. – 708 с.

Кремер, Н.Ш. Высшая математика для экономистов: учебник для студентов вузов. [Текст] / Н.Ш. Кремер, 3-е издание – М.:ЮНИТИ-ДАНА, 2006. C. 412.

Петросян, Л.А. Игры поиска [Электронный ресурс] / Л.А. Петросян, А.Ю. Гарнаев. – М.: СПбГУ, 1992. С. 314.

Реализация игры «Морской бой» [Электронный ресурс] – Режим доступа: http://aka-alex.narod.ru/index.htm

Семакин, И.Г. Основы программирования. [Текст] / И.Г. Семакин, А.П. Шестаков. – М.: Мир, 2006. C. 346.

Симанков, В.С. Основы функционального программирования [Текст] / В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.

Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А. Степанов, А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.

Хювенен Э. Мир Лиспа [Текст] / Э. Хювенен, Й. Сеппянен. – М.: Мир, 1990. – 460 с.

Похожие работы:

  1. Позиционные системы счисления
  2. • "Звезды прелестные" в поэзии Пушкина и его современников
  3. • Краткий курс истории Московского троллейбуса
  4. • Словник слів іншомовного пожодження економічного ...
  5. • Формування маркетингової стратегії ЗАТ "Оболонь"
  6. • Меркантилизм и доктрина А. Смита
  7. • Охрана труда при работе на компьютере
  8. • Исследование уровня безопасности операционной системы Linux
  9. • "Звезды прелестные" в поэзии Пушкина и его современников
  10. • "Звезды прелестные" в поэзии Пушкина и его современников
  11. • Восточные славяне в древности
  12. • Технология HTML
  13. • Публий Теренций Афр
  14. • Решения задачи планирования производства симплекс ...
  15. • Латинский язык: Практические задания для студентов заочного ...
  16. • Проект концептуального анализа развития туризма в ...
  17. • Основы латинского языка
  18. • Основы здорового образа жизни студента. Физическая культура в ...
  19. • Способы отрицания в современном немецком языке
  20. • Changes and specimens of the English language
Рефетека ру refoteka@gmail.com