Занятие 14

Теория Шпрага-Гранди применима к беспристрастным играм, в которых побеждает тот, кто делает последний ход. Из теории следует, что каждая позиция в игре имеет определенное ним-значение, то есть эквивалентна кучке камней в игре ним.

Ним-значение любой позиции можно найти как минимум исключенных значений (mex) от множества ним-значений позиций, которые возникают при всех допустимых ходах. Mex множества неотрицательных целых чисел равен наименьшему неотрицательному целому числу, не принадлежащего данному множеству. Например, mex {5,3,0,7,1} = 2, а mex {} = 0. Ним-значение позиции, когда на столе не осталось ни одного камня и нельзя сделать ни одного хода, равно нулю. С помощью ним-значения легко определить, является ли текущая позиция выигрышной или проигрышной (ним-значение проигрышной позиции равно 0), а также найти выигрышный ход (это ход, после которого получается позиция с ним-значением равным 0). Для игры, в которой можно брать 1, 2 или 3 камня, получаются следующие ним-значения.

А для игры, в которой можно брать от 1 до `[n/2]` камней, получаются следующие ним-значения.

Позиции игр образуют аддитивную абелеву группу. Сумма позиций – это позиция в новой составной игре, получаемая объединением позиций-компонент, со следующим правилом игры: игрок, который делает ход, выбирает одну из игр-слагаемых и делает ход по правилам этой игры. Составная игра заканчивается, когда заканчивается все игры-слагаемые. Нетрудно видеть, что сложение игр ассоциативно и коммутативно. Нулевым элементом группы служит конец игры. Противоположным элементом можно считать ту же позицию, в которой ход делает другой игрок. То есть в беспристрастных играх позиция противоположна самой себе. Игра может быть разделена на игры-слагаемые не только с самого начала (игра ним для нескольких кучек камней), такое распадение может происходить в результате обычного хода (например, ход в игре заключается в разделении кучки камней на две части, игра заканчивается, если все кучки содержат по одному камню). Основной результат теории Шпрага-Гранди можно сформулировать следующим образом.

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

Хотя теория применима только к обычным беспристрастным играм, ее можно применить и к некоторым пристрастным или мизерным играм после их преобразования. Например, шахматы Доусона допускают преобразование к беспристрастной игре. Игра ведется на шахматной доске размером 3x`n`. Белые пешки расставляются на первой горизонтали, а черные – на третьей. Взятие пешек обязательно. Первыми ходят белые. Тот, кто не может сделать ход, проигрывает.

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

Дополнительные задачи: