Problem solving: Nim - 돌 가져가기 게임
최근의 삽질 얘기
하노이의 탑을 통해 우리애들은 아직 준비가 안된 것인가… 싶었지만, 어쨌든 흥미는 있는 듯 보여서 더 쉬운 문제로 도전해보기로 했다. 뭐가 쉬운 문제인가… 생각해보다가 계절학교에서 처음 접했던 nim 게임이 생각났다. XOR을 알아야 하는 여러 무더기 버전보다는 좀 더 쉬운 1 무더기 버전으로 시도해 보기로 했다.
문제 소개
돌 무더기가 하나 있고, 두 사람이 번갈아 가며 돌을 가져간다.
- 한 번에 1개, 2개, 또는 3개를 가져갈 수 있다.
- 반드시 하나 이상은 가져가야 한다 (건너뛰기 없음).
- 더이상 가져가지 못하면 진다 - 즉 마지막에 남은 돌을 가져가는 사람이 이긴다.
내 차례에 돌이 N개 남아있을 때, 상대가 어떻게 하든 반드시 이기려면 몇 개를 가져가야 할까? 어떻게 해도 질 수밖에 없는 경우도 있다.
자 이제 그럼 문제를 풀어보자
링크 - hash 부분을 변경해서 여러개의 문제집을 생성할 수 있다. 왼쪽 문제들은 돌이 그림으로 그려져 있어서 직접 지워가며 해볼 수 있고, 오른쪽 문제들은 돌이 많아서 규칙을 찾아야만 풀 수 있다.
단계별 힌트
(힌트를 그냥 읽어주시는 것보다, 아이가 막혀있는 부분을 판단해서 상황에 맞는 힌트를 주는 것이 중요합니다)
- 아이와 직접 바둑알로 몇 판 해보세요. 돌이 적을 때부터 시작하는 게 좋습니다.
- 내 차례에 돌이 1개, 2개, 3개 남아있으면 어떻게 할까요?
- 내 차례에 돌이 4개 남아있으면 어떻게 될까요? 몇 개를 가져가도 괜찮을까요?
- 상대 차례에 4개를 남겨주려면, 5개, 6개, 7개일 때 몇 개를 가져가야 할까요?
- 8개는 어떤가요? 1부터 차례대로 이기는 수, 지는 수를 적어보고 규칙을 찾아보세요.
친절한 해설
(LLM이 작성한 초안이 꽤 괜찮아서, 큰 수정없이 그대로 사용한다)
돌이 N개 남았을 때 내 차례라면 “이기는 자리”인지 “지는 자리”인지를 작은 수부터 거꾸로 따져보자.
- 0개: 졌다~
- 1, 2, 3개: 몽땅 가져가면 바로 이긴다. 즉, 필승법이 있는 자리들.
- 4개: 1-3개 중 무엇을 가져가도 상대에게 1-3개가 남고, 상대가 몽땅 가져간다. 필승법이 없는 자리.
- 5, 6, 7개: 각각 1, 2, 3개를 가져가서 상대에게 4개를 남겨주면 이긴다. 다시말해 필승법이 있다는 뜻.
- 8개: 몇 개를 가져가도 상대에게 5-7개가 남는다. 상대 입장에서 필승법이 있다는 뜻 - 다시말해 나한테는 필승법이 없다는 뜻.
규칙이 보인다. 4의 배수가 지는 자리다. 내가 k개를 가져가면 상대는 4 - k개를 가져가서 매 라운드 정확히 4개씩 줄일 수 있기 때문이다. 그래서 4의 배수를 받은 사람은 계속 4의 배수를 받다가 결국 0개가 남게 된다.
코드 작성
최적 전략을 실행하는 프로그램을 작성해 보세요.
(생전 한번도 코드를 작성해본 적이 없는 아이라면 다음 템플릿을 주세요)
def best_move(N):
"""최적 전략: 주어진 N에 대해 1,2,3 중 최선의 선택을 반환한다"""
pass
N = 21
turn = True
while N > 0:
if turn:
print("Your turn")
take = int(input())
else:
take = best_move(N)
if take not in [1,2,3]:
print("Your code is wrong")
exit()
N -= take
turn = not turn
if turn:
print("you lose")
else:
print("you win!!!")- 처음이라면 다른 코드를 이해하기보단, best_move에 어떤 수식을 넣어야 할 지에 대해서만 생각해보는 편이 낫다고 봅니다.
- modular operator (%)에 대해 소개해 주는 것도 좋아요.
- 근데 잘 모르면,
N - (N // 4) * 4를 해도 되니까 굳이 알 필요는… - Python의 integer division은 C와 다르게
//를 써야한다는 점 주의해야 합니다.
- 근데 잘 모르면,
결론
짜긴 짰는데 딱히 재미있어 하지는 않는 듯 했다.