Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

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 연산을 ..

티스토리툴바