3.3. Дерево игры

Данный способ является разновидностью анализа с конца и заключается в том, что мы будем анализировать в знаках «`+`» и «`-`» не все позиции, а только те, в которые можно прийти из начальной позиции. Для этого мы нарисуем дерево ходов из начальной позиции. Разберём этот метод на примере 10.

Первоначальная позиция - `(2,3)`. За один ход из этой позиции можно прийти в позиции: `(3,3)`; `(2,4)`; `(6,3)`; `(2,9)`, добавляя один камень в одну из куч или умножая количество камней в куче на три.

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

Выше приведённое означает, что если из позиции за один ход можно прийти в позицию с количеством камней, не меньшим `16` (что по условию задачи равносильно выигрышу), это - позиция, выигрышная для первого игрока, т. е. позиция «`-`». В связи с этим знаки «`-`» можно поставить в позициях `(6,3)` и `(2,9)`, умножая количество камней в большей куче на `3`, мы получим `6^(**)3+3=21` и `2+9^(**)3=29` камней соответственно, и выиграем.

 Мы не сможем такого утверждать для позиций `(3,3)` и `(2,4)`, поэтому отразим в дереве все позиции, в которые мы можем прийти из них ещё за один ход. Две из полученных после двух ходов позиций повторяются (это позиция `(3,4)`). Можно не делать дубликат позиции `(3,4)`, а провести к ней пути как из позиции `(2,4)`, так и из позиции `(3,3)`. А можно - оставить как есть, что в данном случае мы и сделаем.

Обозначим знаком «`-`» позиции, из которых можно дойти за один ход до выигрышных. Из оставшихся позиций продолжаем дерево дальше позициями, в которые можно попасть за три хода

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

После этого, отметим знаком «`-`» позиции `(3,3)` и `(2,4)` уровнем выше как позиции, из которых существует хотя бы один ход в позицию, отмеченную знаком «`+`». И, наконец, позицию `(2,3)` отметим знаком «`+`» как позицию, все ходы из которой ведут в позиции со знаком «`-`».

Таким образом, в позиции `(2,3)` стоит знак «`+`»[1], а это означает, что в данной игре выиграет второй игрок. Его стратегия формулируется тем же правилом, что и ранее: делать ходы в позиции, отмеченные знаком «`+`». Стратегия выигрывающего игрока в явном виде («образец оформления примера») уже была описана ранее. Аналогично анализу с конца обратим внимание, что важно построить дерево позиций до конца - пропуск любой, даже самой маленькой, ветви может существенно поменять всю расстановку знаков в вершинах дерева существенно поменять всю расстановку знаков в вершинах дерева и даже привести к тому, что победит другой игрок. Причём последнее не является редкостью.

Отдельно отметим, что хотя «анализ с конца» и «дерево игры» являются различными вариациями одной и той же идеи, в некоторых случаях быстрее действовать одним методом, а в некоторых - другим. Так, если в игре легко отобразить схематично всё множество позиций (например, на клетчатом листе), с другой стороны, количество ходов до выигрыша может быть довольно большим (см. пример 9), гораздо легче действовать методом «анализ с конца». В примере 10 решения обоими методами примерно идентичны по трудозатратам.

Однако, если известно, что игра всегда заканчивается за малое количество ходов - логичнее нарисовать дерево игры. Более того, если множество позиций сложно или невозможно каким-либо образом изобразить схематически (например, если не две кучи камней, а три кучи) - «анализ с конца» вообще малоприменим – нужно рисовать дерево игры или вообще решать задачу методом «удачный ход».


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