감이 아니라 수학으로 워들 풀기: 정보 이론이 알려주는 최적 전략

수학으로 워들을 ‘풀어버린’ 연구자들

혹시 워들(Wordle) 해보셨어요? 5글자 영어 단어를 여섯 번 안에 맞히는 그 게임이요. 글자를 입력하면 칸 색깔로 힌트를 주잖아요. 초록색은 ‘이 글자, 이 자리 정답’, 노란색은 ‘이 글자는 있는데 자리가 틀림’, 회색은 ‘이 글자는 아예 없음’. 이 힌트를 단서 삼아 점점 정답에 다가가는 거죠. 많은 사람이 감으로 풀지만, 빙엄턴 대학교 연구진은 여기에 수학을 들이밀었어요. ‘감이 아니라 계산으로 가장 잘 푸는 방법이 뭔지’ 따져본 거예요.

핵심은 ‘정보 이론’이에요

이 문제를 푸는 열쇠가 바로 정보 이론(information theory)이에요. 이게 뭐냐면, ‘어떤 행동이 불확실성을 얼마나 줄여주는가’를 수학적으로 재는 학문이에요.

워들로 설명해볼게요. 게임을 시작할 때 정답 후보는 수천 개예요. 우리가 단어 하나를 추측하면 색깔 힌트가 나오고, 그 힌트에 따라 후보가 확 줄어들죠. 여기서 핵심 질문은 이거예요. 어떤 단어를 추측해야 후보를 가장 많이 줄일 수 있을까?

좋은 첫 단어는 후보를 거의 절반씩, 혹은 그 이상으로 쪼개주는 단어예요. 예를 들어 자주 쓰이는 글자(E, A, R, T, O, S 같은)가 골고루 들어간 단어를 던지면, 어떤 힌트가 나오든 후보군이 크게 갈라지거든요. 반대로 잘 안 쓰이는 글자만 잔뜩 든 단어를 던지면 대부분 회색이 떠서 얻는 정보가 적어요.

정보 이론에서는 이 ‘얻는 정보의 양’을 엔트로피(entropy)라는 값으로, ‘비트(bit)’ 단위로 계산해요. 1비트는 후보를 딱 절반으로 줄이는 정도의 정보예요. 그래서 매 추측마다 엔트로피가 가장 큰(=후보를 가장 많이 쪼개는) 단어를 고르면, 평균적으로 가장 적은 횟수로 정답에 도달할 수 있어요. 실제로 이런 계산을 끝까지 돌리면 SALET, CRANE, TRACE 같은 단어들이 수학적으로 우수한 첫 단어로 꼽혀요.

그냥 ‘엔트로피 최대화’가 끝이 아니에요

흥미로운 건, 매 순간 정보를 가장 많이 주는 단어를 고르는 ‘탐욕적(greedy)’ 전략이 항상 최선은 아니라는 거예요. 당장은 정보를 조금 덜 주더라도, 그다음 수까지 내다보면 더 빨리 끝나는 경우가 있거든요. 그래서 진짜 최적해를 찾으려면 가능한 게임 진행을 결정 트리(decision tree)로 쭉 펼쳐놓고, 모든 경로를 따져 ‘평균 추측 횟수를 최소로’ 혹은 ‘최악의 경우에도 몇 번 안에 끝나게’ 만드는 전략을 탐색해야 해요. 이건 단순 계산이 아니라 조합 최적화(combinatorial optimization) 문제가 돼요. 연구진이 한 일이 바로 이런 ‘증명 가능한 최적 전략’을 수학적으로 찾아낸 거예요.

업계 맥락: 사실 이건 ‘게임’ 얘기가 아니에요

워들 풀이로 유명해진 게 유튜버 3Blue1Brown의 엔트로피 영상이었는데, 그게 널리 퍼진 데는 이유가 있어요. 이 접근법이 워들에만 쓰이는 게 아니거든요.

‘여러 선택지 중에서 정보를 가장 많이 주는 질문이나 행동을 골라 불확실성을 줄인다’는 발상은 머신러닝의 결정 트리 학습(어떤 특성으로 데이터를 나눠야 가장 잘 분류되는지를 정보 이득으로 판단), 능동 학습(active learning)(어떤 데이터에 라벨을 달아야 가장 효율적인지 고르기), 심지어 효율적인 검색·진단 알고리즘(스무고개식으로 후보를 좁히기)에까지 그대로 적용돼요. 워들은 이 강력한 사고법을 누구나 직관적으로 이해할 수 있게 보여주는 완벽한 장난감인 셈이에요.

한국 개발자에게

당장 워들 풀이 봇을 만들 일은 없을지 몰라도, 여기서 얻을 교훈은 꽤 실용적이에요. 우리가 코드를 짜다 보면 ‘수많은 후보 중에서 무엇을 먼저 시도해야 가장 빨리 답에 도달할까’ 하는 문제를 자주 만나거든요. 디버깅할 때 어디부터 찍어볼지(이진 탐색처럼 절반씩 좁히기), A/B 테스트에서 어떤 실험을 먼저 돌릴지, 추천 시스템에서 사용자에게 뭘 물어볼지. 전부 ‘정보를 가장 많이 주는 선택’이라는 같은 뿌리에서 나와요.

엔트로피와 정보 이득이라는 개념 하나만 손에 익혀두면, 막연히 감으로 찍던 일들을 ‘기댓값으로 따져 고르는’ 습관으로 바꿀 수 있어요. 그게 이 연구가 주는 진짜 선물이에요.

한 줄 정리: 워들의 정답은 ‘운’이 아니라 ‘정보를 가장 많이 주는 추측’을 고르는 계산이에요. 여러분이 매일 내리는 기술적 선택 중에, 사실은 ‘엔트로피 최대화’로 다시 볼 수 있는 게 뭐가 있을까요?