그런디 수

조건

• 모든 정보가 공개되어 있어야 한다
  - 포커는 정보가 공개되어 있지 않다.
  - 베스킨라빈스 31은 모든 정보가 공개되었다
• 두 플레이어가 할 수 있는 행동이 같아야 한다.
• 즉 선공, 후공의 차이 외에 모든 조건이 같아야 한다.

즉, 승리조건으로는 선공이 누구인가, 덩어리의 초기상태가 주요 변수이다.

Nim Game

• 대표적으로 덩어리에 각각 구슬이 존재한다고 할 때, 플레이이어가 덩어리를 하나 선택한 뒤 1개 이상의 구슬을 가져간다. 이를 반복한 뒤 구슬을 가져오지 못하는 플레이어가 패배하는 게임이다.
• Nimber(Grundy 수)는 각 게임상태에 할당되는 정수로, 게임에서 모든 Nimber를 $XOR$ 연산한 값을 $S$라고 했을때 $S$가 0보다 크면 선공이 승리, 0이면 후공이 승리한다.
• 실제로 nim game에서 게임판(덩어리)가 1개라면 무조건 선공이 이긴다

XOR 연산과 승리자의 관계

• XOR연산은 두 비트가 서로 다를때 1이 되는 논리 연산이다.
• Impartial game에서 각 상태의 Nimber의 값을 따져보자.
  - 각 Nimber값은 해당 상태에서 플레이어들이 최적의 전략을 수행한 결과이다.
  - 이때 각 Nimber를 XOR 한 결과가 같으면 0 그렇지 않다면 다른 숫자를 반환한다.
  - 즉, Nimber의 XOR이 0보다 크다면 같은 수만큼 가져가서 결과를 0으로 만들어 줄 수 있는 수가 있다.
  - 반대로 결과가 0이라면 그 다음 수는 무조건 0이 될 수 없다.

승리 조건

• 처음 더미가 주어질 때 모든 구슬에대한 XOR을 한 값인 S를 구한 뒤, 선공은 S를 0으로 만드는 전략, 후공은 S를 0이 아닌 수로 만드는 전략을 사용한다.

Grundy Number

정의

• mex(MinimumExclusiveNumber)는 해당 집합에 존재하지 않는 가장 작은 수를 뜻한다.
• 즉 $G_{state}$를 구하기 위해서는 다음 상태를 알아야 하고, 이 과정이 재귀적으로 반복된다.

승리 조건

• 현재 상태가 0이라면 다음 상태는 0이 될 수 없다
• 현재 상태가 0이 아니라면 다음 상태는 0이 될 수 있다
• 위 조건들을 기반으로 nim game과 유사하게 전략 수립이 가능하다.

문제

• 님 게임 2