직사각형 초콜릿 게임

1. 문제

직사각형 모양의 초콜릿이 있습니다. 그리고 이 초콜릿은 일정한 크기의 직사각형으로 나뉘어져 있습니다. 여기서 A는 치약을 왼쪽 아래에 발라놓고(먹으면 민트초코가 되겠네요! 게임을 하는 두 사람 다 민트초코를 싫어한다고 가정합니다.) B에게 게임을 제안합니다. A부터 시작해서 직사각형을 번갈아 가며 하나 씩 선택하고 이 직사각형의 오른쪽 위 영역을 다 먹기로 합니다.

Figure 1. 초콜릿의 예시. 파란색은 치약이 칠해진 부분이다.

1.1. 예시

5×5 모양의 초콜릿이 있다고 가정하면 A는 언제나 이길 수 있습니다. 처음 선택에서 A가 (2,2)를 선택하면 Figure 2와 같이 대칭적인 형태가 남는데, 이후에 B가 선택하는 것을 계속 대칭적으로 따라하면 마지막에 민트초코를 먹는 것은 B가 되기 때문입니다.

Figure 2. A의 필승 전략

2. 필승 전략

이런 형태의 게임은 대칭impartial 게임으로 처음 주어진 초콜릿의 형태에 따라 A나 B 중에 승자가 결정되는 구조처럼 보입니다. 여기서 초콜릿이 임의의 직사각형일 때 A가 언제나 이길 수 있을까요? 물론, 1×1 초콜릿은 제외합니다.

2.1. 존재성

만약에 어떤 초콜릿이 있어서 B(후공)가 언제나 이기는 전략이 존재한다고 가정합니다. A가 처음에 초콜릿을 어떻게 먹어도 B는 그 상황에 맞는 필승수를 생각할 수 있다는 것입니다.

여기서 생각할 수 있는 점은 'B의 전략에는 오른쪽 위 구석의 초콜릿만 먹는 수가 포함되어 있지 않다.'입니다. A가 어떻게 먹어도 오른쪽 위 구석의 초콜릿은 항상 없어지기 때문입니다.

여기서 선공인 A가 오른쪽 위 구석의 초콜릿만 먹는 상황을 생각해봅니다. (앞으로 나오는 그림은 특수한 예시로, 일반적으로도 성립합니다!)

Figure 3. A의 선택

그러면 후공인 B는 그에 맞는 필승수를 두겠죠. 그런데 Figure 4와 같이 A와 B를 거쳤을 때의 초콜릿 모양은 A가 한 번 먹었을 때도 만들어지는 모양입니다.

  

Figure 4-1(왼쪽)과 Figure 4-2(오른쪽). B의 필승수와 동형인 A의 첫 수

Figure 4-1에서는 B가 언제나 이길 수 있고, 같은 원리로 Figure 4-2에서는 A가 언제나 이길 수 있습니다. 따라서 B가 언제나 이기는 초콜릿이었다는 가정에 모순이고, 모든 초콜릿에 대해 A가 이길 수 있습니다.

2.2. 필승, 필패 결정성 증명

사실 이 증명이 전제로 하고 있는 가정은 '모든 상태에서 필승/필패 여부가 결정된다'입니다. 이 가정을 증명하자면 다음과 같습니다.

어떤 상태 c에 대해 '이 상태는 A의 필승 전략이 존재한다'라는 문장을 \(\alpha_A (c)\)라고 놓겠습니다. 이 문장의 의미는 처음에 A가 좋은 수를 놓고, B가 어떤 수를 놓더라도 A가 좋은 수로 맞받아칠수 있다는 것을 뜻합니다. 이 게임이 유한 회 만에 끝나기 때문에 최종 상태는 B의 차례에 민트가 발린 초콜릿만 남아야 하고요.

이제 이 문장의 부정, '이 상태는 A의 필승전략이 존재하지 않는다', \(\lnot \alpha_A(c)\)을 생각해보면, 모든 A의 수에 대해 B가 좋은 수로 맞받아치고, 이것이 계속 반복되더라도 B의 차례에 민트가 발린 초콜릿이 남는 일이 발생하지 않습니다. 그 말은 B의 차례로 끝나지 않는다는 것이고 다음 A의 차례에서 초콜릿 하나만 남거나, 아니면 이 게임이 계속되더라도 초콜릿 하나만 남는 일이 발생하지 않습니다(비김).

따라서 \(\lnot \alpha_A(c)\)는 초기 상태에 비기는 경우이거나, A가 무조건 지는 경우를 뜻합니다. 따라서 A가 필패하는 상태라면 A의 필승전략이 존재하지 않는 상태입니다.

처음 상태가 비기는 경우도 고려할 수도 있습니다만, 이 게임에서 '비긴다'는 것은 아무리 게임이 진행되도 초콜릿 하나만 남는 일이 없다는 것입니다. 하지만 초콜릿의 크기가 유한하기 때문에 그럴 일은 없습니다.

결론은, 초기 상태에서 필승이거나 필패입니다. 유사한 대칭 게임들이 그렇다면 불공평한 것이 아닌가라고 생각할 수 있지만, 바둑과 같은 유명한 게임들은 필승 전략을 계산하는 알고리즘이 너무 계산하기 어렵기 때문에 컴퓨터도 필승 전략을 계산하지는 못합니다. 그러니까 기계학습이 대안이 되고 있는 것이고요.

어쨌든 A는 언제나 이길 수 있습니다. 이 증명은 필승 전략의 존재는 증명했지만, 필승 전략이 무엇인지는 구체적으로 명시하지 않았습니다. 이런 증명을 '비구조적 존재 증명non-constructive proof of existence'이라고 부릅니다. (A가 아주 똑똑하다는 가정 하에) B는 절대 이 게임에 들어가면 안되겠네요.