Sprague-Grundy Theorem (1) 썸네일형 리스트형 63. Nim Game & Sprague-Grundy Theorem 님 게임(Nim Game)은 간단하면서도 게임 이론에서 중요한 역할을 하는 게임으로, 여기서 사용된 전략을 다른 많은 게임에 응용해서 적용할 수 있다. 님 게임은 $0$개 이상의 돌이 있는 $n$개의 더미에서 번갈아 가면서 돌을 가져가는 방식으로 차례를 진행한다. 가져가는 돌의 개수에는 제한이 없지만 한 차례에는 하나의 더미에서만 돌을 가져갈 수 있다. 더이상 돌을 가져갈 수 없는 플레이어가 게임에서 지게 된다. 님 게임에서 각각의 더미에 남아 있는 돌의 개수를 $[x_1, x_2, \ldots x_n]$이라고 하면 이 게임의 상태를 님 합(Nim Sum)으로 분류할 수 있다. 님 합 $s = x_1 \oplus x_2 \oplus \ldots \oplus x_n$이며, $\oplus$는 XOR 연산을 .. 이전 1 다음
