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