The goal of the wordle game is to ask questions to identify a secret word chosen by an adversary out of a large (but known) set of words. Per experiment we get feedback about how `near’ our question, i.e., our selected word, is to the secret. Now I am not particularly interested in playing this game, but I do find it interesting to see how to let the computer find the secret word in an efficient way. There were some sites on the internet that (kind of) `explained’ how to do this; these sites mention entropy and say that word frequencies can be taken into account to improve the guessing strategy. That in itself was not new to me, but I hoped to learn how these concepts connect in detail, as I find entropy an intriguing concept. However, I found these sites very unclear, so, I decided to work on it myself, and start from scratch.

I first discuss my approach to coming to understand the ideas, then I present the mathematical framework that summarizes these ideas. This framework helps to show the commonality of many problems and clarifies several other relating issues such as the selection of a good pivot for quicksort, why certain other types of games are harder than others, and how to develop efficient heuristics to deal with these hard games.

The book `Probability And Information’ by Yaglom and Yaglom provides a nice discussion on information theory and entropy. For this, they consider a game in which one has to identify a deficit (heavier) coin among \(n\) coins with an expected minimum of weightings with a balance with two pans. For nine coins the optimal strategy is easy: put two sets of three coins on either pan of the balance. If the balance remains level, the deficit coin is in the third set. If it tilts to the right, the heavier coin is in the right set, otherwise in the left. Thus, using the information gained by a weighting, i.e., an experiment, we can reduce the nine-coin problem to a three-coin problem. In other words, we can apply recursion to find the heavier coin. With \(n\) coins, the idea works roughly the same. In general terms, with every weighting we can reduce the size of the set containing the deficit coin by a factor three. Hence, the minimum of weightings for \(n\) coins must be about \(\log_3 n\).

A similar problem is to identify a secret word in a set of \(n\) words chosen by an `adversary’ who only responds with `yes’ or `no’ to any question posed. For instance, we can ask a question whether some word is larger than the secret. Realize that we now use the question to split the space of words into two sets, and ask whether the secret is an element of one of the two sets. This explains why this algorithm is called `binary search’. Since we get two possible answers, we need about \(\log_{2} n\) experiments to find the secret word.

In the coin and number-finding problems it is clear (after reading the book of the Yaglom brothers) how entropy helps to find the strategy that is best in the sence of minimizing the number of experiments. In fact in both games we use a question that makes the subsets that are compatible with the feedback as equal in size as possible, because this maximizes the entropy when all coins have an equal probability of being the deficit coin.

Below I make a general framework to analyze these two games, and with this framework we can also deal efficiently with the wordle game. I first built a computer program for the coin problem and binary search and thought about common concepts. Then I tried to make a mathematical formulation of it. Based on that, I refined my programs. After this, I went for a walk, and tried to explain in yet more general terms the essential ingredients. I also tried to tackle more general problems like how to find a coin that can be heavier or lighter among \(n\) coins, or two heavier coins out of \(n\), or \(m\) out of \(n\). These generalizations revealed to me that, actually, all these weighing games can be solved generically, in an efficient, but not optimal, way: just sort the coins from light to heavy with a balance. The most general of these problems is to sort \(n\) coins, and we already know from this page that this takes \(n \log_{2} n\) weightings.

A bit of further research on the web showed that finding the optimal policy for the \(2\) out of \(n\) coin problem is very hard.¹¹Richard Bellman even wrote a paper on this So I dropped this task from my list, but it raised two interesting problems. How to explain, in terms of my general framework, where exactly lies the additional complexity for \(m\) out of \(n\) coin game (with \(m>1\))? And second, what would be good heuristics to efficiently solve this, and similar, problems. As it turns out, this second problem relates directly to the selection of a good pivot in the quicksort algorithm; we will address it below.

Before trying to develop a general mathematical formulation, it is helpful to consider two concrete examples and develop useful terminology at the same time.

In the wordle game, a player tries to find a secret word in a given list of words, and for this, the player can consult an oracle in two different ways. First, the player can ask feedback in terms of "If the word `raise’ is the secret, i.e., my guess for the secret, and I would ask the question whether the word `abate’ is the secret, what feedback would you give me?’. Clearly, asking such feedback is free: the oracle does not have to reveal any information about the secret word because the oracle just uses the player’s guess of the secret. Second, the player can perform an actual experiment, in which the player asks to give feedback about a specific word, and the oracle uses the secret to give the feedback. A player can get unlimited feedback about the quality of a word for a guess (of the secret) provided by the player, but an experiment counts as a try. In the wordle game, the player has 6 tries to identify the secret.

As a second example, consider 4 coins of which one is heavier, with probabilities \(\alpha, \beta, \gamma, \delta\) that the first, second, \ldots, coin is the deficit one. We use a balance to compare the weight of groups of coins. Suppose we would put coins \(1, 2\) on the left pan, and \(3, 4\) on the right pan. The probability that the left pan tilts downwards is \(\alpha + \beta\), because this is the probability that the heavier coin lies in the set \(\{1, 2\}\), and the probability that the right pan tips downward is \(\gamma + \delta\). It cannot happen that the balance stays level. In more detail, our question is the grouping of the coins into sets \(\{1, 2\}\) and \(\{3, 4\}\). Then, if we guess that coin 1 is heavier, the feedback given by the oracle, i.e., the balance, will be that the left pan tips downwards. If coin 2 is heavier, we get the same feedback, while if coins 3 (or 4) is the heavier, the right pan tips. So, given the question, the probability to get as feedback that the left pan tips, is the probability that the heavier coin lies in the set \(\{1, 2\}\). The other probabilities can be computed likewise.

Now we are ready to make a formalized description of such stochastic optimization problems (here games). There is a state space \(S\) from which an oracle selects a secret word \(s\in S\). In wordle, \(S\) is the set of words; for the coins, \(S\) is the set of coins. A player can ask a question \(q\in Q\) for a set of possible questions \(Q\). For wordle, the set of questions is the same as the set of words; for finding a deficit coin, a question is the placement of sets of coins on the left and right pan of the balance, hence, the question set is the set of all possible groupings of coins in three piles, one is placed at the left pan, the other at the right, and the rest is not used in the weighting. The player can ask the oracle to provide feedback in the form of function \(f_{q}(g)\) for question \(q\) and guess \(g\) for the secret. In wordle, the feedback consists of a set of colors for letters; in the coin game, the feedback is \(l, eq\), or \(r\), i.e., the left pan tips, the balance stays equal, or the right pan tips. Finally, the player can perform an experiment (which counts as a try) by asking the oracle a question \(q\) and receiving feedback \(f_{q}(s)\). So, in an experiment, the oracle substitutes the secret \(s\) in the feedback function \(f_{q}\) to give the feedback \(f_{q}(s)\), but does not reveal the secret.

The player can progress like this. For question \(q\), define the set of possible feedbacks compatible with \(q\) as

Then, for each feedback \(f\in F_{q}\), the player collects the states with the same feedback \(f\) into subsets of \(S\):

Clearly, \(\cup_{f\in F_q} W_q(f) = S\), and \(W_q(f) \cap W_{q}(f')=\varnothing\) if \(f\neq f'\). Hence the question \(q\) induces by means of the set of feedbacks \(F_q\) a unique partition of \(S\):

The player’s problem is to identify the question in \(Q\) that minimizes the expected number of experiments, and for this, the player can use the entropy function. Suppose we are given the probability \(p_g\) that element \(g\in S\) is the secret. Then \(P(A) = \sum_{g\in A} p_g\) is the probability that \(s \in A \subset S\). For instance, when \(p_{g}\) is uniform over \(S\), \(\P{A} = |A|/|S|\), i.e., counting measure. Once the probability function (the measure) \(\P{\cdot}\) is known, we can define the entropy of a partition \(\mathcal P\) of \(S\) as

Clearly, by \eqref{org0043671}, a question \(q\) induces the partition \(\mathcal{P}_{q}\), hence, we define the entropy induced by \(q\) as

The best question \(q^{*}\) is the solution of the maximization problem²²Why this is best is explained very well at many places. Besides the book by Yaglom and Yaglom, I recommend Information Theory, Inference, and Learning Algorithms by MacKay.

To complete the procedure, if the player has \(q^*\) and the associated optimal partition \(W^*_{q^*}\) , s/he does an experiment by asking the oracle for

where \(s\) is the oracle’s secret. With this answer, the player starts a new round of the game, but now with the strictly smaller state space

Since this set is a strict subset of \(S\), the player can find the secret \(s\) by means of recursion until the final state space contains just one element, and this must be the secret.

Note that any question \(q\) such that the set of feedbacks \(F_{q}\) contains at least 2 elements is effective in solving the problem, because this question will result in a non-trivial partitioning of the space \(S\). In other words, even when simple questions are not optimal, they do help to work towards identifying the secret.

It’s time now to convert the maths into code. Let me repeat: I did not find the maths or the code in one pass. I first used a bit of math, then built it to see where the ideas would break. This lead to a new cycle of thinking, maths, and coding.

Let us try what we developed up to now to two simple problems whose solutions we can check by hand.

Above we have tackled two simple games. Now it’s time to see how to deal with Wordle. This game is about identifying a secret word, for instance ’aahed’ in a set \(S\) of five letter words. The player formulates a question in the form of a word, for instance ’adopt’. The feedback consists of a string of five colors, for each letter position one color. Green at some position means that the letter of the question is correct at that position; Yellow means that the letter of the question is also in the secret, but not at that position; Gray means that the letter at the position of the question is not in the secret. Thus, the feedback for the question ’adopt’ would be Green, Yellow, Gray, Gray, Gray. Interestingly, feedback is not symmetric, as can be seen when `adopt’ would be the secret and `aahed’ the question.

While the player is simple in essence, we introduce a new idea to demonstrate how to reduce numerical work. To find the secret word in a minimal number of experiments, we have to search \(S\) entirely for the guess that gives the highest entropy. This can be very time consuming when \(S\) is large. To prevent doing lots of useless numerical work (or if we like to have an answer before we die), we can take a sample of n_samples of \(S\) to make the question space \(Q\). Surely this is not optimal, but it still gives exponentially fast convergence (with very large probability).

The feedback of the oracle is somewhat subtle to deal with some easy-to-miss corner cases. I used the implementation from this link.

import random
from collections import Counter

from answers import ColorAnswer as Answer
from oracle_base import Oracle
from player_base import Player

random.seed(3)


def read_words(num=None):
    with open("./valid-wordle-words.txt", "r") as fp:
        words = [w.strip() for w in list(fp)[:num]]
    return words


class Wordle_Player(Player):
    def __init__(self, space, oracle, n_samples=float('inf')):
        self.n_samples = n_samples
        super().__init__(space, oracle)

    def make_question_space(self, space):
        if self.n_samples >= len(space):
            return space
        return random.sample(list(space), self.n_samples)


class Wordle_oracle(Oracle):
    def feedback(self, question, guess):
        pool = Counter(s for g, s in zip(question, guess) if g != s)
        score = []
        for g, s in zip(question, guess):
            if g == s:
                pool[g] -= 1
                score.append(Answer.GREEN)
            elif pool[g] > 0:
                pool[g] -= 1
                score.append(Answer.YELLOW)
            else:
                score.append(Answer.GRAY)
        return tuple(score)


def main():
    space = read_words(num=1000)
    oracle = Wordle_oracle(secret="abase", space=space)
    player = Wordle_Player(oracle=oracle, space=space)
    player.play()


if __name__ == '__main__':
    main()

To keep the output limited, I just read the first 1000 words from this list of valid Wordle words. Here is the output when we don’t use sampling. The actual computation takes a few second because of all the computations.

exec(open("./wordle.py").read())

q_star='arles', answer=(GREEN, GRAY, GRAY, YELLOW, YELLOW), n_tries=1
New state space:
abase abuse amuse anise ansae aside aspie avise

q_star='avise', answer=(GREEN, GRAY, GRAY, GREEN, GREEN), n_tries=2
New state space:
abase abuse amuse

q_star='abase', answer=(GREEN, GREEN, GREEN, GREEN, GREEN), n_tries=3
The secret is abase

Let us now use a sample of 10 words of the space as question words, and read all \(\approx 15K\) words. The search runs real fast, even though we now consider all more than 10 K words. For this change, we modify the main function to this.

def main():
    space = read_words()
    oracle = Wordle_oracle(secret="abase", space=space)
    player = Wordle_Player(oracle=oracle, space=space, n_samples=10)
    player.play()

Let’s run it.

exec(open("./wordle.py").read())

q_star='polts', answer=(GRAY, GRAY, GRAY, GRAY, YELLOW), n_tries=1
New state space:
abase abash abask absey abuse abysm adsum aesir agism agush aksed amuse anise
ansae arise arish arsed arsey asada asana asdic ashed ashen aside askar asked
asker askew assai assam assay assed assez asura asway aswim avise awash bagsy
baisa basan based basen baser basha basic basij basin basse bassi bassy beisa
besaw besee birse birsy brash brise brisk brush brusk bursa burse busby bused
bushy busky bussu byssi caese carse cased caser casky causa cause cease cense
cesse chase chasm chuse cissy crash crise cruse crush crusy cuish curse cursi
cusec cushy cusum daisy danse dashi dashy deash deism dense desex deshi desse
disci dishy disme druse drusy dunsh dusky eased easer ecash eensy ensew ensky
ensue erase escar eskar esker essay farse fasci fease feese fesse fishy fresh
frise frisk frush fubsy funsy fused fusee fussy gashy gassy gawsy geasa geese
gesse girsh gnash grese grise grisy guise gursh gushy gussy guyse hansa hanse
harsh hashy hause hawse herse hissy hushy husky hussy imshi imshy insee isnae
issei issue jasey jesse jessy karsy kasha kasme kesar kiasu kisan kissy knish
maise manse marse marsh mased maser masha mashy massa masse massy masur mausy
mease meism mensa mense mensh merse mersk mesad mesca mesem meshy mesia mesic
mesne messy meuse miasm mimsy minse misch miser misky missa missy msasa mumsy
musar musca mused musee muser musha mushy music musky musse mussy mysid mysie
nashi neese neski newsy nisei nisin nisse nsima nurse nused nyssa nyuse quash
quasi qursh raise raksi ramse ramsh ranse rasam rased raser rasse resam resaw
resay resee resew resid resin resue reuse rinse risen riser rishi risky rushy
rusky rusma russe sabed saber sabha sabin sabir sabji sabra sabre sabzi sacra
sacre saddy sadhe sadhu sadic sadza safed safer sagar sager saggy sagum sahab
saheb sahib saice saick saiga saine sakai saker sakia saman samba samek samen
samey samfi samfu sammy sanad sandy saned saner sanga sangh sansa saran sared
saree sarge sarin sarir sarky saser sasin sasse sassy sauba sauce sauch saucy
saugh sauna saunf saury sauve saved saver savey savin savvy sawah sawed sawer
sayed sayee sayer sayid sayne scaff scand scare scarf scary scaud scaur scena
scend scene schav schif schwa scifi scind scire scrab scrae scrag scram scran
scraw scray scree screw scrim scrub scrum scuba scudi scuff scurf scuse scuzz
sdayn sdein seame seamy seare sease seaze sebum sedan seder sedge sedgy sedum
seedy sefer segar segni segue sehri seine seise seism seiza seize semee semen
semie senex sengi senna sensa sense sensi sensu senvy senza serac serai sered
serer serge seria seric serif serin serir serra serre serry serum serve sesey
sessa sevak seven sever sevir sewan sewar sewed sewen sewer sewin sexed sexer
seyen shack shade shady shaka shake shaky shama shame shand shank shard share
shark sharn shash shave shawm shawn shaya shchi sheaf shear sheen sheer sheik
shend sheng sherd shere sheva shewn shiai shied shier shine shiny shire shirk
shirr shish shiur shiva shive shmek shred shrew shrub shrug shuba shuck shura
shush shyer sibia sicky sided sider sidey sidha sidhe siege sieur sieve sigma
signa sigri siker simar simba since sined sinew singe sinky sinsi sired siree
siren sirih sirra sissy siver sixer sizar sized sizer skank skarn skean skear
skeed skeef skeen skeer skeev skeez skegg skein skene skerm skied skier skiey
skiff skink skirr skive skivy skran skrik skunk skyed skyer skyey skyre smaak
smack smaik smarm smash smaze smear smeek smeik smeke smerk smick smirk smirr
smize smush snack snafu snake snaky snare snarf snark snary snash snead sneak
sneck sneed sneer snick snide snied sniff snive snuck snuff snush squab squad
squaw squee squeg squib squid squiz suave subah subak subby suber subha succi
sucky sucre sudan sudsy suede sugan sugar suhur suing sujee sukuk sumac summa
sunna sunny surah sured surer surfy surge surgy surra sused sushi swack swage
swain swami swamy swang swank sward sware swarf swarm swash swear swede sweed
sweer sweir swerf swine swing swink swire swish swive swizz swung sybbe sycee
syker symar synch syned syrah syren syver ukase unsaw unsay unsee unsew unsex
unsub urase ursae ursid usage usher using usnea usnic usque usure usury versa
verse vised visie visna visne washi washy weise wersh whish whisk wised wiser
wisha wushu wussy yeesh ysame zhush

q_star='raise', answer=(GRAY, YELLOW, GRAY, GREEN, GREEN), n_tries=2
New state space:
abase abuse amuse cease chase fease mease sease ukase

q_star='amuse', answer=(GREEN, GRAY, GRAY, GREEN, GREEN), n_tries=3
The secret is abase

It’s impressive to see how fast this algorithm find the solution.

The above problems are actually quite simple, mainly because the guess space can be taken as equal to the state space. In the next two problems this is no longer the case.

Yet another nice game is Mastermind, the rules of which you can find at Wikipedia.

The number of positions in which the guess and the secret have the same color are the number of black pegs. The number of hits, both black and white, is given by the formula

where \(n_i\) is the number of times color \(i\) occurs in the question, and \(n_i'\) the number of times it occurs in the secret. See this paper of Knuth. The number of white pegs is the number of hits minus the number of black pegs.

I only have to compute once the number of occurrences of the colors in the secret, hence I do this in the __init__.

Note that we minimize the expected number of experiments, we don’t minimize the worst case scenario. As Knuth proves, the guaranteed minimal number of iterations is 5. I think we do better often, but not always.

from collections import Counter
from itertools import product

from oracle_base import Oracle
from player_base import Player


class Mastermind_player(Player):
    def make_question_space(self, space):
        return space


class Mastermind_oracle(Oracle):
    def __init__(self, space, secret):
        super().__init__(space=space, secret=secret)
        self.s_cnt = Counter(c for c in secret)

    def feedback(self, question, guess):
        black = sum(s == g for s, g in zip(guess, question))
        g_cnt = Counter(c for c in question)
        hits = sum(min(self.s_cnt[g], g_cnt[g]) for g in range(6))
        white = hits - black
        return (white, black)


def main():
    space = set(product(range(6), repeat=4))
    oracle = Mastermind_oracle(secret=(1, 2, 3, 4), space=space)
    player = Mastermind_player(oracle=oracle, space=space)
    player.play()


if __name__ == '__main__':
    main()

exec(open("./mastermind.py").read())

q_star=(4, 2, 0, 5), answer=(1, 1), n_tries=1
New state space:
(0, 0, 0, 0) (0, 0, 0, 1) (0, 0, 0, 2) (0, 0, 0, 3) (0, 0, 0, 4) (0, 0, 1, 5)
(0, 0, 2, 5) (0, 0, 3, 5) (0, 0, 4, 5) (0, 0, 5, 5) (0, 1, 0, 0) (0, 1, 0, 1)
(0, 1, 0, 2) (0, 1, 0, 3) (0, 1, 0, 4) (0, 1, 1, 5) (0, 1, 2, 5) (0, 1, 3, 5)
(0, 1, 4, 5) (0, 1, 5, 5) (0, 2, 1, 0) (0, 2, 1, 1) (0, 2, 1, 2) (0, 2, 1, 3)
(0, 2, 1, 4) (0, 2, 2, 0) (0, 2, 2, 1) (0, 2, 2, 2) (0, 2, 2, 3) (0, 2, 2, 4)
(0, 2, 3, 0) (0, 2, 3, 1) (0, 2, 3, 2) (0, 2, 3, 3) (0, 2, 3, 4) (0, 2, 4, 0)
(0, 2, 4, 1) (0, 2, 4, 2) (0, 2, 4, 3) (0, 2, 4, 4) (0, 2, 5, 0) (0, 2, 5, 1)
(0, 2, 5, 2) (0, 2, 5, 3) (0, 2, 5, 4) (0, 3, 0, 0) (0, 3, 0, 1) (0, 3, 0, 2)
(0, 3, 0, 3) (0, 3, 0, 4) (0, 3, 1, 5) (0, 3, 2, 5) (0, 3, 3, 5) (0, 3, 4, 5)
(0, 3, 5, 5) (0, 4, 0, 0) (0, 4, 0, 1) (0, 4, 0, 2) (0, 4, 0, 3) (0, 4, 0, 4)
(0, 4, 1, 5) (0, 4, 2, 5) (0, 4, 3, 5) (0, 4, 4, 5) (0, 4, 5, 5) (0, 5, 0, 0)
(0, 5, 0, 1) (0, 5, 0, 2) (0, 5, 0, 3) (0, 5, 0, 4) (0, 5, 1, 5) (0, 5, 2, 5)
(0, 5, 3, 5) (0, 5, 4, 5) (0, 5, 5, 5) (1, 0, 0, 0) (1, 0, 0, 1) (1, 0, 0, 2)
(1, 0, 0, 3) (1, 0, 0, 4) (1, 0, 1, 5) (1, 0, 2, 5) (1, 0, 3, 5) (1, 0, 4, 5)
(1, 0, 5, 5) (1, 1, 0, 0) (1, 1, 0, 1) (1, 1, 0, 2) (1, 1, 0, 3) (1, 1, 0, 4)
(1, 1, 1, 5) (1, 1, 2, 5) (1, 1, 3, 5) (1, 1, 4, 5) (1, 1, 5, 5) (1, 2, 1, 0)
(1, 2, 1, 1) (1, 2, 1, 2) (1, 2, 1, 3) (1, 2, 1, 4) (1, 2, 2, 0) (1, 2, 2, 1)
(1, 2, 2, 2) (1, 2, 2, 3) (1, 2, 2, 4) (1, 2, 3, 0) (1, 2, 3, 1) (1, 2, 3, 2)
(1, 2, 3, 3) (1, 2, 3, 4) (1, 2, 4, 0) (1, 2, 4, 1) (1, 2, 4, 2) (1, 2, 4, 3)
(1, 2, 4, 4) (1, 2, 5, 0) (1, 2, 5, 1) (1, 2, 5, 2) (1, 2, 5, 3) (1, 2, 5, 4)
(1, 3, 0, 0) (1, 3, 0, 1) (1, 3, 0, 2) (1, 3, 0, 3) (1, 3, 0, 4) (1, 3, 1, 5)
(1, 3, 2, 5) (1, 3, 3, 5) (1, 3, 4, 5) (1, 3, 5, 5) (1, 4, 0, 0) (1, 4, 0, 1)
(1, 4, 0, 2) (1, 4, 0, 3) (1, 4, 0, 4) (1, 4, 1, 5) (1, 4, 2, 5) (1, 4, 3, 5)
(1, 4, 4, 5) (1, 4, 5, 5) (1, 5, 0, 0) (1, 5, 0, 1) (1, 5, 0, 2) (1, 5, 0, 3)
(1, 5, 0, 4) (1, 5, 1, 5) (1, 5, 2, 5) (1, 5, 3, 5) (1, 5, 4, 5) (1, 5, 5, 5)
(2, 0, 0, 0) (2, 0, 0, 1) (2, 0, 0, 2) (2, 0, 0, 3) (2, 0, 0, 4) (2, 0, 1, 5)
(2, 0, 2, 5) (2, 0, 3, 5) (2, 0, 4, 5) (2, 0, 5, 5) (2, 1, 0, 0) (2, 1, 0, 1)
(2, 1, 0, 2) (2, 1, 0, 3) (2, 1, 0, 4) (2, 1, 1, 5) (2, 1, 2, 5) (2, 1, 3, 5)
(2, 1, 4, 5) (2, 1, 5, 5) (2, 2, 1, 0) (2, 2, 1, 1) (2, 2, 1, 2) (2, 2, 1, 3)
(2, 2, 1, 4) (2, 2, 2, 0) (2, 2, 2, 1) (2, 2, 2, 2) (2, 2, 2, 3) (2, 2, 2, 4)
(2, 2, 3, 0) (2, 2, 3, 1) (2, 2, 3, 2) (2, 2, 3, 3) (2, 2, 3, 4) (2, 2, 4, 0)
(2, 2, 4, 1) (2, 2, 4, 2) (2, 2, 4, 3) (2, 2, 4, 4) (2, 2, 5, 0) (2, 2, 5, 1)
(2, 2, 5, 2) (2, 2, 5, 3) (2, 2, 5, 4) (2, 3, 0, 0) (2, 3, 0, 1) (2, 3, 0, 2)
(2, 3, 0, 3) (2, 3, 0, 4) (2, 3, 1, 5) (2, 3, 2, 5) (2, 3, 3, 5) (2, 3, 4, 5)
(2, 3, 5, 5) (2, 4, 0, 0) (2, 4, 0, 1) (2, 4, 0, 2) (2, 4, 0, 3) (2, 4, 0, 4)
(2, 4, 1, 5) (2, 4, 2, 5) (2, 4, 3, 5) (2, 4, 4, 5) (2, 4, 5, 5) (2, 5, 0, 0)
(2, 5, 0, 1) (2, 5, 0, 2) (2, 5, 0, 3) (2, 5, 0, 4) (2, 5, 1, 5) (2, 5, 2, 5)
(2, 5, 3, 5) (2, 5, 4, 5) (2, 5, 5, 5) (3, 0, 0, 0) (3, 0, 0, 1) (3, 0, 0, 2)
(3, 0, 0, 3) (3, 0, 0, 4) (3, 0, 1, 5) (3, 0, 2, 5) (3, 0, 3, 5) (3, 0, 4, 5)
(3, 0, 5, 5) (3, 1, 0, 0) (3, 1, 0, 1) (3, 1, 0, 2) (3, 1, 0, 3) (3, 1, 0, 4)
(3, 1, 1, 5) (3, 1, 2, 5) (3, 1, 3, 5) (3, 1, 4, 5) (3, 1, 5, 5) (3, 2, 1, 0)
(3, 2, 1, 1) (3, 2, 1, 2) (3, 2, 1, 3) (3, 2, 1, 4) (3, 2, 2, 0) (3, 2, 2, 1)
(3, 2, 2, 2) (3, 2, 2, 3) (3, 2, 2, 4) (3, 2, 3, 0) (3, 2, 3, 1) (3, 2, 3, 2)
(3, 2, 3, 3) (3, 2, 3, 4) (3, 2, 4, 0) (3, 2, 4, 1) (3, 2, 4, 2) (3, 2, 4, 3)
(3, 2, 4, 4) (3, 2, 5, 0) (3, 2, 5, 1) (3, 2, 5, 2) (3, 2, 5, 3) (3, 2, 5, 4)
(3, 3, 0, 0) (3, 3, 0, 1) (3, 3, 0, 2) (3, 3, 0, 3) (3, 3, 0, 4) (3, 3, 1, 5)
(3, 3, 2, 5) (3, 3, 3, 5) (3, 3, 4, 5) (3, 3, 5, 5) (3, 4, 0, 0) (3, 4, 0, 1)
(3, 4, 0, 2) (3, 4, 0, 3) (3, 4, 0, 4) (3, 4, 1, 5) (3, 4, 2, 5) (3, 4, 3, 5)
(3, 4, 4, 5) (3, 4, 5, 5) (3, 5, 0, 0) (3, 5, 0, 1) (3, 5, 0, 2) (3, 5, 0, 3)
(3, 5, 0, 4) (3, 5, 1, 5) (3, 5, 2, 5) (3, 5, 3, 5) (3, 5, 4, 5) (3, 5, 5, 5)
(4, 0, 1, 0) (4, 0, 1, 1) (4, 0, 1, 2) (4, 0, 1, 3) (4, 0, 1, 4) (4, 0, 2, 0)
(4, 0, 2, 1) (4, 0, 2, 2) (4, 0, 2, 3) (4, 0, 2, 4) (4, 0, 3, 0) (4, 0, 3, 1)
(4, 0, 3, 2) (4, 0, 3, 3) (4, 0, 3, 4) (4, 0, 4, 0) (4, 0, 4, 1) (4, 0, 4, 2)
(4, 0, 4, 3) (4, 0, 4, 4) (4, 0, 5, 0) (4, 0, 5, 1) (4, 0, 5, 2) (4, 0, 5, 3)
(4, 0, 5, 4) (4, 1, 1, 0) (4, 1, 1, 1) (4, 1, 1, 2) (4, 1, 1, 3) (4, 1, 1, 4)
(4, 1, 2, 0) (4, 1, 2, 1) (4, 1, 2, 2) (4, 1, 2, 3) (4, 1, 2, 4) (4, 1, 3, 0)
(4, 1, 3, 1) (4, 1, 3, 2) (4, 1, 3, 3) (4, 1, 3, 4) (4, 1, 4, 0) (4, 1, 4, 1)
(4, 1, 4, 2) (4, 1, 4, 3) (4, 1, 4, 4) (4, 1, 5, 0) (4, 1, 5, 1) (4, 1, 5, 2)
(4, 1, 5, 3) (4, 1, 5, 4) (4, 3, 1, 0) (4, 3, 1, 1) (4, 3, 1, 2) (4, 3, 1, 3)
(4, 3, 1, 4) (4, 3, 2, 0) (4, 3, 2, 1) (4, 3, 2, 2) (4, 3, 2, 3) (4, 3, 2, 4)
(4, 3, 3, 0) (4, 3, 3, 1) (4, 3, 3, 2) (4, 3, 3, 3) (4, 3, 3, 4) (4, 3, 4, 0)
(4, 3, 4, 1) (4, 3, 4, 2) (4, 3, 4, 3) (4, 3, 4, 4) (4, 3, 5, 0) (4, 3, 5, 1)
(4, 3, 5, 2) (4, 3, 5, 3) (4, 3, 5, 4) (4, 4, 1, 0) (4, 4, 1, 1) (4, 4, 1, 2)
(4, 4, 1, 3) (4, 4, 1, 4) (4, 4, 2, 0) (4, 4, 2, 1) (4, 4, 2, 2) (4, 4, 2, 3)
(4, 4, 2, 4) (4, 4, 3, 0) (4, 4, 3, 1) (4, 4, 3, 2) (4, 4, 3, 3) (4, 4, 3, 4)
(4, 4, 4, 0) (4, 4, 4, 1) (4, 4, 4, 2) (4, 4, 4, 3) (4, 4, 4, 4) (4, 4, 5, 0)
(4, 4, 5, 1) (4, 4, 5, 2) (4, 4, 5, 3) (4, 4, 5, 4) (4, 5, 1, 0) (4, 5, 1, 1)
(4, 5, 1, 2) (4, 5, 1, 3) (4, 5, 1, 4) (4, 5, 2, 0) (4, 5, 2, 1) (4, 5, 2, 2)
(4, 5, 2, 3) (4, 5, 2, 4) (4, 5, 3, 0) (4, 5, 3, 1) (4, 5, 3, 2) (4, 5, 3, 3)
(4, 5, 3, 4) (4, 5, 4, 0) (4, 5, 4, 1) (4, 5, 4, 2) (4, 5, 4, 3) (4, 5, 4, 4)
(4, 5, 5, 0) (4, 5, 5, 1) (4, 5, 5, 2) (4, 5, 5, 3) (4, 5, 5, 4) (5, 0, 0, 0)
(5, 0, 0, 1) (5, 0, 0, 2) (5, 0, 0, 3) (5, 0, 0, 4) (5, 0, 1, 5) (5, 0, 2, 5)
(5, 0, 3, 5) (5, 0, 4, 5) (5, 0, 5, 5) (5, 1, 0, 0) (5, 1, 0, 1) (5, 1, 0, 2)
(5, 1, 0, 3) (5, 1, 0, 4) (5, 1, 1, 5) (5, 1, 2, 5) (5, 1, 3, 5) (5, 1, 4, 5)
(5, 1, 5, 5) (5, 2, 1, 0) (5, 2, 1, 1) (5, 2, 1, 2) (5, 2, 1, 3) (5, 2, 1, 4)
(5, 2, 2, 0) (5, 2, 2, 1) (5, 2, 2, 2) (5, 2, 2, 3) (5, 2, 2, 4) (5, 2, 3, 0)
(5, 2, 3, 1) (5, 2, 3, 2) (5, 2, 3, 3) (5, 2, 3, 4) (5, 2, 4, 0) (5, 2, 4, 1)
(5, 2, 4, 2) (5, 2, 4, 3) (5, 2, 4, 4) (5, 2, 5, 0) (5, 2, 5, 1) (5, 2, 5, 2)
(5, 2, 5, 3) (5, 2, 5, 4) (5, 3, 0, 0) (5, 3, 0, 1) (5, 3, 0, 2) (5, 3, 0, 3)
(5, 3, 0, 4) (5, 3, 1, 5) (5, 3, 2, 5) (5, 3, 3, 5) (5, 3, 4, 5) (5, 3, 5, 5)
(5, 4, 0, 0) (5, 4, 0, 1) (5, 4, 0, 2) (5, 4, 0, 3) (5, 4, 0, 4) (5, 4, 1, 5)
(5, 4, 2, 5) (5, 4, 3, 5) (5, 4, 4, 5) (5, 4, 5, 5) (5, 5, 0, 0) (5, 5, 0, 1)
(5, 5, 0, 2) (5, 5, 0, 3) (5, 5, 0, 4) (5, 5, 1, 5) (5, 5, 2, 5) (5, 5, 3, 5)
(5, 5, 4, 5) (5, 5, 5, 5)

q_star=(2, 5, 1, 5), answer=(2, 0), n_tries=2
New state space:
(0, 0, 0, 0) (0, 0, 0, 1) (0, 0, 0, 2) (0, 0, 0, 3) (0, 0, 0, 4) (0, 1, 0, 0)
(0, 1, 0, 1) (0, 1, 0, 2) (0, 1, 0, 3) (0, 1, 0, 4) (0, 2, 2, 0) (0, 2, 2, 1)
(0, 2, 2, 2) (0, 2, 2, 3) (0, 2, 2, 4) (0, 2, 3, 0) (0, 2, 3, 1) (0, 2, 3, 2)
(0, 2, 3, 3) (0, 2, 3, 4) (0, 2, 4, 0) (0, 2, 4, 1) (0, 2, 4, 2) (0, 2, 4, 3)
(0, 2, 4, 4) (0, 2, 5, 0) (0, 2, 5, 1) (0, 2, 5, 2) (0, 2, 5, 3) (0, 2, 5, 4)
(0, 3, 0, 0) (0, 3, 0, 1) (0, 3, 0, 2) (0, 3, 0, 3) (0, 3, 0, 4) (0, 4, 0, 0)
(0, 4, 0, 1) (0, 4, 0, 2) (0, 4, 0, 3) (0, 4, 0, 4) (1, 0, 0, 0) (1, 0, 0, 1)
(1, 0, 0, 2) (1, 0, 0, 3) (1, 0, 0, 4) (1, 1, 0, 0) (1, 1, 0, 1) (1, 1, 0, 2)
(1, 1, 0, 3) (1, 1, 0, 4) (1, 2, 2, 0) (1, 2, 2, 1) (1, 2, 2, 2) (1, 2, 2, 3)
(1, 2, 2, 4) (1, 2, 3, 0) (1, 2, 3, 1) (1, 2, 3, 2) (1, 2, 3, 3) (1, 2, 3, 4)
(1, 2, 4, 0) (1, 2, 4, 1) (1, 2, 4, 2) (1, 2, 4, 3) (1, 2, 4, 4) (1, 2, 5, 0)
(1, 2, 5, 1) (1, 2, 5, 2) (1, 2, 5, 3) (1, 2, 5, 4) (1, 3, 0, 0) (1, 3, 0, 1)
(1, 3, 0, 2) (1, 3, 0, 3) (1, 3, 0, 4) (1, 4, 0, 0) (1, 4, 0, 1) (1, 4, 0, 2)
(1, 4, 0, 3) (1, 4, 0, 4) (3, 0, 0, 0) (3, 0, 0, 1) (3, 0, 0, 2) (3, 0, 0, 3)
(3, 0, 0, 4) (3, 1, 0, 0) (3, 1, 0, 1) (3, 1, 0, 2) (3, 1, 0, 3) (3, 1, 0, 4)
(3, 2, 2, 0) (3, 2, 2, 1) (3, 2, 2, 2) (3, 2, 2, 3) (3, 2, 2, 4) (3, 2, 3, 0)
(3, 2, 3, 1) (3, 2, 3, 2) (3, 2, 3, 3) (3, 2, 3, 4) (3, 2, 4, 0) (3, 2, 4, 1)
(3, 2, 4, 2) (3, 2, 4, 3) (3, 2, 4, 4) (3, 2, 5, 0) (3, 2, 5, 1) (3, 2, 5, 2)
(3, 2, 5, 3) (3, 2, 5, 4) (3, 3, 0, 0) (3, 3, 0, 1) (3, 3, 0, 2) (3, 3, 0, 3)
(3, 3, 0, 4) (3, 4, 0, 0) (3, 4, 0, 1) (3, 4, 0, 2) (3, 4, 0, 3) (3, 4, 0, 4)
(4, 0, 2, 0) (4, 0, 2, 1) (4, 0, 2, 2) (4, 0, 2, 3) (4, 0, 2, 4) (4, 0, 3, 0)
(4, 0, 3, 1) (4, 0, 3, 2) (4, 0, 3, 3) (4, 0, 3, 4) (4, 0, 4, 0) (4, 0, 4, 1)
(4, 0, 4, 2) (4, 0, 4, 3) (4, 0, 4, 4) (4, 0, 5, 0) (4, 0, 5, 1) (4, 0, 5, 2)
(4, 0, 5, 3) (4, 0, 5, 4) (4, 1, 2, 0) (4, 1, 2, 1) (4, 1, 2, 2) (4, 1, 2, 3)
(4, 1, 2, 4) (4, 1, 3, 0) (4, 1, 3, 1) (4, 1, 3, 2) (4, 1, 3, 3) (4, 1, 3, 4)
(4, 1, 4, 0) (4, 1, 4, 1) (4, 1, 4, 2) (4, 1, 4, 3) (4, 1, 4, 4) (4, 1, 5, 0)
(4, 1, 5, 1) (4, 1, 5, 2) (4, 1, 5, 3) (4, 1, 5, 4) (4, 3, 2, 0) (4, 3, 2, 1)
(4, 3, 2, 2) (4, 3, 2, 3) (4, 3, 2, 4) (4, 3, 3, 0) (4, 3, 3, 1) (4, 3, 3, 2)
(4, 3, 3, 3) (4, 3, 3, 4) (4, 3, 4, 0) (4, 3, 4, 1) (4, 3, 4, 2) (4, 3, 4, 3)
(4, 3, 4, 4) (4, 3, 5, 0) (4, 3, 5, 1) (4, 3, 5, 2) (4, 3, 5, 3) (4, 3, 5, 4)
(4, 4, 2, 0) (4, 4, 2, 1) (4, 4, 2, 2) (4, 4, 2, 3) (4, 4, 2, 4) (4, 4, 3, 0)
(4, 4, 3, 1) (4, 4, 3, 2) (4, 4, 3, 3) (4, 4, 3, 4) (4, 4, 4, 0) (4, 4, 4, 1)
(4, 4, 4, 2) (4, 4, 4, 3) (4, 4, 4, 4) (4, 4, 5, 0) (4, 4, 5, 1) (4, 4, 5, 2)
(4, 4, 5, 3) (4, 4, 5, 4) (5, 0, 0, 0) (5, 0, 0, 1) (5, 0, 0, 2) (5, 0, 0, 3)
(5, 0, 0, 4) (5, 1, 0, 0) (5, 1, 0, 1) (5, 1, 0, 2) (5, 1, 0, 3) (5, 1, 0, 4)
(5, 2, 2, 0) (5, 2, 2, 1) (5, 2, 2, 2) (5, 2, 2, 3) (5, 2, 2, 4) (5, 2, 3, 0)
(5, 2, 3, 1) (5, 2, 3, 2) (5, 2, 3, 3) (5, 2, 3, 4) (5, 2, 4, 0) (5, 2, 4, 1)
(5, 2, 4, 2) (5, 2, 4, 3) (5, 2, 4, 4) (5, 2, 5, 0) (5, 2, 5, 1) (5, 2, 5, 2)
(5, 2, 5, 3) (5, 2, 5, 4) (5, 3, 0, 0) (5, 3, 0, 1) (5, 3, 0, 2) (5, 3, 0, 3)
(5, 3, 0, 4) (5, 4, 0, 0) (5, 4, 0, 1) (5, 4, 0, 2) (5, 4, 0, 3) (5, 4, 0, 4)

q_star=(4, 1, 2, 4), answer=(2, 1), n_tries=3
New state space:
(0, 0, 0, 4) (0, 1, 0, 0) (0, 1, 0, 1) (0, 1, 0, 2) (0, 1, 0, 3) (0, 2, 2, 0)
(0, 2, 2, 1) (0, 2, 2, 2) (0, 2, 2, 3) (0, 2, 3, 4) (0, 2, 4, 4) (0, 2, 5, 4)
(0, 3, 0, 4) (0, 4, 0, 4) (1, 0, 0, 4) (1, 1, 0, 0) (1, 1, 0, 1) (1, 1, 0, 2)
(1, 1, 0, 3) (1, 2, 2, 0) (1, 2, 2, 1) (1, 2, 2, 2) (1, 2, 2, 3) (1, 2, 3, 4)
(1, 2, 4, 4) (1, 2, 5, 4) (1, 3, 0, 4) (1, 4, 0, 4) (3, 0, 0, 4) (3, 1, 0, 0)
(3, 1, 0, 1) (3, 1, 0, 2) (3, 1, 0, 3) (3, 2, 2, 0) (3, 2, 2, 1) (3, 2, 2, 2)
(3, 2, 2, 3) (3, 2, 3, 4) (3, 2, 4, 4) (3, 2, 5, 4) (3, 3, 0, 4) (3, 4, 0, 4)
(4, 0, 3, 0) (4, 0, 3, 1) (4, 0, 3, 2) (4, 0, 3, 3) (4, 0, 4, 0) (4, 0, 4, 1)
(4, 0, 4, 2) (4, 0, 4, 3) (4, 0, 5, 0) (4, 0, 5, 1) (4, 0, 5, 2) (4, 0, 5, 3)
(4, 3, 3, 0) (4, 3, 3, 1) (4, 3, 3, 2) (4, 3, 3, 3) (4, 3, 4, 0) (4, 3, 4, 1)
(4, 3, 4, 2) (4, 3, 4, 3) (4, 3, 5, 0) (4, 3, 5, 1) (4, 3, 5, 2) (4, 3, 5, 3)
(4, 4, 3, 0) (4, 4, 3, 1) (4, 4, 3, 2) (4, 4, 3, 3) (4, 4, 4, 0) (4, 4, 4, 1)
(4, 4, 4, 2) (4, 4, 4, 3) (4, 4, 5, 0) (4, 4, 5, 1) (4, 4, 5, 2) (4, 4, 5, 3)
(5, 0, 0, 4) (5, 1, 0, 0) (5, 1, 0, 1) (5, 1, 0, 2) (5, 1, 0, 3) (5, 2, 2, 0)
(5, 2, 2, 1) (5, 2, 2, 2) (5, 2, 2, 3) (5, 2, 3, 4) (5, 2, 4, 4) (5, 2, 5, 4)
(5, 3, 0, 4) (5, 4, 0, 4)

q_star=(4, 0, 3, 0), answer=(1, 1), n_tries=4
New state space:
(0, 0, 0, 4) (0, 1, 0, 0) (0, 2, 2, 0) (0, 2, 3, 4) (1, 0, 0, 4) (1, 1, 0, 0)
(1, 2, 2, 0) (1, 2, 3, 4) (3, 0, 0, 4) (3, 1, 0, 0) (3, 2, 2, 0) (3, 2, 3, 4)
(4, 3, 4, 1) (4, 3, 4, 2) (4, 3, 4, 3) (4, 3, 5, 1) (4, 3, 5, 2) (4, 3, 5, 3)
(4, 4, 4, 1) (4, 4, 4, 2) (4, 4, 4, 3) (4, 4, 5, 1) (4, 4, 5, 2) (4, 4, 5, 3)
(5, 0, 0, 4) (5, 1, 0, 0) (5, 2, 2, 0) (5, 2, 3, 4)

q_star=(0, 2, 2, 0), answer=(0, 1), n_tries=5
New state space:
(0, 0, 0, 4) (1, 1, 0, 0) (1, 2, 3, 4) (3, 1, 0, 0) (3, 2, 3, 4) (5, 1, 0, 0)
(5, 2, 3, 4)

q_star=(3, 2, 3, 4), answer=(0, 3), n_tries=6
New state space:
(1, 2, 3, 4) (5, 2, 3, 4)

q_star=(1, 2, 3, 4), answer=(0, 4), n_tries=7
The secret is (1, 2, 3, 4)