"Информатика", Семёнов А.Л., Рудченко Т.А.
Игра с полной информацией — это игра, в которой каждый участник знает правила, текущее положение и все сделанные ходы. Поэтому игрок может заранее рассуждать о возможных продолжениях и проверять разные варианты ответов соперника. Главное понятие темы — выигрышная стратегия: такой выбор ходов, который приводит к победе при любом допустимом поведении противника.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Игра с полной информацией — игра, в которой участники знают правила, текущее положение и все сделанные ходы. Например, игроки видят все предметы на столе и знают, что уже забрал соперник. Это позволяет рассуждать о будущем без догадок о скрытых действиях.
Позиция — состояние игры в данный момент, от которого зависит, какие ходы доступны игрокам. Положением может быть расстановка фишек на доске или число предметов, оставшихся на столе. Позиция нужна, чтобы точно описать, где находится игра перед очередным ходом.
Ход — действие игрока, которое по правилам переводит игру из одной позиции в другую. Если на столе было пять предметов, а игрок взял два, новая позиция содержит три предмета. По ходам можно восстановить всю последовательность партии.
Выигрышная стратегия — способ выбирать ходы, который приводит игрока к победе независимо от ответов соперника. Такая стратегия должна учитывать не один предполагаемый ответ, а каждый допустимый вариант. Она нужна, чтобы доказать гарантированную победу, а не просто угадать удачный ход.
Знание всех правил и сделанных ходов позволяет каждому игроку рассуждать о продолжении партии. Он видит, какие действия разрешены сейчас, и может представить, что произойдёт после каждого из них. Если бы часть информации была скрыта, результат зависел бы не только от рассуждения, но и от неизвестных сведений.
Положение на доске или набор предметов описывают текущую позицию игры. Например, для игры с предметами достаточно указать, сколько их осталось, если порядок предметов не имеет значения. Позиция определяет доступные ходы: при двух оставшихся предметах нельзя взять три, если правила этого не разрешают.
Последовательность ходов образует партию, потому что каждый новый ход меняет прежнюю позицию. Правила заранее задают начальную позицию и описывают, какие переходы допустимы. Они же определяют, когда игра заканчивается и какое конечное положение означает победу одного из игроков.
Чтобы искать выигрышную стратегию, сначала перечисляют возможные ходы, а затем для каждого проверяют ответы соперника. Нужно выбирать такой ход, после которого у игрока сохраняется путь к победе при любом ответе противника. Если хотя бы один ответ соперника приводит к его победе, проверяемый ход не является гарантированно выигрышным.
При анализе полезно начинать с конечных позиций и рассуждать от них назад. В конце игры легко установить, кто забирает последний предмет или кто сделал последнее правильное действие. Затем можно найти позиции, из которых игрок способен попасть в уже выгодную конечную позицию.
| Элемент игры | Что нужно указать | Вопрос для анализа |
|---|---|---|
| Правила | Что разрешено и как проходит партия | Какие действия считаются допустимыми? |
| Начальная позиция | С чего начинается игра | Как выглядит положение перед первым ходом? |
| Допустимые ходы | Какие действия можно сделать из позиции | Какие переходы в новые позиции возможны? |
| Условие окончания | Когда партия прекращается | В какой момент ходить больше не нужно? |
| Условие победы | Как определить победителя | Кому засчитывается выигрыш? |
Заполнять таблицу удобно до начала поиска стратегии. Сначала описывают исходное положение и разрешённые действия, а затем условия окончания и победы. После этого для каждой позиции можно проверять, какие ходы ведут к выигрышу.
Условие: игроки по очереди забирают один или два предмета, а последний предмет приносит победу тому, кто его взял. На столе лежат три предмета. Нужно назвать первые ходы и определить победителя при правильной игре.
Ответ: возможны первые ходы на один или на два предмета. При правильной игре выигрывает первый игрок, если сразу берёт один предмет и затем забирает последний после любого ответа.
Условие: правила те же, но на столе четыре предмета. Требуется найти ход, после которого любой ответ соперника позволит выиграть следующим ходом.
Ответ: первый игрок берёт один предмет. После ответа соперника он берёт столько, чтобы всего за два хода было убрано три предмета, и выигрывает следующим ходом.
Условие: игроки берут за ход один, два или три предмета, а победителем становится тот, кто забрал последний. Нужно выяснить, есть ли стратегия у первого игрока и проверить все ответы соперника.
Ответ: выигрышная стратегия есть у первого игрока. Его первый ход — взять один предмет, а затем дополнять ход соперника до четырёх.
Считать выигрышным любой ход, который уменьшает число ходов соперника. Игрок может оставить противнику мало вариантов, но среди них всё равно может быть победный ответ. Проверьте не только число вариантов, но и результат каждого допустимого ответа.
Анализировать только один ответ соперника. Такой ответ может оказаться удобным, но соперник не обязан его выбирать. Перечислите все его ходы и убедитесь, что для каждого существует продолжение вашей стратегии.
Путать позицию с ходом. Позиция — это описание состояния игры, а ход — действие, меняющее это состояние. Проверьте себя вопросом: можно ли назвать объект положением до действия или самим действием?
Не учитывать условие окончания и победы. Без этих условий неизвестно, какая конечная позиция выгодна и когда нужно остановить анализ. Перед поиском стратегии отдельно запишите, кто и при каком действии выигрывает.
До изучения игр с полной информацией нужно уметь читать правила, перечислять допустимые действия и пошагово выполнять алгоритм. Эти навыки помогают не пропустить вариант хода и правильно описать изменение позиции. По сути, разбор партии похож на точное выполнение инструкции.
Такие игры связаны с алгоритмами, перебором вариантов и доказательством правильности решения. Перебирая ответы соперника, мы проверяем все случаи, а не один пример. Поэтому полученная стратегия может работать независимо от конкретного выбора противника.
Что значит, что игра имеет полную информацию?
Это значит, что игроки видят текущее положение, знают правила и помнят все сделанные ходы. В игре нет скрытых карт, тайных действий или неизвестных результатов.
Чем позиция отличается от хода?
Позиция описывает состояние игры в определённый момент: например, сколько предметов осталось на столе. Ход — это действие игрока, которое изменяет позицию.
Как понять, есть ли у игрока выигрышная стратегия?
Нужно проверить, может ли игрок выбирать ходы так, чтобы победить при любом ответе соперника. Для этого перебирают возможные продолжения и часто рассуждают от конца игры.
Почему нужно рассматривать все ответы соперника?
Соперник может выбрать любой разрешённый правилами ход, а не только тот, который удобен для нашего рассуждения. Если хотя бы один его ответ разрушает план, стратегия не гарантирует победу.
Зачем при поиске стратегии рассуждать с конца игры?
В конечной позиции уже ясно, кто победил и какие ходы привели к этому результату. От неё можно двигаться назад и находить позиции, из которых победа гарантирована.
Игры с полной информацией
