Лабораторная работа № 27 (к § 58) Построение стратегии на основе списка проигрышных позиций

Определения и обозначения

Проигрышная позиция — положение игры, из которого при правильной игре обоих участников проигрывает тот, чей сейчас ход. Например, конечное положение может оказаться проигрышным для игрока, которому правила не оставляют разрешённого хода. Понятие нужно, чтобы отмечать положения, в которые выгодно переводить соперника.

Выигрышная позиция — положение, из которого игрок может одним из разрешённых ходов перевести игру в проигрышную позицию соперника. Здесь оценивается не просто наличие хода, а его результат для следующего игрока. Это определение позволяет распознавать выгодные положения по уже изученным случаям.

Выигрышная стратегия — способ выбирать ходы так, чтобы гарантировать победу независимо от ответов соперника. Стратегия задаёт правило действий на протяжении игры, а не только удачный первый ход. Она нужна, чтобы обосновать, почему победа сохраняется при любом допустимом ответе противника.

Список проигрышных позиций — упорядоченный перечень положений, распознанных как проигрышные и используемых для выбора выигрышного хода. Порядок важен: новые положения классифицируют на основе тех, что уже проверены. Список помогает не пропускать случаи и применять найденное правило при выборе хода.

Как это устроено

Разбор начинают с конечных положений, потому что у них нет дальнейших ходов, а результат напрямую задают правила игры. Например, правила могут считать проигравшим того, кто не может сделать ход; в другой игре завершение может трактоваться иначе. Пока не определено, что означает конец игры, нельзя верно разметить даже самые простые положения. Поэтому сначала фиксируют исход для каждого вида окончания партии.

Затем используют уже известные проигрышные положения, чтобы находить выигрышные. Если из рассматриваемого положения существует разрешённый ход в проигрышное для соперника положение, игрок может выбрать именно его. Остальные ходы могут быть невыгодными, но для вывода о выигрышности они не отменяют найденной возможности. Важно проверять, что переход действительно разрешён и что в целевом положении ход принадлежит сопернику.

Чтобы распознать новую проигрышную позицию, проверяют не один удобный вариант, а все возможные ходы. Если каждый из них приводит к выигрышной позиции для следующего игрока, текущий игрок не может своим ходом передать сопернику проигрышное положение. Поэтому при правильной игре он оказывается в невыгодном положении. Если же обнаружен хотя бы один переход в проигрышную позицию, эту позицию следует считать выигрышной, а не проигрышной.

Список строят последовательно, располагая положения по удалённости от завершения игры. Сначала отмечают конечные случаи, потом проверяют позиции, ход из которых ведёт в уже разобранные случаи, и далее повторяют процедуру. Такой порядок нужен, чтобы каждый вывод опирался на известные результаты, а не на предположение о ещё не исследованных положениях. Для каждой новой записи следует перечислить варианты ходов и указать основание классификации.

Список превращается в стратегию, когда игрок использует его для выбора хода из текущего положения. Нужно найти доступную проигрышную позицию для соперника и перевести игру туда; после ответа соперника анализ повторяют. Если это правило применимо на каждом этапе, оно позволяет сохранять преимущество, а не рассчитывать на ошибку противника. Гарантия действует при условии, что правила соблюдаются и игрок каждый раз выбирает подходящий ход.

Как классифицировать позицию и выбрать ход

Используйте таблицу сверху вниз: сначала проверьте, не завершена ли игра, затем разберите все доступные переходы. Не считайте отсутствие позиции в списке готовой классификацией — список может быть ещё не полон. При выборе хода убедитесь, что найденное проигрышное положение достижимо именно одним разрешённым ходом.

Разбор задач

Составляем начальную часть списка

Условие. Для игры из § 58 рассмотрите несколько ближайших к завершению положений и составьте начальную часть списка проигрышных позиций. Конкретные правила переходов нужно взять из описания самой игры, поскольку без них нельзя перечислить положения или установить исход окончания. Здесь разберём порядок действий, применимый к заданной игровой схеме.

1. Сначала найдите положения, в которых игра уже закончилась, и примените правило окончания. Если оно объявляет проигравшим игрока без хода, такие положения записывают как проигрышные для него. Этот шаг задаёт отправные точки анализа.
2. Перечислите положения, из которых за один разрешённый ход можно попасть в отмеченные случаи. Если в положении есть такой переход, отметьте его как выигрышное. Причина в том, что игрок может передать сопернику проигрышный ход.
3. Проверьте оставшиеся ближайшие положения: выпишите каждый разрешённый ход и классифицируйте результат. Положение добавляйте в список проигрышных лишь тогда, когда все переходы ведут в выигрышные позиции. Повторяйте проверку, двигаясь от завершения игры к более ранним состояниям.

Ответ. Начальная часть списка состоит из конечных проигрышных положений и тех более ранних положений, для которых проверены все варианты и каждый ведёт в выигрышную позицию. Точный перечень зависит от разрешённых ходов в игре § 58. Записывайте рядом с каждым положением основание, чтобы можно было проверить вывод.

Определяем тип заданной позиции

Условие. Для заданной позиции перечислите все допустимые ходы и определите, выигрышная она или проигрышная. Предполагается, что часть более близких к завершению игры положений уже классифицирована. Если данных для какого-либо перехода пока нет, сначала продолжите построение списка, а не угадывайте результат.

1. Запишите текущее положение и отдельно перечислите каждый ход, разрешённый правилами. Это нужно, чтобы не принять частичный просмотр вариантов за полный анализ. Если ходов нет, сразу примените правило окончания игры.
2. Для каждого хода установите, в какое положение он приводит, и сравните его с уже классифицированными случаями. Если хотя бы один результат — проигрышная позиция для следующего игрока, исходное положение выигрышное. Отметьте конкретный ход, который даёт этот результат.
3. Если перехода в известную проигрышную позицию нет, убедитесь, что проверены все варианты и каждый ведёт в выигрышную позицию. Тогда исходное положение проигрышное. При неполных сведениях оставьте классификацию открытой и разберите недостающие положения.

Ответ. Позиция выигрышная, если найден хотя бы один разрешённый ход в проигрышное положение соперника; иначе она проигрышная только после проверки всех ходов. В ответе укажите классификацию и основание. Для выигрышной позиции назовите подходящий ход, а для проигрышной — подтвердите, что исключений нет.

Строим стратегию по списку

Условие. По составленному списку предложите стратегию игроку, начинающему из указанной позиции, и объясните, почему она гарантирует победу. Сначала нужно выяснить, содержит ли список положение, достижимое из начального одним разрешённым ходом. Стратегия должна учитывать не только первый ход, но и ответы соперника.

1. Сравните все доступные из начальной позиции переходы со списком проигрышных положений. Выберите ход, который ведёт в одно из них, если такой ход существует. Так соперник получает положение, классифицированное как невыгодное для игрока, чей ход.
2. После ответа соперника определите новое положение и снова перечислите разрешённые ходы. Ищите переход в проигрышную позицию для соперника, пользуясь тем же списком и его обоснованными продолжениями. Не полагайтесь на то, что противник выберет удобный вам ответ.
3. Повторяйте правило до завершения игры, каждый раз проверяя, что выбранный переход разрешён. Гарантия опирается на то, что из каждой возникающей выигрышной позиции существует нужный ход. Если такого положения или перехода в списке нет, данных для обещания победы пока недостаточно.

Ответ. Стратегия состоит в переводе соперника в проигрышную позицию и повторении этого выбора после каждого его ответа. Она гарантирует победу, если для всех возникающих положений переходы проверены, правила игры соблюдаются, а нужный ответ доступен. Одного удачного первого хода без анализа продолжения недостаточно.

Типичные ошибки

Считать позицию проигрышной только потому, что пока не найден выигрышный ход, — преждевременно. Обычно так происходит, когда проверяют несколько вариантов и принимают отсутствие находки за доказательство. Перечислите все разрешённые ходы и только после этого делайте вывод; при неполном списке продолжите анализ.

Позиция не становится выигрышной от перехода в любое известное положение: оно должно быть проигрышным именно для соперника. Эту ошибку допускают, когда смотрят только на знакомый пункт списка и не учитывают, чей ход будет следующим. Перед выводом проверьте тип целевой позиции и сторону, которой предстоит ходить.

Пропуск допустимого хода может перевернуть классификацию: именно среди незамеченных вариантов иногда оказывается путь в проигрышную позицию соперника. Такое случается при небрежном перечислении ходов или попытке упростить проверку. Сверьте список переходов с правилами игры и отметьте каждый рассмотренный вариант.

Нельзя смешивать положение игры с игроком, которому принадлежит ход: одно и то же состояние доски может оцениваться по-разному в зависимости от очереди хода. Ошибка возникает, если записывают только набор игровых объектов, не фиксируя, чей ход и как правила трактуют окончание. В каждой записи указывайте очередь хода и проверяйте конечный результат по правилам.

Связь с другими темами

Для работы нужны правила игры из § 58, умение перечислять допустимые ходы и понимание того, когда партия заканчивается. Без точного описания переходов нельзя проверить все варианты, а без правила окончания — классифицировать конечные положения. Этот способ анализа применяется в конечных играх, при построении выигрышных стратегий и решении задач на перебор игровых позиций. Он связывает описание правил с последовательным доказательством того, какой ход выгоден.

Что запомнить

• Классифицировать положения нужно, начиная с завершения игры.
• Из выигрышной позиции есть ход в проигрышную позицию соперника.
• Из проигрышной позиции все разрешённые ходы ведут в выигрышные.
• Список строят последовательной проверкой допустимых ходов.
• Выигрышная стратегия опирается на перевод соперника в проигрышную позицию.
• Стратегия гарантирует победу только при соблюдении правил и правильном ответе на каждый ход соперника.