NYT 게임이 유독 어려운 이유: 계산 복잡도(Computational Complexity) 관점에서의 분석
아침 스크럼보다 중요한 의식, NYT Games
개발자라면 아침에 커피를 내리며 슬랙(Slack)이나 팀 챗방에 그날의 Wordle 점수를 공유하는 문화, 한 번쯤 겪어보셨을 겁니다. 저 역시 매일 아침 ‘Connections’ 때문에 머리를 쥐어뜯고 시작하는데요. 단순히 “오늘 단어가 어렵네”라고 넘길 수도 있지만, 최근 흥미로운 논문 하나가 ArXiv에 올라와서 엔지니어 관점에서 뜯어보려고 합니다.
제목부터 도발적인 “Man, these New York Times games are hard! A computational perspective”라는 논문입니다. 이 논문은 NYT의 퍼즐 게임들이 단순히 ‘단어를 많이 알아야 하는’ 언어적 문제가 아니라, 컴퓨터 과학적으로 NP-Complete 에 해당하는 난제들이라는 것을 증명하고 있습니다.
오늘은 이 논문의 내용과 Hacker News의 반응을 섞어, 우리가 왜 이 조그만 3x3, 4x4 그리드 앞에서 좌절감을 느끼는지 기술적으로 파헤쳐 보겠습니다.
1. 언어 영역? 아니요, 그래프 이론입니다.
이 논문은 Letter Boxed, Pips, Strands, Tiles 네 가지 게임을 분석합니다. 연구진이 밝혀낸 핵심은 이 게임들의 일반화된 형태(generalized version)가 계산 복잡도 이론에서 말하는 NP-Complete 문제라는 것입니다.
가장 흥미로운 예시는 Letter Boxed 입니다. 사각형 변에 있는 글자들을 이어 단어를 만드는 이 게임은, 사실상 그래프 탐색(Graph Traversal) 문제입니다. 논문에서는 주어진 인스턴스가 해결 가능한지 판별하는 것 자체가 일반적인 설정에서 NP-Complete임을 보였습니다. 물론 특정 파라미터 설정에서는 다항 시간(Polynomial time) 내에 풀리기도 하지만, 우리가 매일 마주하는 ‘최적해(2단어 안에 끝내기)‘를 찾는 과정은 결코 만만치 않은 최적화 문제(Optimization Problem)인 셈이죠.
Hacker News의 한 유저(anon)는 이렇게 말합니다.
“Letter Boxed를 2단어 안에 끝내려고 하면 정말 어렵다. 나는 영어가 모국어가 아니라서 언어적 직관보다는 계산적 관점(computational perspective) 으로 접근하는데, 이게 오히려 도움이 될 때가 있다.”
저도 이 의견에 전적으로 동의합니다. 어휘력이 부족해서 못 푸는 게 아닙니다. 탐색 공간(Search Space)이 너무 넓은 겁니다. 우리는 무의식적으로 Pruning(가지치기) 알고리즘을 뇌에서 돌리고 있는 것이죠.
2. “재미”를 위한 난이도 설계: P vs NP
왜 굳이 게임을 NP-Hard 수준으로 어렵게 만들까요? 여기에 게임 디자인의 정수가 있습니다. 만약 퍼즐이 P(Polynomial time) 문제라면, 즉 쉬운 알고리즘으로 금방 풀린다면 인간의 뇌는 금방 패턴을 파악하고 지루함을 느낄 겁니다.
Hacker News의 댓글 중 인상 깊었던 통찰이 있습니다.
“퍼즐 게임이 재미있으려면 NP-hard여야 한다는 이론이 있다. 그렇지 않으면 뇌가 ‘꼼수(trick)‘를 너무 빨리 찾아내서 게임이 시시해진다.”
우리의 뇌는 훌륭한 패턴 매칭 엔진입니다. 너무 쉬우면 자동화해버리고, 너무 어려우면 포기합니다. NYT 게임들은 그 임계점(Threshold) 을 기가 막히게 타고 있습니다.
물론, 엄밀히 따지자면(Pedantic하게 접근하자면), 영어 단어의 수는 유한하고 보드 크기도 고정되어 있으므로 이론적으로는 O(1)입니다. 하지만 우리가 체감하는 난이도는 입력 사이즈(n)가 커질 때의 Asymptotic complexity 를 따라가기 때문에, 이 논문의 분석은 여전히 유효합니다.
3. NYT는 이제 뉴스 회사가 아니다
기술적인 이야기에서 살짝 벗어나 비즈니스 관점에서 보면 상황은 더 재밌습니다. 2023년 기준 NYT 웹사이트 방문의 55% 가 뉴스가 아닌 ‘게임’에서 발생했다고 합니다.
한 HN 유저는 이를 두고 이렇게 평했습니다.
“항공사가 마일리지 사업을 위해 비행기를 띄우는 것처럼, NYT는 게임 구독을 위해 뉴스를 제공하는 회사가 되어가고 있다.”
실제로 많은 엔지니어들이 뉴스 구독은 끊어도 ‘Games Only’ 구독은 유지합니다. 저 역시 그렇고요. 이는 미디어 기업이 살아남기 위해 어떻게 User Engagement 를 확보해야 하는지 보여주는 강력한 사례입니다. 텍스트(뉴스)는 Commodity가 되었지만, 잘 설계된 NP-Complete 퍼즐은 대체 불가능한 경험(Experience)을 제공하니까요.
4. 엔지니어의 시각: Strands와 Pips
논문에서 언급된 Strands 와 Pips 도 마찬가지입니다. Strands에서 단어를 찾는 과정은 제약 조건 만족 문제(Constraint Satisfaction Problem)와 유사합니다.
특히 미국 문화에 익숙지 않은 경우, 이런 게임은 순수한 알고리즘 챌린지가 됩니다. “Znyorp” 같은 로직으로 힌트를 해독해야 한다는 댓글을 보며 쓴웃음을 지었습니다. 문화적 맥락(Context)이라는 휴리스틱(Heuristic)이 없으면, 이 문제는 순수한 Brute-force 공격 대상이 되어버리니까요.
결론: 우리는 매일 아침 튜링 머신을 돌린다
이 논문은 우리가 단순히 시간을 때우기 위해 게임을 하는 것이 아니라, 꽤 고차원적인 연산 능력을 테스트하고 있음을 상기시켜 줍니다.
Connections 가 유독 어렵게 느껴지시나요? 그건 여러분의 뇌가 성능 나쁜 CPU라서가 아닙니다. 그저 문제 자체가 NP-Complete 라서 그렇습니다. 그러니 내일 아침 퍼즐이 안 풀려도 너무 자책하지 마세요. 여러분은 지금 수학적으로 증명된 난제와 싸우고 있는 거니까요.
Verdict: 이 논문은 단순한 게임 분석을 넘어, 인간이 ‘재미’를 느끼는 난이도의 수학적 배경을 잘 설명해 줍니다. 엔지니어라면 일독을 권합니다. 아, 그리고 Letter Boxed 2단어 클리어는… 그냥 스크립트 짜서 돌리는 게 정신 건강에 이로울지도 모릅니다.
References: