좀비 7천 마리에 멈춰선 프로그램: 인간에겐 뻔한 승리, AI는 왜 멈췄나

좀비 7천 마리에 멈춰선 프로그램: 인간에겐 뻔한 승리, AI는 왜 멈췄나

게임 개발Rust알고리즘시스템 아키텍처

데이터 소스:HN + web research

화면 속 카드 대결은 58턴에 멈춰 섰다. 한쪽 전장에는 7,258마리의 좀비가 가득 차 있었고, 수비 측의 생명력은 겨우 31점뿐이었다. 좀비 16마리만 돌격시켜도 즉시 끝날 경기였다. 하지만 규칙 연산 프로그램은 한 번의 처리에 35초나 멈춰 서더니, 결국 좀비 딱 한 마리만 내보내 상대를 툭 치는 데 그쳤다.

이는 개발자 Levi Neuwirth가 Rust로 작성한 매직 더 개더링(MTG) 룰 엔진 Arcana를 테스트하던 중 겪은 일이다. 그는 카드 AI 알고리즘을 시험하기 위해 64개 덱을 구성하고 403,200회의 자동 대전을 진행했다. 대전이 끝난 뒤, 9개 작업이 2시간 제한에 걸려 시스템에 의해 강제 종료되었다.

코드 자체에는 무한 루프 버그가 전혀 없었다. 시스템을 마비시킨 진짜 원인은 카드 메커니즘이 촉발한 기하급수적 지수 팽창이었다. 수천 마리의 생물이 동시에 전장에 쏟아져 나오자, 미시적인 전수 탐색이 연산 자원을 순식간에 집어삼켰다.

MTG는 수학적으로 튜링 완전성이 이미 입증된 게임이다. 그러나 이를 실제 소프트웨어로 구현하는 문제는 완전히 다른 차원의 공학적 도전이다. 인간은 승패를 한눈에 파악하지만, 프로그램은 모든 생물을 두고 전장 전체를 매번 다시 훑어야 한다. 플레이어가 외치는 “전원 공격” 한마디가 코드 안에서는 수백만 개의 분기로 폭증한다.

8번의 대지 배치로 벌레 6천 마리 복제, 지수 폭증의 시작

MTG는 1993년에 탄생했다. 모든 카드는 고유한 특수 규칙을 지니고 있어 기본 규칙을 언제든 덮어쓸 수 있다. 연쇄 효과를 지닌 카드들이 모이면 게임 내 수치는 걷잡을 수 없이 폭주한다.

‘딱정벌레 떼’(Scute Swarm) 카드가 대표적이다. 전장에 대지가 하나 깔릴 때마다 자신의 복제 토큰을 하나씩 만든다. 한 마리가 두 마리, 두 마리가 네 마리로, 행동을 거듭할 때마다 두 배로 불어난다.

테스트 환경에서 이 카드는 생명력 회복 카드 및 토큰 복제 아티팩트와 결합했다. 8번 연속으로 대지를 내려놓자 전장에는 6,561마리의 벌레 떼가 쏟아져 나왔다. 플레이어 생명력은 26,240점까지 치솟았다. 일반 대전의 시작 생명력이 20점인 점을 감안하면, 이 수치는 기존 보드게임의 허용 한계를 아득히 넘어선 것이다.

증가 곡선 비교 그림: Scute Swarm과 릴리아나 문양의 지수적 증가 비교. 세로축의 눈금 하나는 10배 팽창을 나타낸다. 출처: Levi Neuwirth

사람들이 테이블을 마주하고 플레이할 때는 주사위 두 개를 카드 위에 올려놓고 수천 마리의 벌레를 대신 처리하면 그만이다. 하지만 프로그램은 메모리 안에서 6,561개의 개체마다 독립된 데이터 구조를 일일이 할당해야 한다.

한 턴 연산에 35초, 복제 메커니즘이 메모리를 잠식하다

벌레 떼가 아무리 거세도 전체 파괴 마법 한 번이면 정리할 수 있다. 엔진을 진짜 탈진으로 몰아넣은 것은 플레인즈워커 릴리아나의 궁극기였다. 이 기술은 전장 바깥 영역에 제거할 수 없는 영구 문양을 남긴다.

문양의 규칙은 단순하다. 자신의 턴 종료 단계마다 현재 조종 중인 좀비 수에 2를 더한 만큼 새 좀비 토큰을 만든다. 다음 턴의 좀비 수는 이전 턴의 2배에 2를 더한 값이 된다. 단 8번의 처리만으로 전장에는 510마리의 좀비가 쌓였다.

상대가 마법으로 전장을 쓸어버려도 사령관 구역에 새겨진 문양은 멀쩡히 남는다. 다음 턴에 새 좀비 두 마리가 들어오면서 복제 사슬이 다시 작동한다. 이 제거 불가능한 자동 증식 루프는 규칙 엔진에게 악몽이 되었다.

Neuwirth는 멈춰선 대전을 프레임 단위로 분석했다. 52턴에는 단일 문양 처리에 1.72초가 걸렸다. 54턴에는 7.78초로 늘어났고, 56턴에는 처리 시간이 무려 35.15초까지 치솟았다.

처리 시간 곡선 그림: 전장의 좀비 수가 두 배로 늘어날 때마다 단일 상태 처리 시간은 약 4.5배씩 증가했다. 출처: Levi Neuwirth

좀비 수가 두 배로 늘어날 때마다 단일 처리 시간은 약 4.5배씩 불어났다. 알고리즘 복잡도가 초선형으로 악화된 것이다. 새로운 생물이 들어올 때마다 엔진은 전장 전체를 훑으며 모든 지속 능력과 조건을 재검증해야 한다. 수천 개의 객체가 서로 맞물리면서 규칙 검증은 연산의 늪으로 빠져들었다.

좀비 7천 마리를 쥐고도 한 마리만 출격시킨 사연

대결은 58턴에 이르러 좀비 총수가 7,258마리에 도달했다. 수비 측은 생명력이 31점만 남았고 방어할 생물도 턱없이 부족했다. 좀비 16마리만 달려가 32점의 피해를 입히면 즉시 승리할 수 있었다.

바로 그 순간 황당한 상황이 벌어졌다. AI는 한참을 고민하더니 공격력 2짜리 작은 좀비 딱 한 마리만 공격으로 내보냈다. 적 생물을 맥없이 툭 건드렸을 뿐이다. 7천 대군을 거느린 압도적 우세 측이 눈앞의 결정타를 스스로 포기해 버렸다.

대전 다시보기 화면 그림: 58턴 다시보기 화면. 한 스택에 7,234마리의 좀비가 쌓여 있고 상대 생명력은 31점만 남았다. 출처: Levi Neuwirth

원인은 수 생성기에 들어 있던 보호 로직 때문이었다. 수천 마리의 생물이 여러 대상을 공격하는 조합의 경우의 수는 천문학적으로 폭증한다. 시간 초과를 막기 위해 개발자는 코드 내에서 후보 수의 상한을 1,024개로 제한해 두었다.

생성기는 단일 공격 계획부터 우선적으로 나열하도록 설계되어 있었다. 전장에 7,258마리의 좀비가 있는 상황에서는 단독 출격 조합만으로도 1,024개의 자리가 가득 차버렸다. 전원 돌격을 포함한 다수 생물의 협공 계획은 대기열 뒤쪽에 밀려 생성조차 되지 못했다.

생물이 58마리였던 44턴에는 229개의 후보 수가 생성되었고, 그중 4개는 다수 생물의 연계 공격이었다. 그러나 50턴에 이르러 상한에 부딪히자 다수 생물 공격 선택지는 완전히 사라졌다. 연산 정지를 막으려던 안전장치가 거꾸로 필승 전략을 가려버린 셈이다.

인간의 직관 대 컴퓨터의 수백만 갈래 분기

인간 플레이어라면 이런 상황을 전혀 다른 방식으로 다룬다. 전장에 만 마리의 좀비가 있더라도 각 좀비의 공격 위치를 일일이 계산하지 않는다. 총공격력이 상대의 생명력을 압도한다는 사실을 확인하고, 전원 공격을 선언해 일정한 시간에 경기를 끝낸다.

컴퓨터 프로그램에는 이러한 거시적 추상화 능력이 없다. 엔진은 철저히 미시적 시각을 따라 모든 객체를 성실하게 데이터 구조로 분해해 처리한다. 생물이 몇 마리 없을 때는 이러한 전수 조사가 판정의 완벽한 정확성을 보장한다.

그러나 규모가 임계점을 넘어서는 순간 미시적 전수 탐색은 치명적인 짐이 된다. 규칙에 부합하는 사소한 루프들이 누적되며 모든 연산 자원을 갉아먹는다. 컴퓨터가 둔해진 것이 아니라, 무의미한 미시적 세부 사항에 갇혀버린 것이다.

이론적 완전성과 공학적 실현 가능성 사이에는 깊은 간극이 있다. MTG는 카드가 기본 규칙을 자유롭게 덮어쓰도록 허용하여 무한한 재미를 제공한다. 하지만 이러한 자유도가 지수적 번식과 맞물리는 순간, 규칙 시뮬레이션은 제어 불능의 벼랑 끝으로 내몰린다.

전장에 500개 차단선을 설정해 실험을 정상화하다

대규모 자동 테스트를 이어가기 위해 Neuwirth는 공학적 해결책을 마련했다. 전장 내 지속물이 500개를 초과하면 통제 불능으로 판정하고 무승부로 처리하는 안전장치를 환경에 도입한 것이다.

이 차단 메커니즘이 적용되자 테스트는 즉시 정상을 되찾았다. 기존에 2시간 동안 멈춰 있던 대전은 새 장치 덕분에 단 0.16초 만에 안전하게 종료되었다(지속물 576개 시점에 중단). 무한 팽창에 물리적 경계를 긋는 것이 전체 작업 진행을 보장하는 최선의 방책이었다.

더 근본적인 구조 개선도 진행 중이다. 토큰이 생성될 때마다 전장을 매번 다시 훑지 않도록 자주 확인되는 상태를 캐싱하기 시작했다. 수 생성 알고리즘 역시 전원 공격과 같은 거시적 선택지를 우선 큐에 배치하도록 개선했다.

좀비 7,258마리가 프로그램을 멈춰 세운 사건은 규칙 시뮬레이션과 진정한 지능 사이의 경계를 명확히 보여준다. 컴퓨터가 미시적 분기를 맹렬한 속도로 탐색할 때, 인간은 거시적 상식을 바탕으로 핵심을 찌른다. 규칙이 지수적 번식을 허용할 때, 거시적 시각이 결여된 코드는 통제를 잃기 마련이다. 미시적인 갈래를 빈틈없이 계산하다가 자신이 쏟아낸 숫자의 바다에 스스로 갇혀버리고 만 것이다.

참고 링크:

  • Levi Neuwirth 기술 블로그 원문
  • Arcana 오픈소스 룰 엔진 코드 저장소
  • Hacker News 커뮤니티 기술 토론