Nim

일반적으로 Nim은 완전 정보 게임인 2인 게임입니다. 여러 줄, 즉 ‘더미’에 놓인 물체가 있고, 한 번의 합법적인 수로 한 더미에서 원하는 만큼 물체를 가져갈 수 있습니다. 게임을 제대로 진행하려면 더미를 세 개 이상 놓고 시작해야 합니다. ‘표준 방식’에서는 자기 턴에 가져갈 물체가 없어 수를 둘 수 없는 플레이어가 패배합니다. 이런 게임을 폭넓게 다루는 일반 이론은 Berlekamp, Conway, Guy의 저서 《Winning Ways for Your Mathematical Plays》에서 전개됩니다. 사진에 나온 상업용 버전에서는 플레이어가 번갈아 한 줄에 놓인 말뚝을 1개, 2개, 3개 또는 4개씩 가져갑니다. 사진만 보면 ‘줄’이 어느 방향으로든 이어질 수 있어 ‘더미’가 서로 교차하는 것처럼 보입니다. 이는 대부분의 사람이 아는 Nim과는 다릅니다. 또한 최초 설명에 따르면 이 버전에서는 마지막 말뚝을 가져가야 하는 플레이어가 패배합니다. 이를 표준 승리 조건과 구별해 ‘미제르 플레이’라고 합니다. 많은 조합 게임에서 미제르 플레이는 변형 규칙으로 선택할 수 있습니다. Nim은 해법이 알려진 게임입니다. 즉, 어떤 초기 배치에서든 다음 플레이어 또는 직전 플레이어 중 누가 승리 전략을 갖는지 쉽게 판별할 수 있으며, 다음 플레이어에게 승리 전략이 있다면 좋은 다음 수까지 찾아낼 수 있습니다. Nim에서는 더미의 크기가 아무리 커도 놀라울 만큼 쉽게 이를 알아낼 수 있지만, 그 비결을 알려드리지는 않겠습니다. Nim에 관심을 가질 만한 사람이라면 대부분 해법을 알고 있으므로, 이 게임 자체에는 할 만한 것이 많지 않습니다. 하지만 Nim은 조합 게임 이론에서 핵심적인 역할을 합니다. 모든 유한한 2인 공정 게임은 어떤 의미에서 Nim을 감춘 형태이기 때문입니다. 그런 게임의 각 상황은 Nim의 특정 더미 하나에 대응하며, Nim에서 승리하는 수에 해당하는 수를 두면 감춰진 게임도 완벽하게 플레이할 수 있습니다. Sprouts가 한 예입니다. 그렇다고 Sprouts 자체의 해법이 알려져 있다는 뜻은 아닙니다. ‘감춰진 형태’가 일부만 드러나 있기 때문입니다.