Игры и стратегии с точки зрения математики

Следствие. Позиция (𝑃, 𝑄) в сумме игр является проигрышной тогда
и только тогда, когда 𝜑(𝑃) = 𝜑(𝑄).
В самом деле, 𝜑(𝑃) ⊕ 𝜑(𝑄) = 0 равносильно 𝜑(𝑃) = 𝜑(𝑄).
В частности, если мы играем на обеих досках в одну и ту же игру, то
симметричная позиция (𝑃, 𝑃) всегда проигрышная. (Это ясно и непосред-
ственно: второй игрок может повторять ходы на другой доске.) Однако не
следует думать, что проигрышны только симметричные позиции: если
𝑃
1
≠ 𝑃
2
, но 𝜑(𝑃
1
) = 𝜑(𝑃
2
), то позиция (𝑃
1
, 𝑃
2
) тоже проигрышная.
Описанный способ вычисления оценок позиций не только изящен,
но и позволяет иногда быстро находить проигрышные и выигрышные
позиции. Это происходит, когда игра после хода игрока разбивается в
сумму нескольких отдельных игр.
В заключение несколько кратких замечаний (которые не используют-
ся в дальнейшем).
1. Теорию игр Шпрага – Гранди можно изложить в другом порядке.
На множестве пар (игра, начальная позиция) определяем сложение. За-
тем называем две пары (𝐴, 𝑎) и (𝐵, 𝑏) эквивалентными, если для любой
пары (𝐶, 𝑐) суммы (𝐴, 𝑎) + (𝐶, 𝑐) и (𝐵, 𝑏) + (𝐶, 𝑐) одновременно являются
41

---

выигрышными или проигрышными. Сложение корректно определено
на классах эквивалентности, более того, классы образуют группу, еди-
ничным элементом которой является игра с единственной позицией, а
обратным элементом к паре является она сама. (Тут надо доказать, что
игра (𝐴, 𝑎) + (𝐴, 𝑎) + (𝐵, 𝑏) является выигрышной или проигрышной
одновременно с (𝐵, 𝑏); это так, поскольку ходы в (𝐴, 𝑎) можно париро-
вать теми же ходами в другом слагаемом.) Приведённое выше опреде-
ление оценки позиции устанавливает изоморфизм этой группы с груп-
пой целых неотрицательных чисел с поразрядным сложением по моду-
лю 2.
2. Вместо конечных графов можно рассматривать и бесконечные гра-
фы без циклов, в которых нет бесконечных путей. Можно при этом отож-
дествить игру (частью которой считаем начальную позицию) с множе-
ством игр, которые получаются из неё после одного хода. Тем самым иг-
ры отождествляются с множествами, и на классе всех множеств (точнее,
на классах эквивалентности) возникает структура группы!
3. Можно пойти ещё дальше и рассматривать игру как пару множеств
игр (после ходов одного и другого игрока). Получается интересная и зага-
дочная структура, внутри которой можно отыскать действительные чис-
ла и многое другое. Эту конструкцию придумал Конвей (John Conway, On
Numbers and Games, 1976).