Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 124
Спасибо, хоть и достаточно очевидно, но все равно интересно читать так хорошо формализованные и упорядоченные мысли:)
В свое время я ради тренировки мозгов разрабатывал формализацию оптимальной стратегии игры для древней игрушки LINES, если помните такую. Постараюсь реанимировать свои труды и поделиться с Хабра аудиторией, раз не только я так «схожу с ума»:)
В свое время я ради тренировки мозгов разрабатывал формализацию оптимальной стратегии игры для древней игрушки LINES, если помните такую. Постараюсь реанимировать свои труды и поделиться с Хабра аудиторией, раз не только я так «схожу с ума»:)
Такой контест уже был:
community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=10101
Если у вас есть логин на топкодере, можете скачать мое решение.
community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=10101
Если у вас есть логин на топкодере, можете скачать мое решение.
О, я был бы вам премного благодарен! Часто в обед запускаю Lines поиграть. Хотелось бы улучшить свои навыки игры, в особенности стратегию. Искал в интернете, результата — ноль. Если будет время — напишите, пожалуйста.
Я думал что под катом увижу статью о том как автор написал реалтайм игру например на NodeJS еще с какими-нить обучающими раундами вначале перед реальным противником итд))
но вообще лично для меня материал оказался интересен ибо не очень хорошо играю в данную игру(хотя в школе круто играл)
но вообще лично для меня материал оказался интересен ибо не очень хорошо играю в данную игру(хотя в школе круто играл)
Чтобы не было недоразумений, изменил заголовок. Спасибо.
Спасибо за статью!
Глупый вопрос, но все же. А были ли у вас фиаско с данной стратегией? К примеру, корабли расставлены параллельно. Противник может ведь догадаться о простоте расстановки крупных кораблей и быстро выпилить их (после попадания ведь можно продолжать стрелять?). А далее случайно попасть по паре катеров :)
Глупый вопрос, но все же. А были ли у вас фиаско с данной стратегией? К примеру, корабли расставлены параллельно. Противник может ведь догадаться о простоте расстановки крупных кораблей и быстро выпилить их (после попадания ведь можно продолжать стрелять?). А далее случайно попасть по паре катеров :)
В том-то и дело, что абсолютно не страшно потерять большие корабли, об этом вся статья. Но фиаско, конечно, случаются, но гораздо реже, чем раньше.
Так может если не cтрашно потерять большие корабли — то не так уж и важно поскорее их найти. Ведь речь всего лишь о том, как минимизировать количество попаданий в околокарабельные клетки. Для этого не обязательно искать большие корабли. Можно например стрелять по соседним диагональным клеткам равномерно расширяясь от одной точки. При игре с компьютером с такой стратегией я выигрывают чаще, чем с предложенным вами подходом.
К тому же ценность поиска больших кораблей сильно снижается если противник их расставил плотно. Ведь проблема все равно будет в оставшемся свободном поле.
Кстати фраза Для поиска катеров оптимальной стратегии не существует, поэтому в конце игры приходится опираться в основном на удачу — не совсем верна. Такая стратегия есть. Несложно догадаться что если в конце игры остаются группы неисследованных клеток то выгоднее бить сначала по ним последовательно — потому что выбивая однопалубник в такой группе мы можем исследовать несколько дополнительных клеток. Если выбьем его в «дырке» то конечно ничего не выиграем. То есть определенный вред от «решета» в конце игры тоже имеется.
К тому же ценность поиска больших кораблей сильно снижается если противник их расставил плотно. Ведь проблема все равно будет в оставшемся свободном поле.
Кстати фраза Для поиска катеров оптимальной стратегии не существует, поэтому в конце игры приходится опираться в основном на удачу — не совсем верна. Такая стратегия есть. Несложно догадаться что если в конце игры остаются группы неисследованных клеток то выгоднее бить сначала по ним последовательно — потому что выбивая однопалубник в такой группе мы можем исследовать несколько дополнительных клеток. Если выбьем его в «дырке» то конечно ничего не выиграем. То есть определенный вред от «решета» в конце игры тоже имеется.
А нет ли у автора желания сделать серию постов? Есть еще такие замечательные игры, как «Точки» и «Крестики-нолики на бесконечном поле» — там пространство для исследований куда больше!:)
Вы прямо мысли мои читаете! Хотя крестики-нолики не так просты, как кажутся на первый взгляд. Думаю, обязательно напишу о них.
Для тех, кто играл в крестики-нолики (на бесконечном поле, конечно), они вряд ли кажутся простыми:)
Вы на самом деле подтолкнули меня на написание поста о рэндзю. В конце-концов эти игры заслуживают популярности.
Про рендзю почитал бы с огромным удовольствием. Но вообще это ж древняя серьезная игра, там такие общие принципы много не дадут. Есть толстые книжки, в которых расписано как себя вести при каком дебюте, и все равно везде все очень неоднозначно.
На самом деле в рендзю многие дебюты заведомо проигрышны, поэтому там и вводится довольно сложный дебютный регламент.
Все-таки не «заведомо проигрышные», а дают преимущество одному из игроков. Давно не интересовался темой, но насколько я помню, только про один дебют в книге («звон камней» кажется) было написано, что черные выигрывают при любых действиях белых. И еще парочка дают существенное преимущество. Остальные вполне равноценные, и тут уже преимущество зависит от того, кто лучше знает, как правильно разыгрывать такой дебют, но все равно это преимущество ничуть не гарантирует победу.
А статью жду с нетерпением)
А статью жду с нетерпением)
На мой взгляд, вряд ли к этому есть еще что добавить :)
Играя в морской бой, применял чит, позволяющий выигрывать при игре с любым противником :)
Суть была в том, что во время расстановки кораблей, сделать вид, что рисуешь, но на деле придумать и запомнить расположение кораблей, а во время игры отслеживать, если какой то корабль был обнаружен выстрелом противника, то либо найти ему новое место, если такое возможно, либо поставить под удар корабль наименьшего размера. Кроме поднятия ЧСВ, прокачивался скил памяти.
Суть была в том, что во время расстановки кораблей, сделать вид, что рисуешь, но на деле придумать и запомнить расположение кораблей, а во время игры отслеживать, если какой то корабль был обнаружен выстрелом противника, то либо найти ему новое место, если такое возможно, либо поставить под удар корабль наименьшего размера. Кроме поднятия ЧСВ, прокачивался скил памяти.
Ваш чит на самом деле ужасно неэффективен. Особенно в той части, где вы подставляете корабль меньшего размера. Если уж читерить, то надо рисовать честно все корабли, кроме последнего катера.
Возможно, но он позволял выходить из игры практически без потерь. Нарисовать все, кроме одного — это было начало.
> Если уж читерить, то надо рисовать честно все корабли, кроме последнего катера.
После нескольких таких игр и подозрений чит контрится просьбой убрать в сторону ручку и сфотографировать расположение кораблей, а после боя сравнить :P
После нескольких таких игр и подозрений чит контрится просьбой убрать в сторону ручку и сфотографировать расположение кораблей, а после боя сравнить :P
С удивлением открыл для себя, что кто-то читерит в морской бой. Это ж как надо не верить в себя-то.
Дешевое у вас ЧСВ, если вы его только читами поднимать можете.
Это были суровые девяностые, мы развлекались как могли… Тупо играть в одно и тоже быстро надоедало, где узнать о новых играх мы тогда не знали, поэтому придумывать читы и модификации к имеющимся играм. В ответ на читы придумывались различие античиты (судьи, дублирование досок, различные цвета ручек), которые, в свою очередь, тоже обходились. И это было действительно интересно.
Самая оптимальная стратегия расстановки кораблей — до самого конца игры не выставлять на поле крайний однопалубник, и только в случае когда остается ода клетка — выставлять его туда.
Не тот ли это случай, когда вместо «крайний» как раз следует написать «последний», пусть даже вы и парашютист/моряк/кто-еще-там-использует-крайний-вместо-последний?
Это бред. Точно так же про многие компьютерные игры можно сказать, что оптимальная стратегия для них — использовать ArtMoney. Мы же тут про алгоритмы говорим, а не про мелкое жульничество.
Что именно бред? Это алгоритм? Алгоритм. Оптимальный? Оптимальный.
Если играть для фана — то и вышеприведенный алгоритм использовать не стоит.
Если играть для фана — то и вышеприведенный алгоритм использовать не стоит.
Следование этому алгоритму приведет не к выигрышу в игре, а к нарушению правил, незаметному для второго игрока. Нас же интересуют алгоритмы для выигрыша в игре.
Оптимальность этого алгоритма стоит рассматривать исходя из теории игр, а не исходя из правил игры в морской бой. Все не так однозначно получается, однако.
А как получается?
Расчет осилите? Теоретически у нас должна быть взвесь из стратегий, поскольку неполная информация.
Но не будут ли другие стратегии иметь нулевые веса за счет повышенной жизни однотрубников?
Перебрать _ВСЕ_ возможные стратегии это чуть ли не ситуация с шахматами, но перебрать парочку самых очевидных — относительно реально. Хотя я не осилю.
Расчет осилите? Теоретически у нас должна быть взвесь из стратегий, поскольку неполная информация.
Но не будут ли другие стратегии иметь нулевые веса за счет повышенной жизни однотрубников?
Перебрать _ВСЕ_ возможные стратегии это чуть ли не ситуация с шахматами, но перебрать парочку самых очевидных — относительно реально. Хотя я не осилю.
Можно просто дать в глаз сопернику и признать себя победителем. Этот алгроритм еще эффективнее.
А чтобы защититься от вашего при игре на бумаже — достаточно после расстановки кораблей поменяться ручками.
А чтобы защититься от вашего при игре на бумаже — достаточно после расстановки кораблей поменяться ручками.
Теперь при игре с опытным противником я буду всегда искать большие корабли по границам поля.
Для поиска катеров оптимальной стратегии не существует, поэтому в конце игры приходится опираться в основном на удачу.
Спорное утверждение. Если катеров осталось больше одного, то, подбив один из них, мы закрываем ещё и все неизвестные клетки, соседние с ним. Так что выгоднее стрелять в клетку, у которой больше незакрытых соседей.
С другой стороны, если противник тоже это знает, то ему выгоднее ставить катера на «невыгодные» клетки, а значит, и нам следовало бы стрелять по ним… Я как-то пробовал рассчитать оптимальную стратегию за обоих игроков для простейших случаев (поле 1x5, два катера) — но не хватило терпения.
Совершенно точно видел этот алгоритм в какой-то книге, прочитанной в первой половине 90-х. Но ценности статьи это нимало не уменьшает
Первый раз вижу чтобы играли в морской бой прямыми кораблями. Всю жизнь играл по правилам в которых можно было загибать корабли.
У нас в школе за такое можно было по мордасам схлопотать, как за жульничество (в том возрасте мы все легко лезли в драку).
А за что так жёстко минусуют Magnum72? Ну, я тоже когда был маленький играл в основном в морской бой с угловыми кораблями. По мордастам не хлопотал — отец вряд ли бы меня стал бить за такое :)
За что по «мордасам»? Это было разрешено нашими правилами, впритык ставить и углами соприкасать было нельзя, зато играть было интересней.
Загибать. Корабли. Ага.
Морской камуфляж.
Угадали. Камуфляж времён Первой Мировой для затрудруднения прицеливания торпедистам с немецких подлодок. Кроме чёрно-белого был еще и «весёленьких» цветов:
Источник
Источник
Из первого правила сразу вытекает второе: если вам удалось подбить вражеский корабль, необходимо сразу же его добить, чтобы как можно раньше получить список гарантировано свободных клеток.Это если не считать вероятности. Например, если шибанули в угол, а так кусок корабля, то в одной из двух клеток, с вероятностью ¹⁄₂ есть его продолжение, так зачем тратить ход на уточнение? Можно пока пострелять в другое место, а тут разобраться потом.
После того как корабль был «ранен» или «убит» стрелявший получает внеочередной ход. Так что разницы нет, когда добивать. Выигрыша от выстрела куда-то еще нет.
Боюсь, вы всё-таки недопоняли статью. Вся суть в том, что добивание корабля оказывается гораздо эффективнее. Представим, что в углу двухпалубник, тогда за два хода (максимум) вы дополнительно проверите 3 клетки.
У меня несколько раз при такой стратегии все корабли оставались целыми.
то знает, кем бы она работала, если бы в своё время слушала лекции?
А какие у нас лекции слушать? Я думаю что у все таких примеров просто вагон:
Два парня учатся в университете. Один балду пинает, другой прилежно учится. Вопрос, это что то гарантирует по устройству в жизни?
В универах обучают:
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/
Для меня университет важен исключительно развитием у человека момента стрессового погружения в размышления. Пики экзаменационных напрягов,, подготовка к сессии — это знакомство человека с глубинами своих возможностей. Знакомством со своей головой. Поэтому до сих пор без них никуда, хоть на сегодня там такой бардак.
Простите, я конечно всё понимаю, хороший преподаватель и всё такое, но «все берут взятки и он взял» — херовое оправдание. Закон нарушать нельзя, сколько бы людей вокруг тебя его не нарушали.
Получается, что выгоднее на лекциях таки в М.Б. играть. Или еще во что-то. Или прогуливать их…
Тем самым усиливаем стрессовое погружение в размышления под сессию. :)
P.S.… а если официантке топикстартер просто понравился? Читай — искала способ обратить на себя внимание )
Тем самым усиливаем стрессовое погружение в размышления под сессию. :)
P.S.… а если официантке топикстартер просто понравился? Читай — искала способ обратить на себя внимание )
«Или прогуливать их… » — не значит напрягаться потом) Сидят студенты, пишут конспекты. Тонны бумаги. Слушают лектора.
Покажите мне хоть одного студента кто):
а) достает тетрадь после сессии хоть раз в жизни если вообще вспоминает о ней.
б) Кто то там что-то запоминает когда пишет. Якобы механическая память.
Студенты пишут лекции, а лекторы это читают, это некий протокол обмена информацией. Рот-уши-ручка. Полудуплексный.
Это некая сделка, вот, ваши знания в тетрадях, вы их поимели они ваши. Вы их отработали. А раз мы их поимели и они наши, то мы их складируем на полку. Ну они наши. зачем о них вспоминать?
Покажите мне хоть одного студента кто):
а) достает тетрадь после сессии хоть раз в жизни если вообще вспоминает о ней.
б) Кто то там что-то запоминает когда пишет. Якобы механическая память.
Студенты пишут лекции, а лекторы это читают, это некий протокол обмена информацией. Рот-уши-ручка. Полудуплексный.
Это некая сделка, вот, ваши знания в тетрадях, вы их поимели они ваши. Вы их отработали. А раз мы их поимели и они наши, то мы их складируем на полку. Ну они наши. зачем о них вспоминать?
Да вот, не так давно попалось на глаза
www.ted.com/talks/lang/ru/ramsey_musallam_3_rules_to_spark_learning.html
Еще бы кто у нас в ВУЗах в этом разбирался…
www.ted.com/talks/lang/ru/ramsey_musallam_3_rules_to_spark_learning.html
Еще бы кто у нас в ВУЗах в этом разбирался…
Интерес к любой «ерунде» можно передать или даже заразить, если преподаватель сам чекнутый на этой теме и чувствует тайну в этом предмете, взахлеб о ней рассказывает. А рутина никому не интересна.) Будет тайна — будет кайф.
Наука от женщины тут не отличается. Есть в ней тайна, будет вечная любовь. Тайны нет, будем менять по очереди жен — потреблять.
Наука от женщины тут не отличается. Есть в ней тайна, будет вечная любовь. Тайны нет, будем менять по очереди жен — потреблять.
a) Перед подготовкой к госэкзамену вполне нормальная практика — пройтись по конспектам на нужные темы. Редко, но бывает, что там написано понятнее, чем в учебнике.
б) Если лекции читал и записывал, то к коллоквиуму иногда (в 10-20% случаев) можно подготовиться, вообще не открывая ни учебника, ни лекций. Проверено. Если лекции не записывать (и вообще на них не ходить), то это заметно сложнее.
б) Если лекции читал и записывал, то к коллоквиуму иногда (в 10-20% случаев) можно подготовиться, вообще не открывая ни учебника, ни лекций. Проверено. Если лекции не записывать (и вообще на них не ходить), то это заметно сложнее.
Ну вот вы и описали что сдаете всего один предмет под названием «память». Есть память, получай пятерку. Нету ее… два. Понял не понял. Кого это волнует) Понятые вещи никогда не забываются)
Насчёт «никогда» — теперь уже не уверен. Только что дочка спросила про разложение оператора на ортогональный и симметричный — сходу вспомнить не удалось, хотя в своё время хорошо это понимал и мог вывести с нуля. И ведь учил всего 28 лет назад.
А про «предмет под названием память» — сами сначала спрашиваете, кто запоминает лекции, когда их записывает, а потом, когда говорят, что такие есть — тыкаете в это носом? Хороший приём, практически непробиваемый.
А про «предмет под названием память» — сами сначала спрашиваете, кто запоминает лекции, когда их записывает, а потом, когда говорят, что такие есть — тыкаете в это носом? Хороший приём, практически непробиваемый.
Автор, ну йомайо — «Все перечисленные корабли должны быть размещены на квадратном поле 10 на 10 клеток» — КАК располагаться?
Вертикально/горизонтально/по диагонали?
В одну линию/палюбас?
Я встречал правила «только вертикально/горизонтально», «только в одну линию», «как попало, но чтобы квадраты соприкасались сторонами», «как угодно, но чтобы квадраты соприкасались».
Клянусь.
Вертикально/горизонтально/по диагонали?
В одну линию/палюбас?
Я встречал правила «только вертикально/горизонтально», «только в одну линию», «как попало, но чтобы квадраты соприкасались сторонами», «как угодно, но чтобы квадраты соприкасались».
Клянусь.
«Значит, при размещении корабли надо ставить таким образом, чтобы в случае их потери минимизировать количество гарантировано свободных клеток»
Я когда-то маленьким в больнице (делать было нечего) играл в МБ и интуитивно выбрал именно эту стратегию — рассовать по углам и краям.
Эта стратегия была вычислена противником (тоже первоклашкой) примерно на 6..10-м ходу.
И я был мгновенно побит :-)
Я когда-то маленьким в больнице (делать было нечего) играл в МБ и интуитивно выбрал именно эту стратегию — рассовать по углам и краям.
Эта стратегия была вычислена противником (тоже первоклашкой) примерно на 6..10-м ходу.
И я был мгновенно побит :-)
Есть еще один алгоритм — работает на людях с ручками и бумажками: называется клетка, в уме стартует быстрый счет, в случае промаха в клетку записывается состояние счетчика на момент ответа противника. После первоначального прострела карты расстреливаются точки, соседствующие с наибольшими цифрами счетчиков.
Смысл — если клетка рядом с кораблем, человек, прежде чем ответить, проверяет правильность ответа и на это тратится немножко больше времени.
Смысл — если клетка рядом с кораблем, человек, прежде чем ответить, проверяет правильность ответа и на это тратится немножко больше времени.
При этом всём надо как-то так расставить корабли, чтобы противник не догадался о методе и не применил его сам в следующей игре
А у меня всегда была тактика, делать выстрел так, чтобы в случае попадания «закрывалось» как можно больше неизвестных клеток, то есть я старался стрелять в центр наименее заполненных квадратиков 3х3.
Стратегия, близкая к оптимальной — стрелять в клетку, которая занята с наибольшей вероятностью (т.е. в наибольшем числе конфигураций, не противоречащих полученной информации). Она будет хорошо работать, даже когда разрешено читерство. Вот только пользоваться ей в реальном времени довольно сложно…
Минус расположения своих кораблей вплотную к краям поля: если такой корабль ранен, то вероятность ошибки при добивании уменьшается.
Есть небольшая оптимизация правил, которая нивелирует выигрыш от такой расстановки кораблей, при этом стратегия для победы остается той же — стрельба залпами, количество залпов = количеству оставшихся типов кораблей. Т.е. сначала — 4 выстрела, после потери линкора — 3 выстрела, после потери всех 3х/2х1-палубников убирается по одному выстрелу.
В статье много важных для понимания фактов, но называть это оптимальной стратегией я бы не решился. Во-первых очень много ни чем не обоснованных допущений. А во вторых, автор постоянно упирается в максимизацию количества «проверенных клеток». Это тоже самое, что называть оптимальным алгоритмом для игры в шахматы тот, в котором мы постоянно пытаемся покрыть своими фигурами максимальное количество позиций, что очевидно, неверно. Короче, в карму — плюс, за статью — минус.
Стратегия как выиграть же «разбита» на две части, — как подбить противника, и как не быть подбитым самому.
А теперь немного теории (игр).
Для пошаговых игр существует решение в общем виде — это выстраивается дерево всех состояний (даже для шахмат оно теоретически существует), и ходы делаются те, которые в итоге приводят к победе делающего ход. И побеждает чаще всего, в зависимости от игры, первый ходящий, если не делает ошибок (для шахмат просто еще есть ничья).
В случае морского боя, максимизация проверенных клеток на чужом поле, и минимизация проверки своих, это стратегия, которая позволяет максимизировать разницу между подбитыми чужими и подбитыми своими. Понятно, что чем больше эта разница, тем ближе победа. На дереве это выглядит так, что вы на каждом шаге (не отматываете всё дерево назад, как в идеале приводит к победе), а идете в ту локальную конфигурацию, которая ведет приближает вас к победе каждым шагом. Так что стратегия рабочая, а вот с понятием «оптимальности» следует разбираться. Оптимальной с точки зрения математических определений она бы была если бы приводила к победе за наименьшее количество шагов.
То есть данный алгоритм — это максимизация конечной величины через максимизацию дельт каждого шага.
А теперь немного теории (игр).
Для пошаговых игр существует решение в общем виде — это выстраивается дерево всех состояний (даже для шахмат оно теоретически существует), и ходы делаются те, которые в итоге приводят к победе делающего ход. И побеждает чаще всего, в зависимости от игры, первый ходящий, если не делает ошибок (для шахмат просто еще есть ничья).
В случае морского боя, максимизация проверенных клеток на чужом поле, и минимизация проверки своих, это стратегия, которая позволяет максимизировать разницу между подбитыми чужими и подбитыми своими. Понятно, что чем больше эта разница, тем ближе победа. На дереве это выглядит так, что вы на каждом шаге (не отматываете всё дерево назад, как в идеале приводит к победе), а идете в ту локальную конфигурацию, которая ведет приближает вас к победе каждым шагом. Так что стратегия рабочая, а вот с понятием «оптимальности» следует разбираться. Оптимальной с точки зрения математических определений она бы была если бы приводила к победе за наименьшее количество шагов.
То есть данный алгоритм — это максимизация конечной величины через максимизацию дельт каждого шага.
Ошибся с тем, что морской бой — пошаговая игра (тем более тогда сравнение с шахматами некорректно), каюсь, так как на момент расстановки кораблей — игра идёт одновременно, плюс обычно для пошаговых игр расстановка сил заранее известна. Однако все рассуждения в предыдущем комменте про морской бой (кроме примера с деревом где я поспешил изложить мысли) в силе.
Кстати, в теории игр есть и решение для игр, где одновременно принимается решение. Называется «проникновением в замыслы соперника». Максимизируется собственный выигрыш исходя из возможных выборов соперника, путем выбора доминирующей стратегии (хода). Доминирующая та, когда выигрыш максимален при любом из ходов соперника. Доминирующая (как и доминируемая) стратегии не всегда существуют, но в данном посте приведен пример стратегии, которая доминирует, или по-крайней мере, не проигрывает ходам соперника (при расстановке кораблей).
Более того, стратегия «максимизировать количество известных клеток» также соответствует тому, что веса у кораблей разные, то есть при одинаковой силе их подбить по-разному сложно. Известные клетки снижают количество ходов, тем самым, снижая возможность проигрыша. Однако повторюсь, что количество шагов здесь наименьшее, следует доказывать математически.
Кстати, в теории игр есть и решение для игр, где одновременно принимается решение. Называется «проникновением в замыслы соперника». Максимизируется собственный выигрыш исходя из возможных выборов соперника, путем выбора доминирующей стратегии (хода). Доминирующая та, когда выигрыш максимален при любом из ходов соперника. Доминирующая (как и доминируемая) стратегии не всегда существуют, но в данном посте приведен пример стратегии, которая доминирует, или по-крайней мере, не проигрывает ходам соперника (при расстановке кораблей).
Более того, стратегия «максимизировать количество известных клеток» также соответствует тому, что веса у кораблей разные, то есть при одинаковой силе их подбить по-разному сложно. Известные клетки снижают количество ходов, тем самым, снижая возможность проигрыша. Однако повторюсь, что количество шагов здесь наименьшее, следует доказывать математически.
Наименьшим оно не будет. В лучшем случае можно доказать, что меньшее матожидание по сравнению с другими (известными) стратегиями.
Вы правы. Вот хорошую статью нашел.
В шахматах это немного не так работает, люди именно считают - ходов на пять вперед, а дальше - интуиция, хотя, конечно, есть и критерии оценки для позиции: количество и качество материала, пешечная структура, наличие и принадлежность открытых и полуоткрытых линий, пространство и т.п. Просто считают по дереву ходов движки, а не люди. Вот они могут на 20-30 ходов вперед посчитать и опираться только на вероятность мата (победы) в определенном варианте.
Я-то думал, что в статье будет серьезное исследование с применением теории игр, ну или на худой конец просчитаны вероятности различных исходов при различных стратегиях игры. А тут — такая банальщина, как «сначала подбейте линкор»… Спасибо, кэп.
По поводу расстановки ИМХО лучше более случайно ставить корабли, чем прижимая их в какую-ту сторону, противник может понять что все корабли в том, нужном углу и атаковать только туда.
Да, но ведь ставка именно на то, что попасть в катера (1х1) крайне тяжело.
В «морском бое» самые сильные фигуры — одноклеточные корабли, несмотря на то, что жизненный опыт подсказывает что самый большой корабль — самый сильный. Грубо говоря, одноклеточные корабли — это ферзи морского боя. Сдавая «многоклеточные пешки», вы освобождаете простор для наиболее сильных фигур.
В общем-то, если начать с угла, то за каждый ход можно будет вынести как минимум по ряду кораблей, ориентируясь на подсказки «ранен … ранен … убит (пропускаем клетку) … ранен … убит (пропускаем клетку)» и т. д.
То есть, в самом эффективном по мнению автора случае противник может вынести всё, кроме катеров, за 0 ходов. Довольно неплохая экономия для противника. (Хотя, на самом деле, эффект от этого только психологический — оба игрока к концу игры сберегут поровну ходов в результате убийства кораблей.)
То есть, в самом эффективном по мнению автора случае противник может вынести всё, кроме катеров, за 0 ходов. Довольно неплохая экономия для противника. (Хотя, на самом деле, эффект от этого только психологический — оба игрока к концу игры сберегут поровну ходов в результате убийства кораблей.)
За 0 в лучшем случае. В некоторых схемах два угла свободные и только с третьего хода нащупаешь.
И эффект не только психологический обычно. При случайной схеме расположения у противника будет какое-то количество зря сделанных выстрелов, не в смысле промахов вообще, а в смысле «попаданий» в клетку, где корабля быть не может. Самый простой пример — первым выстрелом ранил двухтрубник в центре, но убить его можно в этот же ход, а можно три раза промахнуться (в среднем два промаха), не угадав направление.
И эффект не только психологический обычно. При случайной схеме расположения у противника будет какое-то количество зря сделанных выстрелов, не в смысле промахов вообще, а в смысле «попаданий» в клетку, где корабля быть не может. Самый простой пример — первым выстрелом ранил двухтрубник в центре, но убить его можно в этот же ход, а можно три раза промахнуться (в среднем два промаха), не угадав направление.
В детстве я и дед играли в морской бой против компьютера.
Компьютер был читером — программисту было лень писать алгоритм «добивания» и после первого попадания в корабль он его всегда добивал.
Интуивно выработали алгоритм расстановки кораблей по краям карты, и накрытие поля сеткой. Но мы пропускали одну клетку, мысль про то, что нужно сначала найти линкор до нас не дошла :-(
Компьютер был читером — программисту было лень писать алгоритм «добивания» и после первого попадания в корабль он его всегда добивал.
Интуивно выработали алгоритм расстановки кораблей по краям карты, и накрытие поля сеткой. Но мы пропускали одну клетку, мысль про то, что нужно сначала найти линкор до нас не дошла :-(
У нас в университете за слово «оптимальный» баз постановки задачи оптимизации сразу на пересдачу отправляли. На самом деле здесь приведены просто эвристические наблюдения, возможно, приводящие к победе с бОльшей вероятностью, чем игра наугад, но, как мне кажется, не с максимально возможной вероятностью.
А за слово «кажется» в чисто технических вопросах, что в вашем университете делали? Если серьёзно, я с удовольствием почитаю о вашем варианте стратегии.
Без обид — я имел ввиду, конечно, что заявление об оптимальности не может быть истинным пока не поставлена и не решена задача оптимизации. Опять же, нужно делать предположения об оппоненте — играет ли он наугад или же, зная вашу стратегию, специально подстраивается под неё. Немного погуглив нашёл ответ, хоть как-то затрагивающий теорию вероятностей: otvety.google.ru/otvety/thread?tid=4c354bc83317c41f&pli=1. Конечно, это далеко от идеала, но уже что-то. Конечно, для вероятность ещё можно посчитать практическим путём — написать программу, которая играет сама с собой разными методами и найти наиболее выигрышный из них (но опять же не факт что это будет оптимальным решением задачи).
К сожалению, не обладаю сейчас свободным временем для исследования, но думаю запишу куда-нибудь, если появится время — подумаю.
К сожалению, не обладаю сейчас свободным временем для исследования, но думаю запишу куда-нибудь, если появится время — подумаю.
Вот в этой статье подробно рассмотрены различные стратегии игры и приведены вероятности победы: www.datagenetics.com/blog/december32011/index.html
Некоторое время назад от безделья поиграл в онлайн морской бой на телефоне. В отличии от классического варианта, в нем были корабли трех видов: один из 4х клеток, два из 3х и четыре из 2х. Кроме того, изначально каждый игрок осуществляет 5 выстрелов за ход, и это число сокращается на единицу c каждым погибшим кораблем (не опускается ниже 1).
Вот небольшая статистика из ~60 партий.
1) Расстановка кораблей противником (число в ячейке – количество партий, в которых соперник разместил на этой клетке один из кораблей)
В целом, люди видят выгоду в размещении кораблей вдоль стенок.
2) Атака противника (число в ячейке – количество партий, в которых соперник не выстрелил в эту клетку, при этом не обстрелянные клетки, которые в финале партии были очевидно свободны, в расчет не идут)
Конкретных цифр у меня нет, но при выстраивании своих кораблей и выборе ячеек для атаки с учетом собранной информации, процент выигранных партий увеличился.
Вот небольшая статистика из ~60 партий.
1) Расстановка кораблей противником (число в ячейке – количество партий, в которых соперник разместил на этой клетке один из кораблей)
В целом, люди видят выгоду в размещении кораблей вдоль стенок.
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).
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).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Оптимальный алгоритм игры в морской бой