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

задан 12 Ноя '12 14:27

изменен 12 Ноя '12 15:09

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

10|600 символов нужно символов осталось
1

Для игры "ним" расчёт производится так. Берём число камней в каждой кучке, и представляем его в двоичной форме. Далее вычисляем поразрядную сумму этих чисел, то есть в каждом разряде производим сложение по принципу 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

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×107

задан
12 Ноя '12 14:27

показан
2898 раз

обновлен
8 Фев '13 0:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru