이기는 쪽이 존재한다

"이 판은 백이 이긴 판이다"는 백이 실제로 이긴다는 말이 아닙니다. 흑이 어떻게 받든 백에게 답이 있다는 말입니다. 연속의 정의도, 무한의 크기도, 논리의 한계도 같은 모양의 문장으로 적힙니다. 수학의 참을 두 사람의 게임으로 읽으면, 따로 배운 것들이 한 생각으로 모입니다.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속의 점과 칸은 대부분 누르거나 끌 수 있고, 몇몇 그림에서는 컴퓨터가 상대가 되어 받아 둡니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

체스 해설가가 판을 가리키며 "여기서는 백이 이긴 판입니다"라고 말합니다. 아직 한 수도 더 두지 않았고, 실제 대국에서는 백이 실수해서 질 수도 있습니다. 그런데도 해설가의 말은 뜻이 분명합니다. 백에게 어떤 수가 있어서, 흑이 그 뒤에 어떻게 두든, 백에게 또 어떤 수가 있어서, … 결국 백이 이긴다는 것입니다. '어떤'과 '모든'이 번갈아 나옵니다.

수학책의 문장도 자주 이런 모양입니다. 가장 쉬운 예부터 봅시다. 소수(1과 자기 자신으로만 나누어떨어지는 2, 3, 5, 7, 11, … 같은 수)가 무한히 많다는 것은 "모든 수 n에 대해 n보다 큰 소수⁠(prime number)⁠가 있다"는 것입니다.

이 문장을 두 사람의 주고받기로 바꾸어 봅시다. 문장을 의심하는 사람이 "그럼 100보다 큰 소수를 대 봐"라고 수 n = 100을 부릅니다. 문장을 지키는 사람은 101을 댑니다. 의심하는 사람이 1000을 부르면 1009를 댑니다. 의심하는 사람이 어떤 n을 부르든 지키는 사람이 늘 답할 수 있다면 문장은 참입니다. '모든'은 의심하는 사람이 고르는 수이고, '어떤'('~이 있다')은 지키는 사람이 고르는 수입니다.

함수⁠(function)⁠가 연속이라는 문장(2절에서 자세히 봅니다)은 수가 셋입니다. "모든 허용 오차 ε에 대해 어떤 거리 δ가 있어서, δ보다 가까운 모든 x에서 오차가 ε보다 작다." ε(엡실론)과 δ(델타)는 작은 양수를 가리킬 때 흔히 쓰는 그리스 문자입니다. 여기서는 의심하는 사람이 ε를, 지키는 사람이 δ를, 다시 의심하는 사람이 x를 고릅니다. 이렇게 '모든'과 '어떤'이 섞인 문장은 두 사람이 번갈아 두는 게임으로 바꿀 수 있습니다. 그리고 문장이 참이라는 것은 지키는 사람에게 이기는 전략⁠(winning strategy)⁠, 곧 상대가 무엇을 두든 이기게 해 주는 대응 방법이 있다는 것과 같습니다.

이 글의 질문은 이것입니다. 참이라는 것과 이기는 전략이 있다는 것은 어떻게 같은가, 그리고 그렇게 보면 무엇이 새로 보이는가? 먼저 1912년의 체스 정리에서 게임을 끝에서부터 거꾸로 푸는 법을 보고, 그다음 ε–δ를 직접 두어 봅니다. 이어서 전략이 곧 함수라는 것, 돌무더기 게임 님이 이진법⁠(binary)⁠이라는 것, 가위바위보처럼 동시에 두는 게임에는 수를 확률⁠(probability)⁠로 섞는 전략이 필요하고 거기서 '최대를 구하는 문제 뒤에 짝이 되는 최소 문제가 숨어 있다'는 쌍대성⁠(duality)⁠이 나온다는 것을 봅니다. 뒤쪽에서는 논리가 구별하지 못하는 것을 재는 게임, 끝나지 않는 게임과 집합론⁠(set theory)⁠의 공리⁠(axiom)⁠, 증명을 대화로 읽는 논리, 그리고 두 신경망⁠(neural network)⁠을 겨루게 하는 오늘의 학습까지 갑니다.

1 · 1912년 케임브리지체스는 이미 정해진 게임이다

아직 한 수도 두지 않은 게임에서, 누가 이길지가 이미 정해져 있다고 말할 수 있을까요? 이 절은 게임을 끝에서부터 거꾸로 따지는 방법으로 이 물음에 답합니다. 이 방법은 이 글 전체의 바탕입니다.

1912년 8월, 영국 케임브리지에서 제5회 국제수학자대회가 열렸습니다. 발표자 가운데 취리히 대학의 교수 에른스트 체르멜로가 있었습니다. 4년 전 괴팅겐에서 집합론의 공리를 적어 러셀의 역설⁠(Russell's paradox)⁠을 피할 길을 낸 사람입니다. 집합론의 공리는 '모임'(집합⁠, set⁠)을 만들고 다룰 때 따라야 할 기본 규칙들이고, 러셀의 역설은 '자기 자신을 원소⁠(element)⁠로 갖지 않는 집합들의 모임'처럼 아무 모임이나 허락하면 생기는 모순입니다. 그가 이번에 가져온 주제는 뜻밖에도 체스였습니다. 발표문은 이듬해 대회 회보에 「집합론을 체스 이론에 응용하는 일에 대하여」라는 제목으로 실렸습니다.

체르멜로가 물은 것은 심리나 요령이 아니었습니다. 판 위의 말들의 배치와 누구 차례인지를 합쳐 국면이라고 부릅시다. 그의 물음은 이것이었습니다. "어떤 국면이 백에게 '이긴 국면'이라는 말을 수학적으로 정확히 할 수 있는가? 그렇다면 이기기까지 몇 수가 필요한가?" 그는 '이긴다'를, 흑이 어떻게 두든 유한한 수 안에 반드시 이기게 만들 수 있다는 뜻으로 정의했습니다. 그리고 그런 국면이라면 체스판 위에 있을 수 있는 국면의 개수보다 적은 수 안에 이길 수 있다는 것을 보였습니다. 같은 국면을 두 번 거치는 길은 줄여도 되기 때문입니다. 체르멜로는 판이 반드시 끝난다고 가정하지 않았으니, 이 논증은 같은 수순이 끝없이 되풀이될 수 있는 체스에도 통합니다.

오늘날 '체르멜로의 정리'라는 이름으로 전하는 명제는 조금 더 단순합니다. 우연이 끼지 않고, 두 사람이 모든 것을 보며 번갈아 두고, 반드시 유한한 수 안에 끝나는 게임에서는, 먼저 두는 사람이 이기는 전략이 있거나, 나중 두는 사람이 이기는 전략이 있거나, 두 사람 모두 적어도 비기는 전략이 있다. 이 깔끔한 형태와 끝에서부터 거꾸로 따지는 증명은 1927년 쾨니그 데네시 등을 거치며 다듬어진 것이고, 체르멜로 자신의 논증은 조금 달랐다고 역사가들은 지적합니다.

여기서 전략은 '어떤 국면에서 내 차례가 오면 무엇을 둘지'를 모든 국면에 대해 미리 정해 둔 규칙입니다. 전략을 정해 둔 사람은 대국 중에 생각할 필요 없이 규칙을 따르기만 하면 됩니다. 이기는 전략은 상대가 어떻게 두든 그 규칙을 따르면 이기는 전략입니다. 정리는 세 경우 가운데 하나가 반드시 성립한다고만 말합니다. 그것이 어느 경우인지, 그 전략이 구체적으로 무엇인지는 알려 주지 않습니다.

'거꾸로 따지기⁠(backward induction)⁠'는 작은 게임에서 손으로 해 볼 수 있습니다. 돌 20개가 있고, 두 사람이 번갈아 한 번에 씩 가져갑니다. 마지막 돌을 가져가는 사람이 이깁니다. 돌이 몇 개 남았는지가 국면의 전부이니, 국면은 0부터 20까지 21개뿐입니다. 끝에서부터 이름을 붙여 봅시다. 차례를 맞은 사람이 이길 수 있는 국면을 이기는 자리(W), 상대가 최선을 다하면 반드시 지는 국면을 지는 자리(L)라고 부릅니다.

• 0개는 L입니다. 방금 상대가 마지막 돌을 가져갔으니까요.
• L로 보낼 수 있는 국면은 W입니다. 그 수를 두면 상대가 L을 떠안습니다.
• 어디로 가든 W만 나오는 국면은 L입니다. 무엇을 두어도 상대에게 이기는 자리를 넘겨줍니다.

한 번에 1, 2, 3개를 가져가는 규칙으로 처음 몇 칸을 손으로 채워 봅시다. 1개, 2개, 3개가 남았으면 전부 가져가 상대에게 0개(L)를 넘길 수 있으니 셋 다 W입니다. 4개가 남았으면 1, 2, 3개를 가져가 3, 2, 1개를 남길 수 있는데, 셋 다 W이니 4는 L입니다. 5개에서는 1개를 가져가 상대에게 4(L)를 넘길 수 있으니 W입니다. 이렇게 한 칸의 이름은 그보다 작은 칸들의 이름만 보고 정해지므로, 0에서 시작해 차례로 올라가면 모든 칸에 이름이 붙습니다.

아래 그림에서 단계 버튼을 눌러 이 과정을 20까지 이어 보세요. 그다음 직접 컴퓨터와 한 판 두어 보세요. 눈여겨볼 것은 L 칸이 어떤 규칙으로 늘어서는지입니다.

처음부터(당신이 먼저) 컴퓨터가 먼저

지금 고른 규칙에서 L은 , …입니다. 규칙이 한 번에 1, 2, 3개를 가져가는 처음 규칙이라면 이 목록은 4의 배수입니다. 까닭은 두 가지를 확인하면 됩니다. 첫째, 4의 배수⁠(multiple)⁠가 아닌 국면에서는 4로 나눈 나머지⁠(remainder)⁠만큼 가져가 상대에게 4의 배수를 넘길 수 있습니다. 예를 들어 7 = 4 + 3이니 7개에서는 3개를 가져가 4개를 남깁니다. 둘째, 4의 배수에서는 1~3개 가운데 무엇을 가져가도 4의 배수가 아닌 곳에 닿습니다. 8에서 가져가면 7, 6, 5가 남을 뿐입니다. 그러니 4의 배수를 넘겨받은 사람은 계속 4의 배수가 아닌 수를 돌려줄 수밖에 없고, 결국 0개를 넘겨받아 집니다.

20은 4의 배수이니 L입니다. 그래서 돌 20개에서 먼저 두면, 컴퓨터가 실수하지 않는 한 집니다. 먼저 한 판 져 본 뒤 '컴퓨터가 먼저'를 눌러 보세요. 이번에는 당신이 4의 배수를 계속 넘겨주면 이깁니다. 두 판의 차이는 실력이 아니라 20이라는 수가 L이라는 사실 하나입니다.

이런 놀이는 오래되었습니다. 1612년 프랑스의 클로드 가스파르 바셰 드 메지리아크는 수로 하는 수수께끼를 모은 책 『수로 하는 즐겁고 재미있는 문제들』에 이런 놀이를 실었습니다. 두 사람이 번갈아 1부터 10까지의 수 하나를 부르며 더해 가고, 합을 먼저 100으로 만드는 사람이 이깁니다. 바셰의 풀이가 바로 거꾸로 따지기입니다. 100을 부르려면 그 전에 89를 차지해야 하고(상대가 무엇을 더해도 90~99에 닿으니까요), 89를 차지하려면 78을, … 이렇게 11씩 내려가면 1, 12, 23, …, 89가 이기는 자리입니다. 그러니 먼저 하는 사람이 1을 부르면 반드시 이깁니다. 끝에서부터 값을 매기는 이 생각은 1654년 파스칼이 도중에 멈춘 도박판의 판돈을 나눌 때도 썼습니다. 마지막 판에서부터 한 판씩 거슬러 올라가며 각자의 몫을 매긴 그 계산은 「도박판에서 온 편지」 3절에 있습니다. 게임에서는 '이긴다, 진다'를, 판돈 문제에서는 '받을 몫의 기댓값'(같은 판을 여러 번 되풀이했을 때 평균적으로 받는 몫)을 거꾸로 전하는 것이 다를 뿐입니다.

체스에서도 원리는 같습니다. 끝난 국면에 이름을 붙이는 데서 시작합니다. 체크메이트(왕이 잡힐 위기를 피할 수 없는 상태)를 당한 쪽은 진 것이고, 스테일메이트(차례인 쪽이 둘 수 있는 수가 없는데 왕이 위협받고 있지는 않은 상태)는 비김입니다. 여기서 거꾸로 올라오면, 원리적으로는 처음 국면에까지 W, L, 또는 비김(D)이라는 이름이 붙습니다. 손으로 해 볼 수 없을 뿐입니다.

얼마나 할 수 없는지는 1950년 클로드 섀넌이 「체스를 두도록 컴퓨터를 프로그래밍하기」에서 어림했습니다. 백이 한 번, 흑이 한 번 두는 한 수마다 나올 수 있는 경우를 대략 1,000가지, 한 판을 40수로 잡았습니다. 그러면 나올 수 있는 수순은 1,000을 40번 곱한 수, 곧 $10^{120}$(1 뒤에 0이 120개)가지쯤입니다. 그래서 섀넌은 끝까지 따지는 대신 몇 수 앞까지만 내다보고 거기서 국면에 점수를 매기자고 제안했습니다. 1997년 5월 뉴욕에서 세계 챔피언 가리 카스파로프를 이긴 IBM의 딥 블루도 이 방식을 아주 빠른 계산으로 밀어붙인 기계였습니다.

반대로 말이 몇 개만 남은 끝내기에서는 거꾸로 따지기가 실제로 이루어졌습니다. 1970년대부터 벨 연구소의 켄 톰프슨은 체크메이트 국면에서 거슬러 올라가며 말 다섯 개까지의 끝내기를 모두 푼 표를 만들었습니다. 체스에는 50수 동안 어느 쪽도 말을 잡지 않고 폰도 움직이지 않으면 비김을 청할 수 있다는 '50수 규칙'이 있습니다. 그런데 그 표에서 50수 안에는 이길 수 없는 이긴 국면들이 나오자, 국제체스연맹은 1980년대 말 몇몇 끝내기에 한해 50수 규칙에 예외를 두었습니다. 그러나 더 긴 국면이 잇달아 발견되자 1992년 예외를 모두 거두었습니다. 2012년 모스크바 국립대학의 슈퍼컴퓨터 로모노소프로 완성한 말 일곱 개의 표에는 양쪽이 최선을 다할 때 549수 만에 메이트되는 국면이 있습니다.

더 작은 게임들은 처음 국면까지 모두 풀렸습니다. 틱택토의 처음 국면은 비김이고, 체커도 2007년 캐나다 앨버타 대학의 조너선 섀퍼 연구진이 18년에 걸친 계산 끝에 비김으로 밝혀냈습니다. 하지만 체스의 처음 국면이 어느 쪽인지는 지금도 모릅니다. 이렇게 내다보는 계산을 실제로 하는 방법은 게임 트리⁠(game tree)⁠ 탐색에 있습니다. 컴퓨터 과학의 말로 하면, 거꾸로 따지기는 작은 문제의 답을 표에 적어 두고 그것으로 큰 문제의 답을 채우는 동적 계획법⁠(dynamic programming)⁠이고, 가능한 수순을 나뭇가지처럼 펼친 트리⁠(tree)⁠를 끝까지 내려갔다가 답을 들고 올라오는 재귀⁠(recursion)⁠입니다.

이 글의 제목은 여기서 왔습니다. 체르멜로의 정리는 누가 이기는지 알려 주지 않습니다. 그저 이기는 쪽이 존재한다(또는 둘 다 비길 수 있다)고 말합니다. 이런 증명이 극단으로 가면 이기는 쪽이 누구인지까지 알면서 이기는 방법은 모르는 일도 생깁니다.

그 예가 보드게임 헥스입니다. 육각형 칸으로 된 마름모꼴 판에서 두 사람이 번갈아 빈칸에 자기 색 돌을 하나씩 놓고, 판의 마주 보는 두 변을 자기 돌로 먼저 이으면 이깁니다. 한 사람은 위아래 변을, 다른 사람은 왼쪽과 오른쪽 변을 맡습니다. 판이 다 차면 반드시 어느 한쪽이 이어져 있어서, 헥스에서는 비기는 일이 없습니다.

1949년 무렵 존 내시는 헥스에서 먼저 두는 쪽에게 이기는 전략이 있다는 것을 이렇게 증명했습니다. 거꾸로 나중 두는 쪽에게 이기는 전략이 있다고 해 봅시다. 먼저 두는 사람은 첫 수를 아무 데나 둔 뒤, 그 돌은 없는 셈 치고 자신을 나중 두는 사람이라고 여겨 그 전략을 훔쳐 씁니다. 전략이 지시한 칸에 이미 자기 돌이 있으면 또 아무 데나 둡니다. 판 위에 자기 돌이 하나 더 있는 것은 헥스에서 결코 손해가 아니니, 그러면 먼저 두는 사람이 이깁니다. 그런데 처음에 나중 두는 쪽이 반드시 이긴다고 했으니 모순입니다. 비김이 없으므로 남는 경우는 먼저 두는 쪽이 이기는 것뿐입니다.

이 '전략 훔치기⁠(strategy stealing)⁠' 논증은 이기는 첫 수가 어디인지 말하지 않습니다. 실제로 공식 판인 11×11에서는 이기는 전략이 아직 알려져 있지 않습니다. 과자판을 베어 먹는 게임 촘프에도 같은 논증이 통한다는 것은 데이비드 게일에서 볼 수 있습니다.

헥스는 1940년대에 덴마크의 피트 헤인과 프린스턴의 내시가 따로 발명했습니다. 시인이자 발명가였던 헤인은 1942년 12월 26일 코펜하겐의 신문 『폴리티켄』에 '폴리곤'이라는 이름으로 이 게임을 처음 소개했고, 1948~49년 무렵 프린스턴의 대학원생 내시가 그것을 모른 채 같은 게임을 생각해 냈습니다. 프린스턴 수학과 학생들 사이에 퍼진 이 게임은 1952년 미국의 파커 브러더스가 '헥스'라는 이름으로 팔면서 지금의 이름을 얻었습니다.

정리하면, 우연이 없고 모든 것이 보이며 반드시 끝나는 게임에서는 끝에서부터 W, L, D를 거꾸로 매길 수 있고, 그래서 처음 국면에도 이름이 하나 정해져 있습니다. 다만 그 이름을 실제로 알아내는 일은 게임이 조금만 커져도 불가능할 만큼 비쌉니다.

2 · 1861년 베를린ε와 δ의 대결

함수의 그래프가 '끊기지 않는다'는 말을, 그림을 보지 않고 정확히 할 수 있을까요? 이 절은 그 정확한 정의가 세 수짜리 게임이라는 것을 보고, 그 게임을 직접 두어 봅니다. 게임으로 보면 정의의 부정도, 비슷해 보이는 두 개념의 차이도 저절로 드러납니다.

체스와 아무 상관없어 보이는 곳에서 같은 모양의 문장이 자리를 잡았습니다. 미분⁠(differentiation)⁠과 적분⁠(integral)⁠을 극한⁠(limit)⁠으로 엄밀하게 다시 세우는 분야, 해석학입니다. 1821년 파리의 코시는 에콜 폴리테크니크 강의를 위해 쓴 『해석학⁠(mathematical analysis)⁠ 강의』에서, 변수가 한없이 작아질 때 함수의 변화도 한없이 작아지면 함수가 연속이라고 했습니다. 입력을 조금만 바꾸면 출력도 조금만 바뀐다는 것, 그래프로는 끊긴 데가 없다는 것입니다. '어떤 값에 한없이 다가간다'는 극한을 해석학의 중심에 놓은 책이었지만, '한없이 작아진다'는 말은 움직임의 비유여서 무엇이 무엇보다 먼저 정해지는지가 흐렸습니다. 그 흐림 때문에 코시 자신도 잘못된 정리를 적은 적이 있습니다. 연속함수를 무한히 더해도 연속이라는 정리로, 무엇을 먼저 고르는지를 따지지 않은 탓이었습니다. 그 이야기는 「틀린 증명이 만든 수학」 1절에 있고, 이 절의 끝에서 게임의 말로 다시 만납니다.

이 비유를 부등식으로 바꾼 사람은 베를린 대학의 카를 바이어슈트라스였습니다. 그는 오랫동안 시골 김나지움(대학 진학을 준비하는 독일의 중등학교)의 교사로 일하다 마흔이 넘어서야 베를린으로 왔고, 논문보다 강의로 영향을 끼쳤습니다. 1861년 무렵의 강의를 들은 학생의 노트에 오늘날의 정의가 거의 그대로 있습니다(그보다 앞서 1817년 프라하의 베른하르트 볼차노도 비슷한 말로 연속을 정의했습니다).

정의를 보기 전에 작은 예로 생각을 잡아 둡시다. 함수 $f(x) = x^2$과 점 $a = 1$을 봅니다. $f(1) = 1$입니다. 누군가 "출력을 1에서 0.5 이내로, 곧 0.5와 1.5 사이로 붙잡아 달라"고 요구한다고 합시다. 우리는 "입력을 1에서 0.2 이내로, 곧 0.8과 1.2 사이로 두면 된다"고 답할 수 있습니다. $0.8^2 = 0.64$이고 $1.2^2 = 1.44$이며, 양수에서 $x^2$은 x가 커질수록 커지니 그 사이의 x에서 $x^2$은 0.64와 1.44 사이, 따라서 0.5와 1.5 사이에 머뭅니다. 요구가 0.5가 아니라 0.001처럼 아무리 엄해져도 늘 이렇게 답할 수 있다는 것이 '1에서 연속'이라는 뜻입니다.

이제 일반적으로 적습니다. 함수 $f$가 점 $a$에서 연속이라는 것은

입니다. 기호 $\forall$는 '모든', $\exists$는 '어떤 ~이 있어서', $\Rightarrow$는 '~이면'이라고 읽습니다. $|x - a|$는 x에서 a를 뺀 값의 절댓값(부호를 떼어 낸 크기), 곧 수직선 위에서 x와 a 사이의 거리입니다. 그러니 식 전체를 말로 읽으면 이렇습니다. "모든 양수 ε에 대해, 어떤 양수 δ가 있어서, 모든 x에 대해, x와 a의 거리가 δ보다 작으면 f(x)와 f(a)의 거리가 ε보다 작다." 위의 예에서는 ε = 0.5, δ = 0.2였습니다. '모든'과 '어떤'처럼 '어느 범위의 것에 대해 말하는가'를 정하는 말을 양화사라고 부릅니다.

이 문장을 두 사람의 게임으로 바꾸어 봅시다. 한 사람은 연속이라는 주장을 의심하는 사람, 다른 사람은 증명하는 사람입니다.

1. 의심하는 사람이 허용 오차 $\varepsilon \gt 0$를 부릅니다. 작을수록 까다롭습니다.
2. 증명하는 사람이 그것을 보고 거리 $\delta \gt 0$를 부릅니다.
3. 의심하는 사람이 $a$에서 $\delta$보다 가까운 점 $x$ 하나를 고릅니다.
4. $|f(x) - f(a)| \lt \varepsilon$이면 증명하는 사람이, 아니면 의심하는 사람이 이깁니다.

이 게임은 세 수를 두면 판정만 남습니다. 정의의 양화사⁠(quantifier)⁠ 셋(모든 ε, 어떤 δ, 모든 x)이 바로 그 세 수입니다. 그리고 함수가 $a$에서 연속이라는 것은, 증명하는 사람에게 이기는 전략이 있다는 것과 정확히 같습니다. 아래 그림에서 당신은 의심하는 사람이고, 컴퓨터가 증명하는 사람입니다. 컴퓨터는 통하는 δ 가운데 가장 큰 것(1까지만 봅니다)을 냅니다.

함수는 , 점 $a =$ , 당신이 부른 허용 오차는 $\varepsilon =$ 입니다. δ를 절반으로 줄이게 하기

처음 설정은 $f(x) = x^2$, $a = 1$, $\varepsilon = 0.5$입니다. 컴퓨터가 내놓는 δ는 약 0.225로, $\sqrt{1.5} - 1 = 0.2247\ldots$입니다(띠의 오른쪽 끝에서 $(1+\delta)^2 = 1.5$가 되는 곳). 분홍 점을 초록 띠 안 어디로 끌어도 곡선은 노란 띠를 벗어나지 않습니다. ε를 0.05로 줄여도 컴퓨터는 더 좁은 δ로 답하고, 역시 이깁니다.

이제 함수를 '계단'으로 바꾸어 보세요. $a = 0$에서 값은 1이고, 조금이라도 왼쪽으로 가면 0입니다. ε가 1 이하이면 컴퓨터는 통하는 δ를 찾지 못합니다. 그래도 규칙상 양수 δ를 하나 내야 하니 할 수 없이 작은 δ를 냅니다. 분홍 점을 띠 안의 왼쪽으로 옮기면 당신이 이깁니다. 그곳에서 값은 0이고, f(0) = 1과의 거리 1이 ε 이상이기 때문입니다. 'δ를 절반으로 줄이게 하기'를 몇 번 눌러 보세요. δ가 아무리 작아져도 그 안의 왼쪽 점 하나면 충분합니다.

'sin(1/x)'에서는 사정이 더 나쁩니다. x = 0에서는 1/x를 계산할 수 없으니, 이 함수와 다음의 'x·sin(1/x)'는 x = 0에서의 값을 0으로 정해 둡니다. 0에 가까워질수록 1/x가 한없이 커지므로 곡선이 −1과 1 사이를 점점 빠르게 오갑니다. 그래서 $a = 0$에서 어떤 δ를 잡아도 그 안에 값이 1인 곳이 있고, 그곳과 f(0) = 0의 거리는 1입니다. ε가 1 이하이면 당신이 이깁니다.

그런데 'x·sin(1/x)'로 바꾸면 곡선은 똑같이 빠르게 흔들리는데도 컴퓨터가 이깁니다. sin의 값은 늘 −1과 1 사이이므로 $|x \sin(1/x)| \le |x|$입니다. 흔들림의 폭이 x만큼으로 눌려 있는 것입니다. 그러니 $\delta = \varepsilon$만 불러도 충분합니다. $|x - 0| \lt \varepsilon$인 x에서 $|f(x) - f(0)| \le |x| \lt \varepsilon$이기 때문입니다.

흔히 연속을 "펜을 떼지 않고 그릴 수 있다"로 설명하지만, 이 두 함수 앞에서 그 그림은 별 도움이 되지 않습니다. 0 근처를 펜으로 그릴 수 없기는 둘 다 마찬가지인데, 하나는 연속이고 하나는 아닙니다. 정의는 그림이 아니라 게임의 승패로 판정합니다.

정의의 부정도 게임으로 보면 저절로 나옵니다. '연속이 아니다'는 증명하는 사람에게 이기는 전략이 없다는 것인데, 이 게임에서 그것은 의심하는 사람에게 이기는 전략이 있다는 것과 같습니다. 이 세 수짜리 게임도 1절의 정리처럼 반드시 어느 한쪽이 이기기 때문입니다. 1절에서는 한 수에 고를 수 있는 것이 몇 가지뿐이었지만, 여기서는 ε 하나를 부르는 데도 무한히 많은 선택지가 있습니다. 그래도 수의 개수가 셋으로 유한하면, 마지막 수부터 거꾸로 '이 국면에서 이기는 쪽이 있는가'를 따지는 일이 그대로 통합니다.

의심하는 사람의 이기는 전략을 문장으로 적으면, '모든'과 '어떤'이 서로 자리를 바꾸고 마지막 부등식이 뒤집힙니다.

말로 읽으면 "어떤 양수 ε가 있어서, 모든 양수 δ에 대해, a와의 거리가 δ보다 작으면서 f(x)와 f(a)의 거리가 ε 이상인 x가 있다"입니다. '모든 것이 그렇다'가 아니면 '그렇지 않은 것이 하나는 있다'이고, '그런 것이 있다'가 아니면 '모든 것이 그렇지 않다'입니다. 이 두 규칙을 바깥쪽 양화사부터 하나씩 적용한 결과입니다. 마지막 부분 "거리가 δ보다 작으면 ε보다 작다"가 거짓이라는 것은 "거리가 δ보다 작은데 ε보다 작지 않다"는 뜻이라, '이고'와 ≥로 바뀝니다.

계단 함수에서 당신이 쓴 전략이 바로 이 문장입니다. ε = 0.5를 부르고, 어떤 δ가 오든 $x = -\delta/2$를 고르면 됩니다. 이 x는 0과의 거리가 δ/2로 δ보다 작고, f(x) = 0과 f(0) = 1의 거리는 1로 0.5 이상입니다. 불 대수⁠(Boolean algebra)⁠의 드모르간 법칙("A 그리고 B가 아니다"는 "A가 아니거나 B가 아니다")이 양화사로 넓어진 것이, 게임에서는 두 사람이 역할을 바꾸는 일입니다.

마지막으로 함수를 $x^2$로 돌리고 노란 점 a를 오른쪽으로 끌어 보세요. 같은 ε = 0.5에 대해 δ가 줄어듭니다. a = 1.7에서는 약 0.141입니다. 곡선이 가팔라질수록 x가 조금만 움직여도 값이 크게 변하니, 좁게 답해야 하기 때문입니다.

이것은 무엇을 뜻할까요? 지금까지 증명하는 사람은 a를 본 뒤에 δ를 불렀습니다. 만약 a를 보기 전에 δ를 불러야 한다면, 곧 수의 순서가 "ε → δ → a → x"라면, 실수⁠(real number)⁠ 전체에서 $x^2$에 대해서는 증명하는 사람이 집니다. 어떤 δ를 부르든 의심하는 사람이 a를 충분히 멀리 잡으면 되기 때문입니다. 예를 들어 ε = 0.5에 증명하는 사람이 δ = 0.1을 불렀다면, 의심하는 사람은 a = 5와 x = 5.05를 고릅니다. 거리 0.05는 δ보다 작지만 $5.05^2 - 5^2 = 25.5025 - 25 = 0.5025$로 ε 이상입니다. δ가 더 작으면 a를 더 멀리 잡으면 됩니다.

이 바뀐 순서의 게임에서 증명하는 사람이 이기는 것을 균등 연속⁠(uniform continuity)⁠이라고 부릅니다. 같은 낱말들을 늘어놓는 순서만 바꾸었을 뿐인데 다른 개념이 됩니다. 흔히 양화사의 순서는 문장을 읽기 좋게 늘어놓는 방식일 뿐이라고 생각하지만, 게임으로 보면 순서는 '누가 무엇을 보고 나서 고르는가'이고, 그것이 승패를 바꿉니다. 함수들을 하나씩 늘어놓은 열(함수열)이 어떤 함수에 다가가는 방식에서도 같은 일이 일어납니다. '충분히 뒤의 번호 N부터는 가깝다'고 할 때 그 N을 x를 보기 전에 부르느냐 본 뒤에 부르느냐가 점별 수렴과 균등 수렴⁠(pointwise and uniform convergence)⁠을 가릅니다.

한편 [0, 1]처럼 양 끝을 포함하고 길이가 유한한 구간(닫힌 유계 구간) 위에서는 두 순서의 게임이 같은 결과를 냅니다. 곧 그런 구간에서 연속인 함수는 균등 연속입니다. 1872년 에두아르트 하이네가 이것을 증명해 발표했습니다. $x^2$도 [0, 2] 위로만 제한하면 의심하는 사람이 a를 멀리 잡을 수 없습니다. 실제로 $|x^2 - a^2| = |x - a|\,|x + a|$이고 x와 a가 모두 [0, 2] 안에 있으면 $|x + a| \le 4$이니, δ = ε/4를 부르면 a가 어디든 $|x^2 - a^2| \lt 4\delta = \varepsilon$입니다.

정리하면, 연속의 정의는 '의심하는 사람이 ε, 증명하는 사람이 δ, 의심하는 사람이 x'를 두는 게임이고, 연속이라는 것은 증명하는 사람에게 이기는 전략이 있다는 것입니다. 부정은 역할 바꾸기이고, 수를 두는 순서를 바꾸면 다른 개념이 됩니다.

바이어슈트라스 자신도 1872년 베를린 아카데미에서, 모든 점에서 연속이지만 어느 점에서도 미분할 수 없는 함수를 발표해 그림에 기댄 직관이 얼마나 쉽게 틀리는지를 보였습니다. 미분할 수 있다는 것은 그 점에서 곡선에 접선(곡선을 한 점에서 스치는 직선)의 기울기⁠(slope)⁠가 하나로 정해진다는 뜻입니다. 바이어슈트라스의 곡선은 끊긴 곳은 하나도 없는데 어느 점에도 접선⁠(tangent line)⁠을 그을 수 없습니다. 미분이 무엇을 요구하는지는 「순간의 속도」에 있습니다.

3 · 1920년 크리스티아니아전략은 함수다

2절에서 '연속이다'는 증명하는 사람에게 이기는 전략이 있다는 것이었습니다. 그렇다면 연속임을 증명한다는 것은 정확히 무엇을 하는 일일까요? 이 절의 답은 이렇습니다. 증명은 이기는 전략을 적어 주는 일이고, 그 전략은 상대의 수를 받아 내 수를 돌려주는 함수입니다.

교과서에서 $x^2$이 점 a에서 연속임을 증명하는 ε–δ 증명은 흔히 "δ = min(1, ε/(2|a| + 1))로 잡으면"으로 시작합니다. min은 괄호 안의 두 수 가운데 작은 쪽입니다. 예를 들어 a = 1, ε = 0.5이면 ε/(2|a| + 1) = 0.5/3 ≈ 0.167이 1보다 작으니 δ ≈ 0.167입니다. 2절의 컴퓨터가 낸 0.225보다 작지만 상관없습니다. 통하는 δ보다 작은 δ는 언제나 통하니, 가장 큰 δ를 찾을 필요는 없습니다.

게임의 눈으로 보면 이 한 줄이 증명의 전부입니다. 증명하는 사람의 이기는 전략을 적어 준 것이기 때문입니다. 남은 일은 이 δ가 정말 이기는지 확인하는 것이고, 확인은 세 걸음입니다.

1. $x^2 - a^2 = (x - a)(x + a)$이므로 $|x^2 - a^2| = |x - a|\,|x + a|$입니다. 게임에서 x는 $|x - a| \lt \delta$인 점이니, 첫째 인수는 δ보다 작습니다.
2. 둘째 인수는 $x + a = (x - a) + 2a$로 쪼개어 봅니다. 두 수를 더한 것의 크기는 각각의 크기를 더한 것을 넘지 않으므로 $|x + a| \le |x - a| + 2|a|$이고, δ가 1 이하이니 $|x - a| \lt 1$입니다. 합치면 $|x + a| \le |x - a| + 2|a| \lt 1 + 2|a|$입니다.
3. 두 인수를 곱하고, δ가 $\varepsilon/(2|a| + 1)$ 이하라는 것을 쓰면 다음과 같습니다.

δ를 min으로 잡은 까닭이 여기서 보입니다. 1 이하라는 조건은 둘째 걸음에, $\varepsilon/(2|a| + 1)$ 이하라는 조건은 셋째 걸음에 쓰였습니다.

이 전략이 ε와 a를 받아 δ를 돌려주는 함수라는 데 주목하세요. 1920년 노르웨이 크리스티아니아(지금의 오슬로)의 논리학자 토랄프 스콜렘은 이 관찰을 논리의 도구로 만들었습니다. φ(x, y)를 'x와 y에 대한 어떤 조건'이라 하면(φ는 '파이'라고 읽습니다), "모든 x에 대해 어떤 y가 있어서 φ(x, y)"는 "어떤 함수 g가 있어서 모든 x에 대해 φ(x, g(x))"와 같다는 것입니다. 머리말의 소수 문장이라면 φ(n, p)는 'p는 n보다 큰 소수'이고, g(n)으로는 'n보다 큰 소수 가운데 가장 작은 것'을 잡을 수 있습니다. g(100) = 101, g(1000) = 1009입니다.

이 g를 오늘날 스콜렘 함수⁠(Skolem function)⁠라고 부릅니다. 게임의 말로는 지키는 사람의 전략이고, 증명의 말로는 증명이 실제로 만들어 내는 것입니다. (소수의 예처럼 '가장 작은 것'으로 하나를 콕 집을 수 없을 때, 무한히 많은 x에 대해 y를 한꺼번에 골라 함수 하나로 묶으려면 일반적으로 선택공리⁠(axiom of choice)⁠가 필요합니다. 무한히 많은 선택을 한꺼번에 했다고 쳐도 된다고 허락하는 집합론의 공리입니다. 7절에서 이 공리가 다시 게임에 끼어듭니다.)

1960년대 말 핀란드 헬싱키의 철학자 야코 힌티카는 이 생각을 모든 논리식으로 넓혔습니다. 문장 하나마다 두 사람, 검증자와 반증자가 두는 게임을 정합니다. '어떤'(∃)과 '또는'(∨)에서는 검증자가 대상이나 한쪽을 고르고, '모든'(∀)과 '그리고'(∧)에서는 반증자가 고르고, '아니다'(¬)를 만나면 두 사람이 역할을 바꿉니다. 끝에 남은 단순한 사실이 참이면 검증자가 이깁니다.

자연수⁠(natural number)⁠에 대한 문장 "모든 n에 대해 어떤 p가 있어서 (p > n 그리고 p는 소수)"로 해 봅시다. 반증자가 '모든'에서 n = 100을 고릅니다. 검증자가 '어떤'에서 p = 101을 고릅니다. 이제 '그리고'이니 반증자가 두 조건 가운데 따질 쪽을 고르는데, 101 > 100도 '101은 소수'도 참이니 어느 쪽을 골라도 검증자가 이깁니다. 반증자가 어떤 n을 고르든 검증자는 위의 g(n)을 대면 되니, 검증자에게 이기는 전략이 있습니다. 일반적으로 문장이 참이라는 것은 검증자에게 이기는 전략이 있다는 것이고, 거짓이라는 것은 반증자에게 이기는 전략이 있다는 것입니다.

이 정의에는 작지만 깊은 전제가 숨어 있습니다. 모든 문장이 참이거나 거짓이려면, 모든 문장의 게임에서 어느 한쪽이 반드시 이겨야 합니다. 문장 하나의 게임은 양화사와 '그리고, 또는, 아니다'의 개수만큼의 수로 끝나니 1절의 체르멜로 정리와 같은 논리로 늘 그렇습니다(각 수에서 고를 수 있는 것이 무한히 많아도, 수의 개수가 유한하면 됩니다). 어느 한쪽에 이기는 전략이 반드시 있다는 성질을 게임의 결정성이라고 부릅니다. 곧 게임으로 읽으면 고전 논리의 배중률⁠(law of excluded middle)⁠, "P이거나 P가 아니다"(모든 문장은 참이거나 거짓이다)는 유한한 게임의 결정성으로 나타납니다. (그 결정성을 증명하는 거꾸로 따지기에도 고전 논리가 쓰이니, 배중률을 증명했다기보다 같은 사실을 게임의 말로 옮긴 것입니다.) 그렇다면 수가 무한히 이어지는 게임에서도 반드시 이기는 쪽이 있을까요? 이 물음이 7절의 주제입니다.

게임의 눈은 계산의 비용도 보여 줍니다. 먼저 한 사람만 두는 경우입니다. 한 사람이 증명서를 내밀고 상대는 확인만 하면 되는 문제가 있습니다. 이를테면 "이 지도를 세 가지 색으로 칠할 수 있다"는 주장은 실제로 칠한 지도를 증명서로 내밀면, 이웃한 나라끼리 색이 다른지만 확인하면 됩니다. 이렇게 답이 '예'일 때 빨리 확인할 수 있는 증명서가 있는 문제들이 NP라는 부류를 이룹니다(「기계가 풀 수 없는 문제」 7절). '어떤 칠하기가 있다'는 '어떤' 하나짜리 게임인 셈입니다.

두 사람이 번갈아 두어야 하는 문제는 더 어려워 보입니다(정말 더 어려운지는 아직 증명되지 않았습니다). 증명서 하나로는 부족하고, 상대의 모든 대응에 대한 답을 준비해야 하기 때문입니다. 1973년 래리 스톡마이어와 앨버트 마이어는 '모든'과 '어떤'이 번갈아 붙은 논리식의 참을 가리는 문제가 PSPACE-완전임을 보였습니다. PSPACE는 입력 크기의 거듭제곱 정도의 기억 공간만으로 풀 수 있는 문제들의 부류이고, '완전'은 그 부류의 어떤 문제도 이 문제로 바꾸어 풀 수 있다는 뜻, 곧 그 부류에서 가장 어려운 문제라는 뜻입니다. 1981년 아쇼크 찬드라, 덱스터 코젠, 스톡마이어는 두 사람이 번갈아 (입력 크기의 거듭제곱 정도의) 여러 번 두는 게임의 승패를 가리는 계산이 정확히 이 부류와 같다는 것을 정리했습니다.

판을 n × n으로 키운 헥스의 승패 판정도 PSPACE-완전입니다. 같은 식으로 키운 체스는 EXPTIME, 곧 입력 크기에 대해 지수적으로(2를 거듭 곱하듯) 늘어나는 시간으로 풀 수 있는 부류의 완전 문제입니다. EXPTIME은 PSPACE를 포함하는데, 둘이 정말 다른지는 아직 모릅니다. '어떤' 하나를 더 얹을 때마다 문제가 한 층씩 어려워질 수 있다는 것은, 논리식의 양화사를 세어 실수 집합의 복잡도를 재는 기술 집합론⁠(descriptive set theory)⁠의 층과도 닮았습니다.

정리하면, 증명은 이기는 전략을 적어 주는 일이고 전략은 함수입니다. 모든 논리식은 검증자와 반증자의 게임이 되고, 참은 검증자에게 이기는 전략이 있다는 것입니다.

힌티카의 1968년 논문 제목은 「양화사를 위한 언어 게임」이었고, '언어 게임'이라는 말은 비트겐슈타인에게서 빌린 것입니다. 비트겐슈타인은 그가 죽은 뒤인 1953년에 나온 『철학적 탐구』에서, 낱말의 뜻은 많은 경우 언어 안에서 그 낱말이 쓰이는 방식이라고 보고, 말을 주고받는 여러 활동을 규칙이 있는 놀이에 빗대어 '언어 게임'이라 불렀습니다. 힌티카는 '모든'과 '어떤'의 뜻을 정하는 언어 게임은 찾기의 게임이라고 했습니다. '어떤'은 내가 그런 대상을 찾아내는 수이고, '모든'은 심술궂은 자연이 내미는 대상을 버티는 수라는 것입니다. 반론도 있었습니다. 게임의 규칙만으로는 두는 사람이 왜 이기려고 애써야 하는지가 나오지 않는데, 비트겐슈타인을 끌어온 이 설명이 그 빈자리를 채우기에 충분하지 않다는 것입니다. 그래도 문장의 참을 주고받는 수로 정하는 생각은 이 절의 검증자와 반증자로, 8절의 대화 논리⁠(dialogical logic)⁠로 수학 안에 자리를 잡았습니다.

1612년 리옹에서 나온 바셰의 놀이 책에서 20세기 중반까지. 파리와 베를린의 ε–δ, 취리히에서 케임브리지로 간 체르멜로의 체스, 하버드의 님이 베를린과 케임브리지에서 모든 공정한 게임⁠(impartial game)⁠의 이론이 되는 길을 지도에서 보세요. 수학 줄(파랑)에서 1920년대에 게임과 논리의 사건⁠(event)⁠이 몰려 있는 것도 눈여겨보세요.

4 · 1901년 하버드님, 이진법으로 이기는 게임

1절에서는 국면의 이름(W 또는 L)을 알려고 0부터 차례로 표를 채웠습니다. 국면이 많아지면 이 방법은 금방 힘에 부칩니다. 국면을 보자마자 이름을 계산해 주는 공식이 있을까요? 이 절은 돌무더기 게임 님에서 그런 공식을 찾고, 그 공식이 다른 많은 게임에도 통한다는 것을 봅니다.

1901년 하버드 대학의 수학자 찰스 부턴은 『수학 연보』에 다섯 쪽짜리 글 「님, 완전한 수학적 이론을 가진 게임」을 실었습니다. 첫머리에서 그는 이 게임의 역사를 별로 찾지 못했다고 털어놓습니다. 미국의 여러 대학과 장터에서 여러 형태로 놀던 게임이고, '판탄'이라고도 불렸지만 같은 이름의 중국 게임과는 다르니 '님'이라는 이름을 제안한다는 것입니다.

게임의 규칙은 이렇습니다. 탁자 위에 돌무더기가 세 개 있습니다. 두 사람이 번갈아 무더기 하나를 골라 거기서 돌을 원하는 만큼(적어도 하나, 무더기 전체도 됩니다) 가져갑니다. 마지막 돌을 가져가는 사람이 이깁니다.

1절의 게임과 달리 가져갈 수 있는 양에 제한이 없고 무더기가 셋이라, 국면의 수가 금방 불어납니다. 그런데 부턴은 이기는 규칙을 한 줄로 적었습니다. 그 규칙은 이진법으로 적힙니다.

이진법은 수를 1, 2, 4, 8, …(2를 거듭 곱한 수)의 합으로 적는 방법입니다. 예를 들어 5 = 4 + 1이니 4의 자리에 1, 2의 자리에 0, 1의 자리에 1을 적어 101입니다. 3 = 2 + 1은 011, 4는 100입니다. 각 수는 이런 식으로 딱 한 가지로 적힙니다.

부턴의 규칙은 이렇습니다. 무더기의 크기를 이진법으로 적어 자리를 맞추어 세로로 늘어놓고, 모든 자리에서 1의 개수가 짝수이면 부턴이 '안전한 조합'이라고 부른 국면, 곧 지는 자리(L)입니다. 자리마다 1의 개수가 홀수이면 1, 짝수이면 0을 적어 얻은 수를 님 합⁠(nim-sum)⁠이라 하고 $\oplus$로 적습니다. 받아올림 없이 자리마다 2로 나눈 나머지를 더하는 셈이며, 컴퓨터의 비트 연산⁠(bitwise operation)⁠ XOR과 같습니다. 님 합이 0인 국면이 L이고, 0이 아닌 국면이 W입니다.

아래 그림의 처음 판은 무더기 3, 4, 5입니다. 그림 오른쪽의 이진법 표에서 님 합을 먼저 읽고, 당신이 먼저 두어 컴퓨터를 이겨 보세요. 막히면 바로 아래 설명을 읽고 돌아와도 됩니다.

처음 판(3, 4, 5) 새 판 컴퓨터가 먼저 힌트 켜기/끄기 지금 님 합은 입니다.

처음 판 3, 4, 5는 이진법으로 011, 100, 101입니다. 가운데(2의) 자리에만 1이 하나라서 님 합은 010, 곧 2입니다. 0이 아니니 먼저 두는 당신이 이길 수 있습니다. 2의 자리에 1이 있는 무더기는 A(3)뿐이고, A를 $3 \oplus 2 = 1$개로 줄이면 1, 4, 5가 되어 님 합이 0이 됩니다. 돌을 눌러 두어 보고, 컴퓨터가 두는 동안 이진법 표의 맨 아랫줄이 어떻게 변하는지 보세요. 당신이 님 합을 0으로 만들면 컴퓨터는 어떻게 두어도 0이 아닌 국면을 돌려주고, 당신은 다시 0으로 만듭니다.

왜 이 규칙이 통하는지는 세 줄로 증명됩니다.

1. 끝은 L입니다. 돌이 모두 없어진 국면은 모든 자리가 0이라 님 합이 0입니다.
2. 님 합이 0인 국면에서는 무엇을 두어도 0이 아니게 됩니다. 한 번에 무더기 하나만 바뀌고, 바뀐 무더기의 이진법 표기는 적어도 한 자리가 달라집니다. 그 자리의 1의 개수는 홀짝이 뒤집히니, 님 합의 그 자리가 0에서 1로 바뀝니다.
3. 님 합이 0이 아닌 국면에서는 0으로 만드는 수가 있습니다. 님 합에서 1인 가장 높은 자리를 찾아, 그 자리에 1이 있는 무더기 하나를 고릅니다. 그 무더기에서 님 합의 1인 자리들을 모두 뒤집으면 모든 자리의 1의 개수가 짝수가 됩니다. 3, 4, 5라면 님 합 010의 1은 2의 자리에만 있고, 그 자리에 1이 있는 A = 011의 2의 자리를 뒤집어 001 = 1로 만든 것이 위의 수입니다. 이 수를 실제로 둘 수 있으려면 새 크기가 원래보다 작아야 합니다. 이진법에서 한 자리의 값은 그보다 낮은 자리들을 모두 합한 것보다 큽니다(4 > 2 + 1). 가장 높은 바뀐 자리가 1에서 0으로 가니, 낮은 자리들이 어떻게 바뀌어도 새 크기는 원래보다 작습니다.

1절의 세 규칙(끝은 L, L로 보낼 수 있으면 W, 어디로 가든 W이면 L)을 님 합이라는 수 하나로 한꺼번에 확인한 것입니다. 님 합이 0인 국면을 L, 아닌 국면을 W라고 부르면 세 규칙이 모두 맞으니, 이 이름이 거꾸로 따지기로 얻는 이름과 같습니다. 거꾸로 따지기를 국면마다 하는 대신, 국면의 이름을 계산하는 공식을 찾은 셈입니다.

부턴의 발견은 님 하나의 요령으로 끝나지 않았습니다. 1935년 베를린의 고등학교 교사 롤란트 스프라그가, 1939년 케임브리지의 학생 패트릭 그런디가 서로 모른 채 같은 정리에 이르렀습니다. 두 사람이 똑같은 수를 쓸 수 있고(이런 게임을 공정한 게임이라 합니다), 반드시 끝나고, 마지막으로 두는 사람이 이기는 게임이라면, 어떤 국면이든 님 더미 하나와 같다는 것입니다. 1절의 가져가기 게임도, 님도 공정한 게임입니다.

그 더미의 크기를 국면의 그런디 수라 하고, 거꾸로 따지며 이렇게 구합니다. 한 번에 갈 수 있는 국면들의 그런디 수⁠(Grundy number)⁠를 모아, 거기에 없는 가장 작은 음 아닌 정수(0, 1, 2, … 가운데 하나)를 고릅니다. 1~3개씩 가져가는 게임으로 해 봅시다. 0개에서는 갈 곳이 없으니 모은 수가 하나도 없고, 없는 가장 작은 수는 0입니다. 1개에서는 0개(그런디 수 0)로만 가니 {0}에 없는 가장 작은 수 1입니다. 2개에서는 {1, 0}이니 2, 3개에서는 {2, 1, 0}이니 3입니다. 4개에서는 3, 2, 1개로 가니 {3, 2, 1}이고, 여기에 없는 가장 작은 수는 0입니다.

그런디 수가 0인 국면이 정확히 L입니다. 그런디 수가 0이라는 것은 그런디 수 0인 국면으로 갈 수 없다는 뜻이고, 이것은 1절에서 L을 정한 규칙과 같습니다. 크기 n인 님 더미에서는 0, 1, …, n − 1개로 갈 수 있으니 그런디 수가 정확히 n입니다. 그래서 '님 더미 하나와 같다'는 말이 이름에 맞습니다.

이 정리의 쓸모는 게임을 더할 때 나옵니다. 여러 게임을 나란히 놓고, 차례마다 그 가운데 하나를 골라 한 수를 두는 게임을 생각합시다. 이 게임의 그런디 수는 각 게임의 그런디 수의 님 합입니다. 님 자체가 그 예입니다. 무더기 세 개를 나란히 놓은 게임이 님이고, 무더기 하나의 그런디 수는 그 크기이니, 님 합이 곧 국면의 그런디 수입니다.

1절의 그림으로 돌아가 단계를 끝까지 넘긴 뒤, 를 '그런디 수'로 바꾸어 보세요. 위에서 손으로 구한 대로, 한 번에 1~3개를 가져가는 게임에서 돌 n개의 그런디 수는 n을 4로 나눈 나머지입니다. 곧 이 게임은 크기가 0~3을 오가는 님 더미가 변장한 것입니다.

그러니 이 게임 둘과 님 더미 하나를 나란히 놓은 복잡한 게임도, 세 그런디 수의 님 합만 계산하면 누가 이기는지 압니다. 예를 들어 돌 6개짜리 가져가기 게임(그런디 수 2), 돌 3개짜리 가져가기 게임(3), 크기 1인 님 더미(1)를 나란히 놓으면 $2 \oplus 3 \oplus 1$은 이진법으로 10, 11, 01이라 두 자리 모두 1이 두 개씩이고, 님 합은 0입니다. 차례를 맞은 사람이 지는 자리입니다.

님 합으로 더하면 0을 포함한 자연수들이 군을 이룹니다. 군은 덧셈처럼 두 원소를 합해 다시 원소를 얻고, 0처럼 아무것도 바꾸지 않는 원소가 있으며, 원소마다 더하면 0이 되는 짝(역원⁠, inverse element⁠)이 있는 체계입니다. 님 합의 군에서는 모든 원소가 자기 자신의 역원입니다($a \oplus a = 0$). 같은 수를 두 번 적으면 모든 자리의 1이 두 개씩이 되기 때문입니다. 그래서 같은 게임 두 개를 나란히 놓으면 언제나 나중 두는 사람이 이깁니다. 상대가 한쪽에 둔 수를 다른 쪽에 그대로 따라 두면 되니까요. 이 흉내 내기 전략은 8절에서 증명의 모습으로 다시 나옵니다. 자세한 계산과 그런디 수의 표는 님과 스프라그–그런디 정리에 있습니다.

스프라그–그런디 이론은 두 사람이 똑같은 수를 쓸 수 있는 공정한 게임에서만 통합니다. 체스나 바둑처럼 내 돌과 상대 돌이 다른 게임은 그렇지 않습니다. 이런 게임까지 나란히 놓고 '더하는' 이론은 1970년대 케임브리지의 존 콘웨이가 세웠습니다. 그는 게임 하나하나를 수처럼 더하고 크기를 비교하다가, 실수와 칸토어의 무한 서수(첫째, 둘째, 셋째, …를 무한 너머까지 이어 가며 순서의 자리를 세는 수)를 한꺼번에 담는 새로운 수 체계⁠(number system)⁠에 이르렀습니다. 크누스가 1974년 소설 형식의 짧은 책에서 이 수들에 '초현실수⁠(surreal number)⁠'라는 이름을 붙였고, 콘웨이는 1976년 『수와 게임에 대하여』에서 이론 전체를 적었습니다. 콘웨이가 엘윈 벌캄프, 리처드 가이와 함께 쓴 『이기는 방법』(1982)은 이 이론으로 수많은 놀이를 풀었고, 벌캄프는 뒤에 같은 방법으로 바둑의 끝내기를 분석했습니다. 게임에서 수가 나오는 이 길은 무한의 크기를 다룬 「무한에도 크기가 있다」에서 칸토어가 무한 너머의 자리를 세려고 만든 초한수⁠(transfinite number)⁠ 이야기(6–7절)와 이어집니다.

정리하면, 님의 국면은 무더기 크기들의 님 합이 0이면 L, 아니면 W입니다. 그리고 공정한 게임의 국면은 모두 님 더미 하나(그런디 수)로 바꿀 수 있어서, 여러 게임을 나란히 놓은 게임도 님 합 하나로 풀립니다.

공식이 있으니 기계도 둘 수 있습니다. 님은 계산하는 기계의 첫 놀이 상대였습니다. 1940년 뉴욕 세계 박람회에서 웨스팅하우스는 물리학자 에드워드 콘던 등이 설계한 전기 기계식 님 기계 '니마트론'을 전시했고, 콘던은 뒤에 관람객이 10만 번 넘게 두었다고 회고했습니다. 1951년 영국 축제(Festival of Britain)에서는 페란티사가 님만 두는 전자 컴퓨터 '님로드'를 선보였습니다. 두 기계가 사람을 곧잘 이긴 것은 앞을 멀리 내다보아서가 아니라, 부턴의 님 합이 무더기마다 이진법 자리를 맞추어 홀짝만 세면 끝나는 계산이기 때문이었습니다. 계전기(전기로 여닫는 스위치)와 진공관이 가장 잘하는 일이 바로 켜짐과 꺼짐, 곧 0과 1의 계산이었습니다(「기계가 풀 수 없는 문제」 1절).

5 · 1928년 괴팅겐동시에 두는 게임과 섞은 전략⁠(mixed strategy)⁠

체스와 님에는 공통점이 있습니다. 두 사람이 번갈아 두고, 상대가 무엇을 두었는지 보고 나서 내 수를 고릅니다. 가위바위보는 다릅니다. 두 사람이 동시에 냅니다. 여기서는 1절의 의미로 '이기는 전략'이 없습니다. 가위만 내는 사람은 바위에게 지고, 무엇을 정해 두든 그것을 아는 상대에게 집니다. 그렇다고 이 게임에 아무 이론이 없을까요? 이 절의 물음은 이것입니다. 동시에 두는 게임에서 '가장 잘 두는 법'이란 무엇이고, 그것은 늘 있을까요?

1921년 파리의 확률론자 에밀 보렐은 『콩트 랑뒤』에 실은 짧은 글에서, 수를 하나로 정하지 않고 확률로 섞어 내는 전략을 생각했습니다. 가위바위보라면 셋을 1/3씩 섞습니다. 그러면 상대가 무엇을 내든, 예를 들어 늘 바위를 내더라도, 내가 이길 확률(보)과 질 확률(가위)과 비길 확률(바위)이 모두 1/3입니다. 이기면 +1, 지면 −1로 쳐서 확률을 곱해 더한 평균⁠(mean)⁠ 득실, 곧 기댓값은 $\tfrac13(+1) + \tfrac13(-1) + \tfrac13 \cdot 0 = 0$입니다. 상대가 내 버릇을 알아도 이용할 것이 없습니다. 보렐은 작은 게임들을 풀었지만, 일반적인 게임에서도 이런 균형이 늘 있으리라고는 생각하지 않았습니다. 1926년 12월 7일, 스물두 살의 존 폰 노이만이 괴팅겐 수학회에서 그 반대, 곧 이런 균형이 늘 있다는 것을 발표했습니다. 1928년 『수학 연보』에 「사교 게임의 이론에 대하여」로 실린 이 논문의 중심이 최소최대 정리입니다.

폰 노이만이 다룬 것은 한 사람이 얻는 만큼 다른 사람이 잃는 게임, 곧 영합 게임입니다(두 사람의 득실을 더하면 늘 0이라는 뜻입니다). 그의 정리를 말로 하면 이렇습니다. 두 사람이 쓸 수 있는 수가 유한하고 수를 확률로 섞어도 된다면, 한쪽이 상대가 무엇을 하든 확보할 수 있는 가장 좋은 기댓값⁠(expected value)⁠과, 다른 쪽이 상대가 무엇을 하든 그 이상은 내주지 않을 수 있는 가장 작은 기댓값이 같습니다. 무슨 뜻인지 실제 예로 먼저 보고, 식은 그 뒤에 적겠습니다.

이 정리가 실제로 들어맞는지 본 연구가 있습니다. 경제학자 이그나시오 팔라시오스우에르타는 1995년부터 2000년까지 유럽 프로 축구 리그의 페널티킥 1,417개를 모아, 2003년 「프로는 최소최대로 둔다」라는 논문을 냈습니다. 공이 너무 빨라 골키퍼는 키커가 차는 순간 이미 한쪽으로 뛰어야 합니다. 두 사람 모두 상대의 선택을 보지 못한 채 고르니, 동시에 두는 게임과 같습니다. 키커가 편하게 차는 쪽을 L, 반대쪽을 R이라 하면, 키커가 골을 넣을 확률은 대략 이렇습니다(논문의 값을 반올림).

표는 이렇게 읽습니다. 처음 값으로 보면, 키커가 L로 차고 골키퍼도 L로 뛰면 골 확률은 58%이고, 골키퍼가 반대쪽 R로 뛰면 95%입니다. 키커가 늘 L로만 찬다면 골키퍼는 그것을 알고 L로 뛰어 골 확률을 58%로 낮춥니다. 늘 R로만 찬다면 R로 뛰어 70%로 낮춥니다. 어느 한쪽만 고집하면 키커가 확보하는 것은 많아야 70%입니다.

섞으면 어떨까요? 키커가 L로 차는 비율을 p라 합시다. 골키퍼가 L로 뛰면 골 확률은 L로 찬 경우와 R로 찬 경우를 비율대로 섞은 $58p + 93(1 - p)$이고, R로 뛰면 $95p + 70(1 - p)$입니다. 예를 들어 p = 0.8이면 앞의 것은 $46.4 + 18.6 = 65.0$, 뒤의 것은 $76 + 14 = 90.0$입니다. 골키퍼는 낮은 쪽인 L을 고를 테니, 키커가 확보하는 값은 65%입니다. 이렇게 '두 값 가운데 낮은 쪽'을 p마다 그린 것이 아래 왼쪽 그림의 노란 선입니다. 키커는 이 선이 가장 높은 p를 찾고 싶습니다. 오른쪽 그림은 같은 일을 골키퍼 쪽에서 한 것입니다.

키커가 L로 차는 비율을 로 두면, 골키퍼가 가장 잘 막아도 골 확률 는 확보합니다. 골키퍼가 L로 뛰는 비율을 로 두면, 키커가 가장 잘 차도 만 내줍니다. 노란 점과 청록 점을 끌어 각자 가장 좋은 곳을 찾아 보세요. 가장 좋은 섞기로 표를 논문의 값으로

키커의 가장 좋은 비율은 L이 , 그때 확보하는 값은 입니다. 골키퍼의 가장 좋은 비율은 L이 , 그때 내줄 수밖에 없는 값은 입니다. 두 값이 같습니다. 이것이 최소최대 정리입니다. 논문의 반올림 전 값으로 계산한 예측은 키커 L 약 39%, 골키퍼 L 약 42%였고, 실제로 관찰된 비율은 약 40%와 42%였습니다.

가장 좋은 섞기가 어디에 있는지 보세요. 아래 껍질의 꼭대기는 두 직선이 만나는 곳입니다. 그 점에서는 골키퍼가 L로 뛰든 R로 뛰든 골 확률이 같습니다. 위 껍질의 바닥에서도 마찬가지로, 키커가 어느 쪽으로 차든 골 확률이 같습니다. 처음 표의 값으로 계산해 보면, 두 직선 $58p + 93(1 - p) = 93 - 35p$와 $95p + 70(1 - p) = 70 + 25p$가 만나는 곳은 $93 - 35p = 70 + 25p$, 곧 $60p = 23$에서 p = 23/60 ≈ 0.383이고, 그때 값은 $93 - 35 \times 23/60 \approx 79.6$%입니다. 늘 한쪽으로만 차서 얻는 70%보다 높습니다. 가장 좋은 섞기는 자기에게 좋은 쪽을 고르는 일이 아니라, 상대가 무엇을 해도 마찬가지가 되게 만드는 일입니다. 그래서 흔히 기대하는 것과 다른 일이 일어납니다(아래 '직접 해 보기'). 두 직선이 [0, 1] 안에서 만나지 않으면(한 수가 다른 수보다 늘 나으면) 섞을 필요가 없고, 껍질의 꼭대기는 끝점에 옵니다.

이제 일반적으로 적습니다. 위의 표처럼 행과 열로 늘어놓은 수의 표를 행렬⁠(matrix)⁠이라 부르고, 득점표를 행렬 $A$로 적습니다. 행을 고르는 사람(키커)이 각 행을 고를 확률들의 묶음을 $p$, 열을 고르는 사람(골키퍼)의 것을 $q$라 합니다. 페널티킥에서 $p$는 (L로 찰 확률, R로 찰 확률)이라는 두 수입니다. 행 쪽의 기댓값은 칸마다 '그 행을 고를 확률 × 그 열을 고를 확률 × 칸의 값'을 구해 모두 더한 것이고, 이것을 $p^{\mathsf T} A q$로 적습니다(p 위의 T는 p의 확률들을 가로로 눕혀 쓴다는 표시이고, 식 전체를 '칸마다 곱해 더한 값'의 이름으로 읽으면 됩니다). 폰 노이만의 정리는 다음과 같습니다.

$\max_p$는 'p를 바꿔 가며 가장 크게', $\min_q$는 'q를 바꿔 가며 가장 작게'라고 읽습니다. 안쪽부터 읽으면 왼쪽은 이렇습니다. 행 쪽이 p를 먼저 정해 공개하면 열 쪽은 그것을 보고 기댓값이 가장 작아지는 q로 대응합니다. 행 쪽은 그렇게 당할 것을 알고 그 결과가 가장 큰 p를 고릅니다. 곧 왼쪽은 행 쪽이 섞기를 먼저 공개해도 확보할 수 있는 값이고, 키커 그림에서 노란 선의 꼭대기입니다. 오른쪽은 열 쪽이 먼저 공개해도 막을 수 있는 값이고, 골키퍼 그림에서 청록 선의 바닥입니다.

먼저 공개하는 쪽이 손해를 보니 왼쪽이 오른쪽보다 클 수는 없습니다. 그 둘이 같다는 것이 정리입니다. 섞은 전략을 허용하면 먼저 공개해도 손해가 없고, 그래서 동시에 두는 게임에도 1절처럼 하나로 정해진 '게임의 값'이 있다는 뜻입니다. 처음 표의 페널티킥에서는 약 79.6%였습니다.

정리하면, 동시에 두는 영합 게임⁠(zero-sum game)⁠에서는 수를 확률로 섞는 것이 가장 잘 두는 법이고, 가장 좋은 섞기는 상대가 무엇을 해도 결과가 같게 만드는 섞기입니다. 그렇게 섞으면 두 사람이 확보하는 값이 일치합니다.

누가 게임 이론⁠(game theory)⁠을 시작했느냐는 뒤에 다툼거리가 되었습니다. 보렐의 1921–27년 짧은 글들은 오래 묻혀 있다가 1953년 『이코노메트리카』에 영어로 옮겨 실렸습니다. 함께 실린 해설에서 파리의 수학자 모리스 프레셰는 보렐을 게임 이론의 창시자라고 불렀고, 폰 노이만은 같은 해 같은 학술지에 실린 답글에서 최소최대 정리⁠(minimax theorem)⁠가 증명되기 전에는 이 이론에 내세울 만한 것이 없었다는 취지로 반박했습니다. 섞은 전략이라는 생각을 먼저 낸 사람과, 그것이 늘 통한다는 것을 증명한 사람이 달랐던 것입니다. 보렐은 정리가 틀릴 것이라고 짐작했으니, 둘의 차이는 순서가 아니라 내용에 있었습니다.

괴팅겐의 정리가 경제학의 책이 된 곳은 대서양 건너편이었습니다. 부다페스트에서 자란 폰 노이만은 괴팅겐과 베를린을 거쳐 1930년 프린스턴으로 건너갔고, 1933년 가을 프린스턴 고등연구소가 첫 교수진을 꾸릴 때 그 가운데 한 사람이 되었습니다. 같은 해 독일에서는 나치가 권력을 잡아 유대계 학자들을 대학에서 몰아냈고, 괴팅겐의 수학자들도 흩어졌습니다. 빈 대학의 경제학자 오스카어 모르겐슈테른은 1938년 프린스턴 대학을 방문하던 중 히틀러가 오스트리아를 합병하자 돌아가지 않고 미국에 남았습니다. 고등연구소에서 폰 노이만을 만난 그는 함께 『게임 이론과 경제 행동』을 써서 1944년에 펴냈습니다. 게임 이론의 첫 교과서는 이렇게 중부 유럽을 떠난 두 사람이 프린스턴에서 만나 나온 책이었습니다.

폰 노이만의 원래 증명은 길었고, 1938년 프랑스의 장 빌이 볼록 집합(두 점을 잇는 선분이 늘 그 안에 드는, 움푹 들어간 데 없는 모양)의 기하⁠(geometry)⁠로 짧은 증명을 내놓았습니다. 결정적인 연결은 1947년 가을 프린스턴에서 드러났습니다. 조지 댄치그가 공군의 계획 문제를 적은 선형 계획법⁠(linear programming)⁠을 설명하자, 폰 노이만은 그것이 자기 게임 이론과 같은 구조라는 것을 알아보았다고 전합니다. 선형 계획법은 '2x + y ≤ 10'처럼 일차식으로 적힌 조건들을 모두 지키면서 일차식 하나를 가장 크게(또는 가장 작게) 만드는 문제입니다.

행 쪽이 가장 좋은 섞기를 찾는 일은 선형 계획 문제입니다. 확률들의 합이 1이라는 조건과 '열 쪽이 무엇을 내든 기댓값이 v 이상'이라는 조건 아래에서 v를 가장 크게 하는 문제이기 때문입니다. 열 쪽의 문제는 정확히 그 쌍대 문제⁠(dual problem)⁠, 곧 같은 수들로 조건과 목표의 자리를 맞바꾸어 만든 최소화 문제입니다. 한쪽의 최댓값과 다른 쪽의 최솟값이 같다는 선형 계획의 쌍대 정리⁠(duality theorem)⁠가 곧 최소최대 정리입니다. 1951년 데이비드 게일, 해럴드 쿤, 앨버트 터커가 이것을 증명해 출판했습니다.

최대화 뒤에는 늘 짝이 되는 최소화가 숨어 있다는 이 생각은 쌍대성의 대표적인 예입니다. 조건 하나하나에 '그 조건을 조금 풀어 주면 목표가 얼마나 좋아지는가'라는 가격을 매기는 라그랑주 승수⁠(Lagrange multiplier)⁠와 볼록 최적화⁠(optimization)⁠의 쌍대성, 관을 따라 보낼 수 있는 흐름의 최댓값이 관을 끊어 막는 비용의 최솟값과 같다는 최대 흐름 최소 절단 정리⁠(max-flow min-cut theorem)⁠가 같은 가족입니다. 부다페스트의 쾨니그와 에게르바리가 짝짓기에서 먼저 본 쌍대성이 쿤의 손을 거쳐 배정 문제⁠(assignment problem)⁠의 알고리즘⁠(algorithm)⁠이 된 이야기는 「짝을 찾는 알고리즘」 2–4절에 있습니다.

최소최대 정리는 한 사람의 이득이 곧 다른 사람의 손실인 영합 게임의 이야기입니다. 두 사람이 함께 이득을 보거나 함께 손해를 볼 수 있는 게임에서는 하나로 정해진 '게임의 값'이 없습니다. 1950년 프린스턴의 대학원생 존 내시는 『미국 국립과학원 회보』에 두 쪽짜리 논문 「n인 게임의 평형점⁠(equilibrium)⁠」을 실었습니다. 사람 수와 저마다 쓸 수 있는 수가 유한한 게임이라면, 섞은 전략까지 허용할 때 누구도 혼자서 전략을 바꾸어 이득을 볼 수 없는 상태가 반드시 있다는 것입니다. 오늘날 이것을 내시 균형⁠(Nash equilibrium)⁠이라고 부릅니다. 페널티킥의 두 가장 좋은 섞기도 내시 균형입니다. 키커가 38%로 섞는 한 골키퍼는 비율을 바꿔도 얻을 것이 없고, 그 반대도 마찬가지입니다.

증명의 열쇠는 고정점 정리⁠(fixed-point theorem)⁠였습니다. 함수 f의 고정점⁠(fixed point)⁠은 f가 제자리로 보내는 점, 곧 f(x) = x인 점이고, 고정점 정리는 어떤 조건에서 그런 점이 반드시 있다는 정리입니다. 이듬해의 긴 논문 「비협력 게임」에서 내시는 모두의 전략을 '각자 조금씩 더 나은 쪽으로 옮기는' 연속 함수를 만들고, 그 함수가 움직이지 않는 점이 곧 균형임을 보였습니다. 더 나아질 쪽이 없는 사람만 제자리에 머무니, 모두가 제자리인 점에서는 아무도 혼자 바꾸어 이득을 볼 수 없습니다. 전기 작가 실비아 네이사의 『뷰티풀 마인드』(1998)에 따르면, 1949년 내시가 이 생각을 들고 찾아가자 폰 노이만은 "그건 뻔한 거야. 고정점 정리일 뿐이지"라고 대꾸했다고 합니다.

균형이 모두에게 좋은 것은 아닙니다. 같은 1950년, 미 공군의 연구소인 샌타모니카의 RAND 연구소에서 메릴 플러드와 멜빈 드레셔는 균형대로 두면 두 사람 모두 손해를 보는 게임으로 동료들에게 실험을 했습니다. 프린스턴의 앨버트 터커가 이 게임을 따로 갇힌 두 공범의 이야기로 풀어 설명하면서 '죄수의 딜레마⁠(prisoner's dilemma)⁠'라는 이름이 붙었습니다. 서로 입을 다물면 둘 다 가벼운 벌을 받지만, 상대가 어떻게 하든 자백하는 편이 자기에게 유리하니 둘 다 자백하고 둘 다 무거운 벌을 받습니다. 냉전 초기의 RAND는 핵 억지 같은 군사 전략을 게임으로 따지려고 수학자들을 모았습니다. 뒤에 게일과 함께 매칭⁠(matching)⁠ 이론을 세운 섀플리도 그 가운데 한 사람이었습니다. 내시는 1994년 존 하사니, 라인하르트 젤텐과 함께 노벨 경제학상을 받았습니다. 이 무렵 게임 이론은 폰 노이만의 영합 게임에서 벗어나 경제학과 정치학의 언어가 되어 있었습니다.

학습과의 연결도⁠(connectance)⁠ 있습니다. 1990년대에 컴퓨터 과학자 요아브 프로인트와 로버트 샤피르는 이런 사실을 보였습니다. 두 사람이 같은 게임을 되풀이하며, 판마다 잘 통한 수일수록 다음에 고를 무게를 일정한 비율로 곱해 늘리는 단순한 규칙을 따른다고 합시다. 그러면 두 사람이 쓴 섞기의 평균이 최소최대 전략에 다가갑니다. 이것 자체가 최소최대 정리의 또 다른 증명이 되고, 대충만 맞히는 약한 분류기(예를 들어 메일이 스팸인지 아닌지를 가르는 규칙)들을 모아 강한 분류기를 만드는 부스팅⁠(boosting)⁠이라는 기계 학습⁠(machine learning)⁠ 방법도 이 게임으로 이해할 수 있습니다.

6 · 1961년 바르샤바논리가 구별하지 못하는 것

이제 게임을 거꾸로 씁니다. 지금까지는 문장이 참인지 가리려고 게임을 두었습니다. 이번에는 게임으로 어떤 문장으로도 말할 수 없는 것이 무엇인지 잽니다. 물음은 이렇습니다. 점들이 한 줄로 늘어서 있고, 우리가 쓸 수 있는 말은 "x가 y보다 앞에 있다"(x < y)와 "x와 y가 같다", 그리고 '그리고, 또는, 아니다, 모든, 어떤'뿐입니다. 이때 '모든'과 '어떤'은 점 하나하나에만 쓸 수 있고, '점들의 모임 가운데 어떤 것이 있어서'처럼 모임에는 쓸 수 없습니다. 이런 말을 1차 논리라고 부릅니다. 이 말로 "점의 개수가 짝수다"라는 문장을 쓸 수 있을까요?

몇 개인지 정해진 수라면 쓸 수 있습니다. "점이 적어도 두 개 있다"는 "어떤 x와 어떤 y가 있어서 x < y"입니다. 그러나 '짝수 개'는 2개, 4개, 6개, …를 한꺼번에 말해야 합니다. 답은 '쓸 수 없다'인데, 쓸 수 없다는 것을 증명하려면 모든 가능한 문장을 한꺼번에 상대해야 합니다. 이 절의 게임이 그 일을 합니다.

1954년 알제 대학의 롤랑 프레세가 학위 논문에서 두 구조의 원소를 번갈아 짝지어 가는 방법을 내놓았고, 1961년 바르샤바의 젊은 수학자 안제이 에렌포이히트가 이것을 두 사람의 게임으로 바꾸었습니다. 두 구조 A와 B, 그리고 라운드 수 k가 주어집니다. 여기서 구조는 점들의 줄처럼, 원소들과 그 사이의 관계(누가 앞인가)를 함께 갖춘 것입니다. 한 사람은 둘이 다르다는 것을 드러내려는 훼방꾼, 다른 사람은 둘이 같아 보이게 하려는 복제자입니다.

• 매 라운드, 훼방꾼이 A나 B 가운데 한쪽을 골라 원소 하나를 집습니다.
• 복제자는 다른 쪽에서 원소 하나를 집어 짝을 지어 줍니다.
• k라운드가 끝났을 때, 짝지은 원소들 사이의 관계(누가 앞인가, 같은가)가 A와 B에서 똑같으면 복제자가, 하나라도 다르면 훼방꾼이 이깁니다.

가장 작은 예를 봅시다. 점 2개의 줄과 3개의 줄은 "∃x (∃y y < x 그리고 ∃y x < y)"라는 문장으로 갈립니다. 말로 읽으면 "어떤 점 x가 있어서, x보다 앞에 있는 점도 있고 x보다 뒤에 있는 점도 있다", 곧 "양옆에 점이 있는 가운데 점이 있다"입니다. 3개짜리 줄에서는 참이고 2개짜리 줄에서는 거짓입니다.

이 차이를 게임으로 드러내 봅시다. 2라운드면 됩니다. 1라운드에서 훼방꾼은 3개짜리 줄의 가운데 점을 집습니다. 복제자는 2개짜리 줄에서 어느 한쪽 끝을 집을 수밖에 없습니다. 왼쪽 끝을 집었다고 합시다. 2라운드에서 훼방꾼은 3개짜리 줄에서 가운데 점보다 왼쪽에 있는 점을 집습니다. 복제자는 2개짜리 줄에서 왼쪽 끝보다 더 왼쪽에 있는 점을 찾아야 하는데, 그런 점은 없습니다. 오른쪽 끝을 집었어도 마찬가지입니다. 문장의 바깥쪽 '어떤 x'가 훼방꾼의 첫 수이고, 안쪽의 '어떤 y'가 둘째 수입니다.

이 예가 일반 정리의 모습을 그대로 보여 줍니다. 양화사가 다른 양화사 안에 몇 겹 포개어 있는지를 문장의 양화사 깊이라고 합시다. 위 문장은 '어떤 x' 안에 '어떤 y'가 들어 있으니 깊이 2입니다(안쪽의 두 '어떤 y'는 나란히 있을 뿐 서로 포개지 않았습니다).

에렌포이히트–프레세 정리: 복제자에게 k라운드 게임의 이기는 전략이 있는 것은, 양화사 깊이가 k 이하인 모든 1차 문장에 대해 A와 B의 참거짓이 같은 것과 동치입니다('동치'는 한쪽이 성립하면 다른 쪽도 성립하고, 그 반대도 그렇다는 뜻입니다). 한 방향의 뜻은 이렇습니다. A에서는 참이고 B에서는 거짓인 문장 "∃x φ(x)"가 있다고 합시다(φ(x)는 x에 대한 어떤 조건입니다). 훼방꾼은 A에서 φ를 참으로 만드는 x, 곧 그 문장의 증인을 집습니다. B에서는 문장이 거짓이니 복제자가 무엇을 집든 거기서는 φ가 거짓이고, 훼방꾼은 남은 φ를 가지고 같은 일을 계속합니다. 위의 예에서 본 그대로, 훼방꾼의 이기는 전략이 곧 두 구조를 가르는 문장입니다.

위 줄의 점은 개, 아래 줄은 개, 라운드는 번입니다. 다시 두기 이기는 수 보기

처음 설정(5개와 6개, 2라운드)에서 당신이 무엇을 집든 복제자는 버팁니다. 라운드를 3으로 올리면 이제 당신에게 이기는 전략이 생깁니다. 막히면 '이기는 수 보기'를 누르세요. 복제자가 어떻게 버티는지도 눈여겨보세요. 당신이 집은 점이 끝에서 가까우면 복제자는 끝에서 정확히 같은 거리의 점을 집고, 멀면 적당히 먼 점을 집습니다. 이 수를 받고 나서 남는 라운드가 r번이면 '먼' 것의 기준은 $2^r - 1$개입니다.

그 기준이 나오는 직관적인 까닭은 이렇습니다. 이미 집은 점들 사이(또는 줄 끝까지)에 남은 점들을 '틈'이라고 부릅시다. 훼방꾼의 가장 좋은 수는 틈의 가운데 점을 집어 틈을 반으로 가르는 것이고, 한 번 가를 때마다 틈은 절반쯤으로 줍니다. 점 7 = $2^3 - 1$개짜리 틈이라면 7 → 3 → 1 → 0으로, 끝까지 가르는 데 세 번이 듭니다. 그래서 r라운드가 남았을 때 $2^r - 1$개 이상인 틈은 훼방꾼이 끝까지 세어 볼 수 없고, 복제자는 그런 틈들을 크기가 달라도 같은 것처럼 다룰 수 있습니다. 정확한 결과는 이렇습니다. 점 m개와 n개의 줄은 m = n이거나 둘 다 $2^k - 1$개 이상일 때, 그리고 그때에만, 양화사 깊이 k 이하의 문장으로 구별되지 않습니다. 처음 설정에서 k = 2이면 기준은 3개이고 5와 6은 둘 다 3 이상이니 복제자가 버팁니다. k = 3이면 기준은 7개이고 5는 7보다 적으니 훼방꾼이 이깁니다.

이제 처음 물음에 답할 수 있습니다. "점의 개수가 짝수다"를 뜻하는 1차 문장이 있다고 해 봅시다. 그 문장의 양화사 깊이는 어떤 정해진 수, 이를테면 k일 것입니다. 그런데 점 $2^k$개의 줄과 $2^k + 1$개의 줄은 둘 다 $2^k - 1$개 이상이니 깊이 k 이하의 문장으로 구별되지 않습니다. 따라서 그 문장은 두 줄에서 참거짓이 같아야 합니다. 그런데 한쪽은 짝수 개이고 한쪽은 홀수 개이니 모순입니다. 짝수라는 성질은 순서의 1차 논리⁠(first-order logic)⁠로 쓸 수 없습니다. 문장 하나는 정해진 깊이만큼만 '세어 볼' 수 있는데, 짝수인지 알려면 끝까지 세어야 하기 때문입니다.

반면 상태 두 개짜리 유한 오토마톤⁠(finite automaton)⁠은 홀짝을 셉니다. 유한 오토마톤은 글자를 하나씩 읽으며 정해진 몇 개의 상태 사이를 옮겨 다니는 가장 단순한 기계입니다. '지금까지 짝수 개'와 '지금까지 홀수 개' 두 상태를 두고, 점을 하나 읽을 때마다 상태를 바꾸면 됩니다. 오토마톤⁠(automaton)⁠과 문법이 기계의 힘에 따라 층을 이룬다는 촘스키의 위계는 「말을 세는 기계」 6절에 있습니다.

1971년 로버트 맥너튼과 시모어 패퍼트는 글자열(글자를 한 줄로 늘어놓은 것으로, 글자의 자리들이 점의 줄이 됩니다)에 대해 1차 논리로 쓸 수 있는 언어가 좁은 부류뿐임을 보였습니다. 정규 표현식⁠(regular expression)⁠은 글자열의 무늬를 적는 식으로, 예를 들어 a*는 'a를 0번 이상 되풀이'를 뜻합니다. 1차 논리로 쓸 수 있는 것은 정규 표현식으로 쓸 수 있는 언어 가운데, 이 별표(되풀이) 대신 여집합('이 무늬에 맞지 않는 모든 글자열')만 써서 적을 수 있는 것들입니다. 짝수 길이는 그 밖에 있습니다.

이것은 쓸모 있는 한계입니다. 1970년 IBM의 에드거 코드가 제안한 관계형 데이터베이스(자료를 표 여러 개로 나누어 담는 방식)의 질의 언어, 곧 표에서 조건에 맞는 행을 고르고 표 두 개를 이어 붙이는 연산들의 모음인 관계 대수⁠(relational algebra)⁠는 1차 논리와 표현력이 같습니다(코드의 모형이 정렬과 함께 데이터베이스의 뼈대가 된 이야기는 「줄 세우기의 한계」 8절에 있습니다). 1979년 벨 연구소의 앨프리드 에이호와 프린스턴의 제프리 울먼은 이런 질의로는 "A에서 B로 비행기를 갈아타며 갈 수 있는가" 같은 도달 가능성을 물을 수 없음을 보였습니다. 그래프가 이어져 있다는 성질도 1차 논리로는 쓸 수 없다는 것이 같은 종류의 게임 논증으로 증명됩니다. 데이터베이스 표준 언어 SQL에 1999년판부터 되부르는 질의(질의의 결과를 다시 같은 질의에 넣기를 더 나올 것이 없을 때까지 되풀이하는 질의)가 들어간 까닭입니다.

반대로 1974년 로널드 페이긴은 '어떤 집합(또는 관계)이 있어서'라는 양화사를 맨 앞에 허용한 논리로 쓸 수 있는 성질이 정확히 NP에 속하는 성질임을 보였습니다. 예를 들어 "지도를 세 가지 색으로 칠할 수 있다"는 "빨강으로 칠할 나라들의 모임, 파랑의 모임, 초록의 모임이 있어서, 모든 나라가 셋 가운데 하나에 들고 이웃한 두 나라는 같은 모임에 들지 않는다"로 적힙니다. 앞의 '모임이 있어서'가 3절에서 본 증명서, 곧 실제로 칠한 지도에 해당합니다. 논리의 표현력과 계산의 어려움이 같은 잣대로 재어지는 것입니다.

정리하면, 에렌포이히트–프레세 게임에서 복제자에게 k라운드를 버티는 전략이 있다는 것은 양화사 깊이 k 이하의 어떤 문장도 두 구조를 가르지 못한다는 것입니다. 그래서 복제자의 이기는 전략을 보이는 것이 '이 성질은 1차 논리로 쓸 수 없다'를 증명하는 방법이 됩니다.

7 · 1935년 르부프끝나지 않는 게임

지금까지의 게임은 모두 정해진 수만큼 두면 끝났고, 그래서 끝에서부터 거꾸로 따질 수 있었습니다. 게임이 끝없이 이어져도 어느 한쪽에 이기는 전략이 늘 있을까요? 이 절은 실수의 구간을 좁혀 가는 끝없는 게임 하나를 두어 보고, 이 물음이 결국 집합론의 공리를 무엇으로 삼느냐의 문제가 된다는 것을 봅니다.

1930년대 폴란드의 도시 르부프(지금 우크라이나의 리비우)에는 대학 근처에 '스코틀랜드 카페'라는 곳이 있었습니다. 스테판 바나흐와 스타니스와프 마주르, 스타니스와프 울람 같은 수학자들이 몇 시간씩 앉아 대리석 탁자에 연필로 문제를 적었다고 합니다. 1935년 바나흐의 아내가 두꺼운 공책 한 권을 사 와 카페에 맡겼고, 수학자들은 거기에 문제를 적고 상금을 걸었습니다. 이 공책이 '스코틀랜드 책'입니다. 36년 뒤에야 풀린 153번 문제에는 마주르가 살아 있는 거위를 걸었고, 1972년 스웨덴의 페르 엔플로가 바르샤바에서 그 거위를 받았습니다.

43번 문제는 마주르가 낸 게임이었고, 상금은 포도주 한 병이었습니다. 실수의 집합 E가 정해져 있습니다. 첫 사람(I)이 구간 하나를 고르면, 둘째 사람(II)이 그 안에서 더 작은 구간을 고르고, I가 다시 그 안에서 더 작은 구간을 고르기를 끝없이 계속합니다. 여기서 구간은 [0.2, 0.5]처럼 두 수 사이의 실수를 모두 모은 것입니다(대괄호는 양 끝도 포함한다는 표시입니다). 겹겹이 줄어든 구간들의 공통 부분, 곧 모든 구간에 동시에 들어 있는 점들 가운데 E의 점이 있으면 I가, 없으면 II가 이깁니다. 마주르는 E가 어떤 집합일 때 누가 이기느냐고 물었고, 1935년 8월 4일 바나흐가 같은 공책에 "마주르의 추측은 옳다"고 적었습니다. 증명은 1957년 미국의 존 옥스토비가 출판했습니다.

판을 [0, 1]로 정하고 E가 그 안의 유리수(1/2, 2/3처럼 분수로 쓸 수 있는 수) 전체라고 합시다. I는 공통 부분에 유리수⁠(rational number)⁠가 남게 하고 싶고, II는 막고 싶습니다. 유리수는 어느 구간에나 빽빽이 들어 있으니 I가 유리해 보입니다. 그러나 이기는 전략은 II에게 있습니다.

열쇠는 유리수를 셀 수 있다는 사실, 곧 1번, 2번, 3번, …처럼 자연수로 번호를 붙여 빠짐없이 한 줄로 늘어놓을 수 있다는 사실입니다. [0, 1]의 유리수라면 분모가 1인 것, 2인 것, 3인 것, … 순서로 0/1, 1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, …처럼 늘어놓으면 됩니다(2/4처럼 앞에 나온 수와 같은 것은 건너뜁니다). II는 자기 차례마다, 지금 구간 안에 남은 유리수 가운데 번호가 가장 앞선 것을 비켜 가는 구간을 고르면 됩니다. 한 번 비켜 갈 때마다 남은 것 가운데 가장 앞선 번호가 밖으로 밀려나니, n번째 차례가 지나면 목록의 처음 n개는 모두 밖에 있습니다. 그래서 몇 번이든 번호가 붙은 유리수는 그 번호의 차례까지는 반드시 쫓겨납니다.

그림에서 당신은 I입니다. 유리수 하나를 노리고 구간을 골라, II가 정말 모든 유리수를 쫓아내는지 확인해 보세요.

처음부터 한 수 무르기 지금 라운드를 두었고, 구간의 폭은 입니다. 지금 구간 안에 남은 유리수 가운데 목록상 가장 앞선 것은 입니다.

유리수 하나를 노리고 그 둘레를 눌러 보세요. 1/2 근처를 누르면 II는 1/2을 비켜 가고, 확대한 막대의 눈금 가운데 하나를 골라 다시 노려도 II는 그 구간에서 번호가 가장 앞선 유리수를 또 비켜 갑니다. 몇 라운드만 지나면 목록의 처음 20개는 모두 회색이나 빨강이 되고, '가장 앞선 유리수'의 번호는 수천, 수백만, 수십억으로 뜁니다. 게임은 끝나지 않지만, 번호가 얼마인 유리수든 그 번호의 라운드까지는 반드시 쫓겨납니다. 한편 이 그림의 II는 구간의 폭을 한 라운드에 10분의 1로 줄입니다. 구간들이 양 끝을 포함하고(닫혀 있고) 겹겹이 줄어들어 폭이 0으로 가니, 공통 부분에는 정확히 한 점이 남습니다. 공통 부분이 비지 않는 것은 실수의 완비성⁠(completeness)⁠, 곧 실수의 수직선에는 구멍이 없다는 성질 덕분입니다. 유리수만으로는 이것이 성립하지 않습니다. 남은 한 점은 유리수를 모두 비켜 갔으니 유리수가 아닌 수, 곧 무리수⁠(irrational number)⁠입니다.

이 전략은 낯이 익습니다. 1874년 칸토어가 실수가 셀 수 없다는 것을 처음 증명할 때 쓴 방법이 바로 이것이었습니다. 실수의 목록이 주어졌다고 하고, 목록의 수들을 차례로 비켜 가는 구간을 겹겹이 고르면, 공통 부분의 점은 목록에 없습니다. '어떤 셀 수 있는 집합이든 II가 바나흐–마주르 게임에서 이긴다'는 사실에서 '실수는 셀 수 없다'가 곧바로 나옵니다. II가 위의 방법으로 두면 공통 부분에 점이 하나 남고(완비성), 그 점은 그 집합 밖에 있습니다. 그러니 어떤 셀 수 있는 집합도 [0, 1]의 실수를 다 담지 못합니다. 뒷날의 대각선 논법⁠(diagonal argument)⁠도 같은 비켜 가기입니다.

바나흐가 증명한 마주르의 추측은 이것을 끝까지 밀고 간 것입니다. 먼저 '어디에서도 조밀⁠(dense)⁠하지 않은' 집합을 정합시다. 어느 구간을 잡든, 그 안에 이 집합의 점이 하나도 없는 더 작은 구간이 있는 집합입니다. 점 하나나 유한 개의 점이 그 예입니다. 이런 집합을 셀 수 있을 만큼(번호를 붙일 수 있을 만큼) 모은 합집합⁠(union)⁠을 '성긴' 집합이라고 합니다. 마주르의 추측은 II에게 이기는 전략이 있는 것은 E가 성긴 집합일 때, 그리고 그때에만이라는 것입니다. 유리수 전체는 점 하나짜리 집합들을 셀 수 있을 만큼 모은 것이니 그 가장 쉬운 예이고, 위의 전략은 '점 하나를 비켜 간다'를 '어디에서도 조밀하지 않은 집합 하나를 비켜 간다'로 바꾸면 그대로 일반화됩니다.

이 게임에는 1절과 결정적으로 다른 점이 있습니다. 끝이 없습니다. 체르멜로의 정리는 끝난 국면에서 거꾸로 올라오는데, 끝나지 않는 게임에는 출발할 끝이 없습니다. 그렇다면 무한한 게임에서도 언제나 어느 한쪽에 이기는 전략이 있을까요? 한쪽에 이기는 전략이 있는 게임을 '결정된' 게임이라고 부릅니다(3절의 결정성과 같은 말입니다).

1953년 게일과 프랭크 스튜어트는 두 가지를 보였습니다. 첫째, I가 이길 때는 언제나 유한한 단계에서 승리가 확정되는 게임(어느 순간 '이제 무엇을 두어도 I가 이긴다'가 되는 게임)은 결정됩니다. 둘째, 선택공리를 쓰면 결정되지 않는 게임을 만들 수 있습니다. 뒤의 증명은 다시 비켜 가기입니다. 전략은 실수만큼 많으니 선택공리로 한 줄로 세우고, 전략 하나하나를 차례로 무력화하도록 이기는 쪽의 조건 E를 만들어 나갑니다. 그러면 어떤 전략도 이기지 못하는 게임이 생깁니다.

무한 게임은 양화사가 끝없이 이어진 문장으로 볼 수 있습니다. "I에게 첫 수 x₁이 있어서, II의 모든 x₂에 대해, I에게 x₃이 있어서, …, 수열이 E에 든다." 이 문장의 부정은 '모든'과 '어떤'을 끝없이 바꾸어 적은 문장, 곧 II가 이긴다는 문장과 같을까요? 양화사가 유한하면 2절의 부정 규칙(드모르간 법칙⁠, De Morgan's laws⁠)을 바깥에서부터 한 번씩 적용해 늘 같다는 것을 확인할 수 있습니다. 양화사가 무한하면 그렇게 끝까지 적용할 수 없고, 두 문장이 같다는 것이 곧 그 게임의 결정성입니다. 그리고 선택공리 아래에서는 그것이 성립하지 않는 게임이 있습니다.

1962년 폴란드 브로츠와프의 얀 미치엘스키와 후고 슈타인하우스는 거꾸로 "모든 무한 게임은 결정된다"를 공리로 삼으면 어떨지 제안했습니다. 이 결정성 공리⁠(axiom of determinacy)⁠는 선택공리와 함께 쓸 수 없습니다. 위에서 본 대로 선택공리가 결정되지 않는 게임을 만들어 내기 때문입니다. 대신 결정성 공리는 실수의 모든 부분집합⁠(subset)⁠을 르베그 측도⁠(Lebesgue measure)⁠로 잴 수 있다는 것(어떤 집합이든 '길이'가 정해진다는 것) 같은 깔끔한 결과를 줍니다. 선택공리 아래에서는 길이를 잴 수 없는 집합이 있습니다.

오늘날 집합론자들은 선택공리를 버리지 않고, 결정성을 '정의할 수 있는' 집합들로 제한해 묻습니다. 1975년 도널드 마틴은 이기는 쪽의 조건이 보렐 집합⁠(Borel set)⁠인 게임은 모두 결정된다는 것을 증명했습니다. 보렐 집합은 구간에서 출발해 '여집합⁠(complement)⁠ 잡기'와 '셀 수 있을 만큼 합치기'를 되풀이해 만들 수 있는 집합으로, 보통 수학에서 만나는 집합은 거의 다 여기에 듭니다. 1980년대 말 마틴과 존 스틸은 아주 큰 무한이 있다고 가정하면, 보렐 집합에서 더 나아가 '그림자 내리기'(평면의 집합을 직선으로 사영하기)와 여집합 잡기를 되풀이해 얻는 사영 집합⁠(projective set)⁠의 게임까지 결정된다는 것을 보였습니다. 자세한 이야기는 게임의 결정성과 기술 집합론에 있습니다.

정리하면, 끝나지 않는 게임에서는 거꾸로 따지기를 시작할 끝이 없고, 선택공리를 받아들이면 어느 쪽도 이기는 전략이 없는 게임이 실제로 있습니다. '이기는 쪽이 존재한다'는 문장은 무한 앞에서 정리가 아니라 공리의 문제가 됩니다.

슈타인하우스는 크라쿠프의 공원 벤치에서 바나흐를 알아본 바로 그 사람으로, 바나흐와 함께 르부프의 수학을 이끌었습니다. 전쟁 뒤 국경이 옮겨져 르부프가 소련 땅이 되고 독일의 브레슬라우가 폴란드의 브로츠와프가 되자, 1945년 그는 이 도시로 옮겨 대학의 수학과를 새로 꾸렸습니다. 미치엘스키도 그곳에서 공부한 수학자입니다. 르부프 카페의 게임이 브로츠와프의 공리로 이어진 데에는 이런 사람의 이동이 있었습니다.

8 · 1958년 베네치아증명은 대화이고, 전략이다

지금까지 게임은 참을 가리는 도구였습니다. 이 절의 물음은 이것입니다. 증명 자체를 두 사람의 대화로 볼 수 있을까? 그렇게 보면 대화의 규칙을 조금 바꾸는 것만으로 '어떤 논리를 쓰는가'가 바뀝니다.

1958년 베네치아의 세계 철학 대회에서 독일의 수학자이자 철학자 파울 로렌첸은 한 걸음 더 나갔습니다. 강연 「논리와 겨룸」에서 그는 논리 법칙 자체를 대화의 규칙으로 정의하자고 했습니다. 한 사람(제안자)이 명제를 주장하고, 다른 사람(반대자)이 공격합니다. "A 그리고 B"를 주장한 사람은 반대자가 고른 쪽을 지켜야 하고, "A 또는 B"를 주장한 사람은 한쪽을 골라 지켜야 하며, "A이면 B"를 주장한 사람은 반대자가 A를 인정하면 B를 지켜야 합니다. 어떤 명제가 논리적으로 참이라는 것은, 명제의 내용과 상관없이 제안자에게 모든 공격을 이겨 내는 전략이 있다는 것입니다.

'명제의 내용과 상관없이'를 대화의 규칙으로 만든 것이 하나 더 있습니다. 제안자는 P처럼 더 쪼갤 수 없는 기본 명제를, 반대자가 먼저 그것을 인정한 뒤에만 주장할 수 있습니다. 제안자는 P가 무엇인지 모르는 채로 이겨야 하니, P를 스스로 내세울 수는 없고 반대자가 내놓은 것을 되쓸 수만 있는 것입니다.

눈여겨볼 것은 규칙의 세부가 논리를 바꾼다는 점입니다. 로렌첸과 킬 대학의 제자 쿠노 로렌츠는 대화의 규칙을 자연스럽게 다듬었는데, 그 핵심은 제안자가 가장 최근의 공격에만 답할 수 있다는 규칙입니다. 이런 규칙 아래에서 제안자가 늘 이기는 명제는 정확히 직관주의 논리⁠(intuitionistic logic)⁠의 정리들입니다. 이것은 1985년 발터 펠셔가 엄밀하게 증명했습니다.

직관주의 논리는 1908년 무렵 브라우어르가 "P이거나 P가 아니다"(배중률)를 무조건 받아들이기를 거부하며 시작한 논리입니다. 무한 집합에 대해서는 모든 경우를 확인해 볼 수 없으니, 둘 중 어느 쪽인지 보일 방법 없이 "둘 중 하나는 참"이라고 말할 수 없다는 것이 그의 이유였습니다.

대화로 보면 배중률이 왜 막히는지 보입니다. "P가 아니다"를 기호로 ¬P라 적고, 대화에서는 'P를 인정하면 모순이 나온다'는 주장으로 봅니다. "P 또는 ¬P"를 주장한 제안자는 어느 한쪽을 골라야 합니다. P를 고르면 P를 지켜야 하는데, 반대자가 아직 P를 인정하지 않았으니 P를 주장할 수 없습니다. ¬P를 고르면 반대자가 "그럼 P를 인정하겠다, 모순을 보여 봐라"라고 공격합니다. 제안자는 모순을 보일 수 없고, 가장 최근의 공격에만 답할 수 있으니 처음의 '또는'으로 돌아가지도 못해 막힙니다.

이제 제안자에게 한 가지 특권을 줍니다. 앞서 한 답으로 되돌아가 다시 답할 수 있게 하는 것입니다. 그러면 제안자는 이렇게 이깁니다. 처음에는 ¬P를 고릅니다. 반대자가 P를 인정하며 공격하면, 제안자는 처음 답으로 돌아가 "사실은 P다"라고 답하고, 방금 반대자가 내놓은 P를 그대로 들이밉니다. 이 되돌아가기를 허용한 대화에서 늘 이기는 명제가 정확히 고전 논리의 정리입니다. 프로그래밍 언어 연구자 필립 워들러는 이것을 악마의 거래로 즐겨 설명했습니다. 악마가 "10억을 주거나, 네가 10억을 내면 어떤 소원이든 들어주겠다"고 제안하고 뒤의 것을 고릅니다. 한참 뒤 사람이 10억을 모아 오자, 악마는 시간을 되돌려 "앞의 것을 고르겠다"며 그 10억을 건넵니다. 되돌아갈 수 있는 쪽은 '또는'을 공짜로 지킬 수 있습니다.

이 대화의 눈은 커리–하워드 대응⁠(Curry–Howard correspondence)⁠과 만납니다. 프로그래밍 언어에서 타입⁠(type)⁠은 값의 종류, 이를테면 '정수⁠(integer)⁠'나 '정수를 받아 정수를 돌려주는 함수' 같은 것입니다. 커리–하워드 대응에 따르면 명제는 타입이고 증명은 그 타입의 프로그램입니다. 예를 들어 "A이면 B"의 증명은 A의 증명을 받아 B의 증명을 돌려주는 함수입니다. 여기에 게임을 더하면 한 걸음 더 갑니다. 타입은 프로그램과 그 환경(프로그램을 부르고 값을 건네주는 쪽)이 주고받는 대화의 규칙, 곧 게임이고, 프로그램은 그 게임의 전략입니다. 이것을 '게임 의미론⁠(game semantics)⁠'이라 부릅니다.

가장 단순한 증명 하나를 봅시다. "A이면 A"의 증명, 프로그램으로는 받은 것을 그대로 돌려주는 함수입니다. 게임으로는 A라는 게임판 두 개를 동시에 두되, 한 판에서는 먼저 두는 쪽, 다른 판에서는 나중 두는 쪽을 맡는 상황입니다. 이기는 전략은 4절의 흉내 내기입니다. 한 판에서 상대가 둔 수를 다른 판에 내 수로 그대로 옮기면, 두 판은 사실상 같은 한 판이 됩니다. 한 판에서 상대가 이기면 다른 판에서는 내가 그 상대의 수를 그대로 둔 것이니 내가 이기고, 그래서 둘 다 지는 일은 없습니다. 체스 명인 두 사람과 동시에 두어 한 판 이상 지지 않는 법이라는 오래된 수수께끼가 이것이고, 게임 의미론에서는 이 전략을 '흉내쟁이'라고 부릅니다. 이 글이 따라온 '증명 = 전략'이 가장 문자 그대로 이루어지는 곳입니다.

정리하면, 증명은 제안자가 모든 공격을 이겨 내는 대화의 전략이고, 대화의 규칙 하나(되돌아가 다시 답할 수 있는가)가 직관주의 논리와 고전 논리를 가릅니다. 증명과 프로그램의 대응이 증명 보조기⁠(proof assistant)⁠에서 실제로 어떻게 쓰이는지는 「증명은 프로그램이다」와 증명 보조기에 있습니다.

배중률을 두고는 격한 논쟁이 있었습니다. 힐베르트는 1927년 함부르크 강연에서 수학자에게서 배중률을 빼앗는 것은 천문학자에게서 망원경을, 권투 선수에게서 주먹을 빼앗는 것과 같다고 브라우어르에게 맞섰습니다. 이 기초⁠(basics)⁠ 논쟁의 자세한 이야기는 「증명은 프로그램이다」 2절에 있습니다. 게임 의미론은 1990년대 초 새뮤얼 에이브럼스키와 동료들, 그리고 마틴 하일랜드와 루크 옹이 세웠고, 오래된 문제 하나에 답했습니다. 간단한 함수형 언어⁠(functional programming language)⁠ PCF의 두 프로그램이 언제 '같은 일을 하는가'를 정확히 반영하는 수학적 모형을 찾는 문제로, 1977년 고든 플롯킨이 분명히 한 것입니다. 그보다 앞서 1992년 앤드리어스 블라스는 지라르의 선형 논리(가정 하나를 정확히 한 번만 쓰도록 자원처럼 다루는 논리)를 게임으로 해석했습니다.

9 · 2014년 몬트리올겨루며 배우는 기계

게임의 수학은 오늘의 기계 학습에서도 쓰입니다. 이 절의 물음은 두 가지입니다. 두 신경망을 최소최대 게임으로 겨루게 하면 무엇을 배우게 되는가? 그리고 그 게임을 실제로 풀려고 할 때 왜 자주 실패하는가?

2014년 몬트리올 대학의 대학원생 이언 굿펠로와 동료들은 신경망 두 개를 겨루게 하는 학습 방법을 발표했습니다. 신경망은 수많은 조절 손잡이(가중치⁠, weight⁠)가 달린 함수로, 손잡이를 조금씩 돌려 가며 원하는 일을 하도록 맞춥니다. 생성자 G는 무작위한 수들(잡음) z를 받아 가짜 그림 G(z)를 만들고, 판별자 D는 그림 x를 받아 그것이 진짜일 확률 D(x)를 냅니다. D는 진짜와 가짜를 잘 가르려 하고, G는 D를 속이려 합니다. 이 '생성적 적대 신경망'(GAN)의 목표는 5절의 모양 그대로 최소최대입니다.

식을 부분별로 읽어 봅시다. $\mathbb{E}$는 평균(기댓값)이고, $x \sim p_{\text{data}}$는 'x를 진짜 그림들 가운데서 뽑는다'는 뜻입니다. log는 자연로그⁠(natural logarithm)⁠로, 0과 1 사이의 수에 대해서는 수가 1에 가까울수록 0에 가깝고 0에 가까울수록 한없이 작아지는(음수 쪽으로 커지는) 값입니다. 그러니 첫째 항은 D가 진짜 그림에 높은 확률을 줄수록 커지고, 둘째 항은 D가 가짜 그림 G(z)에 낮은 확률을 줄수록 커집니다. D는 전체를 가장 크게(max), G는 가장 작게(min) 하려 합니다.

숫자로 보면 이렇습니다. D가 진짜에는 0.9, 가짜에는 0.1을 준다면 두 항은 $\log 0.9 + \log 0.9 \approx -0.105 - 0.105 = -0.21$입니다. D가 전혀 구별하지 못해 둘 다에 0.5를 준다면 $\log 0.5 + \log 0.5 = \log 0.25 = -\log 4 \approx -1.386$으로 훨씬 작습니다. G가 완벽하게 속이면 목표는 $-\log 4$까지 내려갑니다.

논문의 정리는 이것을 정확히 합니다. 어떤 그림이 얼마나 자주 나오는지를 적은 것을 분포라 하고, 진짜 그림들의 분포를 $p_{\text{data}}$, G가 만드는 그림들의 분포를 $p_g$라 합시다. G를 고정했을 때 가장 좋은 판별자는 $D^*(x) = p_{\text{data}}(x) / (p_{\text{data}}(x) + p_g(x))$입니다. 그림 x가 진짜에서 나올 가능성이 가짜에서 나올 가능성의 몇 배인지에 따라 확률을 주는 것입니다. 그 판별자를 넣은 G의 목표는 $-\log 4 + 2\,\mathrm{JS}(p_{\text{data}} \,\|\, p_g)$가 됩니다. JS는 두 분포가 얼마나 다른지를 재는 옌센–섀넌 발산⁠(Jensen–Shannon divergence)⁠으로, 두 분포 각각과 둘의 평균 분포 사이의 KL 발산⁠(KL divergence)⁠을 평균한 것입니다. KL 발산은 한 분포를 다른 분포로 잘못 알고 쓸 때 평균적으로 치르는 손해를 재는 양으로, 0 이상이고 두 분포가 같을 때에만 0입니다. JS 발산⁠(divergence)⁠은 0 이상이고 두 분포가 같을 때에만 0이므로, G의 목표는 $p_g = p_{\text{data}}$일 때 가장 작은 값 $-\log 4$에 이릅니다. 곧 게임의 해에서 가짜의 분포는 진짜의 분포와 같고, 그때 $D^* = 1/2$로 판별자는 동전 던지기밖에 할 수 없습니다.

단, 이것은 G와 D가 어떤 함수든 될 수 있고 매 단계를 정확히 최적화한다고 가정한 이상적인 게임에 대한 정리입니다. 실제 학습이 거기에 이른다는 보장은 아닙니다.

실제 학습에서는 여러 가지가 어긋납니다. 폰 노이만의 정리와 그것을 넓힌 1958년 모리스 시온의 정리는 한쪽에 대해 볼록하고 다른 쪽에 대해 오목한 게임에서 성립합니다. 볼록은 그릇처럼 가운데가 움푹한 모양, 오목은 그것을 뒤집은 모양입니다. 섞은 전략의 기댓값은 p에 대해서도 q에 대해서도 일차식이라 이 조건을 만족합니다. 신경망의 가중치로 적은 게임은 그렇지 않아서 균형점이 있다는 보장부터 없습니다.

균형점이 있어도 두 사람이 경사 하강법⁠(gradient descent)⁠으로 동시에 한 걸음씩 가면 거기에 가지 못할 수 있습니다. 경사 하강법은 지금 자리에서 값이 가장 가파르게 줄어드는 쪽(기울기의 반대쪽)으로 조금씩 움직이는 방법입니다. 가장 단순한 게임 $f(x, y) = xy$에서 확인해 봅시다. x는 f를 줄이려 하고 y는 키우려 합니다. 원점 (0, 0)이 안장점(말안장의 한가운데처럼, 한 방향으로는 가장 낮고 다른 방향으로는 가장 높은 점)이고 게임의 값은 0입니다. x가 0이면 y가 무엇이든 f = 0이고, y가 0이면 x가 무엇이든 f = 0이니 누구도 원점에서 혼자 벗어나 이득을 볼 수 없습니다.

x를 조금 늘리면 f = xy는 y의 비율로 변하니, f를 줄이려는 x는 $-\eta y$만큼 움직입니다. 같은 까닭으로 f를 키우려는 y는 $+\eta x$만큼 움직입니다. η(에타)는 한 걸음의 크기입니다. 예를 들어 (1, 0)에서 출발하면 x는 $-\eta \cdot 0 = 0$만큼, y는 $\eta \cdot 1$만큼 움직여 (1, η)에 닿습니다. 원점으로 가기는커녕 옆으로 비껴 갑니다.

두 사람이 움직이고, 걸음 크기는 $\eta =$ , 걸음 수는 입니다. 원점까지의 거리는 처음 에서 지금 입니다. 출발점 되돌리기

'동시에'에서 자취는 바깥으로 풀려 나가는 나선입니다. 한 걸음마다 원점까지의 거리가 정확히 $\sqrt{1 + \eta^2}$배가 되기 때문입니다. 한 걸음에 (x, y)가 $(x - \eta y,\; y + \eta x)$로 가니, 거리의 제곱을 계산하면 가운데 항 $-2\eta xy$와 $+2\eta xy$가 지워져서 다음과 같습니다.

η = 0.2이면 한 걸음에 거리가 $\sqrt{1.04} \approx 1.02$배, 곧 약 2%씩 늘고, 40걸음이면 $1.04^{20} \approx 2.19$배가 됩니다. 걸음을 아무리 작게 해도 $1 + \eta^2$은 1보다 크니, 나선이 느려질 뿐 방향은 바뀌지 않습니다. 흔히 걸음을 충분히 작게 하면 기울기를 따라가는 방법은 결국 수렴⁠(convergence)⁠한다고 생각하지만, 두 사람이 겨루는 게임에서는 그렇지 않습니다.

'번갈아'(x가 먼저 움직이고, y는 x가 움직인 뒤를 보고 움직임)로 바꾸면 자취는 원점 둘레를 끝없이 맴돕니다. '한 걸음 내다보고'는 1976년 갈리나 코르펠레비치가 제안한 방법으로, 시험 삼아 한 걸음 가 본 곳의 기울기로 실제 걸음을 정합니다. 이번에는 자취가 원점으로 말려 들어갑니다. 같은 계산을 해 보면 한 걸음에 거리가 $\sqrt{1 - \eta^2 + \eta^4}$배가 되는데, η가 0과 1 사이이면 이 값은 1보다 작습니다(η = 0.2이면 약 0.98). 2018년 라르스 메셰더 등은 진짜 자료가 점 하나뿐인 가장 단순한 GAN에서도 규제 없는 보통의 학습은 수렴하지 않는다는 것을 보였습니다. GAN 학습이 불안정하기로 이름난 까닭의 가장 작은 모형이 이 그림입니다. 2020년대에 들어 그림 생성의 주류는 게임이 아니라 한 모형의 손실을 줄이는 확산 모델⁠(diffusion model)⁠로 옮겨 갔습니다.

게임을 통한 학습이 가장 크게 성공한 곳은 오히려 진짜 게임입니다. 기계가 자기 자신과 두며 배운다는 생각은 오래되었습니다. 1959년 IBM의 아서 새뮤얼은 스스로 둔 대국의 결과로 국면의 점수 함수를 고쳐 가는 체커 프로그램을 발표했고, 1992년 IBM의 제럴드 테사우로가 만든 TD-개먼은 자기 대국만으로 백개먼을 익혀 최상급 선수들과 겨룰 만한 수준에 이르렀습니다. 2016년 3월 서울에서 이세돌 9단을 이긴 알파고는 사람의 기보(대국의 수순을 적은 기록)로 배운 뒤, 스스로 둔 대국으로 강화 학습⁠(reinforcement learning)⁠을 더 했습니다. 강화 학습은 좋은 결과로 이어진 행동을 더 자주 하도록 조금씩 고쳐 가는 학습입니다. 2017년의 알파고 제로는 사람의 기보 없이 스스로 둔 약 490만 판만으로 배웠습니다. 둘 다 배운 국면의 값을 게임 트리 탐색으로 다듬어 수를 골랐습니다. 배우려는 목표는 1절의 거꾸로 따지기가 매기는 값, 곧 서로 최선을 다할 때의 결과입니다. 그 값을 다 계산할 수 없으니 신경망으로 어림할 뿐입니다. 1912년 체르멜로가 존재만 보인 값을, 한 세기 뒤의 기계가 어림하고 있는 셈입니다.

정리하면, GAN의 이상적인 게임은 가짜의 분포가 진짜와 같아지는 곳에서 풀리지만, 기울기를 따라 동시에 걷는 실제 학습은 그 해 둘레를 돌거나 멀어질 수 있습니다. 혼자 손실을 줄이는 학습에서 통하던 직관이 두 사람의 게임에서는 통하지 않습니다.

알파고가 넘은 바둑은 이 글의 어느 게임보다 오래되었습니다. 바둑은 2,500년도 더 전에 중국에서 생겼고, 기원전 4세기 무렵의 역사책 『좌전』에 처음 기록이 보이며, 당나라(618–907) 무렵에는 지금의 19줄 판이 표준이 되었습니다. 5–7세기 사이에 한반도로, 7세기에 일본으로 건너갔습니다. 일본에서는 1603년 막부가 당대 가장 강한 기사를 바둑을 맡는 벼슬에 앉혔고, 그 뒤 혼인보를 비롯한 바둑 가문들이 서로 겨루며 단과 급의 등급 제도를 다듬었습니다. 이렇게 오래 쌓인 기보와 수법이 있었는데도 바둑은 기계에게 가장 늦게까지 버틴 게임이었습니다. 규칙에 맞는 판의 배치만 약 $2.1 \times 10^{170}$가지이고, 한 국면에서 둘 수 있는 수가 체스의 서른다섯 가지쯤에 비해 이백오십 가지쯤이라 1절의 섀넌식으로 몇 수 앞을 내다보는 탐색이 금방 불어났습니다. 더 큰 걸림돌은 국면에 점수를 매기기 어렵다는 것이었습니다. 체스는 남은 말을 세는 것만으로도 쓸 만한 어림이 되지만, 바둑의 형세는 돌 무리가 살아 있는지, 어느 돌이 서로 이어질 수 있는지를 따져야 보입니다. 알파고가 신경망으로 어림한 것이 바로 그 형세였습니다.

20세기와 21세기. 르부프의 카페에서 프린스턴으로, 알제에서 바르샤바로, 프로비던스에서 브로츠와프와 로스앤젤레스로 이어지는 무한 게임과 논리의 길, 그리고 몬트리올과 서울의 학습하는 기계를 지도에서 보세요. 철학 줄(보라)에는 로렌첸과 힌티카가, 과학 줄에는 니마트론에서 딥 블루와 끝내기 표⁠(endgame tablebase)⁠까지 게임을 두는 기계들이 있습니다. 르부프에서 브로츠와프로 간 노란 선은 전쟁 뒤 국경이 옮겨지며 슈타인하우스가 간 길이고, 빈에서 프린스턴으로 간 노란 선은 1938년 오스트리아 합병 뒤 돌아가지 않은 모르겐슈테른의 길입니다.

10 · 이어지는 길게임이 닿는 곳

두 사람의 게임은 수학의 여러 갈래를 한 줄로 꿰는 실입니다.

• 해석학으로: 극한과 연속의 ε–δ 정의는 세 수짜리 게임이고, 수의 순서를 바꾸면 균등 연속과 균등 수렴⁠(uniform convergence)⁠이 됩니다. 중간값 정리⁠(intermediate value theorem)⁠처럼 '어떤 점이 있다'는 정리도 게임으로 읽을 수 있습니다. ε를 받아 값이 ε보다 작은 점을 실제로 찾아 주는 전략을 요구하면, 그것이 직관주의 논리가 받아들이는 증명의 모양입니다. 도함수⁠(derivative function)⁠를 극한으로 다시 세운 이야기는 「순간의 속도」에, 양화사의 순서를 헷갈려 틀린 코시의 정리는 「틀린 증명이 만든 수학」에 있습니다.
• 논리로: 양화사는 수이고, 부정은 역할 바꾸기이며, 참은 이기는 전략의 존재입니다. 이 관점에서 불 대수의 드모르간 법칙은 결정성이 되고, 배중률을 거부하는 직관주의 논리는 되돌아가기를 금지한 대화가 됩니다. 증명이 프로그램이라는 커리–하워드 대응은 게임 의미론에서 증명이 전략이라는 말로 바뀝니다.
• 계산으로: 입력 크기의 거듭제곱 정도로 여러 번 번갈아 두는 게임의 승패를 가리는 일은 NP를 포함하는 부류 PSPACE와 같고(둘이 정말 다른지는 P 대 NP처럼 열린 문제입니다), 실제 게임에서는 게임 트리 탐색과 동적 계획법이 거꾸로 따지기를 어림합니다. 1차 논리가 짝수와 도달 가능성을 쓰지 못한다는 사실은 유한 오토마톤과 정규 표현식의 부류, 데이터베이스의 질의 언어로 이어집니다. 비교 정렬의 하한⁠(comparison sorting lower bound)⁠도 알고리즘과, 답을 가장 심술궂게 골라 주는 적수 사이의 게임으로 읽을 수 있습니다. 적수가 비교마다 아직 가능한 순서가 더 많이 남는 쪽으로 답하면, 어떤 알고리즘도 적어도 log₂ n!번은 물어야 합니다. n!은 1부터 n까지를 모두 곱한 수, 곧 n개를 늘어놓는 순서의 가짓수이고, log₂ n!은 2를 몇 번 곱해야 그 수가 되는지입니다(「줄 세우기의 한계」 6절).
• 경제와 제도로: 내시 균형과 죄수의 딜레마는 게임 이론을 경제학과 정치학의 언어로 만들었고, 같은 RAND의 사람들 사이에서 병원과 학생을 짝짓는 안정 매칭⁠(stable matching)⁠이 나왔습니다(「짝을 찾는 알고리즘」). 여러 사람의 선호를 하나의 사회적 순서로 모으는 공정한 규칙은 없다는 애로의 정리도 1940년대 말 RAND에서 던져진 물음에서 시작했습니다(「불가능의 증명」 8절).
• 최적화로: 동시에 두는 게임의 최소최대 정리는 선형 계획법의 쌍대 정리와 같은 내용입니다. 가격이 자원을 재는 라그랑주 승수, 최대 흐름 최소 절단 정리, 두 분포를 옮기는 최적 수송⁠(optimal transport)⁠의 쌍대성이 모두 쌍대성이라는 한 생각의 얼굴들입니다.
• 수와 셈으로: 님의 해법은 이진법의 자리마다 2로 나눈 나머지를 더하는 계산이고, 님 합은 모든 원소가 자기 역원인 군을 만듭니다. 비기는 일이 없다는 헥스의 성질이 브라우어르 고정점 정리⁠(Brouwer fixed-point theorem)⁠와 같다는 것은 데이비드 게일이 설명했고, 여섯 점 사이의 선을 칠하는 심 게임이 비기지 않는 까닭은 「완전한 무질서는 없다」의 램지 이론⁠(Ramsey theory)⁠이 설명합니다.
• 무한으로: 셀 수 있는 집합을 비켜 가는 II의 전략은 칸토어의 구간 논증과 대각선 논법이고, 무한 게임이 늘 결정되느냐는 물음은 선택공리와 기술 집합론의 문제입니다. 무한의 크기 자체는 「무한에도 크기가 있다」에서 이어집니다.
• 학습으로: 판별자와 생성자의 최소최대 게임은 KL 발산과 엔트로피⁠(entropy)⁠의 말로 적히고, 기울기를 따라 겨루는 두 사람이 균형점 둘레를 맴도는 현상은 경사 하강법이 혼자일 때와 여럿일 때가 다르다는 것을 보여 줍니다. 신경망이 어떻게 한 사람의 손실을 줄이며 배우는지는 「배우는 기계」에 있습니다. 체스 기계를 구상하던 무렵 섀넌은 사람에게 다음 글자를 맞히게 하는 추측 게임으로 영어의 정보량을 재었고, 그 게임이 오늘의 언어 모델⁠(language model)⁠로 이어진 이야기와 자기 대국에서 쓰인 강화 학습이 언어 모델을 사람의 선호에 맞추는 데 다시 쓰인 이야기는 「다음 단어를 맞히는 기계」에 있습니다.