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

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

    Правила игры


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



    Все перечисленные корабли должны быть размещены на квадратном поле 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. В комментариях абсолютно верно указывают, что на хабре уже были похожие публикации, было бы неверно не поставить ссылки на них:

    habrahabr.ru/post/82221
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 123
    • +4
      Спасибо, хоть и достаточно очевидно, но все равно интересно читать так хорошо формализованные и упорядоченные мысли:)
      В свое время я ради тренировки мозгов разрабатывал формализацию оптимальной стратегии игры для древней игрушки LINES, если помните такую. Постараюсь реанимировать свои труды и поделиться с Хабра аудиторией, раз не только я так «схожу с ума»:)
      • 0
        Такой контест уже был:
        community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=10101
        Если у вас есть логин на топкодере, можете скачать мое решение.
        • 0
          О, я был бы вам премного благодарен! Часто в обед запускаю Lines поиграть. Хотелось бы улучшить свои навыки игры, в особенности стратегию. Искал в интернете, результата — ноль. Если будет время — напишите, пожалуйста.
          • –2
            Думаете компьютер будет играть лучше вас? Моя программа играла лучше меня (но у меня и опыт игры нулевой), но точно хуже профессионалов.
        • –11
          Я думал что под катом увижу статью о том как автор написал реалтайм игру например на NodeJS еще с какими-нить обучающими раундами вначале перед реальным противником итд))
          но вообще лично для меня материал оказался интересен ибо не очень хорошо играю в данную игру(хотя в школе круто играл)
          • 0
            Чтобы не было недоразумений, изменил заголовок. Спасибо.
            • +2
              Спасибо за статью!

              Глупый вопрос, но все же. А были ли у вас фиаско с данной стратегией? К примеру, корабли расставлены параллельно. Противник может ведь догадаться о простоте расстановки крупных кораблей и быстро выпилить их (после попадания ведь можно продолжать стрелять?). А далее случайно попасть по паре катеров :)
              • 0
                В том-то и дело, что абсолютно не страшно потерять большие корабли, об этом вся статья. Но фиаско, конечно, случаются, но гораздо реже, чем раньше.
                • +1
                  Так может если не cтрашно потерять большие корабли — то не так уж и важно поскорее их найти. Ведь речь всего лишь о том, как минимизировать количество попаданий в околокарабельные клетки. Для этого не обязательно искать большие корабли. Можно например стрелять по соседним диагональным клеткам равномерно расширяясь от одной точки. При игре с компьютером с такой стратегией я выигрывают чаще, чем с предложенным вами подходом.
                  К тому же ценность поиска больших кораблей сильно снижается если противник их расставил плотно. Ведь проблема все равно будет в оставшемся свободном поле.

                  Кстати фраза Для поиска катеров оптимальной стратегии не существует, поэтому в конце игры приходится опираться в основном на удачу — не совсем верна. Такая стратегия есть. Несложно догадаться что если в конце игры остаются группы неисследованных клеток то выгоднее бить сначала по ним последовательно — потому что выбивая однопалубник в такой группе мы можем исследовать несколько дополнительных клеток. Если выбьем его в «дырке» то конечно ничего не выиграем. То есть определенный вред от «решета» в конце игры тоже имеется.
          • +12
            А нет ли у автора желания сделать серию постов? Есть еще такие замечательные игры, как «Точки» и «Крестики-нолики на бесконечном поле» — там пространство для исследований куда больше!:)
            • +4
              Вы прямо мысли мои читаете! Хотя крестики-нолики не так просты, как кажутся на первый взгляд. Думаю, обязательно напишу о них.
              • 0
                Для тех, кто играл в крестики-нолики (на бесконечном поле, конечно), они вряд ли кажутся простыми:)
                • +3
                  Вы на самом деле подтолкнули меня на написание поста о рэндзю. В конце-концов эти игры заслуживают популярности.
                  • 0
                    Про рендзю почитал бы с огромным удовольствием. Но вообще это ж древняя серьезная игра, там такие общие принципы много не дадут. Есть толстые книжки, в которых расписано как себя вести при каком дебюте, и все равно везде все очень неоднозначно.
                    • 0
                      На самом деле в рендзю многие дебюты заведомо проигрышны, поэтому там и вводится довольно сложный дебютный регламент.
                      • +1
                        Все-таки не «заведомо проигрышные», а дают преимущество одному из игроков. Давно не интересовался темой, но насколько я помню, только про один дебют в книге («звон камней» кажется) было написано, что черные выигрывают при любых действиях белых. И еще парочка дают существенное преимущество. Остальные вполне равноценные, и тут уже преимущество зависит от того, кто лучше знает, как правильно разыгрывать такой дебют, но все равно это преимущество ничуть не гарантирует победу.
                        А статью жду с нетерпением)
              • –1
                На мой взгляд, вряд ли к этому есть еще что добавить :)
                • 0
                  На ваш взгляд, 3х3 — это бесконечное поле?
                  • 0
                    Мда. Что-то я самую суть проглядел :)
              • –17
                Играя в морской бой, применял чит, позволяющий выигрывать при игре с любым противником :)

                Суть была в том, что во время расстановки кораблей, сделать вид, что рисуешь, но на деле придумать и запомнить расположение кораблей, а во время игры отслеживать, если какой то корабль был обнаружен выстрелом противника, то либо найти ему новое место, если такое возможно, либо поставить под удар корабль наименьшего размера. Кроме поднятия ЧСВ, прокачивался скил памяти.
                • +41
                  Ваш чит на самом деле ужасно неэффективен. Особенно в той части, где вы подставляете корабль меньшего размера. Если уж читерить, то надо рисовать честно все корабли, кроме последнего катера.
                  • +1
                    Возможно, но он позволял выходить из игры практически без потерь. Нарисовать все, кроме одного — это было начало.
                    • +2
                      > Если уж читерить, то надо рисовать честно все корабли, кроме последнего катера.
                      После нескольких таких игр и подозрений чит контрится просьбой убрать в сторону ручку и сфотографировать расположение кораблей, а после боя сравнить :P
                      • +8
                        Думаю, что многие присутствующие играли в морской бой, когда вот так быстренько «сфотографировать расположение» еще было сильно затруднительно :)
                        • +7
                          Попросить нарисовать в двух экземплярах, а второй отложить. После такой просьбы счет быстро выравнивается :)
                        • +5
                          Зачем такие сложности? Забрать ручку и дать карандаш ;)
                      • +29
                        С удивлением открыл для себя, что кто-то читерит в морской бой. Это ж как надо не верить в себя-то.
                        • 0
                          Блин, у меня тоже глаза открылись…
                        • +7
                          Дешевое у вас ЧСВ, если вы его только читами поднимать можете.
                          • –1
                            Это были суровые девяностые, мы развлекались как могли… Тупо играть в одно и тоже быстро надоедало, где узнать о новых играх мы тогда не знали, поэтому придумывать читы и модификации к имеющимся играм. В ответ на читы придумывались различие античиты (судьи, дублирование досок, различные цвета ручек), которые, в свою очередь, тоже обходились. И это было действительно интересно.
                        • –22
                          Самая оптимальная стратегия расстановки кораблей — до самого конца игры не выставлять на поле крайний однопалубник, и только в случае когда остается ода клетка — выставлять его туда.
                          • +24
                            Не тот ли это случай, когда вместо «крайний» как раз следует написать «последний», пусть даже вы и парашютист/моряк/кто-еще-там-использует-крайний-вместо-последний?
                            • –26
                              Вообще этот контекст не меняется, последний в значении последний в жизни. А это игра, будет новая игра, будут новые корабли.
                              • +2
                                В мире, который нарисован на листке бумаги, новых кораблей не будет, т.к. мир будет уничтожен вскоре после игры (не суть важно, если вы будете хранить листок — по космическим меркам он сгниет и распадется на атомы вмиг).
                          • +21
                            Это бред. Точно так же про многие компьютерные игры можно сказать, что оптимальная стратегия для них — использовать ArtMoney. Мы же тут про алгоритмы говорим, а не про мелкое жульничество.
                            • –21
                              Что именно бред? Это алгоритм? Алгоритм. Оптимальный? Оптимальный.

                              Если играть для фана — то и вышеприведенный алгоритм использовать не стоит.
                              • +8
                                Следование этому алгоритму приведет не к выигрышу в игре, а к нарушению правил, незаметному для второго игрока. Нас же интересуют алгоритмы для выигрыша в игре.
                                • 0
                                  Кстати да. Это как сказать:

                                  Оптимальный алгоритм игры в морской бой — отравить соперника.
                                  • 0
                                    Отравить соперника — это не алгоритм, а план, еси чо. А так молодец, ага.
                                • +1
                                  Оптимальность этого алгоритма стоит рассматривать исходя из теории игр, а не исходя из правил игры в морской бой. Все не так однозначно получается, однако.
                                  • 0
                                    А как получается?
                                    Расчет осилите? Теоретически у нас должна быть взвесь из стратегий, поскольку неполная информация.
                                    Но не будут ли другие стратегии иметь нулевые веса за счет повышенной жизни однотрубников?
                                    Перебрать _ВСЕ_ возможные стратегии это чуть ли не ситуация с шахматами, но перебрать парочку самых очевидных — относительно реально. Хотя я не осилю.
                              • +10
                                Можно просто дать в глаз сопернику и признать себя победителем. Этот алгроритм еще эффективнее.
                                А чтобы защититься от вашего при игре на бумаже — достаточно после расстановки кораблей поменяться ручками.
                                • +2
                                  Это же гениально, про ручки, как я сам не додумался!
                              • +5
                                У меня дежа вю. http://habrahabr.ru/post/82221/
                                • +1
                                  Вот что значит не делать поиск по хабру перед публикацией. Добавил ссылку в статью.
                                  • 0
                                    Как говаривал один известный персонаж одного известного российского фильма: «Сходство мыслей возможно, но плагиат — никогда!»:)
                                    • 0
                                      Вот-вот. В книге-то третьей расстановки кораблей не было ))

                                      Да и вариантов прострела в оригинале 8, а у Вас 7. ))
                                  • +12
                                    Теперь при игре с опытным противником я буду всегда искать большие корабли по границам поля.
                                    • +2
                                      Вам это мало что даст. Как выше уже сказали, большие корабли очень уязвимы и попадание по ним — дело начальных «выстрелов». Главное — минимизировать ущерб от их обнаружения.
                                    • +5
                                      Для поиска катеров оптимальной стратегии не существует, поэтому в конце игры приходится опираться в основном на удачу.


                                      Спорное утверждение. Если катеров осталось больше одного, то, подбив один из них, мы закрываем ещё и все неизвестные клетки, соседние с ним. Так что выгоднее стрелять в клетку, у которой больше незакрытых соседей.
                                      С другой стороны, если противник тоже это знает, то ему выгоднее ставить катера на «невыгодные» клетки, а значит, и нам следовало бы стрелять по ним… Я как-то пробовал рассчитать оптимальную стратегию за обоих игроков для простейших случаев (поле 1x5, два катера) — но не хватило терпения.
                                      • +1
                                        Совершенно точно видел этот алгоритм в какой-то книге, прочитанной в первой половине 90-х. Но ценности статьи это нимало не уменьшает
                                        • +1
                                          Вообще-то до него собственным умом доходит каждый школьник через неделю-две игры на уроках… После чего играть становится неинтересно.
                                          • 0
                                            Ну, я тогда был в более нежном возрасте. Отсюда пошла моя любовь к спойлерам итд.
                                          • +5
                                            image
                                            Е. Я. Гик «Занимательные математические игры»
                                            У меня до сих пор сохранилась, тоже про неё вспомнил.
                                            • +12
                                              Фамилия автора книги хороша!
                                          • –14
                                            Первый раз вижу чтобы играли в морской бой прямыми кораблями. Всю жизнь играл по правилам в которых можно было загибать корабли.
                                            • +6
                                              У нас в школе за такое можно было по мордасам схлопотать, как за жульничество (в том возрасте мы все легко лезли в драку).
                                              • +1
                                                А за что так жёстко минусуют Magnum72? Ну, я тоже когда был маленький играл в основном в морской бой с угловыми кораблями. По мордастам не хлопотал — отец вряд ли бы меня стал бить за такое :)
                                                • +4
                                                  Я думаю очень многие сталкивались с теми, кто загибал корабли, ставил их впритык, и вообще всячески отличался по правилам :) Теперь вот мстят за прошлые обиды :)
                                                • +1
                                                  За что по «мордасам»? Это было разрешено нашими правилами, впритык ставить и углами соприкасать было нельзя, зато играть было интересней.
                                                  • +2
                                                    Я не минусовал, но думаю, что людям не понравился оффтоп. Правила можно менять как душе угодно, только потом не нужно говорить, что вы играете в «морской бой». Или кто-то часто в морях наблюдает Г-образные корабли?
                                                • +5
                                                  Загибать. Корабли. Ага.

                                                  • +1
                                                    Морской камуфляж.
                                                    • 0
                                                      Угадали. Камуфляж времён Первой Мировой для затрудруднения прицеливания торпедистам с немецких подлодок. Кроме чёрно-белого был еще и «весёленьких» цветов:

                                                      Источник
                                                • 0
                                                  Из первого правила сразу вытекает второе: если вам удалось подбить вражеский корабль, необходимо сразу же его добить, чтобы как можно раньше получить список гарантировано свободных клеток.
                                                  Это если не считать вероятности. Например, если шибанули в угол, а так кусок корабля, то в одной из двух клеток, с вероятностью ¹⁄₂ есть его продолжение, так зачем тратить ход на уточнение? Можно пока пострелять в другое место, а тут разобраться потом.
                                                  • 0
                                                    После того как корабль был «ранен» или «убит» стрелявший получает внеочередной ход. Так что разницы нет, когда добивать. Выигрыша от выстрела куда-то еще нет.
                                                    • 0
                                                      А, я позабыл это, давно не играл :)
                                                    • 0
                                                      Боюсь, вы всё-таки недопоняли статью. Вся суть в том, что добивание корабля оказывается гораздо эффективнее. Представим, что в углу двухпалубник, тогда за два хода (максимум) вы дополнительно проверите 3 клетки.
                                                      • 0
                                                        Дело не в этом. Мне тут коментарием выше напомнили правило о котором я позабыл.
                                                    • 0
                                                      У меня несколько раз при такой стратегии все корабли оставались целыми.
                                                      • –2
                                                        то знает, кем бы она работала, если бы в своё время слушала лекции?

                                                        А какие у нас лекции слушать? Я думаю что у все таких примеров просто вагон:
                                                        Два парня учатся в университете. Один балду пинает, другой прилежно учится. Вопрос, это что то гарантирует по устройству в жизни?

                                                        В универах обучают:
                                                        a) устаревшей никому не нужной информации (разве что интререс с точки зрения истории)
                                                        б) нельзя научить можно научится. Нет интереса, будет пиво. Какой интерес если преподаватели нищие, уже какой к ним интерес может быть.
                                                        в) Наша новая кафедра, где мы первый раз выпускались, оказалось просто попилам бабла и диплом я сдвавал секретарше. Я в обиде после этого. Насколько я тогда был тупой до ужаса и то ходил как «хакер» самоутверждался.
                                                        Но, бессомнения были преподаватели, которые вызывали уважение. Были и те кто работал за идею.

                                                        А были и те, кто просил меня помочь ему мозгами в визуальной части этой работы:
                                                        cyberleninka.ru/article/n/modelirovanie-protsessa-sverhplasticheskoy-formovki-poloy-obolochki-iz-listovoy-zagotovki
                                                        Преподаватель не мог кодить интрефейс и ядро, он был просто не в потоке жизни и жил в своей изолированной среде, про открытые библиотеки он знять не знал. Я ему старался помочь с визуальным отображением его данных через rhinoceros. Он просил притока новых мозгов ибо ощущал в этом большую проблему.

                                                        А потом, за то что он не захотел нищенствовать, а количество дебилов в визуах не остановить, взял с кого то деньги и попал на 4 года и 6 месяцев за взятку в 60 тр. Даю подсказку, как будто там он один брал взятки с дебилов.
                                                        newstula.ru/fullnews_29130.html
                                                        Не мне его судить, это его дело, но если бы на этом все закончилось:
                                                        mk.tula.ru/news/n/1551/

                                                        Для меня университет важен исключительно развитием у человека момента стрессового погружения в размышления. Пики экзаменационных напрягов,, подготовка к сессии — это знакомство человека с глубинами своих возможностей. Знакомством со своей головой. Поэтому до сих пор без них никуда, хоть на сегодня там такой бардак.
                                                        • +1
                                                          Простите, я конечно всё понимаю, хороший преподаватель и всё такое, но «все берут взятки и он взял» — херовое оправдание. Закон нарушать нельзя, сколько бы людей вокруг тебя его не нарушали.
                                                          • 0
                                                            Оправдание херовое, согласен, только здесь важно смотреть на тех кто говорит «Ага! попался взяточник! Так вот кто у нас коррупцию разводит! Лови его!». Взял — отвечать надо, только это используется как показуха. Через год суд с ректором.
                                                          • +1
                                                            Получается, что выгоднее на лекциях таки в М.Б. играть. Или еще во что-то. Или прогуливать их…

                                                            Тем самым усиливаем стрессовое погружение в размышления под сессию. :)

                                                            P.S.… а если официантке топикстартер просто понравился? Читай — искала способ обратить на себя внимание )
                                                            • 0
                                                              «Или прогуливать их… » — не значит напрягаться потом) Сидят студенты, пишут конспекты. Тонны бумаги. Слушают лектора.
                                                              Покажите мне хоть одного студента кто):

                                                              а) достает тетрадь после сессии хоть раз в жизни если вообще вспоминает о ней.
                                                              б) Кто то там что-то запоминает когда пишет. Якобы механическая память.

                                                              Студенты пишут лекции, а лекторы это читают, это некий протокол обмена информацией. Рот-уши-ручка. Полудуплексный.
                                                              Это некая сделка, вот, ваши знания в тетрадях, вы их поимели они ваши. Вы их отработали. А раз мы их поимели и они наши, то мы их складируем на полку. Ну они наши. зачем о них вспоминать?
                                                              • +1
                                                                Да вот, не так давно попалось на глаза

                                                                www.ted.com/talks/lang/ru/ramsey_musallam_3_rules_to_spark_learning.html

                                                                Еще бы кто у нас в ВУЗах в этом разбирался…
                                                                • 0
                                                                  Интерес к любой «ерунде» можно передать или даже заразить, если преподаватель сам чекнутый на этой теме и чувствует тайну в этом предмете, взахлеб о ней рассказывает. А рутина никому не интересна.) Будет тайна — будет кайф.
                                                                  Наука от женщины тут не отличается. Есть в ней тайна, будет вечная любовь. Тайны нет, будем менять по очереди жен — потреблять.
                                                                  • 0
                                                                    чувствует тайну в этом предмете, взахлеб о ней рассказывает.

                                                                    Это я про Селедкина как раз говорил.
                                                                • 0
                                                                  a) Перед подготовкой к госэкзамену вполне нормальная практика — пройтись по конспектам на нужные темы. Редко, но бывает, что там написано понятнее, чем в учебнике.
                                                                  б) Если лекции читал и записывал, то к коллоквиуму иногда (в 10-20% случаев) можно подготовиться, вообще не открывая ни учебника, ни лекций. Проверено. Если лекции не записывать (и вообще на них не ходить), то это заметно сложнее.
                                                                  • 0
                                                                    Ну вот вы и описали что сдаете всего один предмет под названием «память». Есть память, получай пятерку. Нету ее… два. Понял не понял. Кого это волнует) Понятые вещи никогда не забываются)
                                                                    • +3
                                                                      Насчёт «никогда» — теперь уже не уверен. Только что дочка спросила про разложение оператора на ортогональный и симметричный — сходу вспомнить не удалось, хотя в своё время хорошо это понимал и мог вывести с нуля. И ведь учил всего 28 лет назад.
                                                                      А про «предмет под названием память» — сами сначала спрашиваете, кто запоминает лекции, когда их записывает, а потом, когда говорят, что такие есть — тыкаете в это носом? Хороший приём, практически непробиваемый.
                                                                      • 0
                                                                        Можно только выразить глубокое уважение вашей семье, мне тут добавить нечего. Я надеюсь что все же смог донести мысль.

                                                            • 0
                                                              Автор, ну йомайо — «Все перечисленные корабли должны быть размещены на квадратном поле 10 на 10 клеток» — КАК располагаться?
                                                              Вертикально/горизонтально/по диагонали?
                                                              В одну линию/палюбас?

                                                              Я встречал правила «только вертикально/горизонтально», «только в одну линию», «как попало, но чтобы квадраты соприкасались сторонами», «как угодно, но чтобы квадраты соприкасались».

                                                              Клянусь.
                                                              • +1
                                                                «Значит, при размещении корабли надо ставить таким образом, чтобы в случае их потери минимизировать количество гарантировано свободных клеток»

                                                                Я когда-то маленьким в больнице (делать было нечего) играл в МБ и интуитивно выбрал именно эту стратегию — рассовать по углам и краям.
                                                                Эта стратегия была вычислена противником (тоже первоклашкой) примерно на 6..10-м ходу.
                                                                И я был мгновенно побит :-)
                                                                • +5
                                                                  Есть еще один алгоритм — работает на людях с ручками и бумажками: называется клетка, в уме стартует быстрый счет, в случае промаха в клетку записывается состояние счетчика на момент ответа противника. После первоначального прострела карты расстреливаются точки, соседствующие с наибольшими цифрами счетчиков.
                                                                  Смысл — если клетка рядом с кораблем, человек, прежде чем ответить, проверяет правильность ответа и на это тратится немножко больше времени.
                                                                  • 0
                                                                    «Каждая из приведённых расстановок оставляет для катеров ровно 60 свободных клеток»
                                                                    Если стратегия вычислена — то надо сделать 1..4 выстрела (по углам) — и дальше дело упрощается.
                                                                    • 0
                                                                      Можно еще нацепить гуглеочки и трассировать зрачки :-)
                                                                      • +1
                                                                        Это уже покер.
                                                                      • 0
                                                                        При этом всём надо как-то так расставить корабли, чтобы противник не догадался о методе и не применил его сам в следующей игре
                                                                        • +1
                                                                          А у меня всегда была тактика, делать выстрел так, чтобы в случае попадания «закрывалось» как можно больше неизвестных клеток, то есть я старался стрелять в центр наименее заполненных квадратиков 3х3.
                                                                          • 0
                                                                            На поле 1x4 с двумя кораблями 1x1 эта стратегия будет проигрышной. В случае промаха может потребоваться три хода, а если первый ход делать в угол, то всегда можно уложиться в два (со средним значением 5/3 хода).
                                                                            • 0
                                                                              Естественно, это не универсальная стратегия, а дополнительный фактор, чтобы выбрать куда стрелять из многих вариантов, эквивалентных по другим, более важным признакам.
                                                                          • 0
                                                                            Стратегия, близкая к оптимальной — стрелять в клетку, которая занята с наибольшей вероятностью (т.е. в наибольшем числе конфигураций, не противоречащих полученной информации). Она будет хорошо работать, даже когда разрешено читерство. Вот только пользоваться ей в реальном времени довольно сложно…
                                                                            • +3
                                                                              Минус расположения своих кораблей вплотную к краям поля: если такой корабль ранен, то вероятность ошибки при добивании уменьшается.
                                                                              • +2
                                                                                Этот минус нивелируется гораздо большей пользой от простора для одноклеточных кораблей.
                                                                              • 0
                                                                                Есть небольшая оптимизация правил, которая нивелирует выигрыш от такой расстановки кораблей, при этом стратегия для победы остается той же — стрельба залпами, количество залпов = количеству оставшихся типов кораблей. Т.е. сначала — 4 выстрела, после потери линкора — 3 выстрела, после потери всех 3х/2х1-палубников убирается по одному выстрелу.
                                                                                • 0
                                                                                  Видел на спектруме такую версию — большое поле (30*30, кажется), но количество выстрелов за ход равно количеству живых клеточек на кораблях.
                                                                                • +2
                                                                                  В статье много важных для понимания фактов, но называть это оптимальной стратегией я бы не решился. Во-первых очень много ни чем не обоснованных допущений. А во вторых, автор постоянно упирается в максимизацию количества «проверенных клеток». Это тоже самое, что называть оптимальным алгоритмом для игры в шахматы тот, в котором мы постоянно пытаемся покрыть своими фигурами максимальное количество позиций, что очевидно, неверно. Короче, в карму — плюс, за статью — минус.
                                                                                  • +1
                                                                                    Стратегия как выиграть же «разбита» на две части, — как подбить противника, и как не быть подбитым самому.

                                                                                    А теперь немного теории (игр).

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

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

                                                                                    То есть данный алгоритм — это максимизация конечной величины через максимизацию дельт каждого шага.
                                                                                    • +1
                                                                                      Ошибся с тем, что морской бой — пошаговая игра (тем более тогда сравнение с шахматами некорректно), каюсь, так как на момент расстановки кораблей — игра идёт одновременно, плюс обычно для пошаговых игр расстановка сил заранее известна. Однако все рассуждения в предыдущем комменте про морской бой (кроме примера с деревом где я поспешил изложить мысли) в силе.

                                                                                      Кстати, в теории игр есть и решение для игр, где одновременно принимается решение. Называется «проникновением в замыслы соперника». Максимизируется собственный выигрыш исходя из возможных выборов соперника, путем выбора доминирующей стратегии (хода). Доминирующая та, когда выигрыш максимален при любом из ходов соперника. Доминирующая (как и доминируемая) стратегии не всегда существуют, но в данном посте приведен пример стратегии, которая доминирует, или по-крайней мере, не проигрывает ходам соперника (при расстановке кораблей).

                                                                                      Более того, стратегия «максимизировать количество известных клеток» также соответствует тому, что веса у кораблей разные, то есть при одинаковой силе их подбить по-разному сложно. Известные клетки снижают количество ходов, тем самым, снижая возможность проигрыша. Однако повторюсь, что количество шагов здесь наименьшее, следует доказывать математически.
                                                                                      • +1
                                                                                        Наименьшим оно не будет. В лучшем случае можно доказать, что меньшее матожидание по сравнению с другими (известными) стратегиями.
                                                                                • +9
                                                                                  Я-то думал, что в статье будет серьезное исследование с применением теории игр, ну или на худой конец просчитаны вероятности различных исходов при различных стратегиях игры. А тут — такая банальщина, как «сначала подбейте линкор»… Спасибо, кэп.
                                                                                  • 0
                                                                                    По поводу расстановки ИМХО лучше более случайно ставить корабли, чем прижимая их в какую-ту сторону, противник может понять что все корабли в том, нужном углу и атаковать только туда.
                                                                                    • +1
                                                                                      Да, но ведь ставка именно на то, что попасть в катера (1х1) крайне тяжело.
                                                                                      • –1
                                                                                        Это спорно, можно перебить быстро основу и стрелять по катерам. Я думаю нужно на практике попробовать.
                                                                                      • 0
                                                                                        В «морском бое» самые сильные фигуры — одноклеточные корабли, несмотря на то, что жизненный опыт подсказывает что самый большой корабль — самый сильный. Грубо говоря, одноклеточные корабли — это ферзи морского боя. Сдавая «многоклеточные пешки», вы освобождаете простор для наиболее сильных фигур.
                                                                                        • +1
                                                                                          жизненный опыт подсказывает что самый большой корабль — самый сильный.

                                                                                          Линкоры перестали строить как раз потому что жизненный опыт показал обратное. Здоровая и дорогая дура тонет от меньших и дешевших эсминцев или подлодок, а то и вообще от торпедных или ракетных катеров.
                                                                                          • 0
                                                                                            Таки опыт такого не показывал) Линкоры пропали после появления авианосцев, сопоставимых по размеру. С меньшими эсминцами и всем остальным они вполне справлялись, а ракетных катеров тогда ещё не было.
                                                                                        • 0
                                                                                          В общем-то, если начать с угла, то за каждый ход можно будет вынести как минимум по ряду кораблей, ориентируясь на подсказки «ранен … ранен … убит (пропускаем клетку) … ранен … убит (пропускаем клетку)» и т. д.

                                                                                          То есть, в самом эффективном по мнению автора случае противник может вынести всё, кроме катеров, за 0 ходов. Довольно неплохая экономия для противника. (Хотя, на самом деле, эффект от этого только психологический — оба игрока к концу игры сберегут поровну ходов в результате убийства кораблей.)
                                                                                          • 0
                                                                                            За 0 в лучшем случае. В некоторых схемах два угла свободные и только с третьего хода нащупаешь.

                                                                                            И эффект не только психологический обычно. При случайной схеме расположения у противника будет какое-то количество зря сделанных выстрелов, не в смысле промахов вообще, а в смысле «попаданий» в клетку, где корабля быть не может. Самый простой пример — первым выстрелом ранил двухтрубник в центре, но убить его можно в этот же ход, а можно три раза промахнуться (в среднем два промаха), не угадав направление.
                                                                                        • +1
                                                                                          В детстве я и дед играли в морской бой против компьютера.
                                                                                          Компьютер был читером — программисту было лень писать алгоритм «добивания» и после первого попадания в корабль он его всегда добивал.
                                                                                          Интуивно выработали алгоритм расстановки кораблей по краям карты, и накрытие поля сеткой. Но мы пропускали одну клетку, мысль про то, что нужно сначала найти линкор до нас не дошла :-(
                                                                                          • –1
                                                                                            У нас в университете за слово «оптимальный» баз постановки задачи оптимизации сразу на пересдачу отправляли. На самом деле здесь приведены просто эвристические наблюдения, возможно, приводящие к победе с бОльшей вероятностью, чем игра наугад, но, как мне кажется, не с максимально возможной вероятностью.
                                                                                            • 0
                                                                                              А за слово «кажется» в чисто технических вопросах, что в вашем университете делали? Если серьёзно, я с удовольствием почитаю о вашем варианте стратегии.
                                                                                              • 0
                                                                                                Без обид — я имел ввиду, конечно, что заявление об оптимальности не может быть истинным пока не поставлена и не решена задача оптимизации. Опять же, нужно делать предположения об оппоненте — играет ли он наугад или же, зная вашу стратегию, специально подстраивается под неё. Немного погуглив нашёл ответ, хоть как-то затрагивающий теорию вероятностей: otvety.google.ru/otvety/thread?tid=4c354bc83317c41f&pli=1. Конечно, это далеко от идеала, но уже что-то. Конечно, для вероятность ещё можно посчитать практическим путём — написать программу, которая играет сама с собой разными методами и найти наиболее выигрышный из них (но опять же не факт что это будет оптимальным решением задачи).
                                                                                                К сожалению, не обладаю сейчас свободным временем для исследования, но думаю запишу куда-нибудь, если появится время — подумаю.
                                                                                          • 0
                                                                                            Некоторое время назад от безделья поиграл в онлайн морской бой на телефоне. В отличии от классического варианта, в нем были корабли трех видов: один из 4х клеток, два из 3х и четыре из 2х. Кроме того, изначально каждый игрок осуществляет 5 выстрелов за ход, и это число сокращается на единицу c каждым погибшим кораблем (не опускается ниже 1).

                                                                                            Вот небольшая статистика из ~60 партий.

                                                                                            1) Расстановка кораблей противником (число в ячейке – количество партий, в которых соперник разместил на этой клетке один из кораблей)


                                                                                            В целом, люди видят выгоду в размещении кораблей вдоль стенок.

                                                                                            2) Атака противника (число в ячейке – количество партий, в которых соперник не выстрелил в эту клетку, при этом не обстрелянные клетки, которые в финале партии были очевидно свободны, в расчет не идут)


                                                                                            Конкретных цифр у меня нет, но при выстраивании своих кораблей и выборе ячеек для атаки с учетом собранной информации, процент выигранных партий увеличился.
                                                                                            • 0
                                                                                              А никто не знает где бы онлайн поиграть в морской бой?
                                                                                            • 0
                                                                                              А я думал, каждый, кто играл хоть раз в морской бой, знает это.
                                                                                              • +2
                                                                                                Реализовал 4 алгоритма:
                                                                                                Random — полностью случайный
                                                                                                Diagonal — простреливающий поле по диагональным линиям, сначала в поиске «четверок», потом — «трёшек» и «двушек». Порядок обстрела точек на линиях каждого ранга — случайный.
                                                                                                NShips — подсчитывается количество способов, которыми ещё не подбитые корабли можно разместить на данную клетку (с учётом количества кораблей каждого размера), выстрел делается в одну из клеток, для которых это количество максимально.
                                                                                                NConfig — рассматриваются все расположения кораблей, не противоречащие имеющейся информации, и выстрел делается в одну из клеток, которые заняты в наибольшем числе конфигураций.
                                                                                                Чтобы NConfig работал разумное время, был взят сокращенный вариант: поле 8*8, 4 катера и по одному кораблю размерами 2, 3 и 4 клетки.
                                                                                                На некотором множестве конфигураций запускался каждый из алгоритмов. Подсчитывалось среднее число ходов, а также число побед (конфигураций, в которых данному алгоритму потребовалось меньше ходов, чем другим).

                                                                                                Сначала проверил их на 200 случайных расстановках кораблей. Результат:
                                                                                                Random — среднее число ходов 24.82, 50 побед
                                                                                                Diagonal — среднее число ходов 24.08, 46 побед
                                                                                                NShip — среднее число ходов 23.64, 56 побед
                                                                                                NConfig — среднее число ходов 23.63, 48 побед

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

                                                                                                Потом взял конфигурации, в которых длинные корабли «прижимались» к стенкам или к другим кораблям. Алгоритмы об этом, понятное дело, не знали.
                                                                                                Итог по 300 конфигурациям:

                                                                                                Random — среднее число ходов 28.78, 62 победы
                                                                                                Diagonal — среднее число ходов 28.39, 65 побед
                                                                                                NShip — среднее число ходов 30.34, 51 победа
                                                                                                NConfig — среднее число ходов 25.66, 122 победы

                                                                                                Причина простая — алгоритм NShip старается стрелять в центр поля, там способов расставить корабль больше. А NConfig, наоборот, бьёт по краям — оказывается, в среднем корабли там размещаются чаще (это понятно: после того, как мы подобьём корабль у стенки, он заберёт меньше клеток у поля, а на оставшемся месте будет больше вариантов размещения кораблей).

                                                                                                Итого: диагональный алгоритм выиграл у полностью случайного от 0.4 до 0.75 хода. Расстановка кораблей у стенок позволила выиграть около 2 ходов (при том, что среднее квадратичное отклонение числа ходов во всех случаях было от 4.5 до 5.5).

                                                                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.