프로그램 균형 입문 — 소스 코드를 공개한 AI들의 협력, 뢰브 정리와 시뮬레이션

핵심 메시지

• 프로그램 게임은 플레이어가 행동 대신 프로그램을 제출하고, 그 프로그램들이 실행 시점에 서로의 소스 코드를 입력으로 받는 설정이다.
• 가장 오래된 해법인 '상대 코드가 나와 같으면 협력'은 공백 하나만 달라도 무너져 실전에서는 쓰기 어렵다.
• 뢰브 정리를 이용하면 '상대가 협력한다는 증명을 찾으면 협력한다'는 프로그램이 자기 자신을 상대로 실제로 협력에 도달한다.
• 카스파어 외스터헬트의 대안은 확률 ε로 그냥 협력하고 나머지 경우 상대를 시뮬레이션해 따라 하는 방식으로, 무한 재귀를 확률적으로 끊는다.
• 후속 논문은 모든 프로그램에 같은 난수열을 넘겨 여러 상대와 자기 자신을 동시에 시뮬레이션해도 모두 같은 지점에서 멈추게 만든다.

쉽게 이해하기

카네기멜런대 박사과정이자 협력적 AI 기초 연구실 부책임자인 카스파어 외스터헬트가 자신의 두 논문을 설명한다. 출발점은 죄수의 딜레마다. 두 참가자가 각자 자기 이득을 1 올리거나 상대 이득을 3 올릴 수 있을 때, 상대가 무엇을 하든 자기 이득을 택하는 쪽이 유리하므로 둘 다 1만 챙기고 끝난다. 프로그램 게임은 여기서 규칙을 하나 바꾼다. 참가자는 행동이 아니라 프로그램을 제출하고, 각 프로그램은 상대 프로그램의 소스 코드를 입력으로 받아 스스로 판단한다.

이 설정에서 1980년대부터 반복해서 재발견된 해법이 있다. '상대 프로그램이 나와 똑같으면 협력하고 아니면 배신한다'는 코드다. 둘 다 이 프로그램을 내면 어느 쪽도 이탈할 유인이 없으므로 내시 균형이 되고, 협력이 성립한다. 문제는 이것이 순전히 구문 비교라는 점이다. 공백 위치가 다르거나 조건문을 반대로 뒤집어 쓰기만 해도 깨지고, 사전에 코드를 맞추지 않은 두 사람이 독립적으로 같은 문자열을 쓸 가능성은 사실상 없다.

그래서 연구는 더 견고한 방식으로 옮겨갔다. 첫 갈래는 증명 기반이다. '상대가 협력한다는 것을 증명할 수 있으면 나도 협력한다'는 프로그램은 직관적으로는 무한 순환에 빠질 것 같지만, 뢰브 정리 덕분에 실제로 자기 자신과 협력한다. 뢰브 정리는 어떤 명제 P에 대해 'P를 증명할 수 있다면 P가 참이다'를 증명할 수 있다면 P 자체를 증명할 수 있다는 결과로, 괴델의 제2 불완전성 정리와 맞닿아 있다. 앤드루 크리치는 여기에 증명 길이를 제한한 유한 탐색 버전에서도 같은 협력이 성립함을 보였다.

외스터헬트의 '견고한 프로그램 균형'은 증명 대신 시뮬레이션을 쓴다. 상대를 그냥 실행해 따라 하면 두 프로그램이 서로를 호출하며 멈추지 않지만, 매 호출마다 작은 확률 ε로 상대를 보지 않고 곧바로 협력하도록 하면 재귀가 확률 1로 종료된다. 이 구성은 반복 게임에서 직전 수만 보고 반응하는 전략과 정확히 대응하며, 팃포탯 같은 전략의 착취 가능성 지표가 그대로 옮겨온다. 다만 한 번에 사실상 한 번의 시뮬레이션만 감당할 수 있어, 자기 지난 수까지 봐야 하는 윈스테이-루즈시프트나 과거 전체를 보는 그림 트리거, 상대가 셋 이상인 게임은 구현할 수 없다.

에머리 쿠퍼, 외스터헬트, 빈센트 코니처의 후속 논문이 이 한계를 푼다. 난수 생성을 '프로그램이 시작될 때 무한한 난수열을 입력으로 받는다'로 모형화한 뒤, 시뮬레이션을 호출할 때 그 난수열의 앞부분을 하나씩 떼어 모두에게 똑같이 넘긴다. 모든 시뮬레이션이 ε보다 작은 첫 난수에서 동시에 멈추므로 여러 상대와 자기 자신을 함께 돌려도 재귀가 폭발하지 않는다. 공유 난수를 쓰는 경우 결과가 훨씬 깔끔하고, 각자의 사설 난수만 쓰는 경우에는 상대 예측이 실제 행동과 어긋나는 혼탁한 결과가 나온다.

왜 이런 연구를 하는가에 대한 답은 AI 위임이다. 사람은 서로의 소스 코드를 읽을 수 없지만, 각자 AI 시스템을 배치하고 그 코드를 공개하는 상황은 그대로 프로그램 게임이 된다. 외스터헬트는 국가나 기관도 헌법과 법률, 구성원의 공개 정보라는 형태로 이미 부분적인 투명성을 갖고 있다고 짚는다. 다만 그는 '상호 처벌보다 나은 결과는 거의 다 균형이 된다'는 폭 정리를 마냥 긍정적으로 보지 않는다. 균형이 많다는 것은 아주 나쁜 균형도 많다는 뜻이고, 선택지가 많을수록 어느 하나로 맞춰질 확률은 떨어지기 때문이다.

주요 인사이트

• 구문이 아니라 행동에 반응하는 프로그램만이 견고할 수 있다는 '행동주의' 기준이 이 분야의 암묵적 목표지만, 정작 그 견고함 자체는 내시 균형 같은 해 개념으로 형식화되어 있지 않다.
• 폭 정리는 좋은 소식만은 아니다. 달성 가능한 균형이 많아질수록 어느 하나로 조율될 가능성은 오히려 낮아지고, 매우 불리한 균형도 함께 가능해진다.
• 정보를 더 공개하는 쪽이 늘 나은 것은 아니다. 상대에 대해 유사성 정도만 알 수 있는 부분 정보 설정에서 오히려 좋은 균형만 남는다는 결과가 있다.
• 국가 간 관계에서 '테러리스트와 협상하지 않는다' 같은 선언은 사실상 그 나라 소스 코드에 박힌 알고리즘적 약속으로 볼 수 있다.
• 프로그램 관점은 '시뮬레이션당하는 나는 어떻게 행동해야 하는가'라는 결정이론의 철학적 난제를 '나는 어떤 코드를 제출해야 하는가'라는 외부 관점의 문제로 바꿔 놓는다.

자주 묻는 질문

관련 AI 소식