[개념] NIM_GAME(필승게임)

필승전략 게임인 NIM 게임의 원리와 XOR 연산을 활용한 승패 판별 방법을 설명합니다. 바구니에 담긴 쿠키를 가져가는 게임의 다양한 상황별 승리 전략, 2진수와 XOR 연산의 관계, 그리고 바둑돌 가져가기 문제를 통한 실제 적용 사례를 다루고 있습니다.

Nim게임은 필승게임이며 필승 전략 게임의 승패를 판별하는 알고리즘들을 다루게 된다.

여기서 Nim게임과 XOR연산 사이의 관계를 보여주려고 한다.

또한 알고리즘 문제들 중에서 Nim 게임 문제들이 다양하게 많기 떄문에 익숙해 져야하며, 대표적인 예시를 소개한다.

Nim Game & XOR

승리하는 방법은 쿠키를 마지막까지 다먹은사람이 승자라고 가정한다.

• 1개의 바구니가 있을 때 : 해당 바구니에서 한번에 다 먹으면 승리
• 2개의 바구니가 있을 때 : 2개의 바구니에 있는 쿠키를 같은 개수가 남게 만들어 주면 승리
• 3개의 바구니가 있을 때 : 1, 2, 3개의 쿠키가 남게 만들어 주면 승리
• 마지막으로, 2진수 sum(합계)을 0으로 만들면 승리
  • 상대방은 0으로 절대 못만들게 되기 때문이다.
    => 최종 0때 승. 다먹은거니까.
• 이처럼 조건들마다 다양한 승리 방법들이 존재한다.

예시(XOR)

예로 바구니 2개에 쿠키가 각각 10, 12개 씩이라 가정

• 2진수 변환시 : 1010, 1100 이고, 두 수를 XOR 하면?
• 0110 (XOR:같은 수 0, 다른 수 1)
• 따라서 10이나 12를 바꿔서 XOR시 0000으로 나오게 할 수 있다면 무조건 승.

1100 -> 1010이면? 12 -> 10으로 바꾼것.

• XOR하면 0000이 나와서 무조건 승(상대방은 뭘해도 XOR하면 0000이 안나와서)
• 위에서 설명한 바구니 2개 때 같은 수로 만들면 승리 한다고 한것도,
• 여기서 12->10으로 바꾸니까 승리 하는것처럼 이야기가 연결됨.

바둑돌 가져가기

• 유사하게 풀었던 문제 : coin move game

NIM게임 = 필승전략게임 = 완전정보게임

아래는 위와 다르게 좀 더 복잡하며, 배열 차원도 더 높아졌다. 위에껀 참고만하고 아래를 중점으로 이해하고 기억하자.