마지막 개체를 제거하면 지게 되는(패배하게 되는) 필승 전략게임

님게임(Nim Game)은 전형적인 필승 전략게임 중 하나이다. 필승 전략게임이란 말 그대로 ‘반드시 이길 수 있는 전략이 존재하는 게임’이라는 의미이다. 이 전략을 먼저 찾는 사람이 게임에서 이길 가능성이 매우 높다. 필승 전략게임의 대표적인 예로는 ‘베스킨라빈스 31’을 들 수 있겠다.

님게임의 종류는 매우 다양하나 이 게임이 필승 전략게임으로서의 가치를 가지려면 1대 1 게임(2명이 대결하는 게임)으로 진행하여야 한다. 선(先)플레이어를 정하고 턴(turn, 차례)을 번갈아가며 플레이를 하게 되는데 자신의 턴에서 최소 한 개 이상의 개체를 규칙에 맞게 제거해야 한다. 이 게임에서는 마지막 개체를 제거하는 사람이 지게 된다.

여기에서 소개할 님게임은 위의 그림처럼 성냥개비를 3개의 층으로 쌓아 올린 구조에서 시작한다.

님게임 플레이 규칙

님게임 플레이 준비물: 활동지(아래에서 다운로드), 연필 한 자루씩

님게임 플레이 규칙은 다음과 같다.

  • 1대 1 게임이며, 턴을 번갈아가며 성냥개비를 제거한다.

  • 자신의 턴에 남아 있는 성냥개비 중 반드시 한 개 이상을 제거해야 한다.

  • 개수에 상관없이 이웃하는 성냥개비를 제거할 수 있으나, 한 개의 층에서만 가능하다([그림2] 참고). 이 때 이미 제거된 성냥개비를 넘나들며 제거할 수는 없다([그림3] 참고).

  • 마지막 성냥개비를 제거하면 이 게임에서 진다.

짝궁과 플레이하기

님게임을 10게임 정도 하다보면 승리 패턴을 승자뿐 아니라 패자들도 이를 찾을 수 있게 된다. 승리 패턴은 다음의 총 4개로 일반화 할 수 있다.

  • 독립된 1개짜리 성냥개비를 1개, 3개를 만들면 이긴다. 이는 “1개짜리 성냥개비 n개 만들기”라는 전략으로 일반화 할 수 있다.

  • 좀 더 큰 전략을 찾는 플레이어도 있다. ‘독립된 2개짜리 성냥개비 2쌍을 만들면 이긴다.’는 전략도 찾을 수 있다.

  • 1개짜리 홀수개, 2개짜리 2쌍 전략을 이용하여 더 큰 문제로 확대하여 ‘독립된 3개짜리 성냥개비 2쌍 만들기’라는 전략을 찾을 수 있다.

  • 1-홀수, 2-2, 3-3 의 문제보다 더 큰 문제 상황에서 찾을 수 있는 패턴은 1-2-3 패턴이다. 게임을 집중하여 분석하는 이는 40분 활동 내에 이 승리 패턴을 찾기도 한다.

짝궁 플레이 후 전략 찾기 활동하기

짝궁과 님게임을 10여 차례 하는 것만으로 승리 패턴을 모두 찾는 것은 힘들다. 그리고 플레이어들에게 승리 패턴을 찾아보자고 하면 이러한 문제를 어떻게 해결해야 할 지에 대한 방법 자체를 모르기 일쑤다. 사실 이 게임의 핵심은 여기서부터이다. 우리는 세상의 모든 문제를 하나하나 예를 들어가며 같이 풀어볼 수는 없지만 이러한 문제들 중 대표적인 일반화 문제들을 접해보고 고민하고 해결해 가면서 ‘문제 해결 방법’ 자체를 학습하는 데에 그 목적이 있다.

님게임의 승리 패턴을 찾는 방법에는 다음과 같은 문제 해결 전략들이 활용된다.

  • 문제를 거꾸로 해결하기 (Bottom-Up)

  • 큰 문제를 작은 문제로 쪼개어 해결하기 (Divide and conquer)

  • 이미 해결된 문제의 해법을 더 큰 문제를 해결하는 데에 재활용하기 (Dynamic Programming)

무턱대고 승리 패턴을 찾아보라고 하면 금세 생각하기를 포기하고 만다. 이 때문에 전략을 찾기 위한 도움 활동지가 필요하다. 활동지에는 게임에서 남은 성냥개비를 제시하고, 나의 턴에서 무엇을 제거할 것인지에 대한 퀴즈 형식의 활동지를 해결해 보게 한다.

님게임의 승리 패턴을 찾는 방법에는 다음과 같은 문제 해결 전략들이 활용된다.

  • 문제를 거꾸로 해결하기 (Bottom-Up)

  • 큰 문제를 작은 문제로 쪼개어 해결하기 (Divide and conquer)

  • 이미 해결된 문제의 해법을 더 큰 문제를 해결하는 데에 재활용하기 (Dynamic Programming)

심화 활동

이 활동에서 예제로 제시된 1-3-5 성냥개비 구조는 승리 패턴을 찾아보기 위한 작은 단위의 문제이다. 이 활동에서 승리 패턴을 찾고 필승 전략을 찾았다면 다음에 제시되는 문제에서 ‘첫 신(神)의 한 수’를 찾아보는 것도 재미있는 일이 될 것이다.

활동지를 단면 또는 양면으로 출력하여 사용하세요.

[활동지]님게임.PDF

님게임 짝 활동 후에 승리 패턴을 찾기 위한 활동지입니다.

[활동지]님게임전략찾기.PDF

님게임 활동을 안내하고 필승 전략에 대한 패턴을 찾는 방법을 알려주는 PPT 및 PDF 자료입니다.

님게임안내.PPT

님게임안내.PDF