Otimizando o Term.ooo

Nas últimas semanas, eu e meus amigos temos nos divertido com Wordle: um jogo de browser no qual você tem 6 palpites pra adivinhar uma palavra, sendo que cada palpite te traz informações novas (se a letra está na posição certa, se está na posição errada, ou se não pertence à solução). É basicamente uma versão modificada de Mastermind/Senha, ou como eu sempre chamei, "aquele puzzle do Gustavinho e o Enigma da Esfinge que eu não conseguia passar"

Sendo um jogo complexo de regras simples, naturalmente surgem perguntas de cunho computacional: qual a melhor palavra pra se começar? qual a melhor estratégia? é possível sempre ganhar com menos de 6 palpites? Estimulado pelo meu caro amigo @BrunoOgava e inspirado por esse post do Matt Rickard, tentei responder algumas dessas perguntas para o term.ooo, a “localização” mais famosa do Wordle em pt-br.

Qual o melhor palpite inicial?

Quando confrontadas com essa pergunta, a maioria das pessoas começa a pensar na frequência das letras: uma palavra com mais letras comuns é melhor, porque você descobre logo de cara se essas letras pertencem à solução. Essa ideia é intuitiva, mas ainda restam dúvidas: será que também devemos considerar a frequência de letras por posição? Como considerar isso? E letras repetidas, são inúteis?

Precisamos usar algum princípio, e o princípio que mais fez sentido pra mim foi o seguinte: a melhor palavra é a que reduz ao máximo o número de soluções possíveis. Para entender o que significa "soluções possíveis", vamos olhar um exemplo simples.

Suponha um Wordle simplificado com 2 letras, no qual você tenta adivinhar qual a solução dentre 4 palavras possíveis: AA, AB, AC e BC. Vamos supôr também que você está em dúvida entre dois palpites: AB e CC. Qual o melhor palpite dentre esses dois? De cara, AB parece mais interessante porque contém duas letras diferentes, enquanto CC repete a mesma letra duas vezes; mas vamos ver isso de uma forma um pouco mais detalhada.

Se você chutar o palpite AB, existem três possíveis respostas que o jogo pode te dar:

• 🟩🟩: Resposta caso a solução seja AB.
  • Resta 1 solução possível.
  • Vitória, você acertou a palavra!
• 🟩⬛: Resposta caso a solução seja AA ou AC.
  • Restam 2 soluções possíveis.
  • Você estava em dúvida entre 4 palavras, agora está em dúvida entre 2 palavras.
• ⬛🟨: Resposta caso a solução seja BC.
  • Resta 1 solução possível.
  • Você errou a palavra, mas vai acertar no turno seguinte!

(Todas as outras respostas que o jogo teoricamente poderia te dar (ex.: ⬛🟩, ⬛⬛, ⬛🟨, etc) não se encaixam em nenhuma palavra possível, portanto elas podem ser seguramente ignoradas.)

Em compensação, se você chutar o palpite CC, existem duas possíveis respostas:

• ⬛⬛: Resposta caso a solução seja AA ou AB.
  • Restam 2 soluções possíveis.
  • Você estava em dúvida entre 4 palavras, agora está em dúvida entre 2 palavras.
• ⬛🟩: Resposta caso a solução seja AC ou BC.
  • Restam 2 soluções possíveis.
  • Você estava em dúvida entre 4 palavras, agora está em dúvida entre 2 palavras.

Olhando pra essa esquematização, é intuitivo que o palpite AB seja melhor: há dois casos em que ele nos leva à solução final, enquanto em contrapartida o palpite CC sempre nos faz continuar em dúvida. Porém, como conseguimos traduzir essa ideia intuitiva em um critério que possa ser programado? A chave está no cálculo da média de soluções possíveis restantes.

Se você se sente confortável chamando números de letras e falando sobre moedas enviesadas, por favor prossiga para a próxima seção. Caso contrário, pule para a parte mais legal que é a de Resultados, logo mais abaixo; assuma que eu consegui capturar a ideia de "soluções possíveis restantes" em um número, e que usei esse número pra ranquear as palavras.

Calculando a média de soluções possíveis restantes

Essa é a parte do texto em que eu tento fingir que aprendi alguma coisa de probabilidade e estatística.

Nosso objetivo é obter uma métrica que nos faça dizer se um palpite é melhor que outro, e pra isso vamos usar o conceito de soluções possíveis restantes: um palpite é melhor do que outro se ele possui, em média, uma quantidade menor de soluções possíveis restantes. Vale lembrar que ter mais soluções possíveis é ruim porque significa que você está em muitas dúvidas sobre qual a real solução; em contrapartida, ter menos soluções possíveis é bom porque significa que você está em dúvida entre poucas palavras (idealmente, apenas 1, que é a solução).

No exemplo anterior, o palpite AB é melhor do que o palpite CC porque AB possui, em média, menos soluções possíveis restantes:

• Se a solução for AB, o palpite AB nos reduz a 1 solução possível;
• Se a solução for AA, o palpite AB nos reduz a 2 soluções possíveis;
• Se a solução for AC, o palpite AB nos reduz a 2 soluções possíveis;
• Se a solução for BC, o palpite AB nos reduz a 1 solução possível.

Assumindo que as soluções são escolhidas com probabilidade uniforme, podemos calcular a média ponderada de soluções restantes, com o valor sendo o “número de soluções possíveis” e o peso sendo a “porcentagem de palavras que produzem aquela resposta”. Para o palpite AB, temos uma média de:

$$ \frac{1}{4} \times 1 + \frac{1}{4} \times 2 + \frac{1}{4} \times 2 + \frac{1}{4} \times 1 = 1.5 \text{ soluções possíveis restantes} $$

Analogamente, o palpite CC nos reduz em média a:

$$ \frac{1}{4} \times 2 + \frac{1}{4} \times 2 + \frac{1}{4} \times 2 + \frac{1}{4} \times 2 = 2 \text{ soluções possíveis restantes} $$

Assim fica evidente que o palpite AB é melhor, porque ele reduz ao máximo o número de soluções possíveis!

Portanto, para trazer isso de volta ao Wordle tradicional, basta passarmos por todos os palpites e fazer esse mesmo cálculo de “média de soluções possíveis” para cada palpite. Descrevendo esse processo algoritmicamente, temos:

• Para cada palpite inicial $w \in W$:
  • Seja $s(w)$ a média de soluções possíveis restantes pro palpite $w$, inicializada com $0$.
  • Para cada possível resposta $r \in R$:
    • Seja $v(w, r)$ o nº de soluções que restam após obter resposta $r$ à palavra $w$.
    • Seja $p(w, r)$ o peso com a qual o palpite $w$ recebe resposta $r$, dada por $\frac{v(w,r)}{|W|}$.
    • $s(w) \leftarrow s(w) + v(w, r) p(w, r)$

Assim, o palpite com menor $s(w)$ é o melhor palpite possível!

O único detalhe que falta ser explicado é como calcular a quantidade de soluções possíveis que são eliminadas por um palpite; felizmente, isso também pode ser descrito de forma simples. Seja $w[k]$ a $k$-ésima letra do palpite $w$, e seja $r[k]$ a resposta à $k$-ésima letra do palpite. Temos:

1. Se $r[k]=$ 🟩, elimine toda palavra $z$ tal que $z[k] \neq w[k]$.
2. Se $r[k]=$ 🟨, elimine toda palavra $z$ tal que $z[k] = w[k]$ ou $w[k] \notin z$.
3. Se $r[k]=$ ⬛, elimine toda palavra $z$ tal que $w[k] \in z$ e pra qual $w[k]$ não foi confirmado.
   1. Explicação: se a solução for FARTO mas seu palpite foi FALAR, então sua resposta vai ser 🟩🟩⬛⬛🟨 - o segundo A vai tomar um ⬛ mesmo estando na solução, porque ele já foi confirmado anteriormente (no segundo 🟩). Portanto, é preciso considerar as outras letras confirmadas na hora de eliminar os ⬛s.

Com o procedimento definido, o resto é só implementação. O repositório em que fiz meus testes pode ser acessado aqui: https://github.com/vgarciasc/termooo-solver.

(Obs.: como cada palpite tem 5 letras e cada letra pode ser 🟩, ⬛ ou 🟨, então $|R| = 3^5$)

(Obs.: o algoritmo para encontrar o melhor palpite inicial é da ordem de $O(|W|^2 |R|)$)

Resultados

Ok vamos ver a parte dos gráficos legais. O term.ooo tem duas listas internas:

1. Uma lista completa com 18922 palpites válidos, que inclui presumivelmente todas as palavras de 5 letras do dicionário;
2. Uma lista reduzida com 1637 soluções possíveis, que inclui presumivelmente todas as palavras de 5 letras que pessoas normais conhecem.

A ideia é que o term.ooo aceita palpites que pertençam à lista completa (toda palavra de 5 letras no dicionário), mas ele só tira soluções possíveis de uma lista menor (com palavras de 5 letras que as pessoas conhecem).

Rankeando as palavras da lista completa de acordo com a média de soluções possíveis restantes após usar aquela palavra como palpite inicial, temos:

A melhor palavra sendo “SÓRIA”, que reduz em média a quantidade de soluções possíveis a ~31. Honestamente não faço a ideia do que seja uma “SÓRIA”, mas aparentemente é um tipo de tecido português?? (Existe um motivo pra essa lista não ser a lista de soluções possíveis...)

Para o conjunto reduzido, temos:

A melhor palavra desse conjunto é “SÉRIO”, que em média reduz a quantidade de soluções possíveis a ~36 (bem próximo dos ~31 de “SÓRIA”). O que acho mais interessante aqui é que o melhor palpite não tem a letra “A”: nossa intuição nos diz que é melhor começar com letras comuns, e “A” é a mais comum, então começar com uma palavra sem “A” parece sub-ótimo - mas na verdade não é! É um bom exemplo de como nossa intuição pode falhar.

Por curiosidade, os piores palpites do conjunto reduzido são “ESSES” e “OSSOS”, palavras com muitas letras comuns repetidas. Em média, essas palavras nos fazem continuar em dúvida entre ~500 soluções! (Agora dá pra ter uma perspectiva sobre as ~36 de “SÉRIO”)

Além do palpite inicial

Ok, agora temos o melhor palpite inicial. Mas quem disse que precisamos parar por aí? O jogo ainda continua: qual o segundo melhor palpite, e o terceiro, e o quarto?

Felizmente, a estratégia anterior ainda se aplica: com a resposta que você recebeu do palpite inicial, o conjunto de soluções possíveis foi reduzido. Agora, basta escolher o palpite que reduz ao máximo o número de soluções possíveis dentro desse novo conjunto,

Vamos voltar ao exemplo anterior, em que o conjunto de soluções possíveis era {AA , AB, AC e BC} e estávamos comparando os palpites AB e CC. Vamos supôr que você chutou AB e recebeu como resposta 🟩⬛, reduzindo assim o conjunto de soluções possíveis pra {AA, AC}. Qual o melhor palpite a se fazer agora, AB ou CC?

Se você fizer o palpite AB, há 1 resposta possível:

• 🟩⬛: Resposta caso a solução seja AA ou AC. Restam 2 soluções possíveis.

Se você fizer o palpite CC, há 2 respostas possíveis:

• ⬛⬛: Resposta caso a solução seja AA. Resta 1 solução possível (vitória!)
• ⬛🟩: Resposta caso a solução seja AC. Resta 1 solução possível (vitória!)

Assim, o palpite AB nos reduz em média a 2 soluções possíveis, e o palpite CC nos reduz em média a 1 solução possível. O palpite CC é melhor! (O que é óbvio: o palpite AB já foi feito, e portanto não carrega nenhuma informação nova).

Em outras palavras, a cada passo do jogo podemos empregar o princípio guloso de escolher a palavra que em média traz a maior redução em soluções possíveis. Estou confiante de que essa é a estratégia ótima^[1], mas não cheguei a provar.

Pra finalizar, implementei essa estratégia e testei ela em 1637 partidas diferentes, uma para cada solução possível. Assumindo a lista reduzida de palpites, obtive os seguintes resultados:

1. A estratégia leva em média 3.59 turnos pra vencer o jogo, e demora em média 7.575 segundos pra encontrar o melhor palpite;
2. A estratégia vence todo jogo;
3. As palavras mais difíceis pra essa estratégia são JATOS e PATOS, ambos demoram 6 turnos pra serem encontrados - provavelmente o algoritmo demora pra conseguir discerni-los de outras palavras similares como GATOS e FATOS (duas palavras que demoram 5 turnos pra serem encontradas, assim como MOTOS, FOFOS, BOBOS, etc).

Também é legal ver o algoritmo rodando em tempo real. Aqui, por exemplo, o algoritmo percebeu na segunda tentativa que a palavra era _OTAR, mas ao invés de testar uma das quatro possíveis soluções (NOTAR, DOTAR, VOTAR e BOTAR), ele decidiu palpitar BUNDA (uma palavra com B, N e D) pra descobrir com certeza absoluta a resposta. Eu não poderia inventar isso nem se quisesse

Em aberto

Modo difícil: O Wordle possui um “modo difícil” em que você é obrigado a utilizar todas as dicas que recebeu até agora - portanto, se você sabe que a palavra tem um R, então só poderá usar palpites que tem pelo menos um R. Acredito que a estratégia acima tenha que ser modificada um pouco pra esse outro modo de jogo: um palpite deve levar em consideração não apenas o número de palavras que elimina, mas também o número de palavras que ele poderá eliminar no futuro. Por exemplo, se você chutar GATOS e obtiver resposta ⬛🟩🟩🟩🟩, então seus palpites futuros só poderão ser RATOS, PATOS, FATOS, MATOS... É possível que você acabe perdendo o jogo! Portanto, acho que esse tipo de coisa teria de ser considerada pelo algoritmo, algum nível de lookahead.

---

^[1]: se o seu objetivo for reduzir o número médio de turnos até a vitória