Xpoint
   [напомнить пароль]

Морской бой

Метки: [без меток]
[удл]
2004-05-28 03:08:40 [обр] Краев Александр ~ 2fresh(0/13)[досье]

На днях наткнулся на такую тему:
http://mp3.samsung.ru/news/?id=5225

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

спустя 5 часов [обр] Юрий Щапов(0/114)[досье]
Вы имеете в виду классический вариант или сайтовый флэш?
спустя 53 минуты [обр] Краев Александр ~ 2fresh(0/13)[досье]
Юрий Щапов[досье]
Класический.
спустя 3 часа 16 минут [обр] Сергей Сирик(21/737)[досье]
М Уж вы меня простите, но в Досуг :)
спустя 25 секунд [обр] Сергей Сирик(21/737)[досье]
М Перенесено из форума "Программирование::Теория и алгоритмы"
спустя 37 минут [обр] Юрий Щапов(0/114)[досье]
Первое, что в голову приходит — это стрельба из угла в шахматном порядке, отлов 2-х, 3-х, и 4-х трубников (+50% вероятность поражения однотрубников), а после гонки за однотрубниками.
Ещё мысль: Прежде всего стоит пострелять диагоналями через три клетки по вертикали и горизонтали для эффективной поимки 4-х трубника. Его поражение даст наибольшую площадь, стрелять по которой больше не имеет смысла.
спустя 1 час 33 минуты [обр] Краев Александр ~ 2fresh(0/13)[досье]

Юрий Щапов[досье]
Уже интересно, у меня такие соображения.

Начинаю стрельбу так:

`1``2``3``4``5``6``7``8``9`10
`а`XX
`б`XX
`в`XX
`г`
`д`
`е`
`ж`
`з`XX
`и`XX
`к`XX

Отлчино работает этот метод. Если в этих клетках не распологался 4х-палубник - еще лучше. Начинаем бить так, чтоб не осталось расстояние в 4е клетки.

C рассположением - сложнее.

Сначала я думал что основную часть кораблей следует размещать в определенных четвертях или половинах квадрата, а 1о-палубники где нибудь отдельно, чтобы осталось больше свободных клеток.
Потом, мне пришла в голову мысль, что если размещать корабли вдоль стенок квадрата - то мы уменьшим кол-во закрытых клеток после убийства корабля. Тем самым увеличим кол-во нестрелянных клеток и кол-во выстрелов противника. Но тем самым легко будет расстрелять все корабли, стреляя вдлоь стенок.

Идей много было, но как правильно расставлять корабли я так и не определился.

спустя 26 минут [обр] Юрий Щапов(0/114)[досье]
Диагонали а3-в1 и к8-з10 лучше сделать как а4-г1 и к7-ж10.
А вообще гарантированно накрыть 4-хтрубника можно только 24 выстрелами (диагонали):г1-а4 (4), 31-а8 (8), к3-в10 (8), к7-ж10 (4). Конечно, попутно тоже можно прихватить... :-)
спустя 4 минуты [обр] Юрий Щапов(0/114)[досье]
Самое оптимальное расположение 2-, 3-, и 4-хтрубников позволяет занять 40 клеток (с зоной вокруг уничтоженных кораблей) на карте. Итого: 60 клеток остаётся для размещения 1-трубников.
ИМХО неплохо.
спустя 7 минут [обр] Краев Александр ~ 2fresh(0/13)[досье]

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

На счет четырех диагоналей - хе-хе, долго! Тем более, надо сделать нексолько выстрелов, потрепать противника, оценить обстановку, и исходя из этого пулять. :)

Юрий Щапов[досье]
Что на счет расстановки?

спустя 1 минуту [обр] Краев Александр ~ 2fresh(0/13)[досье]
Юрий Щапов[досье]
Цифры впечатляют, а на деле это как?
спустя 3 минуты [обр] Краев Александр ~ 2fresh(0/13)[досье]

Вот думаю, есть же эмуляторы морского боя, какой в них алгоритм?
Неужели random?

Хех, в исходниках что ли порыться... Может кто занимался этой задачей?

спустя 3 часа 40 минут [обр] Rom McRitsky(0/441)[досье]
А может вам двоим сразиться? Вот на практике и проверите :)
Должен же быть какой-нить сетевой М.Б. ?
спустя 47 минут [обр] Краев Александр ~ 2fresh(0/13)[досье]

Rom McRitsky[досье]
Дык, рецепт-то еще не найден!!!

Это все еще версии...

Хе-хе, а сразиться было бы неплохо. Но, Юрий знает мою стратегию... :-)

спустя 2 дня 9 часов [обр] Дмитрий Котеров(11/912)[досье]
Как размещать корабли оптимально, я могу сказать. Вернее, предположить. Ставьте все, за исключением одного однопалубника, по краям — чтобы они покрывали как можно меньше клеток. В центре получится огромная пустая область, вот в нее случайным образом ставьте однопалубник. По-моему, так вероятность получается минимальной — противник перебьет вначале все корабли, а найти последний однопалубник ему ни в жизни не удастся.
спустя 3 часа 56 минут [обр] Сергей Чернышев(18/589)[досье]
Дмитрий Котеров[досье]
Вы уверены, что математически это самый оптимальный вариант?
спустя 1 час 15 минут [обр] Юрий Щапов(0/114)[досье]

Варианты для размышления:

4-х — а1-г1;
3-х — е1-з1, к1-к3;
2-х — а3-б3, г3-д3, ж3-з3.

Или:
4-х — а1-г1;
3-х — е1-з1, к1-к3;
2-х — а3-а4, а6-а7, а9-а10.

В любом случае остаётся 60 свободных клеток для размещения однотрубников.

Ещё порекомендовал бы, размещая однотрубники, учесть частую тактику стрельбы в шашечном порядке, т.е. два разместить как бы на белых клетках, а другие два — на чёрных.

Математически возможно варианты и не плохи, Сергей, но психология важнее. Опять же есть вероятность прямого попадания в тщательно скрываемый однотрубник.
В школе ещё я пользовался подобным алгоритмом и выигрывал у менне искушённых товарищей в пропорции 3:1. Но!.. Нельзя забывать о том, что тактика каждого из них мне уже была хорошо известна!

спустя 5 часов [обр] Краев Александр ~ 2fresh(0/13)[досье]

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

4-х и 3-х ставил по краям квадрата, отступая от угла по три-четыре клетки. Почему? Опять же психология... Многие часто бьют по углам, мой алгоритм по три выстрела на край тоже не прокатывает.

2-x поставил бы в одной половине или четверти квадрата, на клетку от 3-х и 4-х трубников.

1-х: один в глубь ко всей флотилии, еще одни тоже около стенки, ну и два на открытом пространстве, со смещением в определенный край.

Пытаюсь найти исходники или опесорцовский SeaBattle, но никак не могу найти. А узнать как на этот счет думали программисты очень хочется...

спустя 4 часа 30 минут [обр] Дмитрий Котеров(11/912)[досье]

Сергей Чернышев[досье]
Не уверен, конечно. Есть лишь предположение — чем больше клеток, которые не покрываются кораблями, остается, тем меньше вероятность поражения. Нам даже лучше, если противник с первого же выстрела расстреляет все наши корабли, стоящие по краям - потом он будет долго и упоро простреливать центр, а за это время можно многое сделать.

Насчет двух однопалубников в центре. Может быть, что это и оптимальнее. Однако нужно помнить, что однопалубник в угле покрывает 4 клетки, а в центре — целых 9 (почти в 3 раза больше). Таким образом, разместив второй однопалубник в центре, мы увеличиваем вероятность обнаружения второго.

Что касается вероятности прямого попадание, то, я думаю, она все же очень низка. Не факт, что 2 однопалубника ее уменьшают.

спустя 14 часов [обр] Дмитрий Попов(10/509)[досье]

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

И второй важный момент: В идеальной системе, если нападающий и вправду начнет убивать боковые корабли в первую очередь, то да - в конце вероятность меньше. Но! Человек начинает играть сразу по всему полю. И если он, случайно, попадает в однобпалубник, то дальше ему достаточно понять схему расположения. Это уже логика. Которая неподвластна теории вероятности (насколько я понимаю таковую).

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

спустя 3 часа 31 минуту [обр] Дмитрий Котеров(11/912)[досье]
если он, случайно, попадает в однобпалубник
А если ему случайно во время игры на голову упадет метеорит, то и играть незачем будет.
спустя 1 час 6 минут [обр] Дмитрий Попов(10/509)[досье]
Дмитрий Котеров[досье]
Как Вы полагаете - до тех пор пока не сбит ни один корабль - в Вашем случае попадание первым в однопалубник менее вероятно чем при любой другой разумной раскладке?
спустя 9 часов [обр] Сергей Чернышев(18/589)[досье]

Дмитрий Попов[досье]
вероятность в том и состоит, что не важно снача сбит один корабль или потом. Другой вопрос, что оптимальный вариант требует не минимальной вероятности попадания в последний корабль, а минимальную вероятность цепочки выстрелов, а следовательно все корабли должны быть расставлены оптимально. Но вероятно все варианты в конце концов сводятся к предложеному Дмитрием. Правда нужно еще учитывать, что выстрелы производятся не рандомайзером, а человеком и у него могут быть более сложные принципы выбора цели.

Короче, задача не такая уж тривиальная - из серии "какой пароль самый надежный?" ;))

спустя 11 минут [обр] Дмитрий Попов(10/509)[досье]

Сергей Чернышев[досье]

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

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

спустя 9 минут [обр] Дмитрий Котеров(11/912)[досье]
Раз выстрелы производятся не «рандомайзером», значит, корабли надо расставлять «рандомайзером». Рандомайзер рандомайзеру, как говорится, рандомайзер.
спустя 6 минут [обр] Краев Александр ~ 2fresh(0/13)[досье]
Дмитрий Котеров[досье]
Ух ты!!! Надо запомнить ;-)
спустя 11 часов [обр] Артём Сапронов aka Capricorn(28/569)[досье]
SeaBattle проиграывет на раз-два, если тупо стрелять последовательно по диагоналям, попутно достреливая те корабли на которые натыкаешься
спустя 4 часа 30 минут [обр] Сергей Чернышев(18/589)[досье]
Артём Сапронов aka Capricorn[досье]
Его писал человек, а программа написаная человеком заведомо хуже играет чем человек ;)
спустя 49 минут [обр] Сергей Круглов(10/2057)[досье]
Ага, вот в шахматы, к примеру...
Ухожу, ухожу... ;)
спустя 35 минут [обр] Дмитрий Котеров(11/912)[досье]
Кто сказал, что SeaBattle написана оптимально? С ней бы тогда никто играть не стал.
спустя 2 часа 10 минут [обр] Сергей Чернышев(18/589)[досье]
Дмитрий Котеров[досье]
Ну, минимальная вероятность выигрыша еще не обозначает что выиграть невозможно.
Powered by POEM™ Engine Copyright © 2002-2005