47045 (Игра в "Морской бой" с компьютером), страница 2

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)

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

(defun set_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)

(return t)

)

)

(setq l (+ l 1))

)

(setq k (+ k 1))

)

(return nil)

)

(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))

)

(return nil)

)

t

)

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

(defun set_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)) '*))

)

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

(defun blow(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.

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

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

Пример 2.

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

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

Пример 3.

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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