242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
|
1 | |
Расчет вероятности для игры "Охота на Лис"09.04.2021, 11:04. Показов 4904. Ответов 54
Метки нет Все метки)
(
Пишу игрушку «Охота на Лис» (надеюсь, правила известны, не буду на них здесь останавливаться). Хочу прикрутить бота, чтобы можно было играть против компьютера.
Бот не должен «подсматривать» расклад, он должен рассчитывать вероятность нахождения Лисы по заданным координатам и на основании этой вероятности делать ход. Сейчас я рассчитываю вероятность очень простым способом, он не совсем верный, но дает неплохой результат. Хочу рассчитывать вероятность правильно. ![]() Схему расчетов я подготовил в файле .doc (Word97), там нет ни макросов, не вирусов, там несколько небольших таблиц с пояснениями. Если подобный способ неприемлем, закину в виде картинок прямо сюда.
0
|
09.04.2021, 11:04 | |
09.04.2021, 11:04 | |
Ответы с готовыми решениями:
54
"охота на лис" геморно или не очень? Сапер: расчет вероятности, расчет вероятности нахождения мины Игра "Охота на лис" нужно написать алгоритм |
![]() |
|
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 |
Размер поля у меня меняется. Может быть и 10х10, может и 50х50. Так же меняется и количество Лис. Так что накапливая информацию в проверенных ячейках и вычисляя вероятности, бот, исходя из максимальных чисел, определяет куда примерно ему "стрелять". Вот, один из вариантов реального расклада. Зеленым цветом выделены ячейки с максимальной вероятностью.
0
|
![]() |
|
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 |
Точка (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 минуту Разумеется, я считаю только неоткрытых Лис.
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
|
![]() |
|
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 |
0
|
Модератор
![]() 3083 / 2231 / 466
Регистрация: 26.03.2015
Сообщений: 8,675
|
|
12.04.2021, 10:42 | 10 |
Как составить такую систему после двух тестов?
Все эти A11=A21 становятся неправильными.
0
|
Модератор
![]() 3083 / 2231 / 466
Регистрация: 26.03.2015
Сообщений: 8,675
|
|
12.04.2021, 10:49 | 11 |
Можно упростить алгоритм.
Сначала несколько выстрелов (зависит только от размера поля) по предустановленным точкам. Чтобы незакрытая выстрелами часть поля была не больше 4n. Затем ищем произвольную допустимую комбинацию лис и стреляем по любой из них.
0
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
|
12.04.2021, 11:03 [ТС] | 12 |
Честно говоря, я не очень въехал. Та система, которую я привел, тоже неправильная, она не до конца составлена. Уравнений должно быть столько же, сколько неизвестных. Вот, более полный вариант расклада на предыдущей картинке:
0
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
|
12.04.2021, 11:08 [ТС] | 13 |
Этот вариант мы тоже обдумываем - после каждого "выстрела" подбирать набор допустимых комбинаций и "стрелять" уже по ним. Но, мне кажется, там будет слишком много расчетов, бот будет сильно тупить. Допустим, поле 40х40 при 20 Лисах - это немаленькая куча комбинаций. Понятно, что в процессе их количество будет уменьшаться, но в начале будет треш.
![]()
0
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
|
12.04.2021, 11:40 [ТС] | 15 |
0
|
Модератор
![]() 3083 / 2231 / 466
Регистрация: 26.03.2015
Сообщений: 8,675
|
|
12.04.2021, 11:45 | 16 |
Не совсем так в общем случае. Например, выстрелом в центр мы можем покрыть всё поле 3х3, но такой выстрел несёт мало информации. Поэтому для небольших n лучше задать точки вручную, а для больших прописать простой алгоритм вычисления точек для первых выстрелов.
0
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
|
12.04.2021, 12:00 [ТС] | 17 |
Раз уже дискуссия приняла такой характер, должен добавить дополнительную информацию.
![]() Концепт моей игрушки предусматривает пеленг ячеек не только по 8 направлениям (ходом Ферзя), но и всеми шахматными фигурами. Поэтому расчет вероятности еще и усложняется тем, какой именно пеленг активен в текущий момент времени. Добавлено через 9 минут Удалось зарегистрироваться, скачал 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 |
Ну, а как определить для бота ячейки-кандидаты для "прострела"? Вероятность - это первое, что пришло в голову.
При одинаковой вероятности бот "стреляет" рандомно. Когда вероятность изменяется - предпочтения отдаются ячейкам с большей вероятностью. Сейчас бот играет достаточно сильно, чтобы задуматься об уровнях сложности даже при моем неверном алгоритме подсчета вероятности. На больших уровнях человек выигрывает с очень большим трудом. На уровнях от 30х30 даже не уверен, что человек сможет выиграть. Но игрушка - это хобби, проверка различных алгоритмов и идей. Поэтому хочется математически грамотную стратегию, чтобы закрыть вопрос. ![]()
0
|
Модератор
![]() 3083 / 2231 / 466
Регистрация: 26.03.2015
Сообщений: 8,675
|
|
12.04.2021, 13:10 | 20 |
Поле 3х3 с 1 лисой. Вероятности одинаковы, но в центр стрелять невыгодно. После выстрела в центр в худшем случае вероятности будут 1/8, а после выстрела в угол - 1/6. То есть, если стрелять в угол, то вероятность попасть вторым выстрелом будет заметно выше.
Добавлено через 3 минуты То есть, кроме стратегии "стрельба по лисам" есть стратегия "уменьшение количества комбинаций". Предположу, что оптимальной будет какая-то комбинация этих стратегий.
0
|
12.04.2021, 13:10 | |
12.04.2021, 13:10 | ||||||
Помогаю со студенческими работами здесь
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-фреймворков, предоставляет. . .
|