Важная информация

User Tag List

Страница 1 из 4 1234 ПоследняяПоследняя
Показано с 1 по 10 из 38

Тема: Бот для игры в "Морской бой": история, теория, практика

  1. #1
    Veteran
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    1,053
    Спасибо Благодарностей отдано 
    218
    Спасибо Благодарностей получено 
    47
    Поблагодарили
    31 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    Lightbulb Бот для игры в "Морской бой": история, теория, практика

    Математический анализ игры в "Морской бой" занимал меня с давних пор. Все началось с 1996 года, когда я замахнулся реализовать сильного бота для игры в "Морской бой" на сувенирных часах с микропроцессором Z80, причем бота, играющего честно, не подсматривая в корабли противника.

    Интернета тогда не было, а где еще можно было найти подобную теорию, я также не представлял. Было решено начать с опроса одногруппников, которые были сильны в этой игре. Но опрос показал, что эти люди либо скрывают, либо не имеют формального метода наилучшей стрельбы. Действуют интуитивно. Сообщили мне пару приемов, но описание было такое, которое трудно поддается алгоритмизации. Оставалось только действовать самому. И я начал думать.

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

    Исходный пункт моих размышлений на тот момент - это был один красивый прием, подсказанный спектрумистом Андреем Гетало, во время игры в "Battleships". Там корабли были большие, поэтому этот прием очень хорошо действовал. Например, чтобы найти корабль длиной в 4 клетки, нужно в первую очередь стрелять по открытым длинным линиям, причем с интервалом в 3 клетки, т.е. так, чтобы между выстрелами этот корабль не мог спрятаться. Причем каждый выстрел, в идеале, должен максимально сокращать длинные линии как по горизонтали, так и по вертикали.

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

    Сформулировать задачу стрельбы в рамках теорвера - дело непростое, тем более для меня на 2м курсе, когда мы теорвер только начали проходить. Но все же я тогда додумался до следующей идеи, которая оказалась очень близкой к оптимуму. Я начал вычислять для каждой свободной клетки величину, которую я назвал "число возможностей размещения". Что это такое?

    Представим себе чистое (необстрелянное) поле противника и какую-нибудь клетку в центре поля. Рассмотрим корабль длиной в 4 клетки. Сколько существует возможностей разместить этот корабль, чтобы он одной из своих частей оказался в этой клетке? Ответ простой. Корабль можно разместить по горизонтали четырьмя способами, чтобы одна из его клеток попала в искомую, и еще четырьмя по вертикали. Всего 8.

    Теперь представим ту же ситуацию, но клетка справа от искомой уже обстреляна (там "мимо"). Сколькими способами можно разместить 4-палубный корабль, чтобы одна из его частей попала в рассматриваемую клетку? Очевидно, что никакая часть корабля теперь не может оказаться в той клетке, где "мимо". Следовательно, по горизонтали 4-палубный корабль может быть размещен только одним способом: так, чтобы крайняя правая его клетка была в рассматриваемой, а остальные слева. По вертикали число возможностей размещения остается нетронутым, т.е. 4, а всего 5 возможностей размещения.

    Число возможностей размещения связано с вероятностью нахождения корабля в данной клетке. Почему? Ответ можно доказать строго. Корабль длиной в 4 клетки может быть размещен на поле конечным числом способов - назовем это число m. Из них n приходится на рассматриваемую нами клетку. Если все размещения корабля на поле равновероятны (а у нас пока нет причин считать иначе) - то вероятность нахождения корабля в данной клетке будет n/m, где n - число возможностей размещения, как я определил это число выше. Таким образом, вероятность нахождения корабля в клетке пропорциональна числу возможностей его размещения в ней. Важно: вышеприведенное рассуждение справедливо только для случая, когда на поле нет других кораблей. Когда есть другие корабли, ситуация значительно усложняется, и вероятность больше не зависит так явно от числа возможностей размещения.

    Получить некое число, соответствующее вероятности, для случая многих кораблей, на 1996г мне не удалось, поэтому я ограничился следующим алгоритмом стрельбы:
    1) для каждой свободной клетки вычислить число возможностей размещения в ней самого длинного корабля противника, который еще остается на поле.
    2) Найти все клетки, где число возможностей размещения достигает максимума.
    3) Выстрелить случайным образом в одну из этих клеток с максимумом.

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

    2 3 4 5 5 5 5 4 3 2
    3 4 5 6 6 6 6 5 4 3
    4 5 6 7 7 7 7 6 5 4
    5 6 7 8 8 8 8 7 6 5
    5 6 7 8 8 8 8 7 6 5
    5 6 7 8 8 8 8 7 6 5
    5 6 7 8 8 8 8 7 6 5
    4 5 6 7 7 7 7 6 5 4
    3 4 5 6 6 6 6 5 4 3
    2 3 4 5 5 5 5 4 3 2

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

    2 3 4 4 5 5 5 4 3 2
    3 4 5 4 6 6 6 5 4 3
    4 5 6 4 7 7 7 6 5 4
    4 4 4 0 5 6 7 7 6 5
    5 6 7 5 8 8 8 7 6 5
    5 6 7 6 8 8 8 7 6 5
    5 6 7 7 8 8 8 7 6 5
    4 5 6 7 7 7 7 6 5 4
    3 4 5 6 6 6 6 5 4 3
    2 3 4 5 5 5 5 4 3 2

    Как видно, даже один выстрел существенно меняет картину распределения возможностей размещения 4-палубного корабля. Выстрел в клетку с максимальным числом таких возможностей не только обнулял это число в самой клетке, но и максимально уменьшал его значение во всех остальных клетках. Число клеток с максимумом в рассматриваемом примере упало с 16 до 9, сокращая выбор возможностей для следующего выстрела. В конечном итоге, до подбития 4-палубного корабля, поле противника покрывалось "узором" из выстрелов, который принимал различные формы, но всегда в нем соблюдалось одно свойство: расстояние между соседними выстрелами по горизонтали и вертикали не превышало 3, что не позволяло 4-палубнику "проскочить" этот узор.

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

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

    Размещение своих кораблей на поле на 1997г проводилось мной по следующему методу. Сначала на поле размещался корабль максимальной длины случайным образом. Потом проводилась попытка разместить следующий корабль случайным образом. Если сгенерированные случайные числа попадали так, что новый корабль не может быть размещен (он попадает в уже имеющийся корабль или в его "ореол") - то попытка повторялась, и так до победного конца. Таким образом, я на тот момент не пытался разместить корабли таким образом, чтобы противнику было труднее их найти. Это предопределило относительно слабую игру моего бота 1997г.

    Изложенные выше концепции я сначала реализовал в программе на Паскале - seaboy.pas. Так было проще проводить наладку, у меня был компилятор Turbo Pascal под CP/M. Когда алгоритм на Паскале был налажен, я приступил к его переводу на ассемблер.

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

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

    Прилагаю файл seaboy.pas - отладочная версия моего бота 1996-1997г.
    Вложения Вложения
    • Тип файла: rar SEABOY.rar (2.4 Кб, Просмотров: 947)

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Master
    Регистрация
    25.04.2009
    Адрес
    Днепропетровск
    Сообщений
    813
    Спасибо Благодарностей отдано 
    26
    Спасибо Благодарностей получено 
    14
    Поблагодарили
    14 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  4. #3
    R.I.P.
    Регистрация
    16.09.2009
    Адрес
    г. Харьков
    Сообщений
    1,466
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    4
    Поблагодарили
    4 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

  5. #4
    Guru Аватар для Vadim
    Регистрация
    24.07.2008
    Адрес
    г. Курган
    Сообщений
    2,062
    Спасибо Благодарностей отдано 
    10
    Спасибо Благодарностей получено 
    17
    Поблагодарили
    17 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Я могу предложить только свой алгоритм, которым пользовался в Battle Ships. В самом начале игры стреляем наиболее хаотично. Так несколько первых ходов. До 5-го, 7-го. Уже, как правило, пара попаданий будет. Далее, смотрим картинку, используя подсказку, в какие корабли попали. И прикидываем, как они могут располагаться. Игра для выяснения начинает обставлять каждый квадрат у больших кораблей по периметру, да и у мелких тоже. Налицо не оптимальность алгоритма. Потом выяснив, как расположен корабль (возможно за 2-3 хода) уже ставит более нацеленно. Я делаю не так. Продолжаю хаотические выстрелы и бью соседние клетки подбитых, но не весь периметр,а по одной две. Помнится комп у меня выиграл всего раз или два. Игра проходится за 10 минут. Самый длинный корабль анализируем очень просто. Если попали в него, смотрим его возможные размещения (которых может быть 4) и бьем по ним. Т.е. фактически 4 клетки а не 8. как делает комп. и т.д. с другими. Хотя как это запрограммировать я не знаю. Не представляю пока.

    Скрытый текст

    Profi 5.06 1024K 12Mhz (кварц на 24), палитра, COM-порт, часы, hdd, covox, программатор
    ZX-Spectrum +3, ZX-Spectrum +2B, ZX-Spectrum +2, ZX Spectrum 48, ZX Spectrum 48+
    ZX Evolution Rev B.
    Color 48 + Beta Disk Interface +FDD+YM2149F
    Орель-08БК
    Pentagon-48 (недоссобранный кем-то)
    Pentagon-128 (полуубитый)
    Кворум-128 (в ремонте)
    Магик-05 (в ремонте)
    Robotron 1715
    Корвет ПК8020 и ПК8010
    Amstrad CPC 464
    Amstrad CPC 6128
    [свернуть]

  6. #5
    Veteran
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    1,053
    Спасибо Благодарностей отдано 
    218
    Спасибо Благодарностей получено 
    47
    Поблагодарили
    31 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    esl, спасибо за линк, указанную статью я читал недавно, собирался сделать на нее ссылку в своих дальнейших постах. Мои сегодняшние результаты по теории игры в "Морской бой" заходят дальше материалов этой статьи. Обрати внимание, кстати: метод обстрела для поиска 4-палубного корабля, приведенный в той статье, получается автоматически у моего алгоритма поиска клетки с максимальным числом возможностей размещения этого корабля. Более того, когда обстрел по шаблону, приведенному в статье, становится невозможным (например, подбиты другие корабли вместо 4-палубного), мой алгоритм продолжает эффективно действовать. Так что не смотрите даже на этот, имеющий недостатки, алгоритм свысока!

    doorsfan, твои рассуждения, в общем, верные, но они не подтверждаются сколько-нибудь строгими доказательствами. Именно публикацией доказательств я занимаюсь в этой ветке. В чем польза наличия доказательств?
    1) Они позволяют убедиться в истинности некоторых утверждений;
    2) Они позволяют выяснить, нет ли еще более оптимального метода решения задачи.
    И как показывают мои изыскания, такие методы есть! Подождите только немного, пока я напишу продолжение.

  7. #6
    Guru Аватар для osa
    Регистрация
    12.04.2010
    Адрес
    Шмелёво
    Сообщений
    2,263
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    1
    Поблагодарили
    1 сообщение
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    будет ли оформлена отдельная статья на тот же хабр по этому поводу?

  8. #7
    Veteran
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    1,053
    Спасибо Благодарностей отдано 
    218
    Спасибо Благодарностей получено 
    47
    Поблагодарили
    31 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от osa Посмотреть сообщение
    будет ли оформлена отдельная статья на тот же хабр по этому поводу?
    Возможно, материалов, которые я выложу на этой ветке, будет достаточно для написания статьи. Если хватит времени и вдохновения - я этим займусь. Что такое хабр?

    ---------- Post added at 01:04 ---------- Previous post was at 00:07 ----------

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

    Размещение длинных кораблей у краев поля вовсе не является редкостью для игры в "Морской бой". Наоборот, большинство опытных игроков только так свои корабли и расставляют. Причина - то, что подбитие длинного корабля в центре поля окружает его большим ореолом из клеток "мимо", тем самым значительно сужая поле для дальнейших поисков. Данный вопрос был рассмотрен детально Я.И. Перельманом (1882-1942), российским и советским ученым, популяризатором науки. Статья "Морской бой" в русской Википедии со слов Перельмана описывает стратегию, основанную на размещении кораблей у краев поля, и обосновывает ее преимущество. То же описано в статье пользователя habrahabr.ru Подсознание - "Теория и практика игры «Морской бой» — по-честному", на которую дал ссылку esl.

    Очевидно, что алгоритм стрельбы надо каким-то образом изменить, чтобы он больше обстреливал края поля. Но как, по каким критериям? За прошедшие со времени создания моего бота более 10 лет я иногда возвращался к размышлениям на эту тему, но так до недавних пор и не смог придумать хорошего решения. Если приблизительный расчет вероятности, основанный на подсчете числа возможностей размещения, говорит о том, что корабль более вероятно находится в центре поля - значит стрельба куда-либо, кроме центра, в общем случае уменьшает вероятность попадания. И только в специальном случае, когда противник специально размещает корабли у краев, где найти их легче, чем в центре (если знать, что они там) - такая стрельба имеет преимущество. Одно дело человеку понимать все это, а другое дело - реализовать в программе. Это была бы своего рода стрельба, адаптивная к противнику: если бы бот решил, что человек имеет тенденцию размещать корабли у краев - то он начал бы охотнее обстреливать края, а если нет - то снова смещал бы акцент в центр. Интуитивно понятно, но формальных критериев нет по-прежнему. Поэтому я не пытался реализовать эти идеи в виде программы, уж очень все было зыбко. Как потом убедиться, что бот играет сильнее, чем предыдущий? Особенно если противник начал бы адаптироваться к его новому поведению и снова принял какую-то иную стратегию размещения кораблей, которая обеспечила бы ему преимущество?

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

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

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

    Вопросов накопилось больше, чем ответов, и вот недавно я созрел к математической атаке на "Морской бой" с целого ряда направлений, о чем и пойдет речь ниже.

  9. #8
    Veteran Аватар для daniel
    Регистрация
    31.10.2005
    Адрес
    Кемерово
    Сообщений
    1,384
    Спасибо Благодарностей отдано 
    106
    Спасибо Благодарностей получено 
    20
    Поблагодарили
    11 сообщений
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Как потом убедиться, что бот играет сильнее, чем предыдущий?

    Это же очевидно, запускать ботов против друг друга...

  10. #9
    Veteran
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    1,053
    Спасибо Благодарностей отдано 
    218
    Спасибо Благодарностей получено 
    47
    Поблагодарили
    31 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

    Существует конечное множество комбинаций размещения всех кораблей на игровом поле. Это следует из конечности и дискретности самого поля.

    Если предположить, что противник с одинаковой вероятностью может использовать любую комбинацию из этого множества - то вероятность попасть в корабль в клетке с координатами (x,y) равна отношению чисел M/N, где N - общее число комбинаций,
    а M - число таких комбинаций, при которых в клетке с координатами (x,y) имеется корабль или его часть.

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

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

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

    1. Рассмотрим тривиальный случай, когда у нас на всем поле есть лишь один однопалубный корабль. Очевидно, что он может быть размещен в любой из клеток без каких-либо дополнительных ограничений. Поэтому всего существует столько возможностей его размещения, сколько есть клеток, и оно равно 100. Для каждой клетки только одна из таких возможностей соответствует наличию в ней корабля. Поэтому вероятность попасть в корабль для каждой клетки при первом выстреле одинакова и равна 0.01, или 1%. Оптимальная стрельба в этом случае является просто случайным выбором из всех клеток (Данное утверждение доказывается в рамках теории игр).

    2. Рассмотрим случай, когда на поле имеется два однопалубных корабля. Если бы их можно было размещать вплотную друг к другу, а также два корабля в одной клетке, то общее число комбинаций размещения составляло бы 10000. С учетом правил "Морского боя" о недопустимости размещения кораблей вплотную, допустимых комбинаций будет меньше. А именно: размещение первого из кораблей в середине поля уменьшает количество клеток для размещения второго корабля на 9. Размещение первого корабля у границ уменьшает число клеток для второго корабля на 6, а когда первый корабль стоит в углу, второй корабль может быть размещен
    во всех клетках, кроме четырех. Подсчет числа N выглядит так:

    N = 8*8*(100-9) + 8*4*(100-6) + 4*(100-4) = 5824+3008+384=9216

    Число M можно рассчитать из следующих соображений. Возьмем угловую клетку (1,1). Существует 96 комбинаций, при которых первый корабль будет размещен в этой клетке, а второй - в одной из оставшихся. Существует столько же комбинаций, при который второй корабль размещен в этой клетке, а первый - в другом месте. Складываем, получается 96+96=192 комбинации, при которых в клетке (1,1) размещен корабль. Вероятность попасть в корабль при стрельбе в эту клетку будет равна 192/9216~=2.0833%.

    Рассмотрим клетку в центре, например (4,4). При размещении в этой клетке первого корабля второй может быть размещен в любой из оставшихся 91. Такое же число имеем для случая размещения в этой клетке второго корабля, а первого - в любой из оставшихся. В сумме получится p=(91+91)/9216 ~= 1.9748%.

    Для клеток у границ поля, например, (1,5), вероятность попадания составит p=(94+94)/9216 ~= 2.0399%.

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

    Продолжение следует.

  11. #10
    Master
    Регистрация
    25.04.2009
    Адрес
    Днепропетровск
    Сообщений
    813
    Спасибо Благодарностей отдано 
    26
    Спасибо Благодарностей получено 
    14
    Поблагодарили
    14 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Barmaley_m Посмотреть сообщение
    ity Поэтому, если на поле складывается ситуация, что высоко вероятно нахождение трехпалубника в конкретном месте (т.е. велик шанс его подбить) - мой первоначальный алгоритм не воспользовался бы этой возможностью, предпочитая охотиться за 4-палубником, даже если клетки, где он еще может быть размещен, имеют число возможностей размещения много меньше 8.
    ............
    В такой ситуации возможно наличие клеток с максимумами числа возможностей размещения всех кораблей, которые не совпадают с клетками максимумов для одного лишь 4-палубника.
    Не удалось придумать такие ситуации.

    ---------- Post added at 12:22 ---------- Previous post was at 12:19 ----------

    вероятно, это ситуации описанные в последнем абзаце #9 поста?

Страница 1 из 4 1234 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Ответов: 0
    Последнее: 31.01.2011, 18:31
  2. Ответов: 0
    Последнее: 15.08.2010, 14:38
  3. Ответов: 7
    Последнее: 07.10.2009, 14:58
  4. Ответов: 4
    Последнее: 06.01.2009, 00:08

Метки этой темы

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •