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

User Tag List

Страница 4 из 4 ПерваяПервая 1234
Показано с 31 по 38 из 38

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

  1. #31
    Veteran Аватар для GriV
    Регистрация
    18.02.2005
    Адрес
    Набережные Челны
    Сообщений
    1,574
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Barmaley_m Посмотреть сообщение
    Метод Монте-Карло
    По большому счёту у меня почти такое же соотношение и получилось, однако метод дал распределения :-) А как это в режиме реального времени считается? И опять же, как хранить на несколько ходов вперёд? Ведь вариантов много?
    Биты рулят лучше байтов, байты рулят шустрее!
    View, Звук, Цвет

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

  3. #32
    Master
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    961
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от GriV Посмотреть сообщение
    По большому счёту у меня почти такое же соотношение и получилось, однако метод дал распределения :-)
    В принципе, сейчас, кроме метода Монте-Карло, у меня нет других более эффективных методов получения результата. Проблема с методом Монте-Карло заключается в том, что он дает хорошие результаты только в начале игры, а после нескольких выстрелов (как промахов, так и попаданий) количество допустимых комбинаций размещения кораблей уменьшается в тысячи раз. Даже полученные с таким трудом сотни тысяч комбинаций, которые я имею на данный момент, сокращаются до нескольких сотен, что дает большие уровни шума в получаемых на этих этапах картах вероятностей. Поэтому любые новые идеи, усовершенствования или более эффективные методы получения требуемой карты вероятностей - приветствуются.
    Цитата Сообщение от GriV Посмотреть сообщение
    А как это в режиме реального времени считается?
    О расчетах в реальном времени пока что речи не идет. Я думаю, что есть несколько направлений решения этой проблемы:
    1) Хранить много комбинаций размещения кораблей. Допустим, несколько десятков мегабайт - это не проблема для современных компьютеров. Как я посчитал, любая коминация может быть закодирована 71 битами, что округляется до 9 байт (72 бит). Такой подход используется, когда не найдено ничего лучшего, например см. взлом хешей методом Rainbow Tables. Для взлома виндошных паролей приходится скачивать сотни мегабайт рассчитанных ранее кем-то таблиц.
    2) Хранить разветвляющиеся последовательности оптимальных ходов
    3) Изобрести методы, дающие приблизительные результаты (еще менее точные, чем метод Монте-Карло), но за малое время. У меня есть некоторые мысли на этот счет. Метод Монте-Карло можно будет использовать как "золотой стандарт", относительно которого оценивается точность результата менее точных методов.
    Думаю, что какие-то варианты проявятся еще по ходу дальнейших исследований.
    Цитата Сообщение от GriV Посмотреть сообщение
    И опять же, как хранить на несколько ходов вперёд? Ведь вариантов много?
    Не так уж и много. Посмотри карту вероятностей для необстрелянного поля. На ней существует 8 клеток с максимальной вероятностью. Если стрелять только в клетки с максимальной вероятностью, то хранить надо только их координаты. В общем-то, даже само значение вероятности нам не так важно, как сам факт, что в данной клетке оно максимально. И вообще, как при хранении, так и при других манипуляциях с вероятностью попадания, всегда следует иметь в виду, что нам не обязательно знать точное число, а важно только знать, в каких клетках оно максимально.

  4. #33
    Veteran Аватар для GriV
    Регистрация
    18.02.2005
    Адрес
    Набережные Челны
    Сообщений
    1,574
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Barmaley_m Посмотреть сообщение
    1) Хранить много комбинаций размещения кораблей. Допустим, несколько десятков мегабайт - это не проблема для современных компьютеров. Как я посчитал, любая коминация может быть закодирована 71 битами, что округляется до 9 байт (72 бит).
    Речь про спектрум или вообще?

    Цитата Сообщение от Barmaley_m Посмотреть сообщение
    Не так уж и много. Посмотри карту вероятностей для необстрелянного поля. На ней существует 8 клеток с максимальной вероятностью
    Даже если так, то хранение наиболее вероятных клеток подразумевает какое то хранение предыдущего состояния. Соотвественно каждый выстрел подразумевает ветвление... Не знаю как ты собираешься на 8 ходов хранить таблитсы...
    Биты рулят лучше байтов, байты рулят шустрее!
    View, Звук, Цвет

  5. #34
    Master
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    961
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от GriV Посмотреть сообщение
    Речь про спектрум или вообще?
    Для начала - хотя бы вообще, а потом будет видно, можно ли реализовать алгоритм на Спектруме, сохранив его эффективность (хотя бы частично).

    У меня в этом деле такой подход, чтобы двигаться к решению постепенно и не пытаться заткнуть сразу все дыры.
    Цитата Сообщение от GriV Посмотреть сообщение
    Даже если так, то хранение наиболее вероятных клеток подразумевает какое то хранение предыдущего состояния. Соотвественно каждый выстрел подразумевает ветвление... Не знаю как ты собираешься на 8 ходов хранить таблитсы...
    Ну смотри, допустим для начала простой случай - клетка с максимальной вероятностью одна после каждого выстрела. Ее координаты можно закодировать 7ю битами. После каждого хода идет ветвление на 2 направления: попал или не попал. Количество клеток для запоминания после каждого хода будет увеличиваться в 2 раза, так что мы имеем дело с суммой геометрической прогрессии. Для запоминания всех ветвлений из 8 ходов достаточно 511 координат, что равняется 448 байтам (у нас 7 бит на одну пару координат). Вполне приемлемо даже для Спектрума. Если клеток с макс. вероятностью больше одной после каждого хода - то таблица возрастет в несколько раз, но мне бы даже 32кБ было не жалко для такой таблицы, а то и под завязку забить всю память до 128К.

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

  6. #35
    Veteran Аватар для GriV
    Регистрация
    18.02.2005
    Адрес
    Набережные Челны
    Сообщений
    1,574
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Barmaley_m Посмотреть сообщение
    Для запоминания всех ветвлений из 8 ходов достаточно 511 координат
    Погоди, а разве не по количеству оставшихся клеток будет увеличиваться вероятность? И потом, ты хочешь использовать детерменированный алгоритм? Комп всегда будет начинать встрелать в клетку (1,1), потом (1,2) и т.д.? Тогда алгоритм будет уязвимым.
    Биты рулят лучше байтов, байты рулят шустрее!
    View, Звук, Цвет

  7. #36
    Master
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    961
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от GriV Посмотреть сообщение
    Погоди, а разве не по количеству оставшихся клеток будет увеличиваться вероятность?
    Что ты имеешь в виду?
    Цитата Сообщение от GriV Посмотреть сообщение
    И потом, ты хочешь использовать детерменированный алгоритм? Комп всегда будет начинать встрелать в клетку (1,1), потом (1,2) и т.д.? Тогда алгоритм будет уязвимым.
    Не совсем детерминированный. Для каждого хода будет выбор из нескольких клеток (положим, до 4х), и компьютер будет выбирать одну из них случайно.

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

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

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

    Наличие же некоторой, хоть и небольшой, случаности в выборе координат для следующего выстрела затрудняет адаптацию противника к нашей стратегии. Так же как можно сделать вариацию алгоритма угадывания чисел от 1 до 100 с добавкой случайности, которая уменьшила бы шансы противника реализовать наихудший случай при угадывании, при этом не увеличивая число ходов для наихудшего случая, если он все-таки реализуется.
    Последний раз редактировалось Barmaley_m; 01.05.2011 в 23:41. Причина: из-за глюка сети сообщение было отправлено дважды

  8. #37
    Veteran Аватар для GriV
    Регистрация
    18.02.2005
    Адрес
    Набережные Челны
    Сообщений
    1,574
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Barmaley_m Посмотреть сообщение
    Что ты имеешь в виду?
    Ты написал что на кучу комбинаций у тебя уйдёт около 500 байт.
    Я спрашиваю - а разве не по оставшимся клеткам будет идти расчёт?
    Ты же не можешь перерасчитывать каждый раз в ходе игры, ты хранишь все варианты развитий. Я понимаю так: ты можешь хранить каждый выстрел семью битами, но в итоге у тебя каждый следующий выстрел значительно усложняет варианты.
    Я мыслю так: при выстреле в первую клетку у тебя останется 99 клеток (вне зависимости, попадание или нет, попадание просто резко сузит необходимые варианты обстрела).
    Соотвественно вначале у тебя 100 вариантов выстрела, потом 99, потом 98 и т.д. И каждую из комбинаций тебе надо хранить.

    Я тут вижу, что ты можешь кодировать только наиболее вероятные клетки для следующих выстрелов, но всё равно это тебе надо 7 бит на каждую вероятную клетку, в итоге - чтобы алгоритм не был детерменированным, тебе надо хранить минимум 2 ячейки далее. На каждый новый ход по 14 бит данных на промах (наиболее вероятные ячейки следующих двух ходов) и 14 бит данных на попадание (аналогично). Каждый ход добавляет 28 бит данных, каждые 7 бит которых порождают ещё 28 бит данных и т.д. Т.е. таблица каждый следующий ход вариант ветвления увеличивается в 4 раза . Даже для такого примитивного случая тебе надо будет 14*(4^N) бит на маску некоего хода N. Вся память, занимаемая масками будет записана как Mem = 14 * (1 + 4 + 4^2 + 4^3 + 4^4 + 4^5 + .... + 4^N), для 8 ходов это будет 152916,75 байт, почти влезло в 128к...
    Беру свои слова назад... по крайней мере это близко к осуществимости...
    Если продумать формат, чтобы занимаемая память была меньше 28 бит на выстрел, тогда возможно, получится уложить даже 9 или 10 ходов.
    Последний раз редактировалось GriV; 02.05.2011 в 01:29.
    Биты рулят лучше байтов, байты рулят шустрее!
    View, Звук, Цвет

  9. #38
    Veteran Аватар для GriV
    Регистрация
    18.02.2005
    Адрес
    Набережные Челны
    Сообщений
    1,574
    Спасибо Благодарностей отдано 
    0
    Спасибо Благодарностей получено 
    0
    Поблагодарили
    0 сообщений
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Вот, немного не в тему, ребята рассчитали судоку для однозначного разрешения. Там тоже матстат и аналитика: В Ирландии рассчитали минимальное количество подсказок в судоку
    Биты рулят лучше байтов, байты рулят шустрее!
    View, Звук, Цвет

Страница 4 из 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

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

Ваши права

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