스프라그-그런디 수 계산기

한 게임 상태를 숫자 하나로 요약한 값입니다. 그 상태에서 갈 수 있는 다음 상태들의 그런디 수 집합에서, 집합에 없는 가장 작은 음이 아닌 정수(mex)로 정합니다. 더 갈 곳이 없는 상태는 그런디 수가 0입니다.

0부터 하나씩 늘려가며 그 값이 집합에 있는지 확인해, 처음으로 없는 값을 찾으면 됩니다. 예를 들어 다음 상태들의 그런디 수가 {0, 1, 3}이면 2가 없으므로 mex는 2입니다.

돌 k개짜리 무더기에서는 0개부터 k−1개까지 모든 크기로 줄일 수 있습니다. 그 다음 상태들의 그런디 수가 귀납적으로 0, 1, ..., k−1이 되므로, mex({0,...,k−1}) = k가 되어 그런디 수가 늘 무더기 크기와 같아집니다.

스프라그-그런디 정리에 따르면, 여러 독립적인 비셈 게임을 동시에 벌여 놓고 매 차례 그중 하나만 골라 두는 합게임의 그런디 수는 각 게임 그런디 수의 XOR과 같습니다. 이 값이 0이 아니면 먼저 두는 사람이, 0이면 나중에 두는 사람이 이깁니다.

두 사람이 번갈아 두고, 둘 자리가 없어진 사람이 지며, 양쪽이 같은 수를 둘 수 있는 «비셈(부분게임적)» 게임에만 씁니다. 체스나 바둑처럼 두 사람이 서로 다른 말을 쓰는 게임에는 이 이론을 그대로 적용할 수 없습니다.