필승 전략 게임

둘이서 베스킨라빈스 31 게임을 해본 사람이 있는가?

다들 알다시피, 베스킨라빈스 31은 1부터 시작해 숫자를 최대 3개씩 부를 수 있고, 31을 먼저 외치는 사람이 지며, 먼저 시작한 사람에게 필승 전략이 존재한다.

왜 그런지 게임이 끝나는 상황부터 거꾸로 되돌아가보자.

베스킨라빈스 31 게임은 30을 말하는 사람이 무조건 이기게 된다.

30을 말하려면, 26을 외쳐야 한다. 26을 외치면, 다음사람이 어떤 수를 외치든 (4 - 외친수)만큼의 수를 말하면, 30을 만들 수 있기 때문이다. 즉, 26을 외치는 사람이 필승한다.

반복적으로 26을 외치려면 22를 외쳐야 하고, 18, 14, 10, 6, 2...까지 간다. 따라서, 먼저 시작한 사람이 1, 2를 외치기만 하면 이미 게임은 끝난 상태인 것이다. 이러한 게임을 필승 전략 게임이 존재하는 게임이라고 한다. 대표적으로는 많이 사용되는 예시는 님 게임 등이 있다.

이제 한번 자세히 관찰을 해보자. 베스킨라빈스 31에는 최대 64가지의 상태가 존재한다고 말할 수 있다.

순서쌍 (현재까지 불려진 수, 현재 차례인 플레이어)를 생각해보자.

현재까지 불려진 수는 0~31까지 숫자가 가능하고, 현재 차례인 플레이어는 플레이어 A, B 두 명이 가능하다. 게임이 진행될 때, 모든 상태는 저 순서쌍으로 표현 가능하다.

예를 들어 게임을 막 시작했을 때는 (0, A)로 나타낼 수 있고, (플레이어 A가 먼저 시작한다고 가정하자) 이 상태에서 플레이어 A가 1, 2, 3을 말했으면 게임의 상태는 (3, B)로 이동하게 된다. 결국, 상태는 (31, A) 또는 (31, B)에 이르게 되고, 게임은 끝난다.

이러한 상태의 순서도는 다음과 같이 그릴 수 있다.

A가 승리한 상태의 노드는 파란색, B가 승리한 상태의 노드는 초록색이라고 하자.

핵심은, 모든 상태 노드는 파란색 혹은 초록색 둘 중 하나로 결정된다. 이는 게임이 막 시작되는 루트 노드도 마찬가지이다.

색깔은 어떻게 결정할까?

(n, A)의 노드는 자식노드 중 파란색 노드가 하나라도 있을 경우 파란색이고, 아닌 경우 초록색이다.

(n, A)의 노드는 자식노드 중 초록색 노드가 하나라도 있을 경우 초록색이고, 아닌 경우 파란색이다.

위 내용이 무슨 의미일까? (n, A)에서는 A가 노드의 이동을 결정할 차례이다. 이 때, 만약 자식노드 중 파란색 노드(A가 승리한 상태)이 있다면 A는 그쪽으로 이동하면 된다. 따라서 현재 상태도 A가 승리한 상태이고, 현재 노드도 파란색으로 칠하면 된다. 하지만 자식노드 중 파란색 노드가 하나도 없을 경우 A는 어떤 수를 두어도 패배하게 되므로, 현재 상태는 패배한 상태가 된다.

결국 끝에서부터 시작하여, 모든 노드의 색깔을 칠하면 루트 노드가 파란색으로 칠해질 경우 이 게임은 A가 필승하는 게임, 초록색으로 칠해질 경우 B가 필승하는 게임이 된다. 이러한 방식으로 우리는 어떤 사람이 필승하게 되는지를 알아낼 수 있다.

재미있는 사실은, 둘이서 플레이하는 게임 중 각 상태의 cycle이 존재하지 않는 모든 게임은, 항상 루트 노드가 한 가지 색으로 정해진다는 점이다. 이러한 게임에는 오목, 오델로 등이 모두 포함된다. 즉, 오목과 오델로는 흑필승이거나 백필승인 게임이다. 단지 경우의 수가 너무나도 많아서 우리가 흑필승인지 백필승인지, 어떻게 해야 필승인지를 모르고 있는 것 뿐이다.

만약 cycle이 존재한다면 어떻게 될까? 위 베스킨라빈스 31의 예시에서, 숫자를 말하지 않고 그냥 턴을 넘길 수가 있다고 가정해보자. 이 경우 숫자가 30까지 올라간다면, 서로가 턴을 계속 넘기는 무한루프의 상황이 발생하게 된다. 이러한 경우는 무승부라고 정의하자.

오목, 오델로 같은 경우는 판에 있는 돌의 수가 순증가하므로, cycle이 존재하지 않는다는 것은 자명하다. 각 상태를 (판에 놓인 돌, 현재 차례인 플레이어)로 정의한다면 베스킨라빈스 31 게임과 다를 바가 없다.

바둑의 경우 약간 더 복잡한데, 상대방의 돌을 따먹는 것이 가능하며 패라는 것도 존재한다. 하지만 (판에 놓인 돌, 현재 차례인 플레이어, 들어낸 돌 수, 최근 두 수)까지 상태에 저장하면 된다. 경우의 수가 너무 많기는 하지만, 유한하다.

하지만 바둑의 경우 인위적으로 cycle을 만들어낼 수가 있으므로 흑필승인지, 백필승인지, 무승부로 수렴하게 되는지는 알 수 없다. 장기나 체스같은 경우도 마찬가지로 cycle이 존재하므로, 흑필승인지, 백필승인지, 무승부로 수렴하게 되는지는 알 수 없다.

옛날에 더지니어스에 나온 12장기도 cycle이 존재하기는 하지만, 경우의 수가 대충 추산해본 결과 2억 4천만 개 정도만 존재하므로 흑필승인지, 백필승인지, 무승부로 수렴하게 되는지 한 번 분석해볼 수 있을 것 같다. 시험 끝나면 이거나 해봐야겠다.