Решение игр с природой в Excel
Шаблон создается через этот сервис. Никаких дополнительных изменений не требуется. Скачать шаблон решения.
Линейное программирование
Решение ЗЛП графическим методом
Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
| x | f1(x) | f2(x) | f3(x) |
| 1 | 6.3 | 4 | 5 |
| 2 | 5.2 | 6 | 7 |
| 3 | 4.3 | 4.6 | 7.8 |
| 4 | 5 | 6 | 3 |
| 5* | 7 | 6.3 | 8.2 |
Учебно-методический
√ курсы переподготовки и повышения квалификации
√ вебинары
√ сертификаты на публикацию методического пособия
- Задать вопрос или оставить комментарий
- Помощь в решении
- Поиск
- Поддержать проект
Правила ввода данных
Задать свои вопросы или оставить замечания можно внизу страницы в разделе Disqus .
Можно также оставить заявку на помощь в решении своих задач у наших проверенных партнеров (здесь или здесь).
Поиск
Задать свои вопросы или оставить замечания можно внизу страницы в разделе Disqus .
Можно также оставить заявку на помощь в решении своих задач у наших проверенных партнеров (здесь или здесь).
Как теория игр работает на практике и помогает выигрывать
Недавно мы начали разбирать теорию игр — набор инструментов, которые помогают принимать взвешенные, рациональные и точные решения, а также понимать данные. Вот суть прошлой статьи:
- теория игр — это не только про игры, а про любые ситуации, в которых может что-то происходить, меняться и зависеть от разных факторов;
- игрок — это тот, кто находится в этой ситуации и принимает решения;
- смысл теории игр в том, чтобы понять, как нужно действовать игрокам в разных ситуациях, чтобы получить нужный результат;
- есть много разных видов игр: с полной и неполной информацией, с нулевой, ненулевой суммой и так далее;
- для разных игр — разные стратегии.
Сегодня разберём игру Ним — старую игру, на основе которой математики нашли стратегию выигрыша для многих других игр.
Правила игры Ним
Классические правила игры Ним звучат так:
Есть несколько кучек, в каждой из которых лежит сколько-то камней. За один ход игрок может взять из любой одной кучки любое ненулевое число камней. Игроки берут камни по очереди. Побеждает тот, кто забирает последние камни.
Есть более известный вариант — две кучки, за один ход можно взять 1, 2 или 3 камня, а всё остальное то же самое.
Допустим, у нас 3 кучки, в которых лежат 1, 2 и 3 камня соответственно. Разберём последовательность ходов в этой игре:
- Первый игрок забирает один камень из первой кучки — в них теперь лежит 0, 2 и 3 камня.
- Если второй заберёт все камни из второй кучки, то первый возьмёт всё из третьей и выиграет. По этой причине второму игроку невыгодно брать сразу все камни из второй кучки, и он забирает один — в кучках становится 0, 1 и 3 камня. Теперь та же ситуация у первого игрока, и он не хочет забирать все камни из любой кучки.
- Выигрышный ход: первый игрок берёт два камня из второй кучки. В кучках теперь 0, 1 и 1 камень.
- Второй игрок берёт один камень.
- Первый игрок забирает последний камень и выигрывает.
Обратите внимание на расстановку сил после третьего пункта. Теперь у второго игрока нет выбора: у него есть только две кучки, в каждой из которых лежит по камню. Какой бы камень он ни взял, первый игрок заберёт оставшийся камень из другой кучки и выиграет.
Поиск такой выигрышной стратегии и есть суть теории игр: как сделать так, чтобы ты точно выиграл, а соперник — точно проиграл.
Выигрышный ход
Каждому игроку нужно просчитывать свои ходы так, чтобы действия соперника не влияли на финальный выигрыш. В теории игр это называется выигрышным ходом или выигрышной позицией — что бы ни сделал противник после этого, он всё равно проиграет при нашей правильной стратегии.
В примере выше таким выигрышным ходом у первого игрока было взять два камня из третьей кучки — это гарантировало ему выигрыш при любых действиях второго игрока. Задача теории игр — определить такие выигрышные ходы, если они есть.
Бывает так, что выигрышный ход можно сделать уже в самом начале игры, а потом просто поддерживать перевес в свою сторону.
Как выиграть в игру Ним
Математики, когда изучали эту игру, пришли к такому выводу:
Текущий игрок имеет выигрышную стратегию тогда и только тогда, когда XOR-сумма размеров кучек отлична от нуля. В противном случае текущий игрок находится в проигрышном состоянии.
Это значит, что для выигрыша нужно, чтобы после каждого хода XOR-сумма кучек не была равна нулю. Если этого не сделать, то второй игрок своим ходом обнулит сумму и первый игрок попадёт в ситуацию с нулевым XOR — и это значит, что он совершит проигрышный ход.
Напомним, что XOR — это побитовое ИЛИ, которое работает так:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
Для примера рассмотрим ситуацию с ходом первого игрока, когда у него в кучках было 0,1 и 3 камня.
0 в двоичной = 00 в десятичной
1 в десятичной = 01 в двоичной
3 в десятичной = 11 в двоичной
0 XOR 1 XOR 3 = (0 XOR 1) XOR 3 ← в десятичной, переводим в двоичную:
(00 XOR 01) XOR 11 = 01 XOR 11 = 10
Мы получили число, отличное от нуля, — это значит, что игрок в начале своего хода находится в выигрышной позиции. Теперь его задача сделать так, чтобы второй игрок в начале хода оказался в проигрышной позиции, то есть чтобы XOR всех камней в кучках стал равен 0.
XOR возвращает 0, если с обеих сторон от него стоят одинаковые числа. Когда мы посчитали скобки, то увидели, что XOR первых двух кучек даёт 1. Получается, что нам нужно сделать так, чтобы в третьей кучке тоже остался один камень. Мы забираем 2 камня из третьей кучки, и общий XOR всех камней становится нулевым:
0 XOR 1 XOR 1 = 1 XOR 1 = 0
Это значит, что второй игрок начинает свой ход в проигрышной позиции, а мы, если будем придерживаться правильной стратегии, обязательно выиграем.
Где ещё применяется эта стратегия
Стратегия и теория из игры Ним применяется во всех подобных играх, когда несколько игроков меняют состояния нескольких объектов. Главный критерий — чтобы игра точно заканчивалась в какой-то момент, когда остальные игроки не могут сделать свой ход. Например, есть варианты с добавлением камней, перекладыванием из кучки в кучку, объединением камней, ограничением на их количество и так далее — и все они работают под одной и той же стратегии.
Кроме игр, эта стратегия может применяться в обычной жизни. Вот несколько примеров:
Принятие бытовых решений. В жизни часто бывают ситуации, где мы сталкиваемся с какими-то ограничениями и ожидаемыми результатами. Применение концепции выигрышного хода может помочь найти решение, после которого любые внешние действия всё равно приведут к нужному нам результату.
Единственное, что здесь дополнительно нужно учитывать, — в жизни случаются такие форс-мажоры, которые могут полностью изменить ситуацию, и тогда игра начнётся заново, но с другими условиями.
Управление проектами. В проектном менеджменте вместо камней игроки могут управлять рисками, ресурсами и стратегиями, которые помогут достичь желаемых результатов. Для этого в компании вводятся балльные системы оценки влияния каждого фактора. Это помогает построить математическую модель проекта и принимать решения, которые приближают проект к успешному завершению.
Что дальше
В следующей части сделаем игру Ним на компьютере — можно будет играть вдвоём с кем-то или одному против алгоритма.
Теория игр
Теория игр как раздел исследования операций – это теория математических моделей принятия оптимальных решений в условиях неопределенности или конфликта нескольких сторон, имеющих различные интересы. Теория игр исследует оптимальные стратегии в ситуациях игрового характера. К ним относятся ситуации, связанные с выбором наивыгоднейших производственных решений системы научных и хозяйственных экспериментов, организацией статистического контроля, хозяйственных взаимоотношений между предприятиями промышленности и других отраслей. Формализуя конфликтные ситуации математически, их можно представить как игру двух, трех и т.д. игроков, каждый из которых преследует цель максимизации своей выгоды, своего выигрыша за счет другого.
- Оптимальные стратегии игроков. В таких задачах задана платежная матрица. Требуется найти чистые или смешанные стратегии игроков и, цену игры. Для решения необходимо указать размерность матрицы и метод решения. В сервисе реализованы следующие методы решения игры двух игроков:
- Минимакс. Если необходимо найти чистую стратегию игроков или ответить на вопрос о седловой точке игры, выберите этот метод решения.
- Симплекс-метод. Используется для решения игры в смешанных стратегиях методами линейного программирования.
- Графический метод. Используется для решения игры в смешанных стратегиях. Если есть седловая точка, решение прекращается. Пример: По заданной платежной матрице найти оптимальные смешанные стратегии игроков и цену игры, используя графический метод решения игры.
- Итерационный метод Брауна-Робинсона. Итеративный метод применяется тогда, когда не применим графический метод и когда практически не приминимы алгебраический и матричный методы. Этот метод дает приближенное значение цены игры, причем истинное значение можно получить с любой нужной степенью точности. Этот метод недостаточен для нахождения оптимальных стратегий, но он позволяет отслеживать динамику пошаговой игры и определить цену игры для каждого из игроков на каждом шаге.
Варианты (стратегии) Производительность. шт./час Стоимость оборудования. ден. ед. Энергоемкость. у.е. Надежность. у.е. Завода I 5 7 5 6 Завода II 3 4 7 3 Завода III 4 6 2 4 Вес критерия, λj 0.4 0.2 0.1 0.3 Аннуитетные платежи онлайн
Расчет аннуитетных платежей по схеме постнумерандо и пренумерандо с помощью удобного калькулятора.
Профессии будущего
РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса
Налоговый вычет на обучение
√ 120 тыс. руб. — максимальная сумма расходов на обучение
√ вычет от государства
√ вычет от работодателя- Задать вопрос или оставить комментарий
- Помощь в решении
- Поиск
- Поддержать проект
Рубрика «ЕГЭ Задание 19-21»
ЕГЭ информатика 19-21 задание разбор, теория, как решать.
Теория игр, выигрышная стратегия, 19.(Б) — 1 балл, 20.(П) — 1 балл, 21.(В) — 1 балл
Е19-21.38 В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами
23.04.2024 ЕГЭ Задание 19-21 Администратор Комментарии: 0
Е19-21.37 Игра завершается в тот момент, когда количество камней в куче становится не менее 65
23.04.2024 ЕГЭ Задание 19-21 Администратор Комментарии: 0
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня либо увеличить количество камней в куче в три раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы. Игра завершается …
Е19-21.36 если количество камней в куче чётно, добавить половину имеющегося количества
31.12.2023 ЕГЭ Задание 19-21 Администратор Комментарии: 0
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. В игре разрешено делать следующие ходы: – добавить в кучу один камень; – если количество камней в куче чётно, добавить половину имеющегося количества; – если количество камней в куче кратно трём, добавить треть …
Е19-21.35 увеличить количество камней в куче в два раза если оно нечётное
19.12.2023 ЕГЭ Задание 19-21 Администратор Комментарии: 0
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, увеличить количество камней в куче в два раза если оно нечётное, или в полтора раза, если оно чётное. Например, если в куче 5 …
Е19-21.34 когда количество камней в куче становится не менее 129
05.11.2023 ЕГЭ Задание 19-21 Администратор Комментарии: 0
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается …
Е19-21.33 За один ход игрок может добавить в кучу один или четыре камня,
01.05.2023 ЕГЭ Задание 19-21 Администратор Комментарии: 0
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня, либо увеличить количество камней в куче в четыре раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы. Игра завершается …
Е19-21.32 когда количество камней в куче становится не менее 129
26.12.2022 ЕГЭ Задание 19-21 Администратор Комментарии: 0
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается …
Е19-21.31 Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 211.
04.03.2022 ЕГЭ Задание 19-21 Администратор Комментарии: 0
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока …
Е19-21.30 когда количество камней в куче становится не менее 29
16.09.2021 ЕГЭ Задание 19-21 Администратор Комментарии: 0
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. …
Е19-21.29 когда суммарное количество камней в кучах становится не менее 44
18.06.2021 ЕГЭ Задание 19-21 Администратор Комментарии: 0
когда суммарное количество камней в кучах становится не менее 44 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в …