Я пишу сообщение в блоге, чтобы объяснить, как использовать теорему Спрэга-Гранди для решения различных игровых задач, и у меня возникли проблемы с пониманием самого себя, как мы определяем составную игру.
Вот что у меня есть:
Теорема Спрага-Гранди может быть резюмирована следующими пунктами.
Любая позиция в беспристрастной игре может быть сведена к грубому числу (или к нимберу), где грубое число 0 является проигрышной позицией (то есть, если противник играет идеально, вы всегда будете проигрывать).
Любая позиция может оцениваться как минимальная исключительная (или смешанная) дочерних узлов этой позиции. Например, позиция, имеющая дочерние узлы с исходными значениями 0, 1, 3, будет иметь исходное значение 2. Позиция, имеющая дочерние узлы с исходными значениями 1, 2, 3, будет иметь базовое значение 0.
Теперь, следующий момент, на который я хочу обратить внимание, это то, что позиция может быть разделена на составные позиции, и гранди-число для этой позиции оценивается как XOR этих составных позиций.
Например: Для игры ним с двумя стопками:
2 xor 1 = 3, следовательно, это выигрышная позиция.
1 xor 1 = 0, следовательно, это проигрышная позиция.
Мы можем прийти к этому выводу, используя метод mex: т.е. подпозиции 2,1:
1, 1 (0)
2, 0 (2)
0, 1 (1)
мекс 3.
Однако суть метода xor заключается в том, чтобы прийти к такому выводу без необходимости оценивать подпозиции.
Как мы определяем составную позицию для такого рода игры?
