Игры Блотто

  • Игры Блотто (Игры Полковника Блотто) представляют собой класс игр двух лиц с нулевой суммой, в которой задача игроков состоит в распределении ограниченных ресурсов по нескольким объектам (полям битв). В классической версии игры игрок, выставивший больше ресурсов на поле, выигрывает битву на этом поле, а суммарный выигрыш (цена игры) равен сумме выигранных битв.

    Хотя игра полковника Блотто была впервые опубликована Борелем (Borel) в 1921-м году, большинство вариаций классической игры не были решены до 91-го года. В 2006-м году Роберсон (Roberson) описал равновесную цену классической игры для любого числа полей и любого уровня ресурсов, а также характеристические множества равновесия для большинства вариаций классической игры.Игра названа в честь мифического Полковника Блотто из работы Гроса и Вагнера (Gross and Wagner) 1950-го года. Полковник был обязан найти оптимальное распределение своих солдат по N полям сражений, зная что:

    на каждом поле сторона, выставившая больше солдат, выигрывает, но

    ни одна сторона не знает, какое число солдат выставит противоположная сторона на каждом поле, и

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

Источник: Википедия

Связанные понятия

Функция Шпрага-Гранди широко используется в теории игр для нахождения выигрышной стратегии в комбинаторных играх, таких как игра Ним. Функция Шпрага-Гранди определяется для игр с двумя игроками, в которых проигрывает игрок, не имеющий возможности сделать очередной ход.
В теории игр, игра в нормальной или стратегической форме (англ. normal form) состоит из трех элементов: множества игроков, множества чистых стратегий каждого игрока, множества платежных функций каждого игрока. Таким образом, игру в нормальной форме можно представить в виде n-мерной матрицы (таблицы), элементы которой это n-мерные платежные вектора. Эта таблица называется платёжной матрицей (англ. payoff matrix).

Подробнее: Нормальная форма игры
Ним Витхоффа, или игра Витхоффа, — стратегическая математическая игра для двоих игроков с двумя кучками фишек. Игроки по очереди берут фишки из одной или обеих кучек; в последнем случае из обеих кучек берется поровну фишек. Выигрывает тот, кто забирает последнюю или последние фишки.
Равнове́сие Нэ́ша — концепция решения, одно из ключевых понятий теории игр. Так называется набор стратегий в игре для двух и более игроков, в котором ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют. Джон Нэш доказал существование такого равновесия в смешанных стратегиях в любой конечной игре.
Стохастическая игра (англ. stochastic game) в теории игр — повторяющаяся игра со случайными переходами состояний, разыгрываемая одним и более игроками.
Компьютерное го — направление искусственного интеллекта по созданию компьютерных программ, играющих в го.
Некооперативная игра — термин теории игр. Некооперативной игрой называется математическая модель взаимодействия нескольких сторон (игроков), в процессе которого они не могут формировать коалиции и координировать свои действия.
Игра — тип олимпиадных задач по математике, в которых требуется проанализировать стратегию игры и/или назвать победителя этой игры. Обычно заканчивается традиционным вопросом: «Кто выиграет при правильной игре?»
Парадо́кс Парро́ндо — парадокс в теории игр, который обычно характеризуют как комбинацию проигрышных стратегий, которая выигрывает. Парадокс назван в честь его создателя, Хуана Паррондо, испанского физика. Утверждение парадокса выглядит следующим образом...
Квантовая теория игр является расширением классической теории игр в квантовую область. Она отличается от классической теории тремя основными особенностями...
Компьютерные шахматы — популярный термин из области исследования искусственного интеллекта, означающий создание программного обеспечения и специальных компьютеров для игры в шахматы. Также термин «компьютерные шахматы» употребляется для обозначения игры против компьютерной шахматной программы, игры программ между собой.
Домини́рование в теории игр — ситуация, при которой одна из стратегий некоторого игрока дает больший выигрыш, нежели другая, при любых действиях его оппонентов. Обратное понятие, нетранзитивность, возникает, если некоторая стратегия может давать меньшие выигрыши, чем другая, в зависимости от поведения остальных участников.
Байесовская игра (англ. Bayesian game) или игра с неполной информацией (англ. incomplete information game) в теории игр характеризуются неполнотой информации о соперниках (их возможных стратегиях и выигрышах), при этом у игроков есть веры относительно этой неопределённости. Байесовскую игру можно преобразовать в игру полной, но несовершенной информации, если принять допущение об общем априорном распределении. В отличие от неполной информации, несовершенная информация включает знание стратегий и выигрышей...
Это статья о термине теории игр. О режиме сетевых игр см. Кооперативная игра (компьютерные игры)Кооперативная теория игр занимается изучением игр, в которых группы игроков — коалиции — могут объединять свои усилия. Этим она отличается от некооперативных игр, в которых коалиции неприемлемы и каждый обязан играть за себя.

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

Подробнее: Эпсилон-равновесие
Одновременной игрой (англ. simultaneous game) называют игру, в которой стратегии избираются участниками до того, как станут известны стратегии оппонентов. Одновременные игры противопоставлены последовательным, где ходы совершаются по очереди. Чаще всего одновременные игры предстают в нормальной форме.

Подробнее: Одновременная игра
В теории игр Принцесса и Чудовище — это игра преследования, в которой два игрока играют в некоторой области. Разработана Руфусом Айзексом и опубликована в его книге Дифференциальные игры (1965) в следующем виде: «Монстр ищет принцессу, потраченное на поиск время является ценой игры. Оба находятся в совершенно тёмном помещении (любой формы), но оба знают его границы. Найти принцессу означает, что расстояние между принцессой и монстром оказывается в пределах радиуса захвата, который должен быть относительно...
Реверси (другое название — оте́лло) — настольная игра для двух человек на доске 8 на 8 клеток.
Покер планирования (англ. Planning Poker, а также англ. Scrum poker) — техника оценки, основанная на достижении договорённости, главным образом используемая для оценки сложности предстоящей работы или относительного объёма решаемых задач при разработке программного обеспечения. Это разновидность метода Wideband Delphi.
Собственное равновесие — принцип оптимальности в некооперативных играх, представляющий собой сужение равновесия дрожащей руки. Введён Р. Б. Майерсоном.
Ним — математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет. В классическом варианте игры число кучек равняется трём.
Равновесие дрожащей руки (англ. trembling hand perfect equilibrium) — принцип оптимальности в некооперативных играх, представляющий собой равновесие Нэша, обладающее дополнительным свойством устойчивости к достаточно малым отклонениям игроков от равновесных стратегий. Сформулировано Р. Зельтеном в 1975 г. в работе.
Система Хатчинсона (англ. Hutchinson System) — это система определения перспективности любого набора карт, розданных игроку в покер (так называемой руки). Она была разработана для начинающих игроков с целью оказания помощи в принятии решения о разыгрывании руки.
База данных шахматных окончаний — компьютеризированная база данных, содержащая предварительно рассчитанный исчерпывающий анализ шахматных эндшпилей. В такой базе данных хранятся оценки (выигрыш, ничья, поражение) для каждой возможной позиции шахматного окончания как при ходе белых, так и при ходе чёрных. Некоторые распространённые базы данных также содержат количество ходов, необходимых для достижения теоретического результата (мат, переход в младший выигранный эндшпиль и т. п.) при наилучшей игре...
Задача Иосифа Флавия или считалка Джозефуса — известная математическая задача с историческим подтекстом.
Игровой цикл (англ. gameplay loop, также англ. core gameplay loop) — принцип, согласно которому геймдизайнеры задают главный элемент игровой механики, который определяет фундаментальный опыт игрока. Один игровой цикл представляет собой действие игрока, результат этого действия в игровом мире, реакцию игрока на результат и запрос игры на повторение нового действия.
Игра Гранди — это математическая игра на стратегию для двух игроков. Сначала существует одна куча предметов. Два игрока по очереди разделяют одну кучу на две кучи разных размеров. Игра заканчивается, когда остаются только кучи из двух и менее предметов и ни одна не может быть разделена на кучки разных размеров. В игру обычно играют как и в поддавки. Это означает, что последний игрок, который сможет сделать разрешенный ход, выигрывает.
Спарклайн (англ. sparkline, от англ. spark — искра, англ. line — линия) — термин, который придумал Эдвард Тафти для обозначения небольших по размеру, но достаточно информационно-плотных графиков.
В математике под матричными играми понимается игра двух лиц с нулевой суммой, имеющих конечное число стратегий. Выигрыш определяется матрицей игры (матрицей платежей), она же является Нормальной формой игры.

Подробнее: Матричные игры
«Абалон» (фр. Abalone) — настольная абстрактная стратегическая игра для двух игроков, придуманная французскими дизайнерами игр Мишелем Лале (Michel Lalet) и Лораном Леви (Laurent Lévi) в 1987 году под названием «Сумито». В игре используются шарики разных цветов (по 14 шаров каждого цвета) и шестиугольное игровое поле, содержащее 61 пункт. Целью игры является выталкивание шести шаров соперника за пределы поля. Существуют варианты правил для трёх-шести игроков.
Покер на костях — азартная игра в кости. В неё могут играть от двух человек и более, оптимальное число игроков — четыре. Для игры используют 5 кубиков с числовыми достоинствами от 1 до 6. В зависимости от игровой ситуации, выбрасываются от одного до пяти кубиков одновременно. За выполнение определённых комбинаций даются очки. Все комбинации и результаты их выполнения записываются в таблицу. Цель игры — набрать наибольшую сумму очков.
Ниче́йная смерть — этап развития логической игры (обычно речь идёт о настольных играх, таких как шахматы, шашки, го и пр.), когда разработанность теории достигает уровня, позволяющего любому владеющему ей игроку, независимо от квалификации противника, свести партию в худшем случае к ничьей.
В компьютерных и других играх, движение времени должно управляться тем способом, который игроки считают объективным и простым для понимания. Это обычно делается в одном из двух способов...

Подробнее: Системы управления временем в играх
Кооперативные стохастические игры — раздел теории игр, изучающий конфликтно-управляемые системы с недетерминированными переходами из состояния в состояние, в которых возможна кооперация игроков. Стохастические игры — динамические игры, в которых переход из одного состояния (одновременной игры) в другое происходит с некоторой вероятностью, зависящей от стратегий, выбранных игроками в данном состоянии. Под выигрышами игроков в стохастических играх принято понимать математическое ожидание их выигрышей...
Быки и коровы — логическая игра, в ходе которой за несколько попыток один из игроков должен определить, что задумал другой игрок. Варианты игры могут зависеть от типа отгадываемой последовательности — это могут быть числа, цвета, пиктограммы или слова. После каждой попытки задумавший игрок выставляет «оценку», указывая количество угаданного без совпадения с их позициями (количество «коров») и полных совпадений (количество «быков»). Роли участников игры не равнозначны — угадывающий должен анализировать...
Пешечная дуэль — это логическая игра на шахматной доске. В ней участвуют два игрока, у каждого перед началом игры по три (иногда более) пешки, расположенные друг против друга на противоположных крайних горизонталях. Первыми ходят белые. Каждый ход состоит из передвижения одной из пешек своего цвета. Первым ходом каждый из игроков может идти не далее, чем до середины доски, и на любое количество клеток во все последующие ходы. Пешки ходят вперёд либо назад. Задача каждого из игроков — оставить противника...
Задача о свадьбе — математическая задача из области кооперативных игр. Требуется найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. В более простой формулировке: составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам. Решение задачи отмечено Нобелевской премией по экономике 2012 года.
Игровой искусственный интеллект (англ. Game artificial intelligence) — набор программных методик, которые используются в компьютерных играх для создания иллюзии интеллекта в поведении персонажей, управляемых компьютером. Игровой ИИ, помимо методов традиционного искусственного интеллекта, включает также алгоритмы теории управления, робототехники, компьютерной графики и информатики в целом.
Рационализируемость (англ. rationalizability) — концепция решения в теории игр. Концепция задумана как набор минимальных ограничений, при которых игроки остаются рациональными и имеет место общее знание о рациональности каждого из участников. Иными словами, имеют место рациональность и общая вера в рациональность. В частности, концепция менее требовательна, чем равновесие Нэша, и совокупность равновесий в игре является подмножеством множества рационализируемых решений. Обе концепции требуют от игроков...
Ментальный покер — система криптографических задач, касающихся честных игр на расстоянии (через телефонную связь или Интернет). Термин происходит от названия карточной игры покер. С аналогичной проблемой связана задача подбрасывания монеты на расстоянии.
Контро́льная точка (англ. checkpoint) — в компьютерных играх представляют собой игровую механику или технологию, сохраняющую состояние игры в определённых разработчиками местах, и позволяющее в последующем в случае смерти персонажа начинать игру с сохранённого состояния. Такое сохранение происходит в местах, которые игрок достиг самостоятельно, и позволяют в случае завершения игры переигрывать не всю игру, а продолжить с места, где произошло сохранение. Контрольные точки проектируются заранее и могут...
Варианты правил го — различные своды правил настольной игры го. Отличаются отдельными деталями, трактовкой некоторых редко встречающихся в реальных партиях позиций, правилами определения результата в спорных случаях и порядком подсчёта разности очков. Все используемые на практике варианты эквиваленты в абсолютном большинстве случаев, их различия проявляются только в редких ситуациях.
Игровой баланс — в играх (спортивных, настольных, компьютерных и прочих) равновесие между персонажами, командами, тактиками игры и другими игровыми объектами. Игровой баланс — одно из требований к «честности» правил. Особенно баланс важен для многопользовательских игр.
В математике теория момента остановки или марковский момент времени связана с проблемой выбора времени, чтобы принять определённое действие, для того чтобы максимизировать ожидаемое вознаграждение или минимизировать ожидаемые затраты. Проблема момента остановки может быть найдена в области статистики, экономики и финансовой математики (связанные с ценообразованием на американские опционы). Самым ярким примером, относящимся к моменту остановки, является Задача о разборчивой невесте. Проблема момента...

Подробнее: Марковский момент
Микроконтроль (микро) — в стратегиях реального времени контроль за каждым юнитом, участвующим в сражении, а также за выбором места для дополнительных (ресурсодобывающих или производящих войска) баз и процессом разведки. Включает выбор индивидуальных целей и применение заклинаний, не вызывающихся автоматически. На уровне микроконтроля определяется, где будут установлены оборонительные сооружения, как будут размещены здания на базе игрока, с какой стороны атаковать лагерь противника.
Жизнь (англ. life) — свойство игровых персонажей в компьютерных играх, определяемое как период между началом и концом игры. Иногда называется шансом (англ. chance) или попыткой (англ. try), в частности в играх для всех возрастов, во избежания ассоциаций, вызываемых «потерей жизни». Обычно потеря всех очков здоровья означает потерю жизни, а потеря всех жизней приводит к концу игры, после чего игрок может либо начать игру сначала, либо выйти из игры.
Уровень (акт, волна, доска, зона, карта, мир, миссия, раунд, стадия, сцена, эпизод, этап и т. п.) — в компьютерных играх — отдельная область виртуального мира игры, обычно представляет собой определённую локацию, например, здание или город.
Битва полов или семейный спор (англ. Battle of the sexes (BoS), альтернативное расшифровка аббревиатуры — англ. Bach or Stravinsky, «Бах или Стравинский») — одна из основополагающих некооперативных моделей в теории игр, которая предполагает участие двух игроков с разными предпочтениями.
Парадокс Монти Холла — одна из известных задач теории вероятностей, решение которой, на первый взгляд, противоречит здравому смыслу. Эта задача не является парадоксом в узком смысле этого слова, так как не содержит в себе противоречия, она называется парадоксом потому, что ее решение может показаться неожиданным. Более того, многим людям бывает сложно принять правильное решение даже после того, как его им рассказали.
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я