Игра полковника Блотта #731396

Остались программисты на ресурсе? :-) Кто предложит лучшую стратегию? И алгоритм. Я вот потыкался и обнаружил, что матметодов подходящих не знаю (да и те что знаю порядком подзабыл), а матрица решений под перебор содержит много позиций и там думать надо как оптимально делать. Предположу, что прямой перебор будет долго считать.     Полковник Блотто имеет в своем распоряжении отряд из 100 человек. Завтра ему предстоит сразиться с вражеским отрядом, численность которого также составляет 100 человек.     Ночью перед битвой каждая сторона втайне размещает своих солдат произвольным способом на 9 полях сражений. На каждое поле сражений можно поставить любое целое число солдат от 0 до 100.     Утром начинается битва. На каждом из полей сражений выигрывает та сторона, которая выставила больше солдат. Если стороны выставили на некоторое поле одинаковое число солдат, то на этом поле объявляется ничья.     За победу на одном поле дается 1 очко, за ничью — 0.5 очков, за проигрыш — 0 очков. Платеж каждой из сторон равен суммарному количеству набранных очков.     Каждая сторона стремится победить на как можно большем числе полей, то есть набрать как можно большее число очков.

Берем Р-36орб и игра заканчивается.

Скучно, больше относится не к программистам, а к математикам. Не относится к стратегии, и тем более к жизненному опыту ведения боя :) Напоминает...

Да. Есть такая игра. Усложненная версия "Камень-Ножницы-Бумага" Лучшая стратегия - Используй рандом, потому что это проще, а результат такой же.

Я б разделил на 5 полей по 20 человек

Кстати, разбаньте , он бы тут смог что-нибудь подсказать(

Стратегия 1. 100/9 = 11 солдат в каждое поле + 1 случайно. Стратегия 2. 100/8 = 12 солдат в 4 поля и 13 солдат в 4 поля, одно поле пустое. Стратегия 3. 100/5 = 20 солдат в 5 полей и остальные пустые случайным образом. Выигрывает третья, как и в

В ответ я на 5 полей выставляю по одному солдату на 1 поле - 23 и на 3 поля - 24. Мой проигрыш по результатам боя будет лишь если все мои 4 основные команды попадут на 5 свободных полей. Вероятность этого: 5/9*4/8*3/7*2/6 = 0,039. Т.е. вероятность выигрыша 96%

Но проиграет с такой же гарантией первой стратегии

Первой стратегии проиграет 100% там у моей стратегии вероятности выигрыша нет вообще

+ Я ошибся свободных полей - 4, так что вероятность проигрыша 4/9*3/8*2/7*1/6=0,0079 более 99%

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

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

Я тут поразмыслил еще, есть такие соображения. 1) Перебор на деле не реализуем. 9 ячеек даже для двоичных чисел 1,0 даст 2 в девятой степени комбинаций и сравнивать каждую с каждой это еще куча вариантов. А если учесть что в ячейке не два числа 1 или 0, а числа диапазона от 1 до 100, то перебор на деле не реализуем. (Кстати, кто помнит матанализ, прикиньте сколько комбинаций будет на деле, успеет машина подсчитать их до тепловой смерти вселенной.) 2) Можно методом Монте Карло формировать запись в случайную ячейку случайного числа (далее вычитать его из общей суммы и продолжать пока ноль солдат не станет). Таким образом заполнить десяток записей, провести по ним мини турнир. Победителя мини турнира запомнить. Далее еще десяток записей сформировать и по ним определить победителя. Потом собрать победителей, провести турнир среди них. И кто этот турнир победителей выиграет, того считать оптимальным. В принципе, конечно, алгоритм машины и алгоритм человека различается. Т.е. вполне может быть что наборы человека будут не случайными, а станут к какому-то распределению  тяготеть. И если известно к какому, то можно играть машиной против них.

Предлагаю просто разместить на все 9 полей по: 1. 20 человеок 2. 20 человеок 3. 20 человеок 4. 20 человеок 5. 20 человеок 6. 0 человеок 7. 0 человеок 8. 0 человеок 9. 0 человеок При этом, в следующую битву, в случайном порядке выставлять армию. Вероятность побед будет примерно более 50%. :)

Если оба противника будут использовать твою стратегию, в большинстве случаев будет ничья, а никак больше 50%.

+ Всегда ничья

контр-стратегия: 21-21-21-21-4-3-3-3-3

Для любой стратегии, есть контр  стратегия. тут важна уже вероятность

да, хотел уж было написать эмулятор, полностью сравнивающий 2 стратегии, но беспокоит, что 9! х 9! = дофига (~131 млрд.)

Так бери рандом и интерполируй

То есть сила обороны и атаки у всех солдат обеих армий одинаковая?

А то я бы прокачал лучниц в лаборатории и заклинание исцеления или молнии. А еще лучше П.E.K.K.A выпустить

Вот же ж копипастер...

Что такое "Платеж каждой из сторон равен суммарному количеству набранных очков."? В чем заключается итоговая победа?

+Чем платят и влияют ли платежи на дальнейшие бои?

Такая игра напоминает мне игру в кооперируйся или отказывайся

Это элемент теории игр. Там есть такое понятие - платеж. Упрощенно если, например, футбольный матч закончился со счетом 2:3, то платеж первой команды 2, а второй 3. Да. Стратегий много. Но вот поиск оптимальной... Тут еще дело в том, что похожая задача политизирована. Там когда были между Гором и Бушем, вышла статья, где было показано, что Гор показал не лучший результат из-за неоптимальности своего алгоритма. Вполне возможен пул стратегий. Стратегий, чьи результаты будут выше остальных. Т.к. есть стратегии где результаты хуже, и при использовании их проигрыш гарантирован. По моим оценкам число стратегий порядка 91 в девятой. Это 400 квадрильонов. На интерпретаторе вообще результат не посчитается. , Склоняюсь к тому, что игра против человека и игра против машины различается. У человека есть набор типовых решений, если играть машиной против них надо это учитывать, чтобы получить преимущество. Я за 15 лет потерял аккаунтов 6-8. У NS помню было что-то толковое, надеюсь вернется под другим ником. Главное то не ник, подумаешь другие цифры на мониторе. Не уверен. Монте Карло психологию не учтет, типовой выбор человека. В реальной жизни вообще абстрактное мышление требуется редко. Но оно позволяет более медленно тупеть (если развитие на данном этапе не возможно).

По поводу игры против человека. Вот тут приводится анализ игры в варианте 6 полей 120 рыл. Там в 2 турнирах выиграла стратегия 2 31 31 31 23 2 (придуманная разными людьми). и в других крупных турнирах выигрывали вариации с усилением отдельных полей не до 31 а до большего числа или усилением слабого поля до 3.

С интересом прочитал, спасибо.

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

Это раздел, связанный с математикой . Компьютерные поигрушки в другой секции.

Можно усложнить задачу Выигрывает та команда у которой кол-во ост солд * кол-во побед будет больше кол-во побед = кол-во выйгранных ячеек кол-во ост солд  = разница на каждом поле

Зачем усложнять задачу? И на существующую по сути не предложено алгоритма. Даже для метода конкуренции среди случайных наборов (метода для которого и знаний не надо) не показано количество этих наборов для заданной достоверности и т.д. Ведь какая разница, взять 10,100 или 1000 случайных записей из 400 квадрильонов. Это доли процента не составит.

Раздел то да, но не эта игра:) Какая стратегия в угадывании решки или орла при подкидывании монетки? Никакой. Вот и тут никакой стратегии нет. Можно подобрать оптимальный набор чисел, исходя из общей психологии человека, но на этом все.

Ты не прав в корне. В это подробнее изложено для похожего случая.