Autorem wpisu jest  Michał Hałoń – doktorant na Wydziale Elektroniki i Technik Informacyjnych Politechniki Warszawskiej. W drugiej części wpisu ocenia skuteczność opisywanej metody na podstawie wszystkich możliwych rozgrywek i dokonuje próby udoskonalenia algorytmu w celu zwiększenia jego dokładności.

W pierwszym wpisie dotyczącym polskiej wersji gry Wordle wykorzystałem strategię opisaną na blogu Loren on the Art of MATLAB, dzięki której udało się wyszukać pięcioliterowe słowo mogące służyć za dobre rozpoczęcie każdej rozgrywki polskiego odpowiednika - wyraz OKRAI zawiera trzy najczęściej występujące samogłoski (‘AOI’) oraz dwie najczęściej występujące spółgłoski (‘KR’). Ponadto, wykorzystałem gotowe funkcje do próby odgadnięcia docelowego hasła na podstawie wyników dotychczasowych prób. Poszukiwane słowo udało się odnaleźć za czwartym razem co pokazało, że zaproponowana taktyka sprawdza się także w przypadku polskiej wersji gry Wordle.

W drugiej części ocenię skuteczność opisywanej metody na podstawie wszystkich możliwych rozgrywek, a także dokonam próby udoskonalenia algorytmu w celu zwiększenia jego dokładności – zaprezentuję wprowadzenie drobnej modyfikacji, która zwiększa skuteczność z 78.8% aż do 86.2%.

W pierwszej kolejności wykonane zostaną kroki opisane w pierwszym wpisie, polegające na wczytaniu listy zawierającej ponad 28 tysięcy pięcioliterowych wyrazów w języku polskim i obliczeniu dla każdego słowa jego wartościowości (będącej sumą częstości występowania w słowniku liter zawartych w wyrazie - kolumna score) oraz liczby unikalnych liter.

% load the list of unique five letter words
% file 'slowa.txt' to be downloaded from https://sjp.pl/sl/growy/ website
word5 = load_words('slowa.txt');
% find the top scores, their corresponding words and unique letters in each word
word_scores = calculate_scores(word5);

Posiadając te dane możemy przystąpić do rozegrania przykładowej gry z losowo wybranym słowem do odgadnięcia.

% choose random index of word to guess
answer_idx = randi(numel(word5));
% play game with original strategy
[answer,win,played_words] = play_wordle(word_scores,word5(answer_idx),'original')

W wyniku uruchomienia symulowanej rozgrywki (funkcja play_wordle) na wyjściu otrzymujemy następujące zmienne:

• answer – zgadywane słowo,
• win – binarna informacja o pozytywnym (1) bądź negatywnym (0) ukończeniu rozgrywki przez wykorzystaną strategię,
• played_words – lista słów stanowiących kolejne próby odgadnięcia poszukiwanego słowa.

W tym miejscu warto pokrótce przybliżyć szczegóły działania wspomnianej funkcji play_wordle dla oryginalnej strategii:

• w pierwszym podejściu wykorzystywane jest zawsze to samo słowo posiadające największą wartościowość, to znaczy zawierające wszystkie unikalne oraz najczęściej występujące w słowniku litery (w polskiej wersji gry Wordle jest to wspomniane słowo ‘OKRAI’),
• na podstawie symulowanego rezultatu wpisania pierwszego słowa w grze (szare, żółte oraz zielone podświetlenie literek) z listy zawierającej wszystkie słowa usuwane są te niespełniające kryteriów otrzymanego wyniku (co ważne dla dalszej części wpisu, wartościowość pozostawionych wyrazów nie jest aktualizowana i przy każdym podejściu pozostaje identyczna, według początkowych obliczeń na podstawie całego dostępnego słownika) – proces filtracji słów jest powtarzany po każdym podejściu,
• w drugim oraz trzecim podejściu wybierane jest słowo z największą wartościowością wśród przefiltrowanych wyrazów o wszystkich unikatowych literach, jeśli nie jest to możliwe – kryterium unikatowości liter nie jest brane pod uwagę,
• w czwartym i kolejnych podejściach wybierane jest słowo z największą wartościowością bez żadnych dodatkowych kryteriów.

Przykładowy zestaw słów umieszczonych wewnątrz zmiennej played_words, prowadzących do odgadnięcia słowa ‘ZATOK’ w piątej próbie przedstawiono poniżej.

TESTY WYKORZYSTANEJ STRATEGII NA WSZYSTKICH WYRAZACH

Znając szczegóły dotyczące symulowanej rozgrywki z wykorzystaniem przygotowanej wcześniej listy słów z dodatkowymi informacjami, możemy przystąpić do przetestowania skuteczności prezentowanej metody na podstawie wszystkich możliwych rozgrywek, których będzie ponad 28 tysięcy (każdy wyraz jednokrotnie stanowić będzie poszukiwane hasło). W tym celu funkcja play_wordle zostanie umieszczona w pętli for, a jej wyniki zapisane do odpowiednich list.

num_games = numel(word5);
wins = nan(num_games,1);
guesses = strings(num_games,6);
answers = strings(num_games,1);
for ii = 1:num_games % for each word in our vocabulary
    % play a game of Literalnie where that word is the answer we're guessing
    [answers(ii),wins(ii),guesses(ii,:)] = play_wordle(word_scores,word5(ii),'original');
end

Uzyskane dane możemy następnie odpowiednio wyświetlić oraz zwizualizować.

fprintf("Wybrana strategia skutkuje odgadnięciem poszukiwanego słowa w ~%0.1f%% przypadków.\n",sum(wins)/numel(wins)*100)
 
% calculate successful guesses
num_guesses = sum(guesses(wins==1,:)~="",2);
fprintf("Wybrana strategia pozwala odgadnąć słowo średnio po ~%0.1f wpisanych słów.\n",mean(num_guesses))
 
% plot histogram of successful games
h = histogram(num_guesses,"Normalization","count");
% save values for results comparison
hValues = h.Values;
title("Rozkład liczby wygranych według liczby podejść")
xlabel("Liczba podejść przy zwycięskich rozgrywkach")
ylabel("Liczba wygranych")
grid on

Uruchamiając powyższy skrypt uzyskaliśmy informację, że wybrana strategia skutkuje odgadnięciem poszukiwanego słowa w około 78.8% przypadków, co jest wynikiem zdecydowanie niższym od analogicznych analiz dla oryginalnej gry Wordle (91.7%). Najprawdopodobniej jest to spowodowane dużą różnicą w liczności wykorzystywanych słowników dla obu języków (28 535 pięcioliterowych słów dla języka polskiego oraz 4 581 dla angielskiego), co prowadzi do wyboru spośród większych zbiorów wyrazów przy kolejnych podejściach w trakcie rozgrywki. Dowiedzieliśmy się także, że analizowana strategia pozwala odgadnąć poszukiwane słowo średnio po 4.8 wpisanych słów.

Zgodnie z oczekiwaniami, odgadnięcie hasła za pierwszym razem udało się jeden raz – dla słowa ‘OKRAI’. Algorytm najczęściej kończył grę za piątym podejściem (prawie 8 000 przypadków), natomiast za czwartym oraz szóstym podejściem udało się zakończyć w przypadku nieco ponad 6 000 rozgrywek. Na koniec analiz tej wersji algorytmu, sprawdźmy jak wyglądał przykładowy przebieg przegranej rozgrywki w przypadku, gdy hasłem do odnalezienia było słowo ‘AGEND”:

missed_answers = answers(wins==0);
[answer,win,played_words] = play_wordle(word_scores,missed_answers(3), 'original')

Można zauważyć, że do odgadnięcia hasła zabrakło naprawdę niewiele – podane ze szóstym razem słowo różniło się z docelowym jedynie jedną, ostatnią literą. Takich przypadków dla nieudanych rozgrywek jest znacznie więcej.

WPROWADZENIE MODYFIKACJI DO ORYGINALNEJ STRATEGII

Podsumowując dotychczasowe analizy, skuteczność algorytmu wynosząca 78.8% jest wynikiem, który warto spróbować poprawić. Można tego dokonać na wiele sposobów. W tym wpisie zaimplementuję modyfikację będącą wynikiem wspomnianego wyżej spostrzeżenia, że w trakcie rozgrywki wartościowość (kolumna score w wykorzystywanych tabelach) wyrazów nie jest aktualizowana i przy każdym podejściu pozostaje identyczna. Dlaczego fakt ten może mieć znaczenie w procesie poprawy dokładności algorytmu?

Otóż po każdym procesie filtracji słów w danym podejściu (odrzucenie tych, które nie wpasowują się w wyniki poprzednich prób), częstość występowania poszczególnych liter w zaktualizowanej liście zmienia się, przez co zmienia się także wartościowość wyrazów pod kątem wykorzystania w kolejnym podejściu. Zilustrujmy powyższe stwierdzenie na przykładzie wpisania słowa ‘OKRAI’ w dniu, kiedy hasłem był wyraz ‘BUTLA’.

Poniżej przedstawiono rozkłady częstości występowania liter, na podstawie których liczona jest wartościowość wyrazów – każdej literze przypisywana jest wartość (równa częstości wystąpień), następnie dla każdego słowa sumowane są wartości liter, z których się składa. Po lewej zaprezentowano rozkład dla oryginalnej strategii, dla której wartościowość słów jest zawsze taka sama, po prawej dla proponowanej modyfikacji, która wylicza tę charakterystykę na podstawie przefiltrowanej listy słów po wpisaniu wyrazu ‘OKRAI’.

Zaprezentowane rozkłady różnią się między sobą, dlatego listy wyrazów proponowanych do drugiego podejścia dla obu wersji strategii także nie są identyczne.

W proponowanej modyfikacji, po przefiltrowaniu listy wyrazów na podstawie wyników poprzedniego podejścia, dokonywana jest aktualizacja wartościowości tych słów. Opisywana zmiana może prowadzić do znajdowania trafniejszych wyrazów, a w konsekwencji do częściej oraz wcześniej odgadywanych haseł - zweryfikujemy tę tezę w dalszych testach. Kontynuując próby odgadnięcia hasła według opisywanych podejść, dojdziemy do wyników zaprezentowanych poniżej.

Można zauważyć, że w obu przypadkach rozgrywka zakończyła się sukcesem w piątym podejściu, jednak zgodnie z oczekiwaniami, wyrazy prowadzące do uzyskania hasła były różne dla prezentowanych metod. A jak będzie w przypadku pozostałych 28 534 wyrazów? Czy proponowana modyfikacja faktycznie zwiększy skuteczność odgadnięć? Sprawdźmy – w prezentowanym wcześniej kodzie wystarczy zamienić parametr 'original' na 'modified'.

TESTY ZMODYFIKOWANEJ STRATEGII

Uwaga: poniższy kod, z uwagi na wprowadzoną modyfikację, wykonuje się znacznie dłużej w porównaniu do poprzedniej wersji. Wyniki jego działania zostały zapisane i udostępnione w pliku all_games_results_modified.mat, który przy wizualizacji wystarczy wcześniej załadować.

% CALCULATE ALL GAMES RESULTS
num_games = numel(word5);
wins = nan(num_games,1);
guesses = strings(num_games,6);
answers = strings(num_games,1);
for ii = 1:num_games % for each word in our vocabulary
    % play a game of Literalnie where that word is the answer we're guessing
    [answers(ii),wins(ii),guesses(ii,:)] = play_wordle(word_scores,word5(ii),'modified');
    if rem(ii,100) == 0
        disp(ii)
    end
end

save('all_games_results_modified.mat','answers','wins','guesses', 'word_scores');
% RESULTS VISUALIZATION
load('all_games_results_modified.mat')

fprintf("Wybrana strategia skutkuje odgadnięciem poszukiwanego słowa w ~%0.1f%% przypadków.\n",sum(wins)/numel(wins)*100)
num_guesses_modified = sum(guesses(wins==1,:)~="",2);

fprintf("Wybrana strategia pozwala odgadnąć słowo średnio po ~%0.1f wpisanych słów.\n",mean(num_guesses_modified))

h = histogram(num_guesses_modified,"Normalization","count");
% save values for results comparison
hValuesModified = h.Values;
xlabel("Liczba podejść przy zwycięskich rozgrywkach")
ylabel("Liczba wygranych")

Uruchamiając powyższy kod otrzymujemy informację, że „wybrana strategia skutkuje odgadnięciem poszukiwanego słowa w około 86.2% przypadków”. Zanotowaliśmy więc poprawę względem oryginalnej strategii o ponad 7 punktów procentowych – jest to dobry wynik. Porównajmy rozkłady liczby wygranych według liczby podejść dla obu analizowanych wersji strategii.

x = 1:6;
% bar plot with title, legend, grid and labels
bar(x,[hValues;hValuesModified])
legend('Oryginalna','Zmodyfikowana', "Location","northwest")
title("Rozkład liczby wygranych według liczby podejść")
xlabel("Liczba podejść przy zwycięskich rozgrywkach")
ylabel("Liczba wygranych")
grid on

Można zauważyć, że nie tylko liczba zwycięstw jest większa w przypadku zmodyfikowanej wersji, lecz także jej rozkład przesunął się w lewą stronę – więcej zwycięstw względem oryginalnej strategii zostało odnotowanych dla 3,4 oraz 5 podejść, natomiast mniej dla 6 podejść.

Na podstawie informacji uzyskanych na temat wyników działania wprowadzonej modyfikacji możemy podsumować, że każdorazowa aktualizacja wartościowości dla listy przefiltrowanych wyrazów prowadzi do wyboru słów bardziej dostosowanych do aktualnej rozgrywki, dzięki czemu wzrasta prawdopodobieństwo odniesienia sukcesu oraz wcześniejszego zakończenia gry. Warto dodać, że w przypadku oryginalnej wersji gry Wordle wprowadzenie opisywanej modyfikacji także zwiększa skuteczność - z 91.7% do 93.6% (tabelka poniżej). Zatem próba udoskonalenia algorytmu w celu zwiększenia jego skuteczności zakończyła się powodzeniem.

	Skuteczność wersja oryginalna [%]	Skuteczność wersja zmodyfikowana [%]
literalnie	78.8	86.2
Wordle	91.7	93.6

Dotychczasowe rozważania zakładały, że w trakcie próby odgadnięcia hasła w literalnie lub Wordle posiadamy dostęp do programu MATLAB, który wskazuje nam kolejne propozycje słów do wpisania. Jednak nie zawsze jest to możliwe. Czy istnieje zatem taktyka, która ułatwi nam pomyślne zakończenie gry bez korzystania z MATLABa na bieżąco? Na szczęście tak – opowiem o niej w kolejnym wpisie.

Poniżej znajduje się kod całego programu:

% Based on the code from the blog post:
% https://blogs.mathworks.com/loren/2022/01/18/building-a-wordle-solver/
 
%% LOAD DATA
 
% load the list of unique five letter words
% file 'slowa.txt' to be downloaded from https://sjp.pl/sl/growy/ website
word5 = load_words('slowa.txt');
% display number of words in arrays
fprintf("Lista zwiera %i słów pięcioliterowych.\n",height(word5))
%% CALCULATE SCORES
 
% find the top scores, their corresponding words and unique letters in each
% word
word_scores = calculate_scores(word5);
%% PLAY RANDOM GAME
 
% choose random index of word to guess
answer_idx = randi(numel(word5));
% play game with original strategy
[answer,win,played_words] = play_wordle(word_scores,word5(answer_idx),'original')
%% PLAY ALL POSSIBLE GAMES
 
num_games = numel(word5);
wins = nan(num_games,1);
guesses = strings(num_games,6);
answers = strings(num_games,1);
for ii = 1:num_games % for each word in our vocabulary
    % play a game of Literalnie where that word is the answer we're guessing
    [answers(ii),wins(ii),guesses(ii,:)] = play_wordle(word_scores,word5(ii),'original');
end
%% CHECK ALL POSSIBLE GAMES RESULTS
 
fprintf("Wybrana strategia skutkuje odgadnięciem poszukiwanego słowa w ~%0.1f%% przypad-ków.\n",sum(wins)/numel(wins)*100)
 
% calculate successful guesses
num_guesses = sum(guesses(wins==1,:)~="",2);
fprintf("Wybrana strategia pozwala odgadnąć słowo średnio po ~%0.1f wpisanych słów.\n",mean(num_guesses))
 
h = histogram(num_guesses,"Normalization","count");
% save values for results comparison
hValues = h.Values;
title("Rozkład liczby wygranych według liczby podejść")
xlabel("Liczba podejść przy zwycięskich rozgrywkach")
ylabel("Liczba wygranych")
grid on
%% EXAMPLE OF MISSED ANSWER
 
missed_answers = answers(wins==0);
[answer,win,played_words] = play_wordle(word_scores,missed_answers(3), 'original')
%% PLAY ALL POSSIBLE GAMES ON MODIFIED VERSION
 
num_games = numel(word5);
wins = nan(num_games,1);
guesses = strings(num_games,6);
answers = strings(num_games,1);
for ii = 1:num_games % for each word in our vocabulary
    % play a game of Literalnie where that word is the answer we're guessing
    [answers(ii),wins(ii),guesses(ii,:)] = play_wordle(word_scores,word5(ii),'modified');
end
 
save('all_games_results_modified.mat','answers','wins','guesses', 'word_scores');
%% CHECK ALL POSSIBLE GAMES RESULTS ON MODIFIED VERSION
 
load('all_games_results_modified.mat')
 
fprintf("Wybrana strategia skutkuje odgadnięciem poszukiwanego słowa w ~%0.1f%% przypad-ków.\n",sum(wins)/numel(wins)*100)
num_guesses_modified = sum(guesses(wins==1,:)~="",2);
 
fprintf("Wybrana strategia pozwala odgadnąć słowo średnio po ~%0.1f wpisanych słów.\n",mean(num_guesses_modified))
 
h = histogram(num_guesses_modified,"Normalization","count");
% save values for results comparison
hValuesModified = h.Values;
title("Rozkład liczby wygranych według liczby podejść")
xlabel("Liczba podejść przy zwycięskich rozgrywkach")
ylabel("Liczba wygranych")
%% EXAMPLE OF MISSED ANSWER
 
missed_answers = answers(wins==0);
[answer,win,played_words] = play_wordle(word_scores,missed_answers(1),'modified')
%% RESULTS COMPARISON FOR BOTH METHODS
 
% bar plot with title, legend, grid and labels
x = 1:6;
bar(x,[hValues;hValuesModified])
legend('Oryginalna','Zmodyfikowana', "Location","northwest")
title("Rozkład liczby wygranych według liczby podejść")
xlabel("Liczba podejść przy zwycięskich rozgrywkach")
ylabel("Liczba wygranych")
grid on
%% FUNCTIONS
 
function [word_to_guess,win,guesses] = play_wordle(word_scores, word_to_guess, strategy_type)
top_words = sortrows(word_scores,2,"descend"); % ensure scores are sorted
guesses = strings(1,6);
results = nan(6,5);
max_guesses = 6;
for ii = 1:max_guesses % for each of our guesses
    % filter our total vocabulary to candidate guesses using progressively different strategies
    if ii == 1 % for our first guess, filter down to words with five unique letters and take top score
        top_words_filtered = top_words(top_words.num_letters==5,:);
    elseif ii <= 3 % if we're generating our second or third guess
        % filter out ineligible words and require five unique letters if possible
        min_uniq = 5;
        top_words_filtered = filter_words(top_words(top_words.num_letters==min_uniq,:),guesses(1:ii-1),results(1:ii-1,:),strategy_type);
        % if filtering to five unique letters removes all words, allow more repeated letters
        while height(top_words_filtered) == 0 && min_uniq > min(word_scores.num_letters)
            min_uniq = min_uniq - 1;
            top_words_filtered = filter_words(top_words(top_words.num_letters==min_uniq,:),guesses(1:ii-1),results(1:ii-1,:),strategy_type);
        end
    else % after third guess, set no restrictions on repeated letters
        top_words_filtered = filter_words(top_words,guesses(1:ii-1),results(1:ii-1,:),strategy_type);
    end
    % generate our guess (if we have any)
    if height(top_words_filtered) == 0 % if there are no eligible words in our vocabulary
        win = 0; % we don't know the word and we've lost
        return % make no more guesses
    else % otherwise generate a new guess and get the results
        guesses(1,ii) = top_words_filtered.words(1);
        results(ii,:) = wordle_feedback(word_to_guess,guesses(1,ii));
    end
    % evaluate if we've won, lost, or should keep playing
    if guesses(1,ii) == word_to_guess % if our guess is correct
        win = 1; % set the win flag
        return % make no more guesses
    elseif ii == max_guesses % if we've already used all our guesses and they're all wrong
        win = 0; % we've lost and the loop will end
    else % otherwise we're still playing
    end
end
end % play_wordle
 
function results = wordle_feedback(answer, guess)
results = nan(1,5);
for ii = 1:5 % for each letter in our guess
    letter = extract(guess,ii); % extract that letter
    if extract(answer,ii) == letter
        % if answer has the letter in the same position
        results(ii) = 2;
    elseif contains(answer,letter)
        % if answer has that letter in another position
        results(ii) = 1;
    else
        % if answer does not contain that letter
        results(ii) = 0;
    end
end
end % wordle_feedback
 
function word_scores_filtered = filter_words(word_scores,words_guessed,results, strategy_type)
% remove words_guessed since those can't be the answer
word_scores_filtered = word_scores;
word_scores_filtered(matches(word_scores_filtered.words,words_guessed),:) = [];
% filter to words that have correct letters in correct positions (green letters)
[rlp,clp] = find(results==2);
if ~isempty(rlp)
    for ii = 1:numel(rlp)
        letter = extract(words_guessed(rlp(ii)),clp(ii));
        % keep only words that have the correct letters in the correct locations
        word_scores_filtered = word_scores_filtered(extract(word_scores_filtered.words,clp(ii))==letter,:);
    end
end
% filter to words that also contain correct letters in other positions (yellow letters)
[rl,cl] = find(results==1);
if ~isempty(rl)
    for jj = 1:numel(rl)
        letter = extract(words_guessed(rl(jj)),cl(jj));
        % remove words with letter in same location
        word_scores_filtered(extract(word_scores_filtered.words,cl(jj))==letter,:) = [];
        % remove words that don't contain letter
        word_scores_filtered(~contains(word_scores_filtered.words,letter),:) = [];
    end
end
% filter to words that also contain no incorrect letters (grey letters)
[ri,ci] = find(results==0);
if ~isempty(ri)
    for kk = 1:numel(ri)
        letter = extract(words_guessed(ri(kk)),ci(kk));
        % remove words that contain incorrect letter
        word_scores_filtered(contains(word_scores_filtered.words,letter),:) = [];
    end
end
 
if strcmp(strategy_type, 'modified')
    % split our words into their individual letters
    letters = split(table2array(word_scores_filtered(:,1)),"",2);
    % this also creates leading and trailing blank strings, drop them
    letters = letters(:,2:end-1);
 
    [Values, Categories] = histcounts(categorical(letters(:)));
    lt = table(Categories',Values','VariableNames',["letters","score"]);
    
    % for each letter, replace it with its corresponding letter score
    letters_score = arrayfun(@(x) lt.score(lt.letters==x),letters);
    % sum the letter scores to create word scores
    word_score = sum(letters_score,2);
    % find the top scores and their corresponding words
    [top_scores,top_idx] = sort(word_score,1,"descend");
    % update and sort filtered list of words
    word_scores_filtered = table(word_scores_filtered.words(top_idx), top_scores, word_scores_filtered.num_letters(top_idx),'VariableNames',["words","score","num_letters"]);
    word_scores_filtered = sortrows(word_scores_filtered,'num_letters','descend');
end
end % filter_words
 
function word5 = load_words(txt_filename)
% read the list of words into a string array
r = readlines(txt_filename);
% Wordle uses all upper case letters
r = upper(r);
% get the list of unique five letter words
word5 = unique(r(strlength(r)==5));
end %load_words
 
function word_scores = calculate_scores(word5)
% split our words into their individual letters
letters = split(word5,"");
% this also creates leading and trailing blank strings, drop them
letters = letters(:,2:end-1);
% calculate the counts of letters
[Values, Categories] = histcounts(categorical(letters(:)));
% create table with letters and their scores
lt = table(Categories',Values','VariableNames',["letters","score"]);
 
% for each letter, replace it with its corresponding letter score
letters_score = arrayfun(@(x) lt.score(lt.letters==x),letters);
% sum the letter scores to create word scores
word_score = sum(letters_score,2);
% find the top scores and their corresponding words
[top_scores,top_idx] = sort(word_score,1,"descend");
word_scores = table(word5(top_idx),top_scores,'VariableNames',["words","score"]);
 
% find how many unique letters are in each word
word_scores.num_letters = arrayfun(@(x) numel(unique(char(x))),word_scores.words);
end