Комментарии 10
А где же эвристики?
А есть ли обоснование того, что полученные размещения кораблей будут равномерно распределены по всему множеству размещений кораблей? Если такого обоснования нет — то возможно, ваш алгоритм имеет тенденцию к выбору некоторых, менее вероятных расположений, а подобные тенденции являются слабостью алгоритма.
Мною ранее получен метод, позволяющий получать случайные размещения кораблей, равномерно распределенные по всему множеству допустимых размещений. Достигается это методом отбрасывания (rejection method), аналогично генерации случайных чисел по некоторым распределениям, для которых трудно применить более эффективный подход.
Идея в том, что генерируется размещение, равномерно распределенное по расширенному множеству размещений кораблей (U), которое включает в себя множество допустимых размещений (D). После этого производится проверка, является ли сгенерированное расположение допустимым. Если нет — то все размещение аннулируется (все корабли убираются с поля) и заново размещаются, после чего опять происходит проверка и т.д. до тех пор, пока не будет сгенерировано допустимое размещение.
Обоснование равномерности тут простое: поскольку D является подмножеством U, то размещения, равномерно распределенные по U, будут равномерно распределенными и по D, если они принадлежат этому множеству.
Множество U задается простым образом, примерно как и у вас: каждому кораблю соответствуют координаты его левой верхней клетки и ориентация.
Опытным путем мною было установлено, что для генерации таким образом допустимого размещения эскадры на пустом поле требуется в среднем сгенерировать 3911 с копейками размещений по множеству U (число это было вычислено с высокой точностью за несколько недель работы ноута), поэтому можно заключить, что множество U содержит примерно в 3911 раз больше элементов, чем множество D.
Если генератор случайных чисел имеет достаточно длинный период повторения (в моих программах пришлось использовать продвинутые генераторы, вроде Mersenne-Twister, поскольку встроенный библиотечный из языка C не подошел) — то данная процедура тоже гарантированно сформирует допустимое расположение кораблей за конечное время, которое, однако, может быть большим, если на поле присутствует большое число запрещенных клеток.
Мною ранее получен метод, позволяющий получать случайные размещения кораблей, равномерно распределенные по всему множеству допустимых размещений. Достигается это методом отбрасывания (rejection method), аналогично генерации случайных чисел по некоторым распределениям, для которых трудно применить более эффективный подход.
Идея в том, что генерируется размещение, равномерно распределенное по расширенному множеству размещений кораблей (U), которое включает в себя множество допустимых размещений (D). После этого производится проверка, является ли сгенерированное расположение допустимым. Если нет — то все размещение аннулируется (все корабли убираются с поля) и заново размещаются, после чего опять происходит проверка и т.д. до тех пор, пока не будет сгенерировано допустимое размещение.
Обоснование равномерности тут простое: поскольку D является подмножеством U, то размещения, равномерно распределенные по U, будут равномерно распределенными и по D, если они принадлежат этому множеству.
Множество U задается простым образом, примерно как и у вас: каждому кораблю соответствуют координаты его левой верхней клетки и ориентация.
Опытным путем мною было установлено, что для генерации таким образом допустимого размещения эскадры на пустом поле требуется в среднем сгенерировать 3911 с копейками размещений по множеству U (число это было вычислено с высокой точностью за несколько недель работы ноута), поэтому можно заключить, что множество U содержит примерно в 3911 раз больше элементов, чем множество D.
Если генератор случайных чисел имеет достаточно длинный период повторения (в моих программах пришлось использовать продвинутые генераторы, вроде Mersenne-Twister, поскольку встроенный библиотечный из языка C не подошел) — то данная процедура тоже гарантированно сформирует допустимое расположение кораблей за конечное время, которое, однако, может быть большим, если на поле присутствует большое число запрещенных клеток.
Что вы подразумеваете под случайным размещением, равномерным по множеству возможных размещений? То, что каждое расположение кораблей выпадет равновероятно?
Равномерная плотность кораблей не является случайной в строгом смысле слова. Очень не случайной.
Да. То есть это как если взять все множество допустимых размещений кораблей (D), пронумеровать его, сгенерировать случайное число с равномерным распределением от 1 до length(D) и взять из множества D размещение, соответствующее этому числу. Таким образом, любое из допустимых размещений может быть выбрано с равной вероятностью.
Мне кажется, что эта равномерность не очень полезна, т.к. в каких-то клетках корабли могут оказаться с большей вероятностю, чем в других.
Как известно из практики и публиковалось во множестве источников (включая те, на которые ссылается автор поста) задача оптимальной расстановки кораблей заключается не в том, чтобы на каком-то этапе игры (в ее начале, например) выровнять вероятности нахождения кораблей в клетках, а в том, чтобы максимизировать количество выстрелов, которое потребуется противнику для потопления нашего флота. В частности, многие рекомендуют размещать длинные корабли у краев поля. Даже если противник знает о нашей тактике и будет сразу стрелять по краям и потопит все корабли, размещенные там, ему потом останется обстрелять много клеток в центре поля, чтобы потопить однопалубники и выиграть. Идя на жертву — давая противнику легкую возможность потопить почти все наши корабли — мы иногда можем увеличить число выстрелов противника и тем самым победить, потопив его корабли за меньшее количество выстрелов.
Решению задачи максимизации выстрелов противника способствует то, что мы даем ему минимум информации о нашем расположении. А именно, мы можем с равной вероятностью выбрать любое расположение из допустимых. Для этого нужно равномерное распределение.
Решению задачи максимизации выстрелов противника способствует то, что мы даем ему минимум информации о нашем расположении. А именно, мы можем с равной вероятностью выбрать любое расположение из допустимых. Для этого нужно равномерное распределение.
У меня алгоритм расстановки был как-то менее «научным». Приземленным, можно сказать.
Я перебирал корабли начиная от самого большого и заканчивая самыми малыми.
Для каждого корабля пробегалось все поле. Далее для каждой клетки определялось может ли в ней разместиться корабль с учетом уже раставленных кораблей. Имеется ввиду что в этой клетке будет «нос» корабля, а остальное ниже или правее. Причем в каждой клетке проверяется оба варианта размещения — по вертикали и по горизонтали — это две разных допустимых позиции. Из множества допустимых позиций выбиралась одна случайная, туда и ставился текущий корабль (интересное словосочетание получилось :)). И так далее пока не перебраны все корабли.
Возможно, этот алгоритм не всегда находит допустимую расстановку в общем случае, например, при большой плотности кораблей или нестандартной форме кораблей. Но для классического размера поля и набора кораблей — работает безотказно.
Я перебирал корабли начиная от самого большого и заканчивая самыми малыми.
Для каждого корабля пробегалось все поле. Далее для каждой клетки определялось может ли в ней разместиться корабль с учетом уже раставленных кораблей. Имеется ввиду что в этой клетке будет «нос» корабля, а остальное ниже или правее. Причем в каждой клетке проверяется оба варианта размещения — по вертикали и по горизонтали — это две разных допустимых позиции. Из множества допустимых позиций выбиралась одна случайная, туда и ставился текущий корабль (интересное словосочетание получилось :)). И так далее пока не перебраны все корабли.
Возможно, этот алгоритм не всегда находит допустимую расстановку в общем случае, например, при большой плотности кораблей или нестандартной форме кораблей. Но для классического размера поля и набора кораблей — работает безотказно.
Ну вот ваш метод как раз и имеет тенденцию выбирать из всех возможных размещений некоторые, менее вероятные. Скажем, если разместить 4-палубный корабль в центре поля — то он заблокирует больше возможностей разместить остальные корабли, чем если бы он стоял у края. Поэтому среди всех допустимых расположений эскадры больше таких, где 4-палубный корабль стоит у края, а не в центре, а вашим методом будет генерироваться относительно много расположений, где 4-палубный корабль в центре, т.е. выбранные таким образом расположения не будут равномерно распределены по всему множеству допустимых.
Вот самая, на мой взгляд, компетентная статья на Хабре о морском бое, человек даже смог посчитать общее количество допустимых расположений эскадры: Снова «Морской бой». Считаем число возможных расположений кораблей. Я участвовал в комментариях к этой статье.
Вообще проверить и осознать «равномерность распределения» очень просто для случая малого количества кораблей. Например, два однопалубных на пустом поле. Для размещения первого корабля существует всего 100 возможностей, а вот число возможностей размещения второго корабля будет зависеть от того, где стоит первый. Если он стоит в центре — то «откусывает» 9 клеток, остается 91. Если у края — 6 (остается 94), если в углу — 4 (остается 96). Можно легко перебрать все варианты. Всего существует 4*96 (углы) + 32*94 (края) + 64*91(центр) = 9216 комбинаций. Если посчитать число комбинаций, в которых один из кораблей размещен в углу или у края — то оно окажется больше числа комбинаций, в которых один из кораблей размещен в какой-либо клетке в центре поля.
Вот и попробуйте теперь создать такой метод, который выдает любое из допустимых для такой простой конфигурации эскадры размещение кораблей с равной вероятностью. Можно проверить и убедиться, что описанный мною выше метод решает эту задачу правильно.
Вообще проверить и осознать «равномерность распределения» очень просто для случая малого количества кораблей. Например, два однопалубных на пустом поле. Для размещения первого корабля существует всего 100 возможностей, а вот число возможностей размещения второго корабля будет зависеть от того, где стоит первый. Если он стоит в центре — то «откусывает» 9 клеток, остается 91. Если у края — 6 (остается 94), если в углу — 4 (остается 96). Можно легко перебрать все варианты. Всего существует 4*96 (углы) + 32*94 (края) + 64*91(центр) = 9216 комбинаций. Если посчитать число комбинаций, в которых один из кораблей размещен в углу или у края — то оно окажется больше числа комбинаций, в которых один из кораблей размещен в какой-либо клетке в центре поля.
Вот и попробуйте теперь создать такой метод, который выдает любое из допустимых для такой простой конфигурации эскадры размещение кораблей с равной вероятностью. Можно проверить и убедиться, что описанный мною выше метод решает эту задачу правильно.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Игра «морской бой»: расстановка кораблей