필승 전략 게임 편집하기

{{추천 문서}}

== 정의 ==

필승 전략 게임을 정의하는 데에 있어 중요한 점은 운이나 실력이 아닌 철저한 '''수학적 계산'''만을 사용하여 이기는 게임인지 여부다. 이 때문에 확률 놀음인 [[포커]]나 실력이 중요한 [[바둑]]은 이 범위에서 제외된다. 또한, 무수히 많은 [[경우의 수]]를 사용한 승리 전략이나 승패가 결정되지 않는 게임 역시 제외된다. 전자의 예로는 [[오목]]이 있으며,<ref>아무런 규칙도 택하지 않을 경우, 먼저 두는 흑에게 필승 전략이 있기는 하지만 경우의 수가 너무 많다.</ref> 후자의 예는 [[틱택토]]가 있다.<ref>두 사람이 모두 전략적으로만 플레이하면 비기게 된다.</ref> 마지막으로, 여러명이 하는 게임이 아닌 일대일 대결 게임만을 다룬다.

가장 많이 알려진 필승 전략 게임은 배스킨 라빈스 31이라는 게임일 것이다. 31을 부르면 지는<ref>규칙에 따라서는 이기는</ref> 게임으로, 초등학교 수준의 필승 전략이 존재하지만 이 사실을 모르는 사람이 매우 많다. 그러나 필승 전략을 사용하여 상대방을 농락하는 짓은 착한 위키러라면 하지 말자. 더욱이 게임에 '''돈'''을 건다면…….{{ㅊ|사기죄}}

가장 대표적인 유형으로, 개요에서 예시로 들은 배스킨 라빈스 31도 님 게임의 일종이다. 이름의 NIM의 어원은 알려지지 않았으며, 훔치다라는 뜻의 영어 동사 nim에서 왔다는 설,<ref>nim은 현재 사어(死語)다.</ref> 가지고 가다라는 뜻의 독일어 nimm에서 왔다는 설, NIM을 뒤집으면 WIN이기 때문에 NIM이라는 설 등이 있다. 이름 뿐만 아니라 게임 자체의 기원도 명확하지 않은데, 고대 중국의 돌 줍기 게임에서 왔다는 설,<ref>Yaglom, I. M. (2001), "Two games with matchsticks", in Tabachnikov, Serge, Kvant Selecta: Combinatorics, I, Volume 1, Mathematical world 17, American Mathematical Society, p. 1–8</ref> 유럽의 선술집에서 하던 성냥개비 게임에서 왔다는 설 등이 있다. 어느 쪽이든 확실한 증거는 없다. {{ㅊ|그럼 도대체 뭐야 이 게임}}

기본적인 룰은 여러 개의 돌 더미 중 하나를 골라 그 더미 안의 돌을 가져가는 것이며, 가장 마지막 돌을 가져가는 사람이 지는 게임이다. 규칙에 따라서는 마지막 돌을 가져가는 사람이 이기게 만들 수도 있으며, 수학적인 필승 전략과 그 원리는 동일하다. 아래 내용은 특별한 말이 없는한 마지막 돌을 가져가는 사람이 패배하는 규칙을 따른다.

{{숨기기|풀이|n-1을 부르면 이깁니다. n-1을 부르기 위해서는 n-1-(x+1)<nowiki>=</nowiki>n-x-2을 부르면 됩니다. 이 과정을 계속 반복하여 최초에 불러야 하는 수를 부르면 됩니다.}}

{{숨기기|풀이|상대방이 n을 부를 수 없게 할려면, 자신이 n-(x+1)<nowiki>=</nowiki>n-x-1을 부르면 됩니다. 그러면 상대방이 몇 개의 수를 부르든 당신 차례에 n은 x개의 안에 있으므로, 당신은 항상 n을 부를 수 있습니다. 이 과정을 반복하면 됩니다.}}

{{숨기기|풀이|당신이 먼저 해야합니다. 첫 번째 줄에서 돌 3개를 빼 7, 7을 만듭니다. 상대방이 바보가 아닌 이상 한 줄 전체를 빼거나 한 줄에 돌을 하나만 남겨 놓을리는 없습니다. 만약 상대방이 그러면 비웃어 주세요. 그렇지 않으면, 두 줄의 돌의 개수를 똑같이 맞춰 주면 됩니다. 2, 2 상태가 된 후, 상대방이 한 줄을 지우면 당신은 남은 줄에서 돌 하나를 빼면됩니다. 만약 상대방이 돌 하나만 뺐다면 당신이 다른 줄을 지우면 됩니다.}}

|rowspan="4"|<br /><br /><math>\oplus</math><br />=  

:<math>\begin{align*}t&=0\oplus t\\&=s\oplus s\oplus t\\&=s\oplus\left(x_1\oplus x_2\oplus\cdots\oplus x_n\right)\oplus\left(y_1\oplus y_2\oplus\cdots\oplus y_n\right)\\&=s\oplus\left(x_1\oplus y_1\right)\oplus\left(x_2\oplus y_2\right)\oplus\cdots\oplus\left(x_n\oplus y_n\right)\\&=s\oplus0\oplus\cdots\oplus\left(x_k\oplus y_k\right)\oplus0\oplus\cdots\oplus0\\&=s\oplus x_k\oplus y_k\end{align*}</math><br /><math>\therefore t=s\oplus x_k\oplus y_k\quad\cdots\left(*\right)</math>

{{인용문2|<math>s=0</math>이면, 어떤 수를 둬도 <math>t\neq0</math>이다.<br /><math>s\neq0</math>이면, <math>t=0</math>으로 만들 수 있는 수가 존재한다.}}

#이제 <math>s\neq0</math>이라 가정하자. <math>s</math>를 2진법으로 나타내었을 때, 제일 왼쪽에 존재하는 1의 자리를 <math>d</math>라 하자.<ref>만약 <math>s</math>가 00101101이면, <math>d=6</math>이다.</ref> 또한, <math>s\neq0</math>이기 때문에 <math>d</math>의 존재가 보장된다. 이제 2진법으로 나타냈을 때, <math>d</math>번째 자리의 수가 0이 아닌 <math>x_k</math>를 고른다. 만약 이런 <math>x_k</math>가 존재하지 않는다면, 모든 <math>x_i</math>의 <math>d</math>번째 자리는 0이고, 님 합을 구하면 <math>s</math>의 <math>d</math>번째 자리는 0이 되어 모순이다. 이제 <math>y_k=s\oplus x_k</math>라 하자. <math>x_k> y_k</math>임을 보일 것이다. <math>x_k</math>와 <math>y_k</math>의 <math>d</math>자리 왼쪽은 전부 똑같고,<ref><math>s</math>의 <math>d</math>자리 왼쪽은 전부 0이므로</ref> <math>d</math>자리의 수는 1에서 0으로 줄어든다. 이 차이는 10진법으로 <math>2^d</math>이고, <math>d</math>자리 오른쪽의 수는 아무리 차이나 봤자 <math>2^d-1</math>이다. 따라서 <math>x_k</math>는 <math>y_k</math>보다 적어도 1 크다. 이는 곧 <math>x_k-y_k</math>개의 돌을 <math>k</math>번째 더미에서 가져갈 수 있음을 보장한다. 또한, (*)에서, <math>t=s\oplus x_k\oplus y_k=s\oplus x_k\oplus\left(s\oplus x_k\right)=0</math>이다.

역사가 오래된 게임인 만큼, 여러 가지 변형된 님 게임이 존재한다. 사실 엄밀하게 따지면, 돌 더미가 한 개인 경우의 님 게임은 이쪽에 속한다.

#번갈아가면서 숫자를 두 개의 '''다른''' 숫자로 쪼갠다. 즉, 10→7, 3은 되지만, 10→5, 5는 안 된다.

이 게임의 필승 전략은 [[Wikipedia:Sprague-Grundy theorem|스프라그-그룬디 정리]]를 응용하여 해결할 수 있다. 영포자나 수포자를 위해 아주 정말 단순하게 결과만을 설명하자면, 각 숫자에는 수학적으로 계산된 님 더미 숫자(nim heap size, 님 값)가 있는데, 수를 쪼갠 뒤의 님 합이 0이 되도록 해주면 이긴다. 참고로 위 에서는 님 합이 2진법에서만 정의된다 하였는데, 그룬디 게임에선 10진법의 님 합을 정의해야 한다. 그룬디 게임에서의 님 합의 정의는 다음과 같다.

== 외부 링크 ==