Grundy Number (Sprague-Grundy)

최종 수정:

1공정 게임

두 플레이어가 번갈아 수를 두고 동일한 선택지를 공유하는 게임을 공정 게임(impartial game)이라 한다. 이동이 불가능한 플레이어가 지는 정규 플레이(normal play) 규칙을 가정한다. 게임의 유한성도 가정한다.

2그런디 수

집합 S의 mex(minimum excludant)는 S에 속하지 않는 가장 작은 음이 아닌 정수다.

  • mex(∅) = 0
  • mex({0, 1}) = 2
  • mex({0, 2}) = 1
  • mex({1, 2, 3}) = 0

공정 게임의 각 국면 v에 대해 그런디 수 G(v)를 재귀 정의한다. F(v)를 v에서 한 수 만에 도달 가능한 국면의 집합이라 하면,

G(v) = mex({ G(u) : u ∈ F(v) })

종단 국면은 F(v) = ∅이므로 G(v) = 0이다.

3Sprague-Grundy 정리

복합 게임의 국면 (v1, ⋯, vk)는 각 성분에서 독립적으로 진행하는 게임이다. 한 수는 정확히 하나의 성분 vi를 그 후속 국면 u ∈ F(vi)로 바꾸고 나머지 성분은 그대로 둔다. 복합 국면 전체의 그런디 수도 한 수로 도달 가능한 복합 국면들에 대한 mex로 정의한다.

복합 게임의 그런디 수는 각 성분의 그런디 수의 XOR이다.

G(v1, ⋯, vk) = G(v1) ⊕ G(v2) ⊕ ⋯ ⊕ G(vk)

(⊕는 비트 XOR)

각 성분의 종단까지 최장 경로 길이의 합에 대한 귀납법을 사용한다. X = G(v1) ⊕ ⋯ ⊕ G(vk)로 둔다.

기저 (합 = 0): 모든 성분이 종단 국면이므로 도달 가능한 국면이 없고 G(vi) = 0이다. 따라서 G(v1, ⋯, vk) = mex(∅) = 0 = X이다.

귀납 (합 > 0): 한 수로 성분 i를 vi → u로 바꾸면 도달하는 복합 국면의 최장 경로 길이의 합이 줄어드므로, 귀납 가설에 의해 그 국면의 그런디 수는 X' = X ⊕ G(vi) ⊕ G(u)이다. 따라서 G(v1, ⋯, vk) = mex({ X' : 가능한 모든 이동 })이고, 이 mex가 X임을 두 주장으로 보인다.

주장 1: 어떤 이동으로도 X' = X가 될 수 없다.

성분 i를 vi → u로 바꾸면 X' = X ⊕ G(vi) ⊕ G(u)이다. X' = X이려면 G(u) = G(vi)여야 하는데, G(vi) = mex({ G(u') : u' ∈ F(vi) })이므로 어떤 후속 국면도 G(u) = G(vi)를 만족하지 않는다. 따라서 X' ≠ X이다. □

주장 2: 모든 0 ≤ y < X에 대해 X' = y가 되는 이동이 존재한다.

d = X ⊕ y로 두면 y < X이므로 d ≠ 0이고, d의 최상위 비트 b는 X에서 1, y에서 0인 자리다. 따라서 X의 b번째 비트가 1이고, G(vi)의 b번째 비트가 1인 성분 i가 존재한다. G(vi) ⊕ d는 b번째 비트가 0이 되어 G(vi) ⊕ d < G(vi)이므로, G의 정의에 의해 G(u) = G(vi) ⊕ d인 u ∈ F(vi)가 존재한다. 이 u로 이동하면 X' = X ⊕ G(vi) ⊕ (G(vi) ⊕ d) = X ⊕ d = y이다. □

주장 1에 의해 X ∉ { X' }이고 주장 2에 의해 {0, 1, ⋯, X−1} ⊆ { X' }이므로 mex({ X' }) = X이다. 따라서 G(v1, ⋯, vk) = X이다. ■

따름 정리: 현재 턴 플레이어가 이기는 것은 X ≠ 0과 동치이다. 그런디 수가 0인 국면에서는 주장 1(의 X = 0인 경우)에 의해 모든 이동이 0이 아닌 국면으로 가고, 0이 아닌 국면에서는 주장 2(의 y = 0인 경우)에 의해 0인 국면으로 가는 이동이 존재한다. 종단 국면의 그런디 수는 0이며 이동할 수 없어 패배 국면이므로, 그런디 수가 0인 국면이 정확히 패배 국면이다.

4참고 문헌

  • Sprague, R. P. (1935). Über mathematische Kampfspiele. Tôhoku Mathematical Journal, 41, 438–444.
  • Grundy, P. M. (1939). Mathematics and games. Eureka, 2, 6–8.
  • Berlekamp, E. R., Conway, J. H., & Guy, R. K. (2001). Winning Ways for Your Mathematical Plays (2nd ed.). A K Peters.