/>СОДЕРЖАНИЕ
Введение
1 Постановка задачи
2 Математические и алгоритмическиеосновы решения задачи
3 Функциональные модели иблок-схемы решения задачи
4 Программная реализация решения задачи
5 Пример выполненияпрограммы
Заключение
Список использованных источников и литературы
Введение
Игра «морскойбой» достаточно хорошо известна и популярна. Практически каждый школьник в тотили иной период своей жизни играл в эту игру. В последние годы в связи споявлением компьютеров и новых обучающих и развивающих программ вновь возросинтерес к ней. Если набрать запрос о поиске игры в Интернет, то поисковаямашина выдаст несколько тысяч ссылок. Здесь и реклама, и различные вариантыигры, и качественные исследования оптимальных стратегий игры и т.д. Но мало ктознает о том, что эта игра имеет серьезное научное и практическое приложение, идля ее анализа могут быть использованы современные математические икомпьютерные методы. В качестве примера такого приложения можно привестипроблему эффективного поиска записей в больших базах данных, обладающих сложноймногоуровневой структурой.
Остановимсяна некоторых основных правилах классического варианта игры. Первый игрок, игрокА, расставляет корабли на квадратном игровом поле из n клеток (обычно это поле /> клеток). Корабли делятсяна классы: одноклеточные, двухклеточные, трехклеточные и четырехклеточные.Игрок В на своем поле расставляет свои корабли. Заметим, что корабли не должныкасаться друг друга. Игра состоит в том, что игроки по очереди называюткоординаты клеток, в которых, как они предполагают, расположены кораблипротивника, то есть как бы производят выстрел по выбранной клетке. О попаданииили промахе игроку сообщается после выстрела. Игра продолжается до тех пор,пока у одного из игроков не будут уничтожены все корабли.
На первыйвзгляд, эта игра носит чисто вероятностный характер, так как игроки ведутобстрел, не зная расположения кораблей противника. Но, приобретя некоторый опытигры, можно заметить, что существуют стратегии расстановки кораблей, которыеуменьшают вероятность попадания в последний одноклеточный корабль. Например,можно расположить весь флот таким образом, чтобы он занимал минимальное местона игровом поле, а один или два корабля ставят на оставшемся пространстве какна рисунке 1. Поиск кораблей также можно проводить, придерживаясь определеннойсистемы, которая позволяет наиболее быстро обнаружить в начале игрымногоклеточные корабли, а затем на оставшемся пространстве искать одноклеточныекорабли.
/>
Рисунок 1
Этикачественные рассуждения показывают, что у игроков А и В существует множествонеравнозначных различных стратегий игры, то есть может быть поставлен вопрос опоиске оптимальных стратегий.
Заметим, чтовсе это разнообразие стратегий, как это будет показано ниже, определяетсяправилом, запрещающим ставить корабли вплотную, а также правилом окончанияигры.
В дальнейшембудем рассматривать только одностороннюю игру: игрок А расставляет корабли, аигрок В ведет их поиск.
Математическуюмодель игры можно строить двумя способами. Первый способ состоит в том, чтопосле каждого выстрела учитываются изменения поля игры и вероятностиобнаружения кораблей. Такая форма игры называется развернутой, а сама играпредставляется многошаговой. Сложность применения этого подхода связана снеобходимостью определения вероятностей событий, которые являются комбинациейбольшого числа элементарных событий. При увеличении числа выстрелов kколичество комбинаций растет пропорционально k! (факториалу k).
Второй способсостоит в том, что в качестве исходного множества событий рассматриваетсямножество стратегий, элементы которых представляют полную последовательность nвыстрелов. В этом случае игра становится одношаговой, то есть игрок производитвыбор не одной клетки при выстреле, а выбирает последовательность из nвыстрелов. Такая форма игры называется нормальной. Второй подход к построениюигры носит интегральный характер, однако, в этом случае возникает проблема,связанная с понятием окончания игры.
1.Постановка задачи
Задачазаключается в разработке алгоритма, по которому компьютер сможет играть в «Морскойбой» с максимальным качеством, и при этом не подглядывая расположение флотаигрока.
Дополнительноеи очевидное условие: при каждой новой игре вне зависимости от размещения силпротивника компьютер должен играть по-разному, т.е. его ходы должны быть непредсказуемы.
Необходимовспомнить правила игры: участники поединка делают ходы поочередно, причем, еслиодин из игроков попадает по кораблю соперника, то он получает право следующегохода. Если реализовать поиск цели компьютером в виде отдельной процедуры, тонадо как-то научить его запоминать исходы прошлых выстрелов, чтобы адекватнопроизвести следующий. Из этого факта вытекает, что самое простое и рациональноерешение данной проблемы можно оформить в виде конечного автомата, наиболееточно описывающего последовательность действий.
Можновыделить три состояния:
1) прострел игрового поля послучайным координатам до попадания по кораблю, после чего переход во второесостояние;
2) обстрел вокруг подбитойячейки поля для определения направления корабля (вертикальное илигоризонтальное), после очередного попадания – переход в третье состояние;
3) расстрел корабля вполученном направлении до полного его уничтожения, после чего переход в первоесостояние.
И так, всяигра зациклена на трех основных действиях: прострел, обстрел и расстрел. Всеэти действия должны продолжаться до тех пор, пока у одной из сторон не будутуничтожены все корабли.
Прострел
На этом этапекомпьютер должен поймать какой-либо из кораблей противника. Для этого он будетстрелять по произвольным незанятым клеткам поля игрока. Гораздо эффективнеесначала разделаться с большими кораблями, поэтому выбирая координаты длявыстрела надо проверять, что бы в этой позиции мог разместиться самый большойиз оставшихся кораблей. Процесс прекращается, как только произойдет попадание.Обозначим подбитую часть корабля значением «*», а промах «~» соответствующейячейки поля. Если у игрока остались только однопалубные корабли, то этимпопаданием корабль уничтожен полностью и обстреливать его нет смысла. Впротивном случае надо перейти ко второму состоянию.
Обстрел
На этом шагезадача заключается в определении направления пойманного корабля. Для этого надообстрелять четыре ячейки (если они свободны), которые могут служитьпродолжением. В случае, когда все четыре клетки обстреляны, а попадания непроизошло (однопалубный корабль), надо перейти к первому состоянию. Если вкакой-то момент удалось подбить еще одну палубу противника, то можно переходитк расстрелу данного корабля, т. к. его направление стало известно.Аналогично первому состоянию, если у игрока остались корабли не более двух палуб,то этим попаданием корабль уничтожен полностью и надо вернуться к прострелу.
Расстрел
На предыдущемшаге удалось установить в каком направлении размещен пойманный корабль. Теперьзадача заключается в его полном уничтожении. Для этого надо стрелять справа илислева (сверху или снизу) подбитых палуб, пока не добьем его целиком, после чеговернемся в состояние прострела. При этом следует учитывать максимальновозможный корабль и стараться попасть по четвертой палубе, когда четырехпалубный корабль уничтожен, нет никакого смысла.
Пример
Поле кораблей1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Стратегияигры компьютера.
1. Выбирается случайнаяклетка, рассматривается ее значение.
2. Если значение = 1 –попали в корабль, отмечаем удар «*»;
3. Если значение = 0 –промазали, отмечаем удар «~»;
4. Если значение = «*» илизначение = «~», значит в эту клетку нами уже был произведен удар, возвращаемсяк шагу 1.
После тогокак все корабли разбиты, прекращаем бой. Поле разбитых кораблей* * * * ~ ~ * ~ ~ ~ ~ ~ ~ ~ ~ ~ * ~ ~ ~ ~ ~ ~ ~ * ~ * ~ ~ ~ * ~ ~ ~ * ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ * ~ ~ ~ ~ ~ * ~ ~ ~ ~ ~ ~ ~ ~ ~ * ~ ~ ~ ~ * * ~ ~ ~ ~ * ~ * ~ ~ ~ ~ * * *
Нулямиобозначены те клетки, в которые мы не попали.
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)) (>= k10)))
(do
()
((or (> l (+ j 1)) (>= l10)))
(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)) (>= k10)))
(do
()
((or (> l (+ j 1)) (>= l10)))
(if (not (eql (nth l (nthk 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. Реализация игры «Морскойбой» [Электронный ресурс] – Режим доступа: aka-alex.narod.ru/index.htm
5. Семакин,И.Г. Основы программирования. [Текст] / И.Г. Семакин, А.П. Шестаков.– М.: Мир, 2006. C. 346.
6. Симанков,В.С. Основы функционального программирования [Текст] / В.С. Симанков,Т.Т. Зангиев, И.В. Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.
7. Степанов, П.А. Функциональноепрограммирование на языке Lisp. [Электронный ресурс] / П.А. Степанов, А.В. Бржезовский. – М.: ГУАП, 2003. С. 79.
8. ХювененЭ. Мир Лиспа [Текст] / Э. Хювенен, Й. Сеппянен. – М.: Мир, 1990. –460 с.