필승 전략 게임

개요

필승 전략 게임이란, 이름 그대로 어느 한 쪽이 반드시 이길 수 있는 전략을 가진 게임을 말한다. 중요한 것은, 운이나 실력이 아닌 철저한 수학적 계산만을 사용하여 이기는 게임만을 다룬다. 이 때문에 확률 놀음인 포커나 실력이 중요한 바둑은 이 범위에서 제외된다. 또한, 무수히 많은 경우의 수를 사용한 승리 전략이나 승패가 결졍되지 않는 게임 역시 제외된다. 전자의 예로는 오목이 있으며, 후자의 예는 틱택토가 있다. 마지막으로, 여러명이 하는 게임이 아닌 일대일 대결 게임만을 다룬다.

어떤 게임의 필승 전략을 찾는 것은 소위 말하는 창의력 수학의 단골 소재. 수학 경시대회에 나오는 경우도 간혹 있다. 대부분의 경우는 방법을 찾는 것만으로 끝나게 되지만, 게임에 따라서는 그 방법이 왜 필승 전략인지 증명을 해야하는 경우도 있다. 하지만 문제 유형이 거기서 거기라 몇 가지 유형을 풀어봤다면 "아, 이거는 이 방법이구나"하고 감이 온다.

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

목록

NIM 게임

가장 대표적인 유형으로, 개요에서 예시로 들은 배스킨 라빈스 31도 님 게임의 일종이다. 이름의 NIM의 어원은 알려지지 않았으며, 훔치다라는 뜻의 영어 동사 nim에서 왔다는 설, 가지고 가다라는 뜻의 독일어 nimm에서 왔다는 설, NIM을 뒤집으면 WIN이기 때문에 NIM이라는 설 등이 있다. 이름 뿐만 아니라 게임 자체의 기원도 명확하지 않은데, 고대 중국의 돌 줍기 게임에서 왔다는 설, 유럽의 선술집에서 하던 성냥개비 게임에서 왔다는 설 등이 있다. 어느 쪽이든 확실한 증거는 없다. 그럼 도대체 뭐야 이 게임

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

한 더미

배스킨 라빈스 31이 바로 이 유형. 돌 더미가 하나인 경우, 가져가는 돌의 개수에 제한을 두지 않으면 먼저하는 사람이 반드시 이기게 되어 게임의 의미가 없다. 그래서 한 번에 가져갈 수 있는 돌의 수에 제한을 두게 된다. 아래 게임의 필승 전략을 스스로 한번 생각해 보자.

두 사람이 1부터 번갈아 숫자를 부른다. 한 번에 세 숫자까지 부를 수 있으며, 31을 부르면 진다. 당신이 이기기 위해서 먼저 숫자를 불러야 할까 나중에 불러야 할까? 필승 전략은?

힌트 30을 부르면 반드시 이길 수 있습니다. 30을 부르려면 어떤 수를 불러야 할까요?

풀이 30을 부르면 당신의 승리가 보장됩니다. 한 번에 숫자를 세 개까지 부를 수 있으므로, 30-(3+1)=26을 당신이 부르면 상대방이 몇 개의 숫자를 부르든 당신은 30을 부를 수 있습니다. 26을 부르기 위해서는 22를 부르면 되고, 22를 부르기 위해서는 18, 이런 식으로 쭉 내려가면 2를 불렀을 때 승리가 보장됩니다. 따라서 당신이 먼저 수를 2까지 부르면 승리합니다.

위 문제를 해결했으면, 일반적인 경우에 도전해 보자.

두 사람이 1부터 번갈아 숫자를 부른다. 한 번에 x개의 숫자를 부를 수 있으며, n을 부르면 진다. 필승 전략은 무엇일까?

풀이 n-1을 부르면 이긴다. n-1을 부르기 위해서는 n-1-(x+1)=n-x-2을 부르면 된다. 이 과정을 계속 반복하여 최초에 불러야 하는 수를 부르면 된다.

마지막으로, n을 부르면 이기는 경우의 필승 전략도 생각해 보자.

풀이 상대방이 n을 부를 수 없게 할려면, 자신이 n-(x+1)=n-x-1을 부르면 된다. 그러면 상대방이 몇 개의 수를 부르든, n은 x개의 안에 있으므로 당신은 항상 n을 부를 수 있다. 이 과정을 반복하면 된다.

두 더미

돌 더미가 두 개인 경우. 매 턴, 한 더미를 정해 돌을 가져가며, 가져가는 돌의 개수에는 제한이 없다. 한 더미의 돌 전체를 싹 다 빼버려도 가능하단 소리. 아래 예시를 직접 해결해 보자.

두 줄의 돌 더미가 있습니다. 첫 번째 줄에는 돌이 10개, 두 번째 줄에는 돌이 7개. 당신이 이기기 위해서는 먼저 해야할까요 나중에 해야할까요? 당신의 필승 전략은?

힌트 2, 2를 만들면 당신의 승리가 보장됩니다. 왜 일까요?

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

똑같은 방법으로 일반화 된 전략을 세울 수 있으니 일반적인 경우의 해결법은 생략한다. 하지만 중요한 것은, 어째서 위 전략이 성립하는지 모른다는 것이다. 문제의 답을 알지만 풀이는 모르는 그런 경우. 이 필승 전략에 대한 증명은 아랫 문단을 참조하자.