26 мая 2013 в 20:27

Оптимальный алгоритм игры в морской бой

Алгоритмы

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

Правила игры

Существует множество вариантов морского боя, но мы с вами рассмотрим наиболее распространённый вариант со следующим набором кораблей:

Все перечисленные корабли должны быть размещены на квадратном поле 10 на 10 клеток, при этом корабли не могут соприкасаться ни углами, ни сторонами. Самое игровое поле нумеруется сверху вниз, а вертикали помечаются русскими буквами от «А» до «К» (при этом буквы «Ё» и «Й» пропускают).

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

Оптимальная стратегия

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

В дальнейшем объяснении будут использоваться следующие обозначения:

Оптимальная стрельба

Первым и самым очевидным правилом оптимальной стрельбы является следующее правило: не стрелять по клеткам непосредственно окружающим уничтоженный корабль противника.

В соответствии с принятыми выше обозначениями, на рисунке жёлтым отмечены те клетки, по которым уже были произведены безуспешные выстрелы, красным отмечены клетки, выстрелы по которым закончились попаданием, а зелёным отмечены клетки, стрельба по которым не производилась, но можно гарантировано утверждать, что кораблей в них нет (кораблей там быть не может, т.к. по правилам игры корабли не могут соприкасаться).

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

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

Т.о. оптимальную стратегию стрельбы можно свести к целенаправленному поиску и уничтожению самых крупных кораблей противника. К сожалению, сформулировать стратегию мало, необходимо предложить способ её реализации.

Для начала давайте рассмотрим участок игрового поля размером 4 на 4 клетки. Если в рассматриваемом участке есть вражеский линкор, то его гарантировано можно подбить не более чем за 4 выстрела. Для этого надо стрелять так, чтобы на каждой горизонтали и вертикали было ровно по одной проверенной клетке. ниже представлены все варианты такой стрельбы (без учёта отражений и поворотов).

Среди всех этих вариантов, оптимальными на поле 10 на 10 клеток являются только первые два варианта, гарантирующие попадание в линкор максимум за 24 выстрела.

После того, как уничтожен вражеский линкор, необходимо начинать поиск крейсеров, а затем и эсминцев. При этом, как вы уже догадались, можно воспользоваться аналогичной методикой. Только теперь необходимо разбивать поле на квадраты со стороной в 3 и 2 клетки соответственно.

Если при поиске линкора вы использовали вторую стратегию, то для поиска крейсеров и эсминцев вам необходимо стрелять по следующим полям (зелёным отмечены поля, по которым вы уже стреляли при поиске линкора):

Для поиска катеров оптимальной стратегии не существует, поэтому в конце игры приходится опираться в основном на удачу.

Оптимальное размещение кораблей

Оптимальная стратегия размещения кораблей в некотором смысле обратна оптимальной стратегии стрельбы. При стрельбе, мы пытались найти самые крупные корабли, чтобы сократить количество клеток, которые нужно проверять, за счёт гарантировано свободных клеток. Значит, при размещении корабли надо ставить таким образом, чтобы в случае их потери минимизировать количество гарантировано свободных клеток. Как вы помните, линкор в центре поля открывает для противника сразу 14 полей, но линкор, стоящий в углу, открывает для противника всего 6 полей:

Аналогично, крейсер, стоящий в углу, вместо 12 полей открывает всего 6. Т.о., разместив крупные корабли вдоль границы поля, вы оставляете больший простор для катеров. Т.к. стратегии для поиска катеров нет, противнику придётся стрелять наугад, и чем больше свободных полей у вас останется к моменту ловли катеров, тем тяжелее будет выиграть противнику.

Ниже представлено три способа размещения крупных кораблей, которые оставляют большой простор для катеров (отмечено синим):

Каждая из приведённых расстановок оставляет для катеров ровно 60 свободных клеток, а это значит, что вероятность случайно попасть в катер составляет 0,066. Для сравнения стоит привести случайную расстановку кораблей:

При такой расстановке для катеров остаётся всего 21 клетка, а это значит, что вероятность попадания по катеру составляет уже 0,19, т.е. почти в 3 раза выше.

В заключение хочу сказать, что не стоит проводить уж слишком много времени, играя в морской бой. Особенно хочу предостеречь вас от игры на лекциях. Когда я сидел в Ваби-Саби и играл в морской бой со своей девушкой, мимо прошла официантка и сказала, что она весьма неплохо играет, т.к. много практиковалась на парах. Кто знает, кем бы она работала, если бы в своё время слушала лекции?

P.S. В комментариях абсолютно верно указывают, что на хабре уже были похожие публикации, было бы неверно не поставить ссылки на них.

" (реж Питер Берг), я был очень вдохновлен тем, как развивается бой на воде. Вовсю гремят взрывы, стальной робот переводит свои прицелы с одного корабля на другой. И вот в итоге выбирает свою цель. Огонь неведомой силы обрушивается на корабль США, противоударные пушки не спасают и какие-то странные “банки” попадают на палубу корабля. Первую секунду кажется, что ничего не происходит, как вдруг… ВЗРЫВ!!! Корабль разносит на части, команды других кораблей не то, что теряют всякую дееспособность от ужаса, они даже теряют дар речи.

И лишь крики одного из солдат: “Б-б-б-боже!” могут передать остроту момента…

И тогда я вспомнил игру "Морской бой", которая спасала меня от скуки в школе. Простые правила, два листа бумаги в клеточку, пара ручек... и вот ты уже капитан своих собственных войск, ведешь сражение не на жизнь, а на смерть. И каждый твой неудачный шаг может послужить причиной гибели твоих кораблей! Более того, при всей простоте игры, результат того, как пойдет сражение, предсказать совершенно невозможно. Напомню правила для тех кто забыл:

Правила

Кликните чтобы посмотреть ответ :

Эта, по истине гениальная игра, была впервые выпущена как настольный комплект в 1931 году фирмой Милтон Брэдли (Milton Bradley). Точнее, "настольная игра" выпущена компанией, как коммерческий продукт. Бумажный же вариант игры появился гораздо раньше, так что истинного автора уже и не узнать.

У вас в распоряжении десять кораблей, а именно:

1 корабль - ряд из 4 клеток («линкор», или «четырёхпалубный»)
2 корабля - ряд из 3 клеток («крейсеры», или «трёхпалубные»)
3 корабля - ряд из 2 клеток («эсминцы», или «двухпалубные»)
4 корабля - 1 клетка («подлодки», или «однопалубные»)

Корабли нужно расположить на поле размером 10х10 клеток так, чтобы они не касались друг друга ни сторонами палубы, ни углами.

Стреляем вслепую по зоне противника, стараясь угадать, в каких квадратах расположилась его флотилия - не забывая отмечать уже проверенные поля. Чтобы противники могли общаться, клетки пронумерованы по горизонтали и по вертикали как шахматная доска - буквами и цифрами.

Прием первый: пробейте диагонали

Прежде всего, прибегнем к простой математике и прикинем - сколько всего клеток занимает наше войско. Легко посчитать: у нас один корабль занимает 4 клетки, два корабля занимают 3 клетки, три корабля - две клетки и четыре корабля - одну... Всего 17 клеток (обязательно проверь мои вычисления!!).

А сколько всего клеток у нас есть? Посчитать их тоже не составит трудности. Десять полей по вертикали и десять по горизонтали. Всего 100 клеточек. Значит, исходя из теории вероятностей, у нас 17% на успешный выстрел, так как только 17 полей из ста окажутся палубами вражеских кораблей.

Теперь давай нарисуем на квадрате нашей территории две диагонали и посмотрим, какие клетки окажутся на этих диагоналях:

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

Добивайте рационально и отмечайте поля вокруг

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

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

Ход конем

Как нам атаковать, чтобы скорее найти четырехпалубный линкор? Что если попробовать стрелять по клеточкам так, как ходит конь по шахматному полю? Но только чуть иначе: после выстрела в одну клеточку делать еще два шага вперед и один - вбок, по диагонали. То есть после того, как мы обстреляем четыре клеточки в одном направлении, следующий удар нанести направо или налево, чтобы точки образовывать букву “Г”.

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

Тем самым нам скорее удастся задеть четырехпалубник, что даст нам несравненное преимущество!

Расставлять корабли кучно

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

Но истинному капитану не следует полагаться лишь на слепую удачу. Можно придержать два однопалубника, когда будешь расставлять свои корабли плотно на трети карты и поставить их после этого в других двух частях. Посчитай, ведь на две другие части карты приходится примерно 60 клеточек. А занимать наши корабли будут всего 2 клеточки. То есть у противника будет 58 возможностей промахнуться, чем он непременно и займется!

Ставить на край

Корабли разумнее ставить вплотную к краю карты. Особенно большие. Это выгодно, так как после уничтожения линкора, как мы уже выяснили выше, 14 клеточек вокруг него не будут уже обстреливаться противником. Если же корабль будет стоять. скажем, в углу, то таких клеточек ореола окажется всего 6. А это существенно меньше!

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

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

Может быть и ты знаешь несколько приемов? Поделись с мной своими хитростями, ведь только собирая из вместе, нам удастся накопить достаточно опыта, чтобы никогда не проигрывать и слышать от наших противников, что: "С ним/с ней лучше не играть в морской бой, он просто непобедим!"

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

Общее

Игра «Морской бой» давно покорила многих людей. Она интересная, увлекательная, а главное - не требует каких-либо затрат. Чтобы поиграть с человеком вдвоём, понадобятся два листа бумаги в клетку (желательно) и две ручки (или 2 карандаша).

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

Правила

Что ж, можно приступать к основной части. Теперь-то вы узнаете, как играть в «Морской бой»:

1. Для начала нужно нарисовать на листе бумаги два квадрата размером 10х10 клеток (понятное дело, рисовать проще на листе в клетку). Затем на обеих рисунках проставить на верхнем ряду буквы от А до К (слева направо, пропуская Ё и Й), а слева от квадратов - цифры от 1 до 10-и (сверху вниз).

2. На левом квадрате необходимо расставить:

1 корабль, состоящий из 4-х клеток;
2 корабля, состоящих из 3-х клеток;
3 корабля, состоящих из 2-х клеток;
4 корабля, состоящие из 1-ой клетки.

Корабли не могут соприкасаться друг с другом ни бортами, ни углами. Важно, чтобы между ними была как минимум одна свободная клетка. Края игрового поля корабли касаться могут, и они должны быть расположены лишь по вертикали и по горизонтали (по диагонали нельзя).

Правый квадрат должен оставаться пустым.

3. Цель каждого из игроков - уничтожить вражеские корабли. Тот, кто ходит первым (по договорённости или по воле случая (с помощью жребия)), называет координаты (буква-цифра), глядя на правый пустой квадрат. Например, Е7. Соперник смотрит на свой левый рисунок, где расположены его корабли, и отвечает:

а) мимо;
б) ранил;
в) убит.

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

Второй вариант означает, что игрок попал в многопалубный корабль (занимающий от 2-х до 4-х клеток). Пометив в своей карте нужное место, человек имеет право на следующий ход до тех пор, пока не промахнётся. Так, если после выкрика Е7 проследовал ответ «ранен», игрок может назвать либо Е6, либо Ж7, либо Е8, либо Д7, чтобы добить раненный корабль (к слову, делать это не обязательно, можно временно оставить его в покое и искать другие). Второй игрок снова отвечает «мимо», «ранен» или «убит».

Третий вариант означает, что корабль противника уничтожен. Если это случилось с первого хода, значит, он был однопалубным (состоящим из одной клетки), что можно назвать большой удачей. Если со второго (например, после Е7 игрок сказал Е6), значит, двухпалубный и т.д. После подбивания корабля, как и после ранения, игрок ходит до тех пор, пока не получит ответ «мимо».

4. Ход переходит от одного игрока к другому в случае промаха и задерживается у одного из противников в случае удачного попадания. Побеждает тот человек, кто первым найдёт и уничтожит все вражеские корабли.

Иные вариации

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

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

Например, можно добавить больше клеток в «поле боя» (не 10х10, а 20х20, допустим), после чего либо оставить количество кораблей, либо увеличить их. Можно усложнить задачу настолько, что все корабли, которые надо найти противнику - однопалубные. Можно сделать мины, при попадании на которые противник пропускает один ход. Вариантов масса, главное - знать во всём меру.

Заключение

Вот и всё, теперь вы познакомились с новой игрой и вам известны её правила. Вопрос «как играть в "Морской бой"» должен быть исчерпан. Отныне вам с приятелями будет чем заняться во время скучных уроков/лекций или на работе, если имеется возможность находиться недалеко друг от друга и писать на листах бумаги.

Вы играете в морской бой, но не всегда выигрываете? Тогда вам наверняка интересно узнать, как существенно повысить свои шансы на выигрыш, как правильно расставить корабли, как быстро уничтожить корабли противника и, конечно же, как выиграть в игре Морской бой !

Правила игры "Морской Бой"

Как выиграть в игре Морской Бой

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

В дальнейшем объяснении будут использоваться следующие обозначения:

Как стрелять по кораблям противника

Оптимальная стратегия стрельбы

Последовательность лучших ходов для начала игры

Если обратиться к математической теории, то можно построить карту вероятности размещения кораблей:

Исходя из этой карты, последовательность «лучших ходов» при постоянных промахах выглядит так (см. рисунок):

C1, J8, A8, H1, A4, J4, D10, G10, E1, D2, B3, A2, C9, B10, H9, I10, I7, J6, I5, H6, J2, I3, H4, G5, G2, F3, E4, B7, A6, B5, C6, C3, D4, D5, F6.

Как расставить корабли

Если не пробовали играть в Морской Бой, то скорее всего, вас забросили инопланетяне. Потому, что в списке дел русского школьника игра «Морской бой» помечена как «верное средство от скуки» и сегодня самое время убедиться!

Давайте научимся играть в «Морской бой» онлайн - на русском языке бесплатно и без регистрации. Вам даже не нужен соперник - сразитесь с компьютером! Начнём с основ.

Правила как играть в морской бой на листочке

Оригинальный Морской бой - классическая настольная игра на тактику и внимательность, где двум игрокам полагалось начертить на листике в клеточку 2 сетки 10×10 с буквами по горизонтали и цифрами по вертикали. Первая - поле для размещения своего флота из 10 кораблей так, чтобы не видел соперник. Вторая - план боя с отметкой ходов в сторону противника.

Флот состоит из:

1 «четырёхпалубный линкор»;
2 «трёхпалубных крейсера»;
3 «двухпалубных эсминца»;
4 «однопалубные лодки».

При расстановке обязательно учитывается расстояние в 1 клетку (корабли не должны соприкасаться ни бортами, ни кормами).

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

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

Как расставить корабли чтобы выиграть в Морской Бой

Самые уязвимые мишени - четырёхпалубные и трёхпалубные корабли, их просто выявить, если стрелять с интервалом в три клетки. Обычно их ставят далеко друг от друга, но в одной диагонали, под углом. Обойдите это правило - ставьте корабли кучнее - все крупные вертикально или горизонтально.

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

Старайтесь сократить площадь занятых участков и запутать противника - «на виду» размещайте самые маленькие корабли.

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

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

Готовы проверить, насколько действенный этот метод игры в Морской бой? Открывайте игру на весь экран и удачной битвы! Ждём ваших результатов в комментариях.

Управление

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

Для изменения положения в пространстве (разворота горизонтально или вертикально) - удерживайте Ctrl, пока кораблик вне сетки и только после этого кликайте и перетаскивайте.