TIL: 체르멜로 정리와 바둑

개요

장강명 작가의 먼저 온 미래를 읽다가 체르멜로 정리 이야기가 나와서 정리해본다.

체르멜로 정리

체르멜로 정리란

1913년, 에른스트 체르멜로(Ernst Zermelo)라는 독일 수학자가 증명한 게임이론 정리

모든 정보가 공개되고, 운이 개입하지 않는 “완벽정보” 게임(바둑, 체스, 오목 등등)에서는 다음 중 하나가 성립한다.

1. 선수(흑)에게 필승 전략이 존재한다
2. 후수(백)에게 필승 전략이 존재한다
3. 양쪽 모두 최선을 다하면 무승부가 된다

체르멜로 정리를 틱택토로 이해해보자

틱택토는 양쪽이 최선을 다하면 반드시 무승부가 나온다. 체르멜로 정리의 세 번째 경우이다.

틱택토가 무승부로 귀결되는 이유는 게임 트리를 모두 분석할 수 있기 때문이다. 모든 가능한 수순을 컴퓨터로 계산해보면, 완벽한 플레이 하에서는 어느 쪽도 이길 수 없다는 것이 증명된다.

체르멜로 정리를 바둑에 적용해보자

이론적으로는 바둑도 체르멜로 정리가 적용된다. 바둑 역시 완벽정보 게임이므로 다음 중 하나가 반드시 성립한다.

• 흑 필승: 흑이 완벽하게 두면 반드시 이길 수 있다
• 백 필승: 백이 완벽하게 두면 반드시 이길 수 있다
• 무승부: 양쪽 모두 완벽하게 두면 무승부가 된다

문제는 바둑의 복잡성인데 바둑의 경우의 수는 대략 10^170개로, 이는 관측 가능한 우주의 원자 개수(10^80개)의 제곱보다도 크다. 현재의 컴퓨터 기술로는 틱택토에서 했던 것처럼 바둑의 완전해를 구하는 것이 불가능하다.

역귀납으로 증명해보기

1. 게임 나무 그리기
   • 지금 눈앞의 판을 뿌리(root)라고 하고, 한 번 둘 때마다 가지를 뻗는다.
   • 마지막까지 두면 잎(leaf)에서 “흑 승/백 승/무승부”가 결정된다.
   • 바둑은 유한 수 만에 끝나므로 이 나무도 유한하다.
2. 잎에서 거꾸로 색칠
   • 잎이 흑 승이면 검은 점, 백 승이면 하얀 점, 무승부면 회색으로 칠한다.
   • 부모 칸으로 올라오며 규칙을 적용한다.
     • 흑 차례 칸이라면 자식 중 하나라도 검은 점이면 그 칸도 검은 점(흑이 그 길 선택).
     • 검은 점이 없고 모두 하얀 점이면 그 칸은 하얀 점(흑이 아무리 해도 백이 이김).
     • 남은 경우는 회색.
3. 뿌리의 색이 바로 ‘결론’
   • 뿌리가 검은 점이면 “흑의 절대 승리 전략 존재”
   • 뿌리가 하얀 점이면 “백의 절대 승리 전략 존재”
   • 뿌리가 회색이면 “둘 다 완벽히 두면 비김(초읽기 없는 룰에선 흔히 ‘지고’라 불리는 지고·무승부)”
4. 전략 만들기
   • 검은 점을 뿌리로 만들었다면 흑은 항상 ‘검은 점으로 이어지는 가지’만 고르면 됨.
   • 이렇게 하면 어떤 백의 대응이든 결국 흑 승리 잎사귀에 도달.

바둑은 기억력 경기가 되는가

체르멜로 정리에 따르면 바둑은 무조건 이길 수 있는 정답이 있다. 다만 경우의 수가 너무나 많아 현재 컴퓨터 기술로는 계산을 해낼 수 없을 뿐이다. 그런데 바둑 AI가 정답에 상당히 근접해있다.

오늘날 프로 바둑 기사들은 AI의 초반 포석 정답을 외워 이해도 못한 채 빠르게 두어버린다고 한다. 바둑 경기는 시간제한이 있으니 이미 정답을 적용할 수 있는 포석에서 시간낭비를 하지 않는 것이다.

원주율 파이를 소수점 몇 자리까지 암기하는지를 겨루는 것이 있다고 한다. Pi World Ranking List 를 보면 세계 기록은 소수점 70030 자리이다. 바둑이라는 게임이 파이 암기를 겨루는 것과 무슨 차이가 있게되는 것일까?