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

Тип: курсовая работа
Категория: Информатика

Скачать

Купить

СОДЕРЖАНИЕВведение1 Постановка задачи2 Математические и алгоритмические основы решения задачи3 Функциональные модели и блок-схемы решения задачи4 Программная реализация решения задачи5 Пример выполнения программыЗаключениеСписок использованных источников и литературыВведениеИгра «морской бой» достаточно хорошо известна и популярна. Практически каждый школьник в тот или иной период своей жизни играл в эту игру. В последние годы в связи с появлением компьютеров и новых обучающих и развивающих программ вновь возрос интерес к ней. Если набрать запрос о поиске игры в Интернет, то поисковая машина выдаст несколько тысяч ссылок. Здесь и реклама, и различные варианты игры, и качественные исследования оптимальных стратегий игры и т.д. Но мало кто знает о том, что эта игра имеет серьезное научное и практическое приложение, и для ее анализа могут быть использованы современные математические и компьютерные методы. В качестве примера такого приложения можно привести проблему эффективного поиска записей в больших базах данных, обладающих сложной многоуровневой структурой.Остановимся на некоторых основных правилах классического варианта игры. Первый игрок, игрок А, расставляет корабли на квадратном игровом поле из n клеток (обычно это поле клеток). Корабли делятся на классы: одноклеточные, двухклеточные, трехклеточные и четырехклеточные. Игрок В на своем поле расставляет свои корабли. Заметим, что корабли не должны касаться друг друга. Игра состоит в том, что игроки по очереди называют координаты клеток, в которых, как они предполагают, расположены корабли противника, то есть как бы производят выстрел по выбранной клетке. О попадании или промахе игроку сообщается после выстрела. Игра продолжается до тех пор, пока у одного из игроков не будут уничтожены все корабли.На первый взгляд, эта игра носит чисто вероятностный характер, так как игроки ведут обстрел, не зная расположения кораблей противника. Но, приобретя некоторый опыт игры, можно заметить, что существуют стратегии расстановки кораблей, которые уменьшают вероятность попадания в последний одноклеточный корабль. Например, можно расположить весь флот таким образом, чтобы он занимал минимальное место на игровом поле, а один или два корабля ставят на оставшемся пространстве как на рисунке 1. Поиск кораблей также можно проводить, придерживаясь определенной системы, которая позволяет наиболее быстро обнаружить в начале игры многоклеточные корабли, а затем на оставшемся пространстве искать одноклеточные корабли.Рисунок 1Эти качественные рассуждения показывают, что у игроков А и В существует множество неравнозначных различных стратегий игры, то есть может быть поставлен вопрос о поиске оптимальных стратегий.Заметим, что все это разнообразие стратегий, как это будет показано ниже, определяется правилом, запрещающим ставить корабли вплотную, а также правилом окончания игры.В дальнейшем будем рассматривать только одностороннюю игру: игрок А расставляет корабли, а игрок В ведет их поиск.Математическую модель игры можно строить двумя способами. Первый способ состоит в том, что после каждого выстрела учитываются изменения поля игры и вероятности обнаружения кораблей. Такая форма игры называется развернутой, а сама игра представляется многошаговой. Сложность применения этого подхода связана с необходимостью определения вероятностей событий, которые являются комбинацией большого числа элементарных событий. При увеличении числа выстрелов k количество комбинаций растет пропорционально k! (факториалу k).Второй способ состоит в том, что в качестве исходного множества событий рассматривается множество стратегий, элементы которых представляют полную последовательность n выстрелов. В этом случае игра становится одношаговой, то есть игрок производит выбор не одной клетки при выстреле, а выбирает последовательность из n выстрелов. Такая форма игры называется нормальной. Второй подход к построению игры носит интегральный характер, однако, в этом случае возникает проблема, связанная с понятием окончания игры.1. Постановка задачиЗадача заключается в разработке алгоритма, по которому компьютер сможет играть в «Морской бой» с максимальным качеством, и при этом не подглядывая расположение флота игрока.Дополнительное и очевидное условие: при каждой новой игре вне зависимости от размещения сил противника компьютер должен играть по-разному, т.е. его ходы должны быть не предсказуемы.Необходимо вспомнить правила игры: участники поединка делают ходы поочередно, причем, если один из игроков попадает по кораблю соперника, то он получает право следующего хода. Если реализовать поиск цели компьютером в виде отдельной процедуры, то надо как-то научить его запоминать исходы прошлых выстрелов, чтобы адекватно произвести следующий. Из этого факта вытекает, что самое простое и рациональное решение данной проблемы можно оформить в виде конечного автомата, наиболее точно описывающего последовательность действий.Можно выделить три состояния:

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

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

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

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

Другие файлы:

Веселые стихи для запоминания английских слов.
СПб.: 2006. - 32 с. Книга позволяет в увлекательной форме освоить английский алфавит и изучить слова по теме "Времена года", "...

Учебные таблицы по русскому языку. 5-11 классы.
М.: ТЦ Сфера, 2008. - 208 с. Настоящее пособие представляет собой обобщенное изложение в таблицах теоретического материала по основны...

Литература. 7 класс. ("Путь к станции "Я") В 2 кн. Кн. 1.
3-е изд., испр. - М.: 2008. - 288 с. Учебник-хрестоматия является продолжением непрерывного авторского курса "Чтение и литература"...

Охрана труда. Справочник.
М.: Дашков и К, 2008. — 588 с. В предлагаемом справочнике дана законодательная, нормативно-правовая база Российской Федерации в области охраны т...

Обществознание: 10-11кл. Школьный словарь-справочник.
М.: АСТ, Астрель, Транзиткнига, 2004. — 510 с. В школьном словаре-справочнике "Обществознание" для учащихся 10-11 классов представлены...