Темой данного курсового проекта является создание игры «Морской бой». Все, кто имеет дело с компьютером, так или иначе сталкивались с компьютерными играми, и подавляющее большинство может сходу назвать несколько игр, которые им особенно понравились. Те, кто уже совсем наигрался, возможно, хотели бы придумать какие-нибудь свои, не похожие ни на какие другие игры.
Многое захватывает в таком творчестве. И не сам процесс игры, а разработка игровой вселенной, ее проектирование и реализация. Когда можно слить воедино сценарий, а так же искусно задуманный и умело запрограммированный алгоритм — создать единый фантастический мир, живущий по законам, которые ты же для него и придумал.
В данной курсовой работе речь пойдет о создании несложной игровой программы «Морской бой», которая и будет являться объектом исследования.
В данной пояснительной записке представлены следующие главы:
1. математическая постановка задачи (в данной главе описаны математические принципы построения проекта);
C# — Морской Бой — Самый лучший алгоритм ИИ
2. метод решения задачи (в данной главе описаны реализация метода и принципы проектирования);
3. укрупненная структура разработанной программы и описание назначения ее компонентов (в данной главе структура всех данных и наименование юнитов);
4. схемы алгоритмов решения задачи (в данной главе описаны алгоритмы, применяющиеся при решении);
5. результаты тестирования разработанной программы (в данной главе описана методика тестирования);
6. методика работы пользователя с разработанной программой (в данной главе описана область применения проекта).
Математическая постановка задача
Для того чтобы приступить к построению и анализу математической модели игры, необходимо определить вероятности обнаружения кораблей при различном их расположении и различных системах поиска.
Для того чтобы приступить к построению и анализу математической модели игры, необходимо определить вероятности обнаружения кораблей при различном их расположении и различных системах поиска
На поле из n клеток расположен одноклеточный корабль. Определим вероятность попадания в корабль k-ым выстрелом, то есть его уничтожение.
В качестве пространства элементарных исходов выбора игрока В рассмотрим множество стратегий обстрела игрового поля, каждая стратегия состоит из n выстрелов,
где — номер выбранной клетки, то есть рассмотрим множество всех выборок из n по n клеток. Очевидно, что это пространство содержит элементов и все эти стратегии равновозможны. Количество стратегий с благоприятным исходом, то есть количество выборок, содержащих на k-ом месте искомую клетку
Определим вероятность уничтожения корабля за k выстрелов. Это событие состоит в том, что корабль может быть уничтожен либо первым выстрелом, либо вторым и т.д., то есть благоприятная выборка из k клеток содержит искомую клетку с кораблем. Количество благоприятных стратегий определится как число неупорядоченных выборок из множества n — 1 клеток по k — 1 (одна клетка, занятая кораблем не учитывается при выборке), умноженное на число перестановок в самой выборке k! и число перестановок клеток оставшихся за выборкой (n — k)!:)!. Вероятность попадания в одноклеточный корабль за k выстрелов
#8. Расставляем корабли в игре «Морской бой» | Генетические алгоритмы на Python
.(1)
Усложним задачу. На поле из n клеток расположен двухклеточный корабль. Определим вероятность первого попадания в корабль (в одну из его клеток) выстрелом с номером k. Полное число всевозможных стратегий, как и в предыдущем случае, равно , а число благоприятных стратегий определяется как сумма благоприятных стратегий попадания в одну клетку и попадания во вторую клетку, то есть . Вероятность попадания k-ым выстрелом равна .
Очевидно, что при обстреле m-клеточного корабля или m одноклеточных кораблей, вероятность попадания k-ым выстрелом равна
Определение вероятности попадания в двухклеточный корабль за k выстрелов, сведется к определению количества стратегий, содержащих искомые клетки в первых k выстрелах. Число таких стратегий будет вычисляться как следующая сумма
где — выборки, содержащие либо первую клетку, либо вторую клетку, — выборки, содержащие одновременно две клетки. Следовательно
и после преобразований получим
Заметим, что аналогичным образом можно определить вероятность попадания за k выстрелов в корабль из m клеток. Задача попадания за k выстрелов в многоклеточный корабль хотя бы один раз является задачей поиска корабля. Очевидно, что если учесть геометрию корабля, то можно предложить систему его поиска, при которой вероятность обнаружения становится выше. Действительно, при поиске двухклеточного корабля можно рассмотреть подмножество всех стратегий, содержащих обстрел, например, клеток только с четными или с нечетными номерами. Поиск двухклеточного корабля сведется к поиску одноклеточного корабля на этом подмножестве. Полагая n четным, для оптимальной вероятности попадания за k выстрелов получим
Найденное значение вероятности больше вероятности, полученной выше
при всех значениях .
Оптимальная стратегия поиска трехклеточного и четырехклеточного корабля может быть получена аналогичным образом.
Вероятность попадания в игре «Морской бой»
Всего клеток 100
а) вероятность попасть в какой-нибудь корабль равна ;
б) вероятность попасть в четырехпалубный равна ;
в) вероятность попасть в однопалубный равна ;
Всего кораблей 10, не однопалубных 6, «клеточек» 16.
а) вероятность попасть в четырехпалубный равна ;
б) вероятность попасть в трехпалубный равна ;
в) вероятность попасть в двухпалубный равна .
Источник: studentopedia.ru
Алгоритм игры в «морской бой»: обстрел противника
Доброго времени суток, уважаемые! Так случилось, что вопросом программирования более-менее адекватного ИИ для игры «морской бой» я озадачился где-то в конце 2004 года. Быть может я, не имея должных руководств под рукой, изобретал тогда велосипед, но и в последствии, мне попадались потрясающие своей честностью алгоритмы: стрелять наобум, время от времени подглядывая у игрока расположение кораблей, для выравнивания баланса. В последствии я несколько раз улучшал алгоритм. По последним статьям на Хабре можно судить, что тема актуальна, к тому же — мне есть что добавить к написанному другими пользователями.
Итак, цель моей заметки: реализация оптимальной одной из стратегий атаки на корабли соперника, причём не только первое попадание, но и последующее «сопровождение ко дну». Отмечу, что корабли в моей реализации — почти (об этом ниже) произвольной формы.
Введение
Я позволю себе сократить вводную часть — для целостности картины рекомендую обратиться к предшествующим статьям:
- Оптимальный алгоритм игры в морской бой (GORKOFF)
- Теория и практика игры «Морской бой» — по-честному (born2fly)
Примечание
В статье не рассмотрена оптимизация на уровне кода, а алгоритмы приведены в максимально развёрнутом (подробном) виде.
Помимо поясняющих рисунков, статья содержит скриншоты из моих программ/игр.
Режимы
В стратегии ведения боя явно можно выделить две стадии (два режима).
- «Разведка боем». На карте противника нет ни одного «раненого» корабля. ИИ выбирает точку для атаки «полностью здорового» судна.
- «Добивание». На карте есть клетка (клетки) отмеченные как «ранил». ИИ пытается определить корпус и ориентацию судна, чтобы потопить его.
Разведка
Для того, чтобы добиться уровня абстракции, позволяющего атаковать эскадру, сформированную из произвольного количества судов произвольной формы (тем не менее, согласно правилам, данная информация о сопернике заранее известна), введём понятие вероятности нахождения в данной клетке игрового поля фрагмента неподбитого корабля («палубы»). Критерием для выбора точки атаки будет величина, пропорциональная упомянутой выше вероятности, а именно: нормированное количество палуб, которые могут попасть в эту клетку, если каждый из кораблей противника (из тех, что на плаву) попытаться разместить на поле всеми возможными способами.
Поясню: берём матрицу (далее — «P-матрица»), размерами соответствующую, размерам поля противника. Заполняем её нулями. Берём первый доступный (то есть ещё не утонувший) корабль противника из списка кораблей соперника и пробуем его разместить (в соответствии с правилами и опираясь на полученную в ходе обстрела информацию) в координатах А1.
Если разместить удалось, то инкрементируем в P-матрице все элементы (соответствующие клеткам игрового поля), накрываемые корпусом корабля. Повторяем процедуру для всех координат. Затем поворачиваем корабль на 90 градусов и ещё раз повторяем проход для всех координат. То же повторяем для 180 и 270 градусов.
В итоге, мы заполним P-матрицу значениями, которые для удобства нормируем по максимуму. Полученная характеристика принимает единичное значение в наиболее вероятных точках нахождения кораблей и нулевое в невозможных. Например, на необстрелянной карте, центральные точки (для классической эскадры) имеют максимальное значение.
Стоит определиться с термином «вероятность», чтобы избежать его превратного толкования. Данный алгоритм предполагает равномерное расположение кораблей по полю. Попытки распихать суда по краям поля должны детектироваться отдельно. Например, можно ввести весовую матрицу, которая каким-то образом будет формироваться в ходе обучения (предшествующих игр с данным соперником): если до этого противник никогда не ставил корабль в центре поля, то соответствующие клетки весовой матрицы будут иметь минимальный коэффициент. В любом случае: это не шахматы — всегда есть неизвестная информация, которая, при удачном стечении обстоятельств, может дать преимущество «обороняющемуся». 
На рисунке слева приведена визуализация P-матрицы при первом ходе ИИ в игре с классической эскадрой. Цвет [ RGB(0;0;0); RGB(255;0;0) ] показывает значение клетки. Белым крестиком отмечены максимумы значений. Как нетрудно заметить, максимумов, как правило, несколько. Чтобы разнообразить игру и исключить потенциальную возможность предугадать точку атаки, выбранную ИИ (и соответствующим образом расставить корабли), выбирать будем произвольную точку из максимумов (на рисунке — имеет жёлтую рамку).
Ответы соперника «мимо» или «убил» оставляют режим работы ИИ без изменений (во втором случае необходимо произвести ряд действий). Ответы запоминаются в специальную матрицу, аккумулирующую знания о расстановке сил противника. Именно «на этой матрице» производятся попытки размещения кораблей при вычислении P-матрицы.
При использовании только классической эскадры возможно провести оптимизацию вычисления матрицы (об этом ниже).
Добивание
После того, как от соперника получен ответ «ранил», ИИ переходит во второй режим функционирования. 
В этом режиме при вычислении P-матрицы количество «палуб» проверяемого корабля должно быть больше, чем количество клеток «ранил». Корабль инкрементирует значения элементов P-матрицы, только если данное его размещение накрывает все клетки, отмеченные как «ранил».
После перебора всех кораблей происходит дополнительное акцентирование на клетках «ранил». Так как стрелять в такие клетки бессмысленно (но, в отличии от клеток «мимо», они являются частью корабля, и потому имеют ненулевое значение в P-матрице), значения соответствующих элементов P-матрицы обнуляются. Обнуляются так же клетки, не примыкающие ни к одной из клеток «ранил».
Последнее обстоятельство связано с тем, что при некотором стечении обстоятельств, усиленном экзотической формой кораблей не классической эскадры, можно выбрать в P-матрице максимум, который соответствует другом кораблю (что возможно, только если атакуемая клетка отстоит от «раненой»). Такая ситуация приведёт к тому, что ИИ будет пытаться подобрать корабль, удовлетворяющий обеим клеткам, что рано или поздно кончится неудачей. Это в свою очередь приведёт к тому, что все элементы P-матрицы примут нулевые значения, а, следовательно, уже обстрелянные точки станут адекватными вариантами атаки. Поэтому, разумной является атака близлежащих точек. 
На рисунке слева представлены две матрицы (точнее, визуализации их значений). Верхняя — с расположенными на белом поле серыми кораблями. На предыдущем ходу ИИ осуществил успешную атаку на Ж4 (то обстоятельство, что первый же ход увенчался успехом — совпадение), «раненая» клетка отмечена жёлтым. Внизу приведена P-матрица.
Учитывая геометрию актуального набора кораблей, у ИИ было 4 равновероятных варианта атаки (отмеченные крестиком клетки), из которых он выбрал Ж3 (клетка с жёлтой рамкой). Ход завершился промахом (синяя клетка в верхней матрице).
При наборах кораблей с экзотической геометрией, матрицы могут выглядеть куда как более загадочно. Хоть я и привык играть с классической эскадрой, но не вижу ничего предосудительного в использовании кораблей почти произвольной формы. Такие модели, могут имитировать, например, скоростной катамаран, RV FLIP, тяжёлый авианесущий крейсер, «бетонный линкор». Не говоря уже о том, что неподвижные (по логике игры) объекты можно интерпретировать и как маломобильные (или стационарные) стратегические объекты на суше во время глобальной войны. С позиции игрового процесса, на мой взгляд, подобное усложнение лишь добавляет азарта при игре.
На рисунке справа показана ситуация: после нескольких удачных залпов ИИ выбирает не то направление и промахивается на Е13. Обратите внимание, что было 10 вариантов хода, имеющих смысл, из них 2 наиболее вероятных.
Режим «добивание» переключается на «разведку» только после ответа соперника «убил». Как и при первом режиме, полученная в ходе обстрела информация учитывается при формировании P-матрицы на следующем ходу.
Классика
Использование классической эскадры, то есть «одномерных» кораблей, позволяет конкретизировать подход, сократив число операций. С одной стороны, нижеописанные алгоритмы менее гибки и экономят крохи производительности (учитывая, актуальный уровень техники, и большой, обусловленный жанром, запас времени на ход), но с другой стороны — эти алгоритмы более близки к человеческому восприятию игры, что может облегчить понимание процесса функционирования ИИ. 
Отмечу, что специфика геометрии классических кораблей (а именно — одномерность), делает вероятность разместить корпус, развёрнутый на 180 градусов (в зависимости от точки вращения — с соответствующей коррекцией координат) равной вероятности размещения корпуса с нулевым углом вращения. Иными словами, для всех кораблей невозможно определить: расположен он сверху вниз или снизу вверх, слева направо или справа налево (смотри рисунок слева: 4 угла вращения для серого корпуса и 2 — для классического коричневого). Это обстоятельство позволяет уменьшить количество вычислений, оставив для всех кораблей лишь тест на размещение при угле 0 и 90 градусов. 
Начинаем двигать препятствие слева, и получаем характеристики: 1, 2, 3, 3. Из результатов видно, что характеристика ограничена сверху длиной корабля.
Резюмируя:
- Если сумма расстояний + 1 (тестируемая клетка) меньше, чем длина корабля, то результат равен 0.
- Если сумма расстояний + 1 равна длине корабля, то результат равен 1.
- В остальных случаях, характеристика:
- не меньше 1
- не превышает длину корабля
- ограничивается минимальным расстоянием до препятствия
Исходя из вышесказанного, код функции, вычисляющей характеристику имеет вид:
inline unsigned minimum(unsigned A,unsigned B) < return Aunsigned Bf(unsigned A,unsigned B,unsigned K)
Если в эскадре противника несколько кораблей одной длины, то, чтобы учесть их суммарное влияние на клетку, достаточно посчитать Bf один раз и умножить результат на количество единиц техники. Перебрав все уникальные длины кораблей противника (для классики — 4 варианта) и учтя количество кораблей с такой длиной корпуса на плаву, получаем некую характеристику Gf. Данная характеристика описывает количество «палуб», попадающих в клетку при фиксированной ориентации (но не координатах) всех кораблей (например, для рисунка выше — горизонтальной). Итоговая характеристика G2df, представляет собой сумму Gf для горизонтальной и вертикальной ориентации. Матрица значений G2df для всех клеток игрового поля, является аналогом P-матрицы, рассмотренной выше. Опираясь на максимумы матрицы, выбираем точку атаки. В случае успеха, переходим в режим добивания, где выбираем клетку, соответствующую наиболее свободному (но в пределах максимальной длины корпуса среди неуничтоженных кораблей противника) направлению. Если несколько направлений равновероятны — выбираем случайным образом. Выбрав направление атаки, продолжаем огонь до одного из исходов:
- 1. Корабль уничтожен. Переходим в режим поиска новой жертвы.
- 2. Промах. Значит атака была начата не с крайней точки. Инвертируем направление обстрела, продолжаем атаку от точки первого «ранения»
- 2.1. Промах на первом же выстреле в режиме добивания. Значит, направление выбрано ошибочно. Необходимо заново вычислить вероятности направлений, учитывая полученную информацию.
Заключение
Итак, теперь вы знаете как вести огонь по противнику, и как оптимально расставить корабли (см. ссылки в начале статьи).
Самому мне хотелось бы узнать мысли сообщества по поводу неоптимальной (равномерной) расстановки кораблей: даже в классическом варианте возможна тупиковая ситуация, если не двигать уже выставленные корабли. Для кораблей произвольной формы, вероятно, можно обосновать критерий на минимальные размеры поля для размещения.
Спасибо, всем дочитавшим статью до конца. Постараюсь ответить на интересующие вопросы.
Просьба: указания на ошибки и прочие предложения по редактуре пишите в личку, чтобы не разбавлять обсуждение.
Критика
Спасибо за интересные и конструктивные замечания!
mayorovp уточняет, что рассмотренный алгоритм работает оптимально лишь в некотором приближении. В самом деле, рассмотрим предложенную ситуацию:
на поле осталось пять клеток в линии и два корабля 1х2, то оптимальный алгоритм уничтожит их за 4 выстрела без промахов. Ваш же алгоритм определит, что «вероятность» нахождения корабля в центре — максимальна, и может попытаться выстрелить туда (в одном случае из трех).
Действительно:
В отличии от очевидной человеку оптимальной тактики, ИИ с вероятностью в 33% предпримет априорно неверное решение, атаковав А3 на N-ом ходу. На (N+1)-ом ходу (в случае успеха на N-ом) может быть реализована ошибочная атака с вероятностью в 50% (на рисунке — атака на А3 на втором слайде).
Как отмечает mayorovp,
Оптимальный алгоритм должен
1) при подсчете вероятности размещать на поле не один корабль, а всю эскадру противника с учетом ограничений на соседство;
Отмечается и слабость адаптации к неравномерному распределению кораблей на игровом поле в ходе обучения:
2) учитывать, что противник может намеренно разместить свою эскадру в наименее вероятной позиции (по краям, например), и предпринимать ответные действия уже в первой игре, вместо обучения под конкретного соперника.
К сожалению, мой «всеобъемлющий» подход столкнулся со сложностями вычислительного характера, что даже на современных компьютерах просчитать все комбинации невозможно, а можно лишь искать некоторое приближение методом Монте-Карло, но и это оказалось затруднительно в реальном времени.
zorge_van_daar поднимает интересный вопрос: возможно ли вместо добивания, переключиться на поиск новых кораблей (принимая во внимание полученную после атаки информацию), так как обнаружить всю технику противника — и есть основная цель игры, а уничтожить обнаруженное можно и после.
По вполне обоснованному совету limon_spb и других пользователей, убрал излишне претенциозную характеристику «оптимальный». Так как подобное заявление требует объективного доказательства, которое в статье не приведено, и, в силу вышесказанного, приведено быть не может.
- морской бой
- вариант стратегии
- атака
Источник: habr.com
Алгоритм расстановки кораблей (морской бой) — Pascal ABC
Нужен алгоритм (написанный на паскале) расстановки кораблей на поле 10×10, как в морском бою. Нужно что бы корабли при каждом вызове процедуры меняли свое положение, т.е. что бы не ставились всегда в одном месте, а так же что бы стояли как вертикально, так и горизонтально и желательно что-бы однопалубники помечались 1, двухпалубники 2 и т.д.
Код к задаче: «Алгоритм расстановки кораблей (морской бой)»
Листинг программы
type mas = array[1..10,1..10] of integer; //=============поле function show(p1: mas):integer; //================Показывает поле var i,j:integer; begin for i:=1 to 10 do begin for j:=1 to 10 do write(p1[i,j],’ ‘); writeln; end; end; function newgame(p1: mas):integer; //=============ОЧИСТККА ПОЛЯ (ЗАПОЛНЕНИЕ 0) var i,j:integer; begin for i:=1 to 10 do for j:=1 to 10 do p1[i,j]:=0; end; function setship(p1: mas):integer; var i,j,l,pol:integer; //=========== pol — ПОЛОЖЕНИЕ 0-ГОРИЗАНТАЛЬНОЕ 1 — ВЕРТИКАЛЬНОЕ, l — вспомогательная переменная label ij1; label ij2; begin pol:=random(2); if pol=0 then begin //========================вертикальное ij1: i:=random(10)+1; j:=random(10)+1; if j
Источник: studassistent.ru