항상 이기는 전략 게임 - 님(Nim)게임

님게임

님(Nim)게임은 두사람이 하는 간단한 두뇌게임으로 중세 유럽의 선술집에서 유래되었습니다. 현대에는 게임이론의 한 장르로 발전되어 많은 연구가 진행되고 있습니다.

다음은 님게임 예제 규칙입니다. 님게임 전략을 알면 항상이길 수 있습니다.

• 10개의 구슬이 있습니다. 
• 두사람이 번갈아가며 구슬을 앞에서부터 차례로 가져옵니다.
• 한번에 1개에서 3개까지 가져올 수 있습니다.
• 마지막 10번 구슬을 가져오는 사람이 이깁니다.

1. 10개의 구슬을 앞에서부터 1, 2, 3, 4, .... ,9, 10번으로 번호를 붙여 봅시다.
2. 내차례가 되었을 때 7, 8, 9, 10 네개의 구슬이 남았다고 가정을 해봅시다.
    내가 7번 구슬을 가져가게되면 상대방은 8, 9, 10번 구슬을 가져가게 되어 내가 지게됩니다.
    내가 7, 8번 구슬을 가져가게되어도 지고, 7, 8, 9번구슬을 가져가게 되어도 지게 됩니다.
    구슬이 4개가 남았을 때 내 차례라면 항상 지게 됩니다.
3. 구슬이 4개 남았을 때 먼저하는 사람이 항상 지게 되므로 내차례에 4개가 남도록 하여야 합니다. 
    그러면 반드시 6번 구슬을 가져와야 하겠죠.
4. 6번구슬을 가져오려면 6에서부터 4개인 3, 4, 5, 6번 4개가 남아야 하므로
    1, 2번 구슬을 처음에 가져와야 합니다.
5. 여기서 중요한 단서는 게임 순서는 내가 먼저 해야 유리하단 겁니다.

님게임의 필승전략은 자신이 먼저 시작해서 2개를 가져가고 상대가 부르는 숫자에 자신이 부를 숫자의 합이 4가 되도록 진행을 하는 겁니다.

님게임의 변형으로 목표수 말하기 게임이 있습니다. 일명 "베스킨라빈스31" 게임이라고도 합니다.

2명이서 1부터 31의 숫자를 한사람당 1~3개씩 번갈아가며 불러서 31을 부르는 사람이 이깁니다.

1. 31을 부르기 위해서는 직전 차례에서 31보다 4작은 수를 불러야 합니다.
    따라서 바로 전에 27을 반드시 불러야 합니다.
2. 27을 부르기 위해서는 4작은 23을 불러야 합니다.
3. 23을 부르기 위해서는 4작은 19를 불러야 합니다.
4. 같은 방법으로 15, 11, 7, 3 을 말해야 합니다.
5. 따라서 내가 먼저 시작해서 3을 불러야 유리합니다.

님게임의 필승전략은 수학적으로 존재합니다. 규칙을 아는 사람이 먼저 시작하거나 나중에 시작하는 것이 유리한 불공정한 게임인 거죠.