Что такое теория игр и как она встречается в информатике
Теория игр изучает ситуации, где несколько участников по очереди делают ходы и каждый хочет выиграть. В школьной информатике её основы проверяют в заданиях 19–21 ЕГЭ. Два игрока, Петя и Ваня, играют с кучей камней (или с двумя кучами), ходят по очереди, а выигрывает тот, после чьего хода камней в куче становится не меньше заданного числа.
Суть теории игр в таких заданиях не в том, чтобы угадать ходы, а в том, чтобы найти выигрышную стратегию. Это правило выбора хода, которое приводит к победе при любых ответах соперника. Нужно определить, у кого она есть и при каком начальном количестве камней S.
Выигрышные и проигрышные позиции: как рассуждать
Позицию называют выигрышной для игрока, чей ход, если он может выиграть сразу или сделать такой ход, после которого соперник окажется в проигрышной позиции. Проигрышная позиция: какой бы ход ни сделал игрок, соперник получит выигрышную.
Рассуждать удобно с конца, от победной зоны назад к начальной куче. Для этого пригодится дерево игры, то есть граф, где из каждой позиции идут стрелки в позиции после возможных ходов.
Три задания обычно устроены как лестница:
- в 19 нужно найти S, при котором Петя не выигрывает за один ход, но Ваня выигрывает своим первым ходом при любой игре Пети;
- в 20 нужны значения S, при которых Петя выигрывает вторым ходом при любой игре Вани, а первым не может;
- в 21 нужно S, при котором Ваня выигрывает вторым ходом, но не первым.
Главное правило связано с логикой. Игроку, за которого ты ищешь победу, достаточно одного удачного хода («или»). Против него нужно проверить все ходы соперника («и»).
Разбор задания: когда Петя выигрывает вторым ходом
Условие. Петя и Ваня ходят по очереди, первым ходит Петя. За ход можно добавить в кучу один камень или увеличить число камней в 2 раза. Выигрывает тот, после чьего хода в куче стало не менее 30 камней. Вначале в куче S камней, 1 ≤ S ≤ 29. Найди все S, при которых Петя не может выиграть первым ходом, но выигрывает вторым при любой игре Вани.
Шаг 1. Когда выигрывают за один ход. Нужно S + 1 ≥ 30 или 2 × S ≥ 30. Второе условие даёт S ≥ 15. Значит, с кучей от 15 до 29 камней выигрывает любой, чей ход.
Шаг 2. Первое условие задачи. Петя не должен выигрывать сразу, поэтому S ≤ 14.
Шаг 3. Куча после хода Пети. Пусть Петя сделал ход и получил X камней. Если X ≥ 15, Ваня выиграет сразу. Значит, X ≤ 14.
Шаг 4. Все ответы Вани. Ваня может получить X + 1 или 2 × X. В обоих случаях Петя должен выиграть следующим ходом, то есть в куче должно быть не меньше 15 камней. Из X + 1 ≥ 15 следует X ≥ 14. Вместе с X ≤ 14 это даёт X = 14. Тогда Ваня получает 15 или 28, и в обоих случаях Петя выигрывает.
Шаг 5. Идём назад. Кучу в 14 камней Петя получает из S + 1 = 14, то есть S = 13, или из 2 × S = 14, то есть S = 7. Оба значения не больше 14, значит, первым ходом Петя не выигрывает.
Ответ: 7 и 13. Проверка для S = 7: Петя удваивает кучу до 14, Ваня делает 15 или 28, Петя получает 30 (15 + 15 или 28 + 2 не подойдёт, а вот 15 × 2 = 30 и 28 × 2 = 56 подходят) и выигрывает.
Если значений много, ход можно проверить программой. Для этого пишут функцию, которая вызывает саму себя для каждой позиции, как в теме про подпрограммы и рекурсию.
Где ошибаются чаще всего
- Путают порог победы. В условии «не менее 30» значит ≥ 30, а не > 30. Из-за одного знака сдвигается вся цепочка позиций.
- Проверяют один ход соперника. Если Ваня может добавить камень или удвоить кучу, нужно разобрать оба хода. Выигрышная стратегия Пети должна работать против любого.
- Забывают, что Ваня тоже может выиграть. В примере выше значение X ≥ 15 не подходит, потому что Ваня заканчивает игру первым.
- Пропускают условие «не может выиграть за один ход». Тогда в ответ попадают лишние S, при которых Петя выигрывает сразу, а не вторым ходом.
- Не проверяют ответ. Подставь найденное S и пройди игру вручную: для каждого хода Вани должен найтись выигрышный ответ Пети.
Какие задания по теме присылают ученики и как пользоваться страницей
Сейчас на сайте два задания 11 класса, оба про игру с кучей камней, где можно добавить один камень или увеличить кучу в 2 раза. В первом нужно разобраться со стратегией игры, во втором найти наименьшие S, при которых Петя выигрывает вторым ходом при любой игре Вани.
Посмотри в списке выше задание с похожими правилами и сравни его ход решения со своим. Если подходящего нет, сфотографируй своё условие и отправь на сайт, чтобы получить решение с ходом.