Гость
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Террорист против генерала. Алгоритм. / 25 сообщений из 108, страница 1 из 5
25.09.2020, 14:53
    #40002560
Eolt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Допустим есть игровое поле на подобие шахматного 1000x1000 точек имитирующее лес. Один игрок играет за террориста, второй за генерала. Задача террориста - разместить мины в лесу, одна мина в одной точке координат. Задача генерала проложить маршрут через игровое поле для солдат, если точка маршрута пересекается с миной - солдат погибает и очко записывается террористу, если маршрут солдата пересекает игровое поле не встречаясь с миной, очко генералу. Играют 10 раундов, в каждом раунде террорист размещает 100 мин, а генерал прокладывает 100 маршрутов для солдат, после чего проверяют пересечение маршрутов с минами и подсчитывают очки.
После каждого раунда генерал видит где были расположены мины, а террорист как проложены маршруты генерала.

Отсюда у меня вопросы

1. Может ли террорист придумать оптимальный алгоритм раскладки мин, анализирую статистику маршрутов генерала?
2. Может ли генерал придумать оптимальный алгоритм прокладки маршрутов, анализирую как террорист раскладывает мины?
...
Рейтинг: 0 / 0
25.09.2020, 15:10
    #40002564
Eolt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Да забыл добавить. Что террорист и генерал это не живые люди. Это ИИ. Который хитрить не умеет.
...
Рейтинг: 0 / 0
25.09.2020, 15:14
    #40002565
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
ИМХО если солдаты идут друг-за-другом по случайно выбранной траектории, то генерал выиграл.
...
Рейтинг: 0 / 0
25.09.2020, 15:19
    #40002566
Eolt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Dima T
ИМХО если солдаты идут друг-за-другом по случайно выбранной траектории, то генерал выиграл.


Тогда террорист может начать раскладывать мины тоже в случайном порядке. И согласно теории вероятностей должна быть ничья?
...
Рейтинг: 0 / 0
25.09.2020, 15:26
    #40002570
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Eolt
Dima T
ИМХО если солдаты идут друг-за-другом по случайно выбранной траектории, то генерал выиграл.


Тогда террорист может начать раскладывать мины тоже в случайном порядке. И согласно теории вероятностей должна быть ничья?
навскидку подозреваю, что если один из оппонентов может что-то анализировать и улучшать на основе ходов другого, то тот другой сразу применит рандомную стретегию.
...
Рейтинг: 0 / 0
25.09.2020, 15:28
    #40002573
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Eolt
Dima T
ИМХО если солдаты идут друг-за-другом по случайно выбранной траектории, то генерал выиграл.


Тогда террорист может начать раскладывать мины тоже в случайном порядке. И согласно теории вероятностей должна быть ничья?

Нет. Для упрощения пусть солдаты идут прямо, тогда чтобы выиграть надо на их пути поставить минимум 51 мину, остается 49 которые никак не помогут, т.е. дорожка мин может быть только одна, а всего дорожек, по которым могут пойти солдаты - 1000, вот и получается что вероятность победить у генерала 0.999.
...
Рейтинг: 0 / 0
25.09.2020, 15:29
    #40002574
Eolt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Значит генерал всегда выигрывает?
...
Рейтинг: 0 / 0
25.09.2020, 15:36
    #40002582
Eolt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Имя пользователя1
Eolt
пропущено...


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


Допустим оба применяют случайную стратегию. Девять раундов подряд. По идее счет должен быть ничейный. А в десятом раунде генерал отказывается от случайной стратегии и всех солдат пускает по-одному краю поля, террорист же разложит мины в случайном порядке и проиграет. Так что случайная стратегия не всегда выиграшная.
...
Рейтинг: 0 / 0
25.09.2020, 15:38
    #40002584
Eolt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Eolt
Допустим оба применяют случайную стратегию. Девять раундов подряд. По идее счет должен быть ничейный. А в десятом раунде генерал отказывается от случайной стратегии и всех солдат пускает по-одному краю поля, террорист же разложит мины в случайном порядке и проиграет. Так что случайная стратегия не всегда выиграшная.


Это вроде называется систематическая ошибка выжившего.
...
Рейтинг: 0 / 0
25.09.2020, 15:42
    #40002586
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Eolt
Значит генерал всегда выигрывает?

Выигрывает в 999 случаях из 1000, т.е. в 10 раундах - всегда.
...
Рейтинг: 0 / 0
25.09.2020, 15:52
    #40002590
Alibek B
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Eolt
Тогда террорист может начать раскладывать мины тоже в случайном порядке. И согласно теории вероятностей должна быть ничья?

100 мин на 1000000 точек?
Тут террорист может выиграть только в одном случае — если генерал начинает игру с фиксированной точки и она обкладывается минами.
...
Рейтинг: 0 / 0
25.09.2020, 15:55
    #40002592
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Dima T
Eolt
пропущено...


Тогда террорист может начать раскладывать мины тоже в случайном порядке. И согласно теории вероятностей должна быть ничья?

Нет. Для упрощения пусть солдаты идут прямо, тогда чтобы выиграть надо на их пути поставить минимум 51 мину, остается 49 которые никак не помогут, т.е. дорожка мин может быть только одна, а всего дорожек, по которым могут пойти солдаты - 1000, вот и получается что вероятность победить у генерала 0.999.


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

Между прочим, именно так, без искусственного интеллекта, всегда преодолевались минные поля при отсутствии времени на разминирование.
( с появлением танков, стали пускать танки, при возможности - с катками) в качестве разминировщиков)

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

Первый дошедший определяет путь для всех оставшихся - это единственная и не случайная стратегия генерала,
и "много маршрутов" ему не надо, если стоит цель довести хотя бы одного.
...
Рейтинг: 0 / 0
25.09.2020, 16:06
    #40002594
982183
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Требования к маршруту солдатА какие?
...
Рейтинг: 0 / 0
25.09.2020, 16:15
    #40002597
982183
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Eolt
1. Может ли террорист придумать оптимальный алгоритм раскладки мин, анализирую статистику маршрутов генерала?
2. Может ли генерал придумать оптимальный алгоритм прокладки маршрутов, анализирую как террорист раскладывает мины?


Может, если противная сторона не будет видеть его действий.
...
Рейтинг: 0 / 0
25.09.2020, 18:47
    #40002647
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
В задаче не сказано какой длины должен быть маршрут.
...
Рейтинг: 0 / 0
25.09.2020, 23:32
    #40002728
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
booby
Первый дошедший определяет путь для всех оставшихся - это единственная и не случайная стратегия генерала,
и "много маршрутов" ему не надо, если стоит цель довести хотя бы одного.
Не проходит по условию. Ген сначала планирует, потом солдаты колются, плачут, но идут лесом как приказано.

maytonВ задаче не сказано какой длины должен быть маршрут. И какой формы тоже. И минёр не знает заранее. Мож им там надо только на покурить и оправиться (т.е. зайти за кустик и вернуться). Какие реалии стоят за задачей, кто знает?
...
Рейтинг: 0 / 0
25.09.2020, 23:47
    #40002734
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
После каждого раунда генерал видит где были расположены мины, а террорист как проложены маршруты генерала.

После этой рекомендации мне почему-то вспоминается игра камень-ножницы-бумага.

И если копнуть в теорию. Или в теорию игр то наверное нам хватило-бы и более простой постановки задачи
типа "игры в кучки". В таких играх человек неизбежно проигрывает ИИ т.к. первый просто обладает "кривой"
статистикой (чаще может выбрасывать камень или бумагу) и ограниченной памятью.

В случае с ИИ с двух сторон - думаю задача останется без ответа. Всё будет зависеть от того кто программирол
террора и генерала. И наверное имеет смысл разделить задачи между двумя разными разработчиками.

Как в автоматизации тестирования. Код пишет программист и авто-тесты - другой разраб. Тогда схватка
мне видется более-менее интересной.

Вобщем тут нечего теоретизировать. Навскидку ответы думаю такие:

1. Да
2. Да

Может-ли кто-то из них регулярно выигрывать? Не знаю....
...
Рейтинг: 0 / 0
26.09.2020, 00:10
    #40002741
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Варианты.
Планировать что-то вроде броуновского движения, а этот гад разбрасывает случайно в матрице.
Вспомнилась тактика "морского боя" - кучка и штучка. 99 идут одним путём + одиночка другим путём.

Кстати непонятно, мины одноразовые или нет? иначе это грабли, а не мины))
...
Рейтинг: 0 / 0
26.09.2020, 00:56
    #40002748
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Eolt
Да забыл добавить. Что террорист и генерал это не живые люди. Это ИИ. Который хитрить не умеет.
Тогда ответ - оба могут.
Тот ИИ, который первым вычислит алгоритм стратегии соперника всегда будет побеждать, Потому что будет знать, какую именно стратегию будет использовать соперник. А соперник знать не будет, потому что на каждой итерации будет получать на вход нечто новое.
...
Рейтинг: 0 / 0
26.09.2020, 01:14
    #40002749
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Соколинский Борис,

Хорошо, как именно и в серии какой длины, должен гарантированно выигрывать минёр против такой,
заранее известной стратегии генерала:

Генерал всегда будет сначала бросать тысячегранник,
а затем пускать всех солдат друг за другом по выпавшей на нём вертикали.
Конечно, тысячегранник однороден и центр тяжести не смещен => распределение выпаданий граней равномерное.


?
...
Рейтинг: 0 / 0
26.09.2020, 07:07
    #40002764
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Eolt
1. Может ли террорист придумать оптимальный алгоритм раскладки мин, анализирую статистику маршрутов генерала?
Обычная лотерея, как 49 или 36, только очень много цифр (мин).

Сначала необходимо анализировать статистику по 6 из 36 числам, когда только 1 попадание,
а уже потом думать над 100 цифрами (координаты поля) из 1000000.
...
Рейтинг: 0 / 0
26.09.2020, 08:34
    #40002776
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
booby

Хорошо, как именно и в серии какой длины, должен гарантированно выигрывать минёр против такой,
заранее известной стратегии генерала:

Я об общем принципе.
В данном случае, предположим, ИИ минера вычислит RandSeed генерала.
...
Рейтинг: 0 / 0
26.09.2020, 08:37
    #40002777
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Может ли солдат шагать по диагонали ?
...
Рейтинг: 0 / 0
26.09.2020, 08:39
    #40002779
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Знает ли террорист точку Б в которую генерал двигает колонну?
...
Рейтинг: 0 / 0
26.09.2020, 11:49
    #40002813
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Террорист против генерала. Алгоритм.
Как действует генерал, проходя квадрат:

справа налево, сверху вниз?
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Террорист против генерала. Алгоритм. / 25 сообщений из 108, страница 1 из 5
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]