теория-игр - Функция Шпрага - Гранди

Для игры "ним" расчёт производится так. Берём число камней в каждой кучке, и представляем его в двоичной форме. Далее вычисляем поразрядную сумму этих чисел, то есть в каждом разряде производим сложение по принципу 1+1=0, без переноса в следующий разряд. Полученное число переводим из двоичной формы в десятичную, и оно будет значением функции Ш-Г.

Проще всего здесь даже не выписывать разряды, а поступать так: пусть имеется позиция в игре "ним" с числом камней, скажем, $%2, 5, 11, 15$%. Запишем каждое число в виде суммы различных степеней двойки, что делается единственным способом. В данном случае это $%2, 4+1, 8+2+1, 8+4+2+1$%. Далее складываем всё вместе, вычёркивая одинаковые слагаемые. Слагаемое $%8$% встречается здесь два раза, а потому сокращается. То же для слагаемого $%4$%. А слагаемые $%2$% и $%1$% встречаются нечётное число раз, поэтому они остаются, и значение функции будет равно их обычной сумме, то есть $%2+1=3$%.

Игрок выигрывает в данной позиции тогда и только тогда, когда значение функции равно нулю, то есть когда сокращается всё. Это значит, что в рассмотренном примере начинающий выигрывает. Его стратегия -- оставлять противнику позицию с нулевым значением. Можно проанализировать, какие именно ходы выигрывают.

Если мы хотим что-то взять из первой кучки, то легко видеть, что для соблюдения будущего "паритета чётности" должны оставить $%1$%. Это в данном случае возможно, и противник получит позицию $%1,4+1,8+2+1,8+4+2+1$%: здесь каждое из чисел встречается чётное число раз.

Если бы мы захотели взять что-то из второй кучки, то для достижения такого эффекта мы должны были бы оставить в ней $%4+2$% (чтобы получилось $%2, 4+2, 8+2+1, 8+4+2+1$%), но это невозможно из соображений количества, так как $%6>5$%. Значит, из второй кучки брать ничего нельзя, если мы не хотим проиграть.

Аналогичные рассуждения показывают, что в третьей кучке должно остаться $%8$% камней, и этого добиться можно, а если мы решили брать из четвёртой, то в ней должно остаться $%12$% камней. Таким образом, мы можем сделать в данной позиции любой из трёх выигрывающих ходов.

Более быстрый подсчёт может быть осуществлён так. Когда мы решаем, сколько камней следует оставить в кучке, то мы складываем поразрядно уже найденное значение функции для данной позиции (у нас это $%3=2+1$%) с количеством камней в кучке. Например, для третьей кучки происходит сложение с $%11=8+2+1$%, и в результате сокращения одинаковых слагаемых остаётся $%8$%. Это то, что следует оставить противнику, если позволяет количество (со второй кучкой у нас это было сделать нельзя, а с остальными -- можно).