Jak řeší programátoři hru Wordle?
Aneb je GitHub Copilot „programování 2.0“?
Rozhovor s Liborem Mořkovským, CTO Behavio
V březnu byl Libor jedním ze dvou přednášejících na pražském setkání vývojářů v Pythonu, tedy na Pyvu. Ve sklepě holešovického Liberálu se sešlo odhadem 50 pyvařů a pyvařek, které se rozhodl seznámit s tím, jak hacknout hru Wordle.
Wordle vs. Copilot
Libor si dvakrát zkusil, jaké to je hrát Wordle jako člověk, a stačilo. Rozhodl se, že do příštích kol přibere do týmu umělou inteligenci Copilot. Vyzkoušet si ji můžete i v JetBrains a NeoVimu, ale nejlepší zážitek čekejte ve VSCode. Kód můžete sledovat i v GitHubu.
Jak se dá v našem malém experimentu aplikovat maximalizace entropie? A proč se vyplatí začínat s mladým jestřábem? Libor vám vše vysvětlí a ukáže přímo v kódu.
Libore, jak to je s tou umělou inteligencí? Vyřeší Copilot Wordle za tebe?
Dal jsem mu samozřejmě šanci dát to na první dobrou. Moc slavně to nedopadlo. Vypadá to, že když Copilot postavíme před úkol, na který nemá, „rozhodne“ se, že přece musí existovat knihovna, která už problém řeší. Taková ale existovat vůbec nemusí.
V kódu, který bude následovat ve zbytku článku, je šedivě podbarvené to, co jsem psal já. Zbytek navrhl Copilot.
"""This is a program that can solve Wordle games. Wordle is a game where you try to guess a 5-letter word. Each guess gives you clues about the word. It outputs suggested guesses based on the previous guesses and the clues it reads encoded in ! for match, + for match on different position and - for no match. """ import argparse import os import random import re import sys from wordle import Wordle def solve(args): """Solve the wordle game. """ wordle = Wordle(args.wordlist) wordle.load_words() wordle.load_clues() wordle.solve() wordle.print_solution() def main(): """Parse command line arguments and call solve() """ parser = argparse.ArgumentParser(description='Wordle solver') parser.add_argument('wordlist', help='wordlist file') args = parser.parse_args() solve(args) if __name__ == '__main__': main()
Jak to udělat lépe?
Chvíli jsem zkoumal jak by takové „Programování 2.0“ (za pomoci umělé inteligence) mělo fungovat. Trochu mi přijde, že je to jako zahradničení. V zahradě si musím nejprve rozmyslet, co chci pěstovat. Následně si připravím záhonky, předpěstuji sazeničky a pak o rostliny pečuji. A když to všechno běží, tak doufám, že budu mít štěstí a úrodu mi nezničí nějací brouci nebo jiná škodná.
Zpátky ke hře. Je v ní zhruba 12 000 slov, z toho 2 315 jich může být tajenkou a zbývajících cca 10 000 jsou slova, která mohu tipovat, ale nikdy tajenkou nebudou. Seznamy jsou oddělené proto, aby podivnosti jako ‘aalii’ nemohly být tajenkou. Hra mi vylosuje slovo, já si tipnu a ona mi můj tip vyhodnotí tím, že mi písmena z tipu obarví.
Aha. A jak se pěstuje program na řešení Wordle?
"""A library that implements the Wordle game."""
def eval_guess(target: str, guess: str) -> str:
"""Compare target and guess. Target and guess are both the same length.
Return a string of the same length as target and guess,
where a character encodes the match:
- ! for a match
- for a miss
- + when the character appears in a different position.
"""
result = ""
for i in range(len(target)):
if target[i] == guess[i]:
result += "!"
elif guess[i] in target:
result += "+"
else:
result += "-"
return result def eval_guess(target: str, guess: str) -> str: """Compare target and guess. Target and guess are both the same length. Return a string of the same length as target and guess, where a character encodes the match: - ! for a match - for a miss - + when the character appears in a different position. >>> eval_guess('cat', 'dog') '!+' >>> eval_guess('cat', 'cat') '!!' >>> eval_guess('cat', 'act') '!+' >>> eval_guess('cat', 'tac') '!+' """
Tady příběh trochu zkrátíme o mnoho různých pokusů, které nevedly ke správnému řešení. Zakopaný pes je ve žlutých + nápovědách. Jsou to pouze ta písmena, která sice v tajence jsou, ale na jiném místě. Když počítám žlutá + písmena, tak už nesmím započítat zelená !. Jakmile jsem tohle zapsal do komentářů, dostal jsem konečně správný výsledek.
Bonusem tohoto lehce pracného postupu je, že když už se v kódu děje něco složitého, máte to krásně zdokumentované v komentářích. Jenom pozor, jakmile začnete psát komentář – Copilot by v něm nadšeně pokračoval dalších 20 řádků. A vůbec mu nevadí, že už nemá co říct a točí se v kruzích.
# find the indices of characters that don't match the target wrong = [i for i, (t, g) in enumerate(zip(target, guess)) if t != g] # count character occurrences in target # at `wrong` positions using collections.Counter counts = collections.Counter(target[i] for i in wrong)
# for each guessed character in wrong, replace result with + # if the characters count is more than 0, otherwise replace with - # decrease counts by 1 for each + for i in wrong: if counts[guess[i]] > 0: result[i] = '+' counts[guess[i]] -= 1 else: result[i] = '-' return ''.join(result)
Problém se žlutými nápovědami měl i Grant Sanderson ve svém YouTube kanálu 3Blue1Brown. Video si určitě pusťte, ani ne tak kvůli schadenfreude, ale proto, že je v něm krásně vysvětlena metoda řešení Wordle pomocí maximalizace entropie, kterou používám i já.
Zpátky k našemu řešení: už umíme správně vyhodnotit tip. Ještě jedna věc chybí k tomu, aby to byl opravdový Wordle. Potřebujeme seznamy slov, které mohu hádat a které mohou být tajenkou.
Zkusíme tedy vypěstovat Game(), která spojuje eval_guess a slovníky.
class Game: """A single wordle game. """ def __init__(self, word_index=None): """word_index is an index to words.challenges, use random word if None""" self.word = words.get_random_challenge()
if word_index is None else words.challenges[word_index]
def eval_guess(self, guess: str) -> str: """Evaluate the guess is in the wordlist. Then evaluate the guess against the word. """ if not words.in_dict(guess): return '-' * len(guess) return eval_guess(self.word, guess) self.guesses.add(guess)
A tím už počítač začne hrát Wordle?
Skoro. Ke hře naprogramujeme ještě protivníka. Ten musí nejprve porozumět tomu, co mu nápovědy říkají. Snažil jsem se vytvořit nějaký složitý popis informací, které se dají vytěžit z každého tipu. Něco ve smyslu „už vím, že třetí písmeno nemůže být `A` a zároveň páté písmeno může být C nebo Q, ale jen pokud třetí písmeno není C“ … Byla to hromada kódu, a stejně by nezachytila všechny informace kvůli již zmíněným žlutým polím.
Nejlepším způsobem, jak podchytit všechny informace, které mi jedna nápověda poskytne, je zapamatovat si seznam tajenek, které jsou s touto nápovědou konzistentní. To znamená, že když proti této tajence vyhodnotím můj tip, dostanu stejnou nápovědu jako jsem v tomto kole dostal od hry. Správná tajenka musí být konzistentní s každou nápovědou, kterou jsem v průběhu hry dostal. To znamená že musí být v každém seznamu zapamatovaných tajenek. Toho můžu využít k tomu, že seznam tajenek které musím vyhodnocovat postupně zužuju, čímž ještě zpracování trochu zrychlí.
import wordle def filter(candidates: list[str], guess: str, pattern: str) -> list[str]: """Filter candidates by pattern. """ return [word for word in candidates if wordle.eval_guess(word, guess) == pattern] class RandomSolver: """Try to solve wordle game by random guessing. After each guess, filter the candidate list. """ def __init__(self, game: wordle.Game): """Initialze candidates from challenges wordlist.""" self.candidates = list(words.challenges) self.game = game def solve(self) -> str: """Solve the game by random guessing. """ while True: guess = random.choice(self.candidates) pattern = self.game.eval_guess(guess) if pattern == '+-+-!': return guess else: self.candidates = filter(self.candidates, guess, pattern)
Prvním protivníkem byl RandomSolver. Zvládá to překvapivě dobře na to, že tipuje vždy trochu hloupě – úplně náhodné slovo. Často tajenku uhodne třeba na šestý pokus. Je to díky tomu, že se s každým tipem se obvykle dozví něco nového o tajence a pak prostě zůstane jediný kandidát.
Tohle je kus kódu, kde jsem Copilota nezapojil. A využívá ještě argument verbose, který nám krásně zobrazí průběh hry (vytvořený samozřejmě ve spolupráci s Copilotem). Následuje jednoduché vyhodnocení – kolik procent tajenek uhodnu tímto naivním postupem dříve, než prohraju hru? Prohrát znamená, že neuhodnu tajenku na 6 pokusů. Výsledek? Vyhraju zhruba polovinu her (tajenek).
$ ipython
import wordle
import solver
solver.RandomSolver(wordle.Game(word_index=1)).solve(verbose=True)
argil -> !---- -> 35
leres -> -+--+ -> 3
linns -> ----+ -> 3
tardy -> -+--- -> 3
mauls -> -+--+ -> 1
Out[22]: (5, 'abase')
%timeit solver.RandomSolver(wordle.Game(word_index=1)).solve(max_rounds=6)
23.9 ms ± 1.93 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)
run = [
solver.RandomSolver(wordle.Game(word_index=i)).solve(max_rounds=6)
for i in range(len(wordle.words.challenges))
]
sum(1 for rounds, _ in run if rounds < 6) / len(wordle.words.challenges)
0.53
A umíš vyhrát všechny hry, ne jen polovinu?
def entropy_list(strings: list[str]) -> float: """Calculate the entropy of a list of strings. First count the strings using Counter. Then convert the counts to probabilities. Then calculate the entropy. """ counter = Counter(strings) counts = [count / len(strings) for count in counter.values()] return -sum(p * math.log(p, 2) for p in counts) def entropies(guesses: list[str], targets: list[str]) -> list[tuple[float, str]]: """For each guess in guesses generate patterns by calling wordle.eval_guess with each of targets.
Then calculate the entropy of the resulting list of patterns.
Return a list of tuples (entropy, guess).
"""
return [
(entropy_list([wordle.eval_guess(guess, target) for target in targets]), guess)
for guess in guesses
]
class EntropySolver:
"""Try to solve wordle game by maximizing entropy.
"""
def __init__(self, game: wordle.Game):
"""Initialze candidates from challenges wordlist."""
self.candidates = wordle.words.challenges
self.game = game
def solve(self, max_rounds=None, verbose=False) -> tuple[int, Optional[str]]:
"""Solve the game by maximizing entropy. Take guesses from `wordle.words.all`.
If there is only one candidate left, we're done.
If max_rounds is set, limit the number of rounds.
return (rounds, guess)
"""
rounds = 0
while True:
guesses = wordle.words.all
best_guess = max(entropies(guesses, self.candidates), key=lambda x: x[0])
pattern = self.game.eval_guess(best_guess[1])
self.candidates = filter(self.candidates, best_guess[1], pattern)
if verbose:
print(f'{best_guess[1]} -> {pattern} -> {len(self.candidates)}')
rounds += 1
if len(self.candidates) == 1:
return rounds, self.candidates[0]
if max_rounds is not None and rounds >= max_rounds:
return rounds, None
A to je všechno?
Ještě jsem to trochu vylepšil. Na začátku o tajence nevím nic, to znamená, že začínám vždy ze stejné pozice: proti tipu musím vyhodnotit 2 315 kandidátů na tajenku. A to trvá několik minut. Tak jsem první kolo předpočítal. A modří už vědí, že entropický algoritmus jako nejlepší první tip ve hře Wordle vybere slovo soare. Z něj získáme největší množství různorodých nápověd, čímž v průměru nejvíce sníží množství potenciálních tajenek. V překladu je soare mladý jestřáb, pro rodilého mluvčího asi stejně divné slovo jako pro Čecha lapard čili dravec v šatu mladých v druhém roce života (před přepelicháním do dospělého šatu).
Vezme Copilot práci programátorům?
V čem je tedy Copilot dobrý pomocník?
Největší přínos Copilota bych viděl při práci v už existující codebase, protože jak je vidět na příkladu EntropySolveru, Copilot je velmi silný ve využívání existujících vzorů, které vidí „hned vedle“. Jinými slovy dodržování štábní kultury je pro něj hračka.
A na výsledný kód se můžete podívat v GitHubu.
