Teoria da informação e Wordle
Você talvez já tenha visto ou jogado o jogo wordle, ou o termo (a versão pt-br do wordle). É um jogo onde todos os dias uma palavra secreta é escolhida, eu objetivo é adivinhar a palavra, em no máximo 6 tentativas, com base em algumas dicas. Você começa chutando uma palavra qualquer (só podem ser palavras de 5 letras) e o jogo te diz se as letras da palavra que você chutou existem na palavra secreta, se não existem, e se estão na mesma posição que você colocou.
Por exemplo, se a palavra é beijo e seu primeiro chute é jeito, o jogo irá de dizer que o j está na palavra secreta, porém em outra posição; o e está na palavra secreta e está na posição correta; o i também, o t não está na palavra secreta; e o o está e também está na posição correta, assim como o ei. O jogo diz isso colorindo a posição de cada palavra para você, tipo assim:
Tentativa: jeito
Feedback:
Com essa informação, você chuta uma nova palavra. Tente jogar uma partida aqui: termo.pt
Acontece que no primeiro chute, você não tem nenhuma informação sobre a palavra secreta, então vem a pergunta: Existe uma palavra que é um chute inicial melhor do que outras?
A princípio pode parecer que não, a resposta pode ser qualquer palavra e a chance de que você acerte no primeiro chute é ínfima. De acordo com o repositório de palavras da língua portuguesa do IME-USP, há 5481 palavras com cinco letras na língua portuguesa brasileira, excluindo nomes de cidades. Portanto existe 1 em 5481 chances de você acertar a palavra de primeira, supondo que todas as 5841 palavras estão inclusas como possíveis respostas para o jogo.
Mas o nosso objetivo no primeiro chute não deve ser acertar de primeira, mas sim escolher a palavra que nos de as informações mais uteis para pensarmos em qual deve ser a palavra secreta. Por exemplo, sabemos que muitas palavras do português possuem a letra a e e, enquanto pouquíssimas possuem a letra x. Saber quais letras estão inclusas ou não, é uma informação valiosa. Então voltamos à pergunta: Existe uma palavra que é um chute inicial melhor do que outras? Ou melhor ainda, existe uma palavra que nos dê mais informação do que outras?
O meu objetivo aqui nesse texto é mostrar que sim, e encontrar qual é a melhor palavra para servir de chute inicial no termo usando teoria da informação. Antes vale dizer que estas anotações são praticamente uma tradução do vídeo Solving Wordle using information theory, do canal 3Blue1Brown. Se você é confortável com inglês, acredito que valha mais a pena assistir ao vídeo do que ler esse texto, aqui estarei basicamente aplicando o que é mostrado no vídeo para o termo ao invés do wordle, ou seja, usando português ao invés de inglês.
O melhor chute inicial
Se você já jogou termo na época em que ele foi uma febre, você provavelmente tinha uma palavra favorita que gostava de usar nas primeiras tentativas.
Para quantificarmos qual o melhor chute inicial, vamos supor que inicamos com a palavra beijo. Não sabemos qual é a palavra secreta, e portanto não sabemos qual será o feedback que o jogo nos dará. E se o feedback for por exemplo:
Ou seja, as letras e e i estão na resposta final, porém em posições diferentes, enquanto que as demais não estão. Essa informação nos permite eliminar muitas palavras, como “bomba”, já que sabemos que b não está contido na resposta. Na verdade, sobram 293, das 5481 palavras. E se o feedback do jogo fosse outro, por exemplo
Nesse caso restariam 142 palavras. Podemos fazer isso com todos os possíveis feedbacks que o jogo nos dá. Temos 3 opções de feedback para cada uma das 5 letras da palavra, portanto o total de feedbacks possíveis é $3 \times 3 \times 3 \times 3 \times 3 = 3^5 = 243$. Em cada um deles, vai existir uma quantidade $n$ de palavras restantes que atendem às informações fornecidas pelo jogo. Como não sabemos qual é a palavra secreta, cada feedback tem uma chance $p$ de ocorrer dado pela quantidade de palavras restantes dividido pelo total de palavras de 5 letras inicialmente. Ou seja
\[\begin{align} p = \frac{n}{5481} \end{align}\]No caso de beijo como chute inicial, podemos organizar cada possibilidade de feedback da mais provável para a menos provável.
