스프라그 - 그런디의 조건

순차적 게임(sequential game)

여러 사람이 차례를 가지고 순서대로 돌아가면서 하는 게임. 게임 이론에서 유명한 죄수의 딜레마는 두 죄수가 동시에 선택을 하고 각 죄수는 상대방이 어떤 선택을 했는지 자신이 선택하기 전에는 모르기 때문에 순차적 게임이 아니다.

완전 정보 게임(perfect information game)

모든 참가자가 게임에 대한 모든 정보를 공유하는 게임. 포커는 남의 카드를 내가 알 수 없기 때문에 완전 정보 게임이 아니다.

공정 게임(impartial game)

행동 집합이 참가자에 상관 없이 게임판의 상태에 따라서만 결정되는 게임. 바둑은 두 사람이 매 턴마다 할 수 있는 행동이 상대와 달라지기에 공정 게임이 아니다.

노멀 게임(normal game)

자기 차례에 할 수 있는 행동이 하나도 없으면 패배하는 게임. 체스에서 체크메이트를 당하면 이를 의무적으로 피해야 하는데 그럴 수 없으면 패배. 따라서 체스는 노멀 게임입니다.

하지만 비노멀게임이여도 스프라그 - 그런디를 적용 할 수는 있다.

여기에 알고리즘을 풀 때엔 한가지 더 조건이 있어야 한다. 두 플레이어가 최적의 게임을 한다 라는 조건이 있어야 승리와 패배를 예측 할 수 있다.

현실에서는 한쪽이 최적의 게임을 하고 한쪽이 최적의 플레이를 하지 않는다면 무조건 최적의 플레이를 하는 사람이 이기게 된다.

게임 예시

베스킨 라빈스 31 같은 게임에 스프라그 - 그런디를 적용 할 수 있다.

하지만 조금 더 작은 예제인 님 게임을 통해 알아볼 것이다.

님게임은 돌이 n개 있고 마지막 돌을 가져가는 사람이 승리하는것이다.

그렇다면 처음에 시작하는사람이 무조건 이기는게 아닌가? 싶을것이다. 그게 맞다. 실제로도 처음에 다 가져가면 그 사람이 이기기에 선공이 승리를 하게 된다.

이것을 행동 집합으로 표현하게 된다면