영상: 정보 이론 (information theory)을 사용하여 Wordle 해결하기
채널: 3Blue1Brown
길이: 30분 38초
출처: 자막 (자동 생성, 영어)

전사:
Wordle 게임은 지난 한두 달 동안 꽤나 화제가 되었습니다. 수학 수업을 위한 기회를 놓치지 않는 성격상, 이 게임이 정보 이론 (information theory), 특히 엔트로피 (entropy)라고 알려진 주제에 관한 수업에서 매우 좋은 중심 사례가 될 수 있겠다는 생각이 들었습니다. 보시다시피, 많은 사람들처럼 저도 이 퍼즐에 빠져들었고, 많은 프로그래머들처럼 저 또한 이 게임을 최대한 최적으로 플레이할 수 있는 알고리즘을 작성하는 데 빠져들었습니다. 그래서 제가 여기서 하고자 하는 것은 그 과정 중 일부를 여러분과 함께 이야기 나누고, 알고리즘 전체가 이 엔트로피 (entropy)라는 개념을 중심으로 하기 때문에 그 안에 들어간 수학적 원리를 설명하는 것입니다.

가장 먼저, 혹시 들어보지 못했을 수도 있으니, Wordle이란 무엇일까요? 그리고 일석이조로, 게임의 규칙을 살펴보면서 우리가 나아갈 방향, 즉 기본적으로 우리를 대신해 게임을 플레이할 작은 알고리즘을 개발하는 것에 대해서도 미리 살펴보겠습니다. 저는 오늘 자 Wordle을 아직 하지 않았습니다. 오늘은 2월 4일이며, 봇이 어떻게 하는지 지켜보겠습니다. Wordle의 목표는 비밀스러운 다섯 글자 단어를 맞히는 것이며, 당신에게는 추측할 수 있는 여섯 번의 기회가 주어집니다. 예를 들어, 저의 Wordle 봇은 crane이라는 단어로 시작할 것을 제안합니다.

추측을 할 때마다, 당신의 추측이 실제 정답에 얼마나 가까운지에 대한 정보를 얻게 됩니다. 여기서 회색 상자는 실제 정답에 C가 없다는 것을 알려줍니다. 노란색 상자는 R이 있지만 그 위치에 있지는 않다는 것을 알려줍니다. 초록색 상자는 비밀 단어에 A가 포함되어 있으며 세 번째 위치에 있다는 것을 알려줍니다. 그리고 N은 없고, E도 없습니다. 그럼 제가 가서 Wordle 봇에게 그 정보를 알려주겠습니다. 우리는 crane으로 시작했고, 회색, 노란색, 초록색, 회색, 회색을 얻었습니다.

지금 화면에 보이는 모든 데이터에 대해 너무 걱정하지 마세요. 때가 되면 설명해 드리겠습니다. 하지만 우리의 두 번째 선택을 위한 최우선 제안은 stick입니다. 여러분의 추측은 반드시 실제 다섯 글자 단어여야 하지만, 보시다시피 시스템이 허용하는 추측 범위는 상당히 관대합니다. 이번 경우에는 stick을 시도해 보겠습니다. 좋습니다, 상황이 꽤 좋아 보이네요. S와 H를 맞혔으니 처음 세 글자를 알게 되었고, R이 있다는 것도 알게 되었습니다. 따라서 S H A [무엇] R 이거나, S H A R [무엇] 형태가 될 것입니다.

그리고 Wordle 봇은 이제 가능성이 shard 또는 sharp, 이 두 가지뿐이라는 것을 알고 있는 것 같습니다. 현재 시점에서는 두 단어 사이에서 승부를 예측하기 어려운 상황이므로, 아마도 알파벳 순서 때문에 shard를 선택한 것 같습니다. 그리고 만세, 그것이 실제 정답입니다! 이렇게 세 번 만에 맞혔습니다. 이것이 어느 정도 수준인지 궁금하시다면, 어떤 분이 표현한 방식 중 'Wordle에서 4점은 파(par)이고, 3점은 버디(birdie)다'라는 말이 있는데, 저는 이것이 꽤 적절한 비유라고 생각합니다. 4점을 계속 유지하려면 꾸준히 실력을 발휘해야 하지만, 그렇다고 해서 결코 말도 안 되는 수준은 아닙니다.

하지만 3번 만에 맞혔을 때는 정말 기분이 좋습니다. 그래서 여러분이 괜찮으시다면, 제가 Wordle 봇에 접근하는 방식에 대해 처음부터 제 사고 과정을 차근차근 이야기해 보고 싶습니다. 앞서 말씀드렸듯이, 이것은 사실 정보 이론 (Information Theory) 강의를 위한 구실이기도 합니다. 주요 목표는 정보 (Information)란 무엇인지, 그리고 엔트로피 (Entropy)란 무엇인지 설명하는 것입니다. 이 문제에 접근할 때 저의 첫 번째 생각은 영어에서 각 알파벳이 나타나는 상대적 빈도 (Relative frequencies)를 살펴보는 것이었습니다. 그래서 저는 '좋아, 이 빈도가 높은 글자들을 많이 포함하는 첫 번째 추측 단어 혹은 첫 두 개의 추측 단어 조합이 있을까?'라고 생각했습니다.

그리고 제가 꽤 좋아했던 방식 중 하나는 'other' 다음에 'nails'를 입력하는 것이었습니다. 그 생각의 근거는 만약 어떤 글자를 맞춘다면, 즉 초록색이나 노란색을 얻게 된다면, 그것은 항상 기분이 좋다는 것입니다. 마치 정보를 얻고 있는 것처럼 느껴지죠. 하지만 이런 경우, 설령 맞추지 못해 항상 회색만 나온다 하더라도, 이 글자들을 포함하지 않는 단어를 찾는 것이 꽤 드물기 때문에 여전히 많은 정보를 제공합니다. 하지만 그럼에도 불구하고, 이것은 매우 체계적으로 느껴지지는 않는데, 예를 들어 글자의 순서를 고려하는 데 아무런 도움이 되지 않기 때문입니다.

'snail'을 입력할 수 있는데 왜 'nails'를 입력할까요? 's'가 끝에 있는 것이 더 나을까요? 저는 잘 모르겠습니다. 한 번은 제 친구가 'wee-wee'라는 단어로 시작하는 것을 좋아한다고 말해서 좀 놀랐는데, 그 단어에는 'w'나 'y'처럼 흔하지 않은 글자들이 포함되어 있기 때문입니다. 하지만 누가 알겠어요? 어쩌면 그것이 더 나은 시작 단어일지도 모르죠. 잠재적인 추측의 품질을 판단하기 위해 우리가 부여할 수 있는 일종의 정량적 점수(quantitative score)가 있을까요? 이제 가능한 추측 단어들의 순위를 매기는 방식을 설정하기 위해, 다시 돌아가서 게임이 정확히 어떻게 구성되어 있는지 조금 더 명확하게 설명해 보겠습니다.

우선, 유효한 추측으로 간주되어 입력할 수 있는 단어 목록이 있는데, 그 길이는 약 13,000단어에 달합니다. 하지만 살펴보면 'ahead'나 'ali', 'arg'와 같이 스크래블(Scrabble) 게임에서 가족 간의 논쟁을 불러일으킬 법한 정말 흔치 않은 단어들이 많이 있습니다. 하지만 이 게임의 분위기는 정답이 항상 어느 정도 흔한 단어가 될 것이라는 점입니다. 실제로 가능한 정답이 될 수 있는 약 2,300개의 단어로 이루어진 또 다른 목록이 있습니다. 그리고 이것은 사람이 직접 큐레이션한 목록인데, 제 생각에는 특히 게임 제작자의 여자친구가 만든 것 같습니다. 이 점이 꽤 재미있네요.

하지만 제가 하고 싶은 것, 즉 이 프로젝트의 도전 과제는 이 목록에 대한 사전 지식을 포함하지 않고도 Wordle을 해결하는 프로그램을 작성할 수 있는지 확인하는 것입니다. 우선, 그 목록에는 포함되어 있지 않은 꽤 흔한 다섯 글자 단어들이 많이 있습니다. 따라서 공식 웹사이트에서 제공하는 단어들에만 국한되지 않고, 누구를 상대로든 Wordle을 플레이할 수 있는 조금 더 회복 탄력성 (resilient) 있는 프로그램을 작성하는 것이 더 나을 것입니다. 또한, 우리가 가능한 정답 목록을 알 수 있는 이유는 그것이 소스 코드 (source code)에 노출되어 있기 때문입니다.

하지만 소스 코드에 노출되어 있는 방식은 정답이 매일매일 나타나는 특정한 순서로 되어 있습니다. 따라서 내일의 정답이 무엇인지 그냥 찾아볼 수도 있습니다. 그러므로 이 목록을 사용하는 것이 일종의 부정행위 (cheating)라는 의미가 있음은 분명합니다. 더 흥미로운 퍼즐이자 더 풍부한 정보 이론 (information theory) 수업이 되기 위해서는, 대신에 일반적인 단어 빈도 (word frequencies)와 같이 더 보편적인 데이터를 사용하여, 더 흔한 단어를 선호한다는 직관을 포착하는 것이 좋습니다. 그렇다면 이 13,000개의 가능성 중에서, 첫 번째 추측 (opening guess)을 어떻게 선택해야 할까요?

예를 들어, 제 친구가 'weary'를 제안한다면, 우리는 그 품질을 어떻게 분석해야 할까요? 글쎄요, 그가 그 희귀한 'W'를 좋아한다고 말한 이유는, 만약 그 'W'를 맞혔을 때의 그 짜릿한 느낌, 즉 도박적인 성격 (long shot nature)을 좋아하기 때문입니다. 예를 들어, 만약 처음 드러난 패턴이 이와 같다면, 이 거대한 어휘 사전 (lexicon)에서 해당 패턴과 일치하는 단어는 58개뿐이라는 사실이 밝혀집니다. 이는 13,000개에서 엄청나게 줄어든 수치입니다. 하지만 물론 그 반대 측면은, 이런 패턴을 얻는 것이 매우 드물다는 점입니다.

구체적으로, 만약 각 단어가 정답일 확률이 모두 동일하다면, 이러한 패턴을 맞출 확률은 58을 약 13,000으로 나눈 값이 될 것입니다. 물론, 단어들이 정답일 확률이 모두 동일하지는 않습니다. 이들 중 대부분은 매우 생소하거나 심지어 의문스러운 단어들입니다. 하지만 적어도 이 모든 과정의 첫 번째 단계에서는, 모든 단어가 동일한 확률을 가진다고 가정하고 나중에 이를 조금씩 정교화해 나가도록 합시다. 핵심은 정보량이 많은 패턴은 그 본질상 발생할 가능성이 낮다는 점입니다. 사실, 정보가 풍부하다는 것의 의미 자체가 바로 발생 가능성이 낮다는 것을 뜻합니다.

이 첫 번째 시도에서 훨씬 더 높은 확률로 볼 수 있는 패턴은 다음과 같은 형태일 것입니다. 물론 여기에는 W가 포함되어 있지 않습니다. 아마도 E가 포함되어 있을 수도 있고, A나 R, Y는 없을 수도 있습니다. 이 경우, 가능한 일치 항목은 1,400개였습니다. 따라서 모든 단어의 확률이 동일하다면, 이러한 패턴을 보게 될 확률은 약 11%로 계산됩니다. 즉, 가장 가능성이 높은 결과가 가장 정보량이 적은 결과이기도 합니다. 여기서 더 전체적인 관점을 갖기 위해, 여러분이 마주할 수 있는 모든 서로 다른 패턴들에 걸친 전체 확률 분포를 보여드리겠습니다.

여러분이 보고 있는 각 막대는 나타날 수 있는 색상 패턴의 가능성에 대응하며, 그 경우의 수는 3의 5제곱(3^5)입니다. 그리고 이들은 왼쪽에서 오른쪽으로, 가장 흔한 것부터 가장 드문 순서로 정리되어 있습니다. 여기서 가장 흔한 가능성은 모두 회색(grays)이 나오는 경우입니다. 이는 약 14%의 확률로 발생합니다. 여러분이 추측을 할 때 바라는 결과는, 이 긴 꼬리(long tail) 부분 중 어딘가에 도달하는 것입니다. 예를 들어, 이 패턴에 일치하는 가능성이 단 18개뿐인 저 끝부분과 같은 곳 말입니다.

혹은 우리가 왼쪽으로 조금 더 나아가서, 아시다시피 여기까지 완전히 이동한다고 가정해 봅시다. 좋습니다, 여기 좋은 퍼즐이 하나 있습니다. 영어에서 W로 시작하고, Y로 끝나며, 어딘가에 R이 포함된 세 단어는 무엇일까요? 정답은, 음, 어디 보자. Wordy, wormy, 그리고 Riley입니다. 이 단어가 전반적으로 얼마나 좋은지 판단하기 위해서, 우리는 이 분포로부터 얻게 될 기대 정보량 (expected amount of information)에 대한 일종의 측정치를 원합니다. 각 패턴을 살펴보고, 그 패턴이 발생할 확률에 그것이 얼마나 정보가 많은지를 측정하는 무언가를 곱한다면, 아마도 우리에게 객관적인 점수를 줄 수 있을 것입니다.

이제, 그 '무언가'가 무엇이어야 하는지에 대한 여러분의 첫 번째 직관은 일치하는 개수 (number of matches)일 수도 있습니다. 아시다시피, 여러분은 평균 일치 개수가 더 낮기를 원할 것입니다. 하지만 그 대신, 저는 우리가 정보에 흔히 부여하는, 더 보편적인 측정치를 사용하고 싶습니다. 이 측정치는 이 13,000개의 단어 각각이 실제로 정답인지 아닌지에 대해 서로 다른 확률이 할당되었을 때 더 유연하게 작용할 것입니다. 정보의 표준 단위는 비트 (bit)이며, 약간 재미있는 공식을 가지고 있지만 예시를 통해 살펴보면 매우 직관적입니다.

만약 여러분이 가능성의 공간 (space of possibilities)을 절반으로 줄이는 관측을 한다면, 우리는 그것이 1비트의 정보를 가지고 있다고 말합니다. 우리의 예시에서, 가능성의 공간은 가능한 모든 단어들이며, 5글자 단어의 약 절반 정도가 S를 가지고 있다는 사실이 밝혀졌습니다. 그보다 약간 적긴 하지만 거의 절반입니다. 따라서 그 관측은 여러분에게 1비트의 정보를 제공할 것입니다. 만약 대신에 새로운 사실이 그 가능성의 공간을 4분의 1로 쪼갠다면, 우리는 그것이 2비트의 정보를 가지고 있다고 말합니다. 예를 들어, 이 단어들의 약 4분의 1이 T를 가지고 있다는 사실이 밝혀졌습니다.

만약 관찰을 통해 그 공간을 8분의 1로 줄였다면, 우리는 그것이 3비트의 정보를 가지고 있다고 말하며 이런 식으로 계속 이어집니다. 4비트는 16분의 1로 줄이고, 5비트는 32분의 1로 줄입니다. 자, 이제 잠시 멈춰서 스스로에게 질문해보고 싶을 시점입니다. 어떤 사건이 발생할 확률(probability)의 관점에서 볼 때, 정보량(bits)을 구하는 공식은 무엇일까요? 우리가 여기서 말하고자 하는 바는 기본적으로 1/2을 비트 수만큼 거듭제곱한 것이 확률과 같다는 것이며, 이는 곧 2를 비트 수만큼 거듭제곱한 것이 1/확률과 같다는 것과 같습니다. 이를 다시 정리하면 정보량은 1/확률의 밑이 2인 로그(log base two) 값이라고 할 수 있습니다.

그리고 때로는 이를 한 번 더 정리하여 정보량이 확률의 음의 밑 2인 로그(negative log base two)라고 표현하는 것을 볼 수 있습니다. 이렇게 표현하면 익숙하지 않은 사람들에게는 조금 이상해 보일 수 있지만, 사실 이것은 가능성을 몇 번이나 절반으로 줄였는지를 묻는 매우 직관적인 아이디어일 뿐입니다. 만약 여러분이 '그냥 재미있는 단어 게임을 하고 있다고 생각했는데, 왜 로그(logarithm)가 등장하는 거지?'라고 궁금해하신다면, 한 가지 이유는 이 단위가 매우 희귀한 사건들에 대해 이야기하기 훨씬 쉽기 때문입니다.

어떤 사건이 발생할 확률이 0.00000095라고 말하는 것보다, 어떤 관찰이 20비트의 정보를 가지고 있다고 말하는 것이 훨씬 쉽습니다. 하지만 이 로그 표현식이 확률론(theory of probability)에 매우 유용한 추가 요소가 된 더 실질적인 이유는 정보가 합쳐지는 방식 때문입니다. 예를 들어, 하나의 관찰이 공간을 4분의 1로 줄여 2비트의 정보를 제공하고, 그다음 두 번째 관찰(Wordle에서의 두 번째 추측과 같은)이 공간을 다시 8분의 1로 줄여 3비트의 정보를 추가로 제공한다면, 이 둘을 합친 정보량은 5비트가 됩니다.