Форум программистов, компьютерный форум, киберфорум Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.84/25: Рейтинг темы: голосов - 25, средняя оценка - 4.84
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
1

Расчет вероятности для игры "Охота на Лис"

09.04.2021, 11:04. Показов 4904. Ответов 54
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Пишу игрушку «Охота на Лис» (надеюсь, правила известны, не буду на них здесь останавливаться). Хочу прикрутить бота, чтобы можно было играть против компьютера.
Бот не должен «подсматривать» расклад, он должен рассчитывать вероятность нахождения Лисы по заданным координатам и на основании этой вероятности делать ход.
Сейчас я рассчитываю вероятность очень простым способом, он не совсем верный, но дает неплохой результат.
Хочу рассчитывать вероятность правильно.

Схему расчетов я подготовил в файле .doc (Word97), там нет ни макросов, не вирусов, там несколько небольших таблиц с пояснениями.
Если подобный способ неприемлем, закину в виде картинок прямо сюда.
Вложения
Тип файла: doc Охота на Лис - расчет вероятности.doc (106.0 Кб, 48 просмотров)
0
09.04.2021, 11:04
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
09.04.2021, 11:04
Ответы с готовыми решениями:

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

Сапер: расчет вероятности, расчет вероятности нахождения мины
Доброго времени суток! Помогите пожалуйста составить алгоритм для решения задачи. Имеется игровое поле для игры в сапер. Оно...

Игра "Охота на лис" нужно написать алгоритм
Сделал алгоритм, но он работает плохо. Не выигрывает последние 3 и 4 тест. Поспособствуйте пожалуйста написанию алгоритма главное как...

54
 Аватар для vantfiles
1017 / 1906 / 178
Регистрация: 07.05.2013
Сообщений: 3,931
Записей в блоге: 12
09.04.2021, 12:54 2
А зачем вообще нужны вероятности?

1 0 1 0 0 0 0 0
0 1 1 1 0 0 0 0
1 1(1)1 1 1 1 1
0 1 1 1 0 0 0 0
1 0 1 0 1 0 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 0 1 0
0 0 1 0 0 0 0 1

1 0 1 0 1 0 0 0
0 1 1 1 1 0 0 0
2 1(1)1 2 1 1 1
0 2 1 1 1 0 0 1
1 0 2 0 2 0 1 0
0 0 1 1 1 2 0 0
1 1 2 1(1)1 2 1
0 0 1 1 1 1 0 1
При этом нужно учитывать уже открытых лис. Если у открытой точки количество лис соответствует, значит на ее "звездочке" вообще ловить нечего.

Кстати, у бота есть два варианта хода - либо пробовать бить лис по максимальным значениям - либо пытаться накрыть как можно больше неперекрытых точек.
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
09.04.2021, 13:06  [ТС] 3
Цитата Сообщение от vantfiles Посмотреть сообщение
А зачем вообще нужны вероятности?
Размер поля у меня меняется. Может быть и 10х10, может и 50х50. Так же меняется и количество Лис. Так что накапливая информацию в проверенных ячейках и вычисляя вероятности, бот, исходя из максимальных чисел, определяет куда примерно ему "стрелять". Вот, один из вариантов реального расклада. Зеленым цветом выделены ячейки с максимальной вероятностью.
Миниатюры
Расчет вероятности для игры "Охота на Лис"  
0
 Аватар для vantfiles
1017 / 1906 / 178
Регистрация: 07.05.2013
Сообщений: 3,931
Записей в блоге: 12
09.04.2021, 13:55 4
Если X по горизонтали, то почему точка 10,7 на которую звенит сразу три пеленга имеет вероятность меньше, чем допустим точка 8,8 на которую звенит всего один пеленг?

Еще подумал... Для той же точки 8,8 вероятность должна быть равна 6/(количество зеленых точек)

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

Добавлено через 1 минуту
Ну логично - если есть пеленг со значением 1 и на одной из точек сидит лиса, вероятность всех остальных точек = (1-1)/к-во пеленгуемых(зеленых) точек, то есть ноль.
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
09.04.2021, 14:06  [ТС] 5
Цитата Сообщение от vantfiles Посмотреть сообщение
Для той же точки 8,8 вероятность должна быть равна 6/(количество зеленых точек)
Точка (8,8) пеленгуется с точки (7,9), там, где видно 6 Лис. Всего с точки (7,9) пеленгуется 54 ячейки. 6 Лис на 54 ячейки дает ту самую вероятность в 11% (6/54)

Для точки (10,7) расчет следующий:
С точки (3,7), где видно 3 Лисы, пеленгуется 46 ячеек. 3 Лисы на 46 ячеек дают 6.5% = ~7%.
C точки (15,3), где тоже 3 Лисы, пеленгуется 42 ячейки. 3 Лисы на 42 ячейки дают 7%.
С точки (10,4), где видно 5 Лис, пеленгуется 48 ячеек. 5 Лис на 48 ячеек дают 10%.
Т.е., для ячейки (10,7) мы имеем 3 варианта вероятности. Так вот, из-за того, что я не знаю, как правильно поступить в этом случае, я беру максимальную вероятность. В данном случае, это 10%.

Добавлено через 1 минуту
Цитата Сообщение от vantfiles Посмотреть сообщение
Да, и из пеленга нужно вычитать количество найденных по нему лис.
Разумеется, я считаю только неоткрытых Лис.
0
677 / 551 / 74
Регистрация: 20.09.2014
Сообщений: 3,605
10.04.2021, 12:25 6
Задача оптимизационная и, как правильно отмечено, модель вероятностная. Целевая функция оптимизации - математическое ожидание раскрытых лис, эту функцию нужно максимизировать. Эквивалентная целевая функция: минимизация информационной энтропии.

Надо аккуратно определить пространство элементарных событий.
Пусть поле n x n, и количество нераскрытых лис k. Тогда имеем дискретное распределение по n^2 клеток и по (k+1) значениям количества лис. Пространство элементарных событий - дискретное пространство размерности n^2*(k+1), в каждой точке этого пространства изначально равная вероятность 1/(n^2*(k+1)).
После сеанса пеленга раскрывается информация о центральной точке, число k может уменьшиться - это сократит пространство. Прострелы радиолокатора также обнуляет вероятность событий обнаружения k > k0 лис в простреливаемых клетках, где k0 - пропеленгованные лисы.

Итого: создайте трехмерный массив булевых значений размерности n x n x (k+1), заполните значениями true (false - событие невероятно, true - событие вероятно). Значения true потихоньку будут заменяться на false.

Если сделать некий произвольный ход, то.... Блин, в следующий раз доведу мысль до конца.)
0
 Аватар для vantfiles
1017 / 1906 / 178
Регистрация: 07.05.2013
Сообщений: 3,931
Записей в блоге: 12
10.04.2021, 14:15 7
Вот тут все вероятности расписаны:

https://www.elibrary.ru/item.asp?id=39160322

Правда для чтения требуется регистрация, я там накидал от балды в форму - прокатывает.
Сам пдф-ник не буду выкладывать, не знаю как насчет копирайтов.
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
10.04.2021, 23:23  [ТС] 8
Спасибо за наводку! Почитаю, поизучаю.
Мои коллеги предложили практически 100% правильный расчет вероятности - это система линейных уравнений с n*n неизвестными (где n - размерность поля). При каждом простреле количество переменных уменьшается на 1 и соответственно меняется и система.
Правда, предварительно эту систему нужно еще грамотно составить, там достаточно много возни.
Вот, пример для поля 3х3, где расположено 3 Лисы. "*" обозначены Лисы, протестирована одна ячейка (3,1)
Миниатюры
Расчет вероятности для игры "Охота на Лис"  
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
12.04.2021, 00:30  [ТС] 9
Цитата Сообщение от Mikhaylo Посмотреть сообщение
Если сделать некий произвольный ход, то.... Блин, в следующий раз доведу мысль до конца.)
Жду доведенной мысли.
0
Модератор
Эксперт функциональных языков программирования
3083 / 2231 / 466
Регистрация: 26.03.2015
Сообщений: 8,675
12.04.2021, 10:42 10
Цитата Сообщение от Constcat Посмотреть сообщение
это система линейных уравнений с n*n неизвестными
Как составить такую систему после двух тестов?
Все эти A11=A21 становятся неправильными.
0
Модератор
Эксперт функциональных языков программирования
3083 / 2231 / 466
Регистрация: 26.03.2015
Сообщений: 8,675
12.04.2021, 10:49 11
Цитата Сообщение от Constcat Посмотреть сообщение
он должен рассчитывать вероятность нахождения Лисы по заданным координатам и на основании этой вероятности делать ход
Можно упростить алгоритм.

Сначала несколько выстрелов (зависит только от размера поля) по предустановленным точкам. Чтобы незакрытая выстрелами часть поля была не больше 4n.
Затем ищем произвольную допустимую комбинацию лис и стреляем по любой из них.
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
12.04.2021, 11:03  [ТС] 12
Цитата Сообщение от Shamil1 Посмотреть сообщение
Как составить такую систему после двух тестов?
Все эти A11=A21 становятся неправильными.
Честно говоря, я не очень въехал. Та система, которую я привел, тоже неправильная, она не до конца составлена. Уравнений должно быть столько же, сколько неизвестных. Вот, более полный вариант расклада на предыдущей картинке:
Миниатюры
Расчет вероятности для игры "Охота на Лис"  
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
12.04.2021, 11:08  [ТС] 13
Цитата Сообщение от Shamil1 Посмотреть сообщение
Сначала несколько выстрелов (зависит только от размера поля) по предустановленным точкам. Чтобы незакрытая выстрелами часть поля была не больше 4n.
Затем ищем произвольную допустимую комбинацию лис и стреляем по любой из них.
Этот вариант мы тоже обдумываем - после каждого "выстрела" подбирать набор допустимых комбинаций и "стрелять" уже по ним. Но, мне кажется, там будет слишком много расчетов, бот будет сильно тупить. Допустим, поле 40х40 при 20 Лисах - это немаленькая куча комбинаций. Понятно, что в процессе их количество будет уменьшаться, но в начале будет треш.
0
 Аватар для vantfiles
1017 / 1906 / 178
Регистрация: 07.05.2013
Сообщений: 3,931
Записей в блоге: 12
12.04.2021, 11:13 14
Цитата Сообщение от Constcat Посмотреть сообщение
в начале будет треш
Вот и мне кажется, что начальная стратегия должна быть такова, чтобы покрыть максимум непрострелянных полей.

Добавлено через 26 секунд
ps: статью не читали?
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
12.04.2021, 11:40  [ТС] 15
Цитата Сообщение от vantfiles Посмотреть сообщение
ps: статью не читали?
Если честно, запарился с регистрацией.
0
Модератор
Эксперт функциональных языков программирования
3083 / 2231 / 466
Регистрация: 26.03.2015
Сообщений: 8,675
12.04.2021, 11:45 16
Цитата Сообщение от vantfiles Посмотреть сообщение
чтобы покрыть максимум непрострелянных полей
Не совсем так в общем случае. Например, выстрелом в центр мы можем покрыть всё поле 3х3, но такой выстрел несёт мало информации. Поэтому для небольших n лучше задать точки вручную, а для больших прописать простой алгоритм вычисления точек для первых выстрелов.
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
12.04.2021, 12:00  [ТС] 17
Цитата Сообщение от Shamil1 Посмотреть сообщение
Не совсем так в общем случае. Например, выстрелом в центр мы можем покрыть всё поле 3х3, но такой выстрел несёт мало информации. Поэтому для небольших n лучше задать точки вручную, а для больших прописать простой алгоритм вычисления точек для первых выстрелов.
Раз уже дискуссия приняла такой характер, должен добавить дополнительную информацию.
Концепт моей игрушки предусматривает пеленг ячеек не только по 8 направлениям (ходом Ферзя), но и всеми шахматными фигурами. Поэтому расчет вероятности еще и усложняется тем, какой именно пеленг активен в текущий момент времени.

Добавлено через 9 минут
Цитата Сообщение от vantfiles Посмотреть сообщение
ps: статью не читали?
Удалось зарегистрироваться, скачал pdf-ку.
0
Модератор
Эксперт функциональных языков программирования
3083 / 2231 / 466
Регистрация: 26.03.2015
Сообщений: 8,675
12.04.2021, 12:29 18
Constcat,
Для начала нужно сформулировать требования к искину. Предположу, что это - минимизация МО количества ходов.

Затем нужно определить общую стратегию. Нужно ли нам считать эти вероятности?

Если нужно, то написать подсчёт вероятностей "в лоб", то есть, не оптимально.
1. Используя этот код можно проверить наши предположения относительно общей стратегии.
2. Используя этот код можно проверять оптимизированные алгоритмы подсчёта вероятностей.
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
12.04.2021, 12:36  [ТС] 19
Цитата Сообщение от Shamil1 Посмотреть сообщение
Затем нужно определить общую стратегию. Нужно ли нам считать эти вероятности?
Ну, а как определить для бота ячейки-кандидаты для "прострела"? Вероятность - это первое, что пришло в голову.
При одинаковой вероятности бот "стреляет" рандомно. Когда вероятность изменяется - предпочтения отдаются ячейкам с большей вероятностью.
Сейчас бот играет достаточно сильно, чтобы задуматься об уровнях сложности даже при моем неверном алгоритме подсчета вероятности. На больших уровнях человек выигрывает с очень большим трудом. На уровнях от 30х30 даже не уверен, что человек сможет выиграть.
Но игрушка - это хобби, проверка различных алгоритмов и идей. Поэтому хочется математически грамотную стратегию, чтобы закрыть вопрос.
0
Модератор
Эксперт функциональных языков программирования
3083 / 2231 / 466
Регистрация: 26.03.2015
Сообщений: 8,675
12.04.2021, 13:10 20
Цитата Сообщение от Constcat Посмотреть сообщение
При одинаковой вероятности бот "стреляет" рандомно.
Поле 3х3 с 1 лисой. Вероятности одинаковы, но в центр стрелять невыгодно. После выстрела в центр в худшем случае вероятности будут 1/8, а после выстрела в угол - 1/6. То есть, если стрелять в угол, то вероятность попасть вторым выстрелом будет заметно выше.

Добавлено через 3 минуты
То есть, кроме стратегии "стрельба по лисам" есть стратегия "уменьшение количества комбинаций". Предположу, что оптимальной будет какая-то комбинация этих стратегий.
0
12.04.2021, 13:10
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
12.04.2021, 13:10
Помогаю со студенческими работами здесь

Игра "Охота на лис". Нужны примеры
Нужно написать эту игру на C#. Представление как это сделать поверхностное. Если кто поделится, буду очень благодарен.

Тупик по программе "Охота на лис"
Может,кто идею подкинуть,как число лис в сумме находится в одном столбце и строке с выстрелом,игра консольная без графики,и когда игрок...

"Охота на лис", нужны примеры
Нужно написать программу "Охота на лис" на с#. Идей.нет. У кого есть - скиньте пжслста.

Игра "Охота на лис"
Друзья, срочно нужно написать игру "Охота на лис". Если у кого-то есть готовый код на питоне, можете, пожалуйста, поделиться?

Игра "Охота на лис"
Игра похожа очень на "Сапёр". Написана на c# 2010. Даны 4 уровня сложности.Разработал свой алгоритм,но он выигрывает только 1-го игрока...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Новые блоги и статьи
Использование кэша Laravel - полный гайд
bytestream 18.02.2025
Кэширование - один из наиболее эффективных способов повышения производительности веб-приложений. В современном мире, где скорость загрузки страниц напрямую влияет на удержание пользователей и. . .
Создаем REST API в Laravel с аутентификацией через Passport
bytestream 18.02.2025
Разработка современных веб-приложений все чаще требует создания надежного и хорошо структурированного API. REST API стал стандартом де-факто для построения взаимодействия между клиентской и серверной. . .
Пайплайны в Laravel - полный гайд
bytestream 18.02.2025
Разработка современных веб-приложений часто требует обработки сложных процессов, состоящих из множества последовательных шагов. Например, при создании системы комментариев может потребоваться. . .
Как правильно использовать @required в Symfony
bytestream 18.02.2025
При разработке приложений на Symfony мы часто сталкиваемся с необходимостью внедрения зависимостей. Фреймворк предоставляет несколько способов управления этим процессом, и одним из таких инструментов. . .
Система безопасности в Laravel: возможности и примеры
Wired 18.02.2025
Каждый день появляются новые виды атак и уязвимостей, которые могут поставить под угрозу конфиденциальные данные пользователей и функционирование всей системы. В этом контексте выбор надежного. . .
Давайте сравним Django и Laravel
Wired 18.02.2025
Django и Laravel - два мощных инструмента, которые часто сравнивают между собой. Оба фреймворка предлагают разработчикам богатый набор возможностей для создания масштабируемых веб-приложений, но. . .
Laravel или React - что лучше?
Wired 18.02.2025
В разработке веб выбор правильного инструмента часто определяет успех всего проекта. Особенно интересным представляется сравнение Laravel и React - двух популярных технологий, которые часто. . .
Laravel 11: новые возможности, гайд по обновлению
Wired 18.02.2025
Laravel 11 - это новая масштабная версия одного из самых популярных PHP-фреймворков, выпущенная в марте 2024 года. Эта версия продолжает традицию внедрения передовых технологий и методологий. . .
Миграции в Laravel
Wired 18.02.2025
Разработка веб-приложений на Laravel неразрывно связана с управлением структурой базы данных. При работе над проектом часто возникает необходимость вносить изменения в схему базы данных - добавлять. . .
Аутентификация в Laravel
Wired 18.02.2025
В современном мире веб-разработки безопасность пользовательских данных становится критически важным аспектом любого приложения. Laravel, как один из самых популярных PHP-фреймворков, предоставляет. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru