3.2. Анализ с конца

Вторым важным способом решения задач является решение задачи с конца. Предположим (хотя это и не всегда верно), что для обоих игроков одни и те же позиции являются выигрышными.

Вернёмся к примеру 9.

Для нахождения выигрышной стратегии рассмотрим общую задачу. Считаем, что начальная позиция является параметром, и будем искать выигрышную стратегию при старте с этой позиции. Будем обозначать знаком «`-`» позиции, в которых при правильной игре участник, начинающий играть из данной позиции, выиграет, и знаком «`+`» отметим позиции, ведущие к поражению[1].

Если игра начинается в поле `"h"8`, первый игрок уже проиграл – это позиция «`+`» (рис. 1).

Далее, если игра стартует с полей `"h"1-"h"7` или `"a"8-"g"8`, то начинающий игрок может за один ход достичь поля `"h"8` и выиграть. Это позиция «`-`» (рис. 2).

Рассмотрим ладью, стоящую в поле `"g"7`. У первого игрока есть только два хода – `"g"8` и `"h"7`. Но в обеих этих позициях стоит «`-`». Следовательно, второй игрок, стартующий из этих позиций, выиграет. Как бы ни ходил первый игрок, он проиграет. Это снова позиция «`+`».

Далее, рассмотрим группы полей `"g"1-"g"6` и `"a"7-"f"7` (рис. 3). Стартуя из этих полей, первый игрок может за один ход попасть в поле `"g"7`, которое помечено знаком «`+`». Любой ход второго игрока из `"g"7` ведёт к его проигрышу.

Продолжая таким образом заполнять шахматную доску, мы видим, что знаки «`+`» размещаются на диагонали `"a"1-"h"8` (рис. 4). В поле a1 стоит знак «`+`», поэтому первый игрок потерпит поражение.

Зафиксируем общие правила расстановки знаков «`+`» и «`-`»:

правила расстановки знаков «`+`» и «`-`»:

1) знаком «`-`»  обозначаются позиции, в которых при правильной игре участник, стартующий из данной позиции, выиграет, и знаком «`+`» отмечаются позиции, ведущие к поражению;

2) знак «`-`»  ставится в позиции, из которой можно за один ход прийти в позицию со знаком «`+`»;

3) знак «`+`» ставится в выигрышных позициях, а также в тех позициях, из которых все возможные ходы ведут только в позиции, уже отмеченные знаком «`-`»[2].

Таким образом, сначала нужно расставить знаки «`+`» в выигрышных позициях. На втором этапе нужно отметить знаком «`-`» те позиции, которые отделяет от выигрышных один ход. На третьем этапе следует просмотреть все позиции и найти «тупиковые», ведущие к положениям, обозначенным знаком «`-`». На игровом поле обязательно будет хотя бы одна такая позиция[3]. Второй и третий этапы необходимо поочередно повторять до тех пор, пока начальная позиция не будет помечена знаком «`+`» или «`-`», что и даст ответ на вопрос, кто выиграет при правильной игре.

Как же должен действовать побеждающий участник игры? Он должен стремиться ходить в позиции, отмеченные знаком «`+`». При этом после очередного хода соперника он опять окажется в позиции со знаком «`-`», так как по определению знака «`+`» все возможные ходы из этой позиции ведут только в позиции со знаком «`-`». Таким образом, стратегия выигрывающего игрока формулируется просто: делать ход в позиции, обозначенные знаком «`+`». По определению знака «`-`» из  этой позиции существует хотя бы один ход в позицию, отмеченную знаком «`+`», поэтому такой ход у выигрывающего игрока всегда будет в наличии.

Отметим следующий факт. Если известно, что игра длится не более чем `n` ходов при любых действиях первого и второго игроков, то начальная позиция обязательно будет помечена не более чем за `n` повторений шагов `2` и `3`. Это является идеей доказательства основной теоремы из § 2 в частном случае игр, в которых ничейных позиций нет, и каждая позиция является выигрышной для одного из игроков.

Пример 10

Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой – три камня, а во второй – два камня. У каждого игрока имеется неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в три раза число камней в какой-либо куче, или добавляет один камень в любую кучу. Выигрывает тот игрок, после хода которого, в двух кучах станет не менее `16` камней. Кто выиграет при правильной игре: игрок, сделавший первый ход, или игрок, сделавший второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Решение

Попробуем изобразить позиции графически. Рассмотрим таблицу, в которой количество камней в первой куче будет соответствовать номеру столбца, а количество камней во второй куче – номеру строки. Чёрным цветом выделена позиция `(2, 3)`, с которой должна начинаться игра в условии:

1. Выигрышные позиции – точки с координатами `x`, `y`, где `x + y ≥ 16`. Данные точки обозначим знаком «`+`» в таблице ниже[4].

2. Далее, ставим знак «`-`» в позиции, которые отделяет от выигрышных один ход.

По условию, можно либо увеличить одну из кучек в три раза, либо добавить  камень в одну из  куч, т. е.  мы  должны  поставить знак «`-`» в позицию `(x, y)`, если верно одно из условий: `x+y+1≥16`; `x+3y≥16`; `y+3x≥16`.

3. После чего, ставим знак «`+`» в те позиции, из которых все ходы ведут только в позиции, обозначенные знаком «`-`». Таковыми будут позиции `(0, 5)`, `(5, 0)` и `(4, 3)`, `(3, 4)`.

4. Знак «`-`» ставим в те позиции, стартуя из которых можно за один ход дойти до одной из позиций, отмеченных знаков «`+`» (поставленных на этапе 3).

Стартуя из позиций `(4, 0)`, `(0, 4)`, `(3, 3)`, `(2, 4)`, `(4, 2)`, можно попасть в позиции, обозначенные знаком «`+`», увеличив количество камней в одной из кучек на единицу. Из позиций `(1, 4)` и `(4, 1)` можно прийти в позиции со знаком «`+`», увеличив в три раза количество камней в меньшей куче.

5. Знак «`+`» ставим в те позиции, из которых все ходы ведут только в позиции, обозначенные знаком «`-`». На этот раз таковыми будут позиции `(2, 3)` и `(3, 2)`.

В позиции `(2, 3)` был поставлен знак «`+`», а это значит, что победит второй игрок.

При оформлении задачи необходимо указать выигрывающего игрока, записать его стратегию и показать, что этот игрок победит при любых ответах соперника. Если имеется таблица позиций, то стратегия выигрывающего игрока формулируется простым правилом: делать ходы в позиции, отмеченные знаком «`+`». Но эту стратегию рекомендуется записать в явном виде. Таблицу позиций же, наоборот, при оформлении работы можно не рисовать (она уже сделала свое дело: помогла определить победителя и найти его стратегию).

Образец оформления примера 10.

Покажем, что второй игрок может выиграть при произвольных ответах первого игрока.

Рассмотрим все возможные начальные ходы первого игрока и укажем правильные ответы соперника:

а) если первый игрок в три раза увеличивает число камней в одной из куч, то второй игрок должен увеличить количество камней в этой же куче также в три раза. Тогда в обеих кучах будет как минимум 2*3*3+3=21 камень. Второй игрок побеждает. Рассмотрение этого случая закончено;

б) если  первый  игрок из позиции (2, 3) делает ход (2, 4) или (3, 3), то второй игрок должен пойти в позицию (3, 4) (именно она в нашем случае обозначена знаком «+»). Теперь первый игрок делает второй ход (заметим, этот ход не может быть выигрышным). Возможны три варианта:

- первый игрок увеличивает в три раза количество камней в одной из куч. Тогда второй игрок повторяет это действие с оставшейся кучкой камней, получает в сумме 21 камень и выигрывает,


- первый игрок добавляет один камень в первую кучу – позиция (4, 4). Тогда второй игрок увеличивает количество камней в одной из куч в три раза, получает в сумме 16 камней и выигрывает,

- первый игрок добавляет один камень во вторую кучу – позиция (3, 5). Тогда второй игрок увеличивает количество камней во второй куче в три раза, получает в сумме 18 камней и выигрывает.


Таким образом, второй игрок побеждает при любых ходах своего соперника.


Обратите внимание, что стратегию второго игрока можно придумать, не основываясь на таблице позиций. Важно помнить: если вы пропустите или не разберёте хотя бы один ход соперника (проигрывающего игрока), это может быть чревато тем, что данная стратегия может оказаться в корне неверной. Также нужно внимательно отнестись к расстановке знаков «`+`» и «`-`» в таблице позиций: один неверно поставленный знак может изменить ответ. Лучше не торопиться и расставить только те знаки, в которых вы уверены на данный момент. И не существенно, если вы не поставите никакого знака в данной позиции на определенном этапе (например, по правилам его необходимо поставить, но вы этого не заметили). Главное – не поставить неверного знака.




[1] «`+`»-позиции иногда называют `"P"`-позициями, а «`-`»-позиции – `"N"`-позициями по первым буквам английских слов «Previous» (предыдущий) и «Nеxt» (следующий), указывающими, какой из игроков выиграет при старте из этой позиции – игрок, который пришёл в эту позицию последним ходом, или игрок, совершающий следующий ход из этой позиции.


[2] Недопустимо, чтобы из этой позиции один ход вёл  в позицию, обозначенную знаком  «`+`»,  а  другой  –  вёл  в  позицию,  ещё  не  обозначенную ни одним из знаков.


[3] Хотя убедиться в этом непросто, мы предлагаем читателю самостоятельно подумать, почему это верно.


[4] Хотя таблица должна быть бесконечной (количество камней может быть сколь угодно большим), достаточно нарисовать таблицу `17` x `17` – случаи, когда в одной из куч более `16` камней, нас не интересуют, так как все эти позиции являются выигрышными.