Здравствуйте, не могли бы вы мне дать объяснения этой функции, я смотрел все возможные объяснения в гугле, но все равно не понял. Не могли бы вы продемонстрировать поэтапный расчет функции Шпрага гранди для обычного нима (например, для 3 кучек, где в каждой кучке 3 камня). Так же мне понятно следущее, если я правильно понял, то функция Шпрага-Гранди сопоставляет ним - число каждому состоянию игры, и если я правильно понял, то для определения проигравшего в равноправной игре достаточно просчитать рекурсивно значение функции до начального этапа, и например, если начальное состояние игры проигрышно, то проигрывает тот, кто ходит первый и остальные состояния игры анализировать не имеет смысла. Буду очень благодарен за помощь. задан 12 Ноя '12 14:27 ACM_igor |
Для игры "ним" расчёт производится так. Берём число камней в каждой кучке, и представляем его в двоичной форме. Далее вычисляем поразрядную сумму этих чисел, то есть в каждом разряде производим сложение по принципу 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$%. Это то, что следует оставить противнику, если позволяет количество (со второй кучкой у нас это было сделать нельзя, а с остальными -- можно). отвечен 8 Фев '13 0:19 falcao |