On Optimal Strategies for Wordle and General Guessing Games

1 Introduction

Mastermind is a guessing game that has been studied extensively in the past [Knuth, 1977; Stuckman and Zhang, 2005; Doerr et al., 2016; Glazik et al., 2021]. Such work has not seemed to be carried over to other guessing games, however. Our vision is to have AI agents learn how to approach any game of this kind, similar to a general-game-playing setting [Genesereth and Bj ¨ornsson, 2013; Genesereth and Thielscher, 2014]. To do this we supply human intelligence to guide this area of research; this paper aims to do just that for general guessing games. We also aim to add mathematical rigour to the study of meta-reasoning in guessing games, such as in [Filman et al., 1983], or to aid in developing predicates for grounded languages such as in [Thomason et al., 2016].

The timing of this publication coincides with the recent popularity of the online game Wordle [Wardle, 2021], which we will use for our example guessing game of choice. Wordle is a word game that was published in October 2021. Since then, it has gained significant popularity, with over 300,000 daily users in January 2022 [Serrels and Boom, 2022]. There has been widespread interest in the general community for an optimal approach to the game, with several websites making unsupported claims to have determined the best strategy.

The game itself is a guessing game in which players must deduce a hidden word using clues that the game gives in response to the player's guesses, with a fixed limit of 6 guesses allowed. The exact details of these clues and the structure of the game will be explored in further detail in the next section.

The popularity of Wordle has also caused several variants to appear, including with

• Different word sets (e.g. Bardle [Bardle, 2022], FFXIVrdle [FFXIV, 2022])
• Multiple games at the same time (e.g. Dordle [Dordle, 2022], Tridle [Tridle, 2022], Sexaginta-quattuordle [Sexaginta-quattuordle, 2022])
• Completely different forms of input (e.g. Heardle [Heardle, 2022], Chessle [Chessle, 2022]).

As such, the focus of this paper lies in guessing games in general, but we will use Wordle as the main example throughout.

Our main contribution is a series of theorems that build towards a general method to determine if a strategy is optimal or not, without the need for an exhaustive search. These formal results can also be used to find an optimal strategy. The theorems we present are generalized to work for any guessing games to automatically find strategies and prove their optimality. We specifically demonstrate using these theorems to show the Wordle strategy found by our framework is optimal. We also present a method of determining the next optimal guess, which to our knowledge, is a novel approach.

The remainder of the paper is organized as follows. In the next section, we recapitulate the basic components of guessing games in general, including Wordle, and we recapitulate known heuristics from the literature on Mastermind. In Section 3, we show how to combine heuristics to search for good strategies. In Section 4, we present novel and general theorems by which a strategy can be proved optimal without an exhaustive search. In the section that follows, we demonstrate using the general method and theorems on Wordle and some of its variants. We conclude in Section 6. 1

2 Background

2.1 Guessing Games

In this section, we define exactly what we consider to be general guessing games, following similar definitions by Koyama and Lai [1991] and Focardi and Luccio [2012]. Koyama and Lai refer to a guessing game as an 'interactive knowledge transfer model', but for the sake of readability we will use the term 'guessing game'.

In a guessing game, we have two parties: a learner and a teacher. The teacher's goal is to communicate some secret s that is initially hidden from the learner. The learner submits a guess g to the teacher, to which the teacher responds with some response r. The teacher's responses are to be used as clues by the learner to deduce what s is. The teacher computes responses using an answering function a; this function is known to both parties. These communications continue until the teacher responds with the affirmative response r∗ , at which point we say the learner has learnt the secret and has won the game. The following definition summarizes the components of a general guessing game.

1 An extended version of this paper with full proofs and more examples can be found on arXiv: http://arxiv.org/abs/2305.09111.

Definition 1 (Guessing game). A guessing game can be uniquely represented as a tuple (G, S, R, r∗ , a), where

G = Set of allowable guesses

S = Set of allowable secrets, with S ⊆ G

R = Set of possible responses, with |R| > 1

r∗ = Affirmative response, with r∗ ∈ R

and G, S and R are finite sets.

We assume that S is known to the learner, though exactly which element of S is the secret is not known. This may not be true in practice for human players, but we do this because any guessing game should have a well-defined domain of secrets that an AI certainly could use.

2.2 Wordle

In Wordle 2 , the player (learner) must deduce a common 5letter English word chosen by the computer (teacher). Similar to the well-known guessing game Mastermind, the player's guesses are met with colour-coded responses to guide them toward the answer. The secret in Wordle changes daily.

We provide an example play of Wordle in Figure 1 using the game from March 22 2022. The player's first guess was TARES. The computer assigned a grey colour to T, A, R, E, and so none of those letters appear in the secret word. The letter S however was assigned a yellow colour, which indicated that S does appear in the secret, but not in its current position (i.e. the 5th position). The player's next guess was SPOIL. Now S and O are assigned green, which indicates S and O appear in those positions in the secret word. The player uses these colour encodings as responses from the computer to determine what to guess next throughout the game. Wordle ends when the player receives an all-green encoding, as seen in the final row.

To represent colours we use 0 = Grey, 1 = Yellow and 2 = Green in the following definition.

Definition 2 (Wordle). Wordle is a guessing game (GW , SW , RW , r∗W , aW ) according to Definition 1, where

GW = All 5 letter words, curated by the developer.

SW = Common 5 letter words decided by the developer.

RW = {00000, 00001, . . . , 22220, 22222}

r∗W = 22222

aW = See the above paragraph and Figure 1 for example.

2 Wordle has several variants. In this paper we consider Wordle in its default mode.

GW and SW are publicly known sets and can be found in Wordle's source code. It is worth noting however that this set has been altered a few times since the game's creation. Our research into Wordle strategies was initially conducted on Wordle's original sets of guesses and secrets (before 15th February 2022), and so we describe our work using these sets, with |GW | = 12972 and |SW | = 2315. Importantly however, the results presented in this paper could easily be replicated for the updated Wordle sets, or any other word set in general, as we will see.

2.3 Strategies

In this section, we formalize how we intend agents to play guessing games by defining strategies; as well as how we intend to compare the performance of strategies.

As a learner plays a guessing game, they should be using the previously submitted guesses and the corresponding received responses to make informed decisions about what guess to submit next. We may capture this learned information using candidates.

Definition 3 (Candidates). Suppose in a guessing game (G, S,R, r∗ , a) the guesses and responses so far are ((g1, r1), . . . , (gn, rn)), i.e. guess gi was met with response ri. The candidate set C is defined as

If there are no guesses or responses so far, C = S.

Candidates are elements of S that could be the secret word according to the information contained in the guesses and responses played so far. At the start of a game, the set of candidates is S as no information about the secret has been communicated to the learner yet.

A strategy is a learner's method of determining what guess to submit next, recalling the goal is to get response r∗ . We make use of candidate sets in formalising this notion.

Definition 4 (Strategy). A strategy σ can be defined as

where P(S) is the power set of S. Then σ(C), for some candidate set C ⊆ S, would represent what guess to submit next.

Note that the co-domain of σ is G; the learner is allowed to make guesses that may not be possible secrets. Strategies also may be non-deterministic, but in this paper, we only consider ones that are deterministic.

On receiving a response from the teacher, we need to filter the candidate set appropriately. After submitting a guess, we can know the possible future candidate sets; in this sense each guess can split the candidate set.

Definition 5 (Split). For a candidate set C, we say that guessing g creates splits categorized by response r:

We can calculate our score playing according to any strategy using TURNSNEEDED.

Definition 6 (TURNSNEEDED). Suppose we play using strategy σ and the hidden secret is s. Start with candidate set C = S and submit guess g = σ(C). If response r∗ is received, then we are done. Otherwise, replace C with Cg,r and again submit guess σ(C). Repeat until response r∗ is received. TURNSNEEDED(σ, s) is the number of guesses submitted.

Note that in this process, the player does not use s to decide what to guess; we only use the remaining candidates and σ to determine what to guess next.

The objective of this paper is to find an 'optimal' strategy. Existing papers measured the performance of strategies by taking the EXPECTED number of guesses needed (taken over all secrets in S) [Koyama and Lai, 1994; Focardi and Luccio, 2012]. Other authors such as Kooi [2005] also considered the maximum number of guesses needed, but the primary goal historically has always been to minimize the EXPECTED score. In this paper we will be using an equivalent metric TOTAL as defined below.

Definition 7 (TOTAL metric). For a strategy σ, TOTAL(σ) is the total number of turns needed over all secrets in S:

It should be clear that a strategy that is optimal according to the EXPECTED case is also optimal according to the TOTAL (=|S| · EXPECTED) case. We use TOTAL however because it makes the work in Section 4 much easier to read.

2.4 Known Strategies

In the extensive literature on Mastermind [Knuth, 1977; Bestavros and Belal, 1986; Kooi, 2005; Berghman et al., 2009], several strategies have been developed and tested. We restate some of these strategies in this section for later reference. They all determine what guess to submit next by assigning each guess g a numerical score based on the current candidate set using a valuation.

Definition 8 (Valuation-based strategy).

where C is a candidate set and v is some function of type G × P (S) → R. We call v a valuation. In tie-breaks, default to lexicographical ordering.

A simple (yet useful) valuation is the following:

where I is the indicator function. This is adapted from one of the earliest published algorithms on Mastermind [Sterling and Shapiro, 1994]. We use the negative sign since we are taking the min in Definition 8, and prioritising guesses that are in C.

Strategies developed for Mastermind focused on using different valuations such as:

where

Knuth [1977] used MAXSIZESPLIT, Kooi [2005] introduced MOSTPARTS and Bestavros and Belal [1986] used INFORMATION. There are several other valuations developed for Mastermind, but we only included the ones which showed promising results in existing literature.

3 Finding Good Strategies

Before we can prove the optimality of a strategy for any given guessing game, it is necessary to first find a good one. We do this by first using Knuth's [1977] paper on Mastermind for inspiration, and revisit Definition 7 to develop a method by which we may search for strategies with low TOTAL scores.

3.1 Combining Known Valuations

Knuth [1977] used the MAXSIZESPLIT evaluation. In the event several guesses had equally minimal valuations, he suggested that for the next guess, "a valid one should be used", i.e. a guess that is also a candidate. He made no explicit rule about which to choose if there are multiple guesses with equally minimal valuations and that are candidates. We resolve this in the context of a general guessing game.

Definition 9 (Combined valuations). For valuations v1, . . . , vn, we can combine them to assign each guess g a tuple of values:

We can then compare tuples lexicographically.

Only if the combined valuations together are the same for two guesses, then we may revert to choosing alphabetically, but ideally we would append more valuations to avoid this.

In choosing which valuations to combine for Wordle, we tested 3 every non-empty ordered combination of INSET, MAXSIZESPLIT, INFORMATION, MOSTPARTS, EXPSIZESPLIT, giving 325 combined valuations.

3 Full source code for this experiment and all subsequent ones is available at https://github.com/cunananm2000/WordleBot.

As shown by Table 1, using combined valuations does offer an improvement over using any single valuation alone. Moreover, all the best-performing combinations use MOSTPARTS as the main valuation, which makes sense as it was the best-performing standalone valuation for Mastermind [Kooi, 2005].

3.2 Searching For Strategies

Koyama and Lai [1991] presented an equation to calculate the minimum EXPECTED score achievable. We adapt this to an equation to calculate the minimum TOTAL score:

Definition 10 (MINTOTAL). For a non-empty candidate set C, the minimum TOTAL number of guesses needed to reach all candidates in C is given by

Unfortunately, it isn't feasible to calculate MINTOTAL for most candidate sets in real guessing games such as Wordle. The recursive definition means that with each calculation of MINTOTAL we loop over g ∈ G. If we were to limit our recursion depth to d, then our algorithm would run in O(|G|d ). To limit this exponential growth, we propose that instead of searching over all g ∈ G, only search over the 'best' n guesses in G; we call n the search breadth.

Definition 11 (Approximate MINTOTAL). For a candidate set C, the approximate minimum total number of guesses needed is APMINTOTAL(C, n), defined by replacing g ∈ G in Definition 10 with g ∈ {Best n guesses}.

We will be using the topmost combined valuation from Table 1, (MOSTPARTS, INSET, EXPSIZESPLIT), to determine what the best n guesses are; taking the n guesses with the lowest valuations.

Depending on how exhaustively we want to look for strategies we may change n; a higher value of n means a more exhaustive search. It should be clear, then, that APMINTOTAL(C, n) ≥ MINTOTAL(C) for any n ≥ 1, and that at n = |G| the two are equal.

As mentioned previously, we may use the argmin of the 'otherwise' case of Definition 11 to extract a strategy.

Since Wordle is the main guessing game for this paper, we first show our results in Table 2. As we expect, the TOTAL

decreases as the search breadth increases, as this means we search more exhaustively.

We repeated this process of using Definition 11 to search for strategies with low TOTAL scores on the following variants of Wordle:

• FFXIVrdle: S = References to the video game Final Fantasy 14, e.g. HILDA.
• Mininerdle: G = S = 6 character math equations, e.g. 4*7=28.
• Nerdle: G = S = 8 character math equations, e.g. 8*3+2=26.
• Primel: G = S = 5 digit prime numbers, e.g. 42821.

Results are shown in Table 3.

4 Proving Optimality

The previous section was focused on using heuristics to find good strategies; now we'd like to determine if the best ones found were indeed optimal. First, we revisit Definition 10, and explore the idea of representing strategies as 'trees'. Doing so allows us to prove several propositions which we use to create novel theorems by which we can prove a strategy optimal without exhaustive search.

4.1 Useful Guesses

In order to help restrict the search space, we define the notion of usefulness.

Definition 12. For a candidate set C with |C| > 1, a guess g ∈ G is useful w.r.t. C iff NSPLITS (g,C) ̸= 1. We notate this as g ∈ UG (C) for short. If |C| ≤ 1, then UG (C) = C.

Property 1. Equivalently for |C| > 1, g ∈ UG(C) iff |Cg,r| < |C| for all r ∈ R.

Lemma 1. For any non-empty C ⊆ S,

Note the replacement of g ∈ G from Definition 10 with g ∈ UG (C).

Proof. Suppose the minimum was achieved by some g ̸∈ UG(C), so Cg,r = C for a specific r and Cg,r′ = ∅ for r′ ∈ R \ {r}. By Definition 10 this would imply MINTOTAL (C) = |C| +MINTOTAL (C), so |C| = 0, contrary to the assumption.

This also shows that optimal strategies can only have useful guesses.

4.2 Setup

Definition 13 (V ∗ ). By splitting Lemma 1, we define

and MINTOTAL (∅) = 0.

V ∗ (g,C) then represents the minimum TOTAL, starting from candidate set C, provided we guess g ∈ G first. The optimal strategy would then be achieved by taking the argmin.

MINTOTAL (C) and V ∗ (g,C) are what we should try to estimate. Finding an upper bound for MINTOTAL (C) is easy; as noted previously APMINTOTAL(C, n) is an upper bound for any n. We notate such an upper bound as UB(C). As per Table 2, the lowest known value found for Wordle, UB(SW), is 7920. Lower bounding V ∗ is important via the following theorem:

Theorem 1. Suppose we have some function UB such that UB(C) ≥ MINTOTAL (C) for any C ⊆ S. If we can find some estimate function V ′ such that V ′ (g,C) ≤ V ∗ (g,C) for any guess g ∈ G and C ⊆ S, then for any g′ ∈ G

Proof. If V ′ (g′ ,C) > UB(C) for a particular g′ ∈ G,

We then use Definition 13 to complete the proof.

Theorem 1 has the effect that for any guess g′ , if V ∗ (g′ , S) > UB(S), then g′ cannot be an optimal starting word.

In order to estimate V ∗ , we must first estimate MINTOTAL as it is much easier to create bounds for.

4.3 Tree Representations

Ville [2013] demonstrated representing their Mastermind strategy as a decision tree, and we may do the same with strategies in guessing games in general, as illustrated in Figure 2 for a Wordle strategy. We will call these strategy trees. Each node is a guess to be submitted; starting at the root node as the initial guess. The outgoing branches from a node represent the possible responses received by submitting the node's guess. If r∗ is a possible response, then we do not include that branch and instead highlight the node in green as a possible end to the game.

Alternatively, each node can be thought of as corresponding to a current set of candidates C, labelled with σ(C).

It follows that for the tree representation of a strategy σ, the value TURNSNEEDED(σ, s) is represented by the depth of node labelled with s as a leaf node. Note that the same word may appear multiple times in a strategy tree, so we must follow the nodes and branches to properly compute the 'correct' depth. Importantly, we assign the depth of the root node as 1, so the value TOTAL(σ) can be then visualized as the sum of the depths of each secret. With this, we can then notice that MINTOTAL is purely dependent on the placements of the nodes corresponding to possible secrets within a tree. The natural question to ask then is, "What is the best way to arrange the nodes corresponding to possible secrets in a strategy tree to minimize the sum of depths to each of these nodes?", or put more generally,

"What is the best way to arrange the n nodes in a tree to minimize the sum of depths to each node?"

To answer this we need to prove some properties about strategy trees.

Definition 14. For any C ⊆ S,

Lemma 2. For candidate sets C ′ and C, if C ′ ⊆ C, then MAXSPLITS (C ′ ) ≤ MAXSPLITS (C).

Proof. If C ′ ⊆ C, for any guess g ∈ G we must have NSPLITS (g,C ′ ) ≤ NSPLITS (g,C). This is because if C ′g,r is non-empty for some response r, then Cg,r is non-empty. This implies the desired result.

Theorem 2. In any tree made to resolve a candidate set C, all nodes have at most MAXSPLITS(C) children.

Proof. The value MAXSPLITS(C) is the highest number of branches the root node can have. This is true even after noting that r∗ is never assigned a corresponding branch. Recall moreover that each child node also corresponds to a candidate set C ′ ⊂ C. The number of children that the direct child nodes of the root node can have is upper bounded by MAXSPLITS(C ′ ), but by Lemma 2, this value is upper bounded by MAXSPLITS(C). The same logic can be cascaded down each branch of the tree to show that each node has at most MAXSPLITS(C) children.

Definition 15. For integers n ≥ 0 and b ≥ 1, BOUND (n, b) is the minimum sum of depths of each node in a tree with n nodes, and each node having at most b children. We call such a tree a b-tree.

Theorem 3. For integers n > 0 and b > 1,

Proof. Note that BOUND(0, 1) = 0 by either of the last two cases.

This is trivial when n = 0 or b = 1. In the case where n > 0 and b > 1, there are multiple ways to arrange n nodes in a b-tree. We are interested in minimizing the sum of depths to each node; clearly we must fill in level-order, noting that there are at most bi-1 nodes of depth i. Doing this will show that k is the depth of the last completely filled layer. The last term in the definition accounts for the 'leftover' nodes at depth k + 1.

The restriction on the number of children suggests we use BOUND in creating lower bounds for MINTOTAL.

Definition 16.

In turn, we use this to recursively build bounds for V ∗ and MINTOTAL, taking inspiration fromDefinition 13.

Definition 17. For integers i ≥ 1

It remains to prove that LBi and Vi are in fact lower bounds to MINTOTAL and V ∗ respectively.

4.4 Key Theorems and Proofs

We now use the work of Sections 4.1, 4.2 and 4.3 to build the key theorems of this paper.

Proof. Note that BOUND (n, b) increases as b decreases for a fixed n. Recall the definition of BOUND (n, b). Clearly decreasing b means each node's depth can only increase, so the overall sum of depths for each node must increase.

This fact combined with Lemma 2 implies the desired result.

Proof. MINTOTAL is intended to represent the best way to arrange the candidates of C in any valid strategy tree in order to minimize the sum of depths to each candidate. We know that in this 'ideal' strategy tree, there must be at least |C| nodes (one for each candidate), and that by Theorem 2 this tree is a MAXSPLITS(C)-tree. It follows by Definition 16 and Definition 15 that the sum of depths to each node is lower bounded by LB2(C).

Proof. Follows from construction in Definition 17.

Proposition 1. If Vi(C) ≤ Vj(C) for any guess g ∈ G and C ⊆ S, then LBi+2(C) ≤ LBj+2(C) for any C ⊆ S.

Proof. Follows from construction in Definition 17.

Proof. Follows from Lemma 5 and Proposition 1.

Theorem 4. For any integer n ≥ 1, we have that LB2n-1(C) ≤ LB2n(C) ≤ MINTOTAL (C) for any C ⊆ S.

Proof. We may follow a similar proof to Corollary 1 to show that if LBi(C) ≤ MINTOTAL (C) for any C ⊆ S, then LBi+2(C) ≤ MINTOTAL (C) for any C ⊆ S.

The desired result follows combining this with Lemmas 3 and 4 along with Corollary 1.

Theorem 5. For any integer n ≥ 1, we have that LBn(C) ≤ LBn+2(C) ≤ MINTOTAL (C) for any C ⊆ S.

Sketch Proof. We can show that for any C ⊆ S, we have LB1(C) ≤ LB3(C). Intuitively, LB1(C) is the minimum sum of depths in a tree assuming that each node has at most MAXSPLITS (S) children. LB3(C) however asserts that the root node must split according to a legitimate guess. This restriction implies LB1(C) ≤ LB3(C).

We can also show that LB2(C) ≤ LB4(C), for any C ⊆ S. Proving this uses the previous claim of LB1(C) ≤ LB3(C). It requires the trick that we may replace S in the explicit definition of that claim with C, since we only require that S be a super-set of C.

Combine these two inequalities with Lemmas 3 and 4, and Corollary 1 to reach the desired conclusion.

Proposition 2. For any integer n ≥ 1, Vn(g, C) ≤ V ∗ (g, C) for any guess g ∈ G and any C ⊆ S.

Proof. Theorem 4 shows that LBn(C) ≤ MINTOTAL (C) for any integer n ≥ 1 and any C ⊆ S.

By the construction of V ∗ (Definition 13) and Vi (Definition 17), we can use the above to conclude Vn(C) ≤ V ∗ (C) for any integer n ≥ 1 and any C ⊆ S.

Theorem 6. For any integer n ≥ 1, we have that Vn(g,C) ≤ Vn+2(g,C) ≤ V ∗ (g,C) for any guess g ∈ G and C ⊆ S.

Proof. Proposition 2 and Lemma 5 imply that inequalities from Theorem 5 also hold if we replace each LB with V , keeping subscripts the same, which was what we wanted.

This shows we have developed an infinite system of lowerbounds for V ∗ . Recall how we plan to use these as stated in Theorem 1.

Theorem 7. For any guess g ∈ G and any C ⊆ S, we have V2|C|+1(g, C) = V ∗ (g, C).

Proof. First we prove a similar statement about LB, that LB2|C|+1(C) = MINTOTAL (C) for any C ⊆ S. We do this by way of induction.

The base case of |C| = 0 is trivial. Assume then this is true for any |C| ≤ M for some integer M ≥ 0, and suppose we have some C where |C| = M + 1. Then we have

Because we are only considering g ∈ UG(C), we have Cg,r ⊂ C, implying |Cg,r| ≤ M. Since 2 |Cg,r| + 1 and 2M +1 are odd, Theorem 5 and the induction step imply that LB2M+1(Cg,r) = MINTOTAL (Cg,r).

Using Definition 17 and Definition 13 from this completes the induction.

Now that we know LB2|C|+1(C) = MINTOTAL (C) for any C ⊆ S, Definition 17 and Definition 13 again can be used to achieve the desired result.

Theorem 8. Suppose we have an upper bound UB(C) for MINTOTAL(C). If for all g ∈ G there exists an ig such that Vig (g, C) ≥ UB(C), then UB(C) = MINTOTAL(C)

Proof. By Theorem 4, we may 'round up' any odd ig to an even ig + 1 and would still have Vig+1(g,C) ≥ UB(C). Hence w.l.o.g we may assume that all ig are even. Define I = maxg∈G ig, which must also be even. Theorem 5 lets us state that VI(g, C) ≥ Vig (g, C) for all g ∈ G, implying that

The construction of UB(C) implies the desired result.

These theorems are the basis for how we can determine an optimal starting guess and subsequently determine if a strategy is provably optimal:

1. Given a guessing game with secret set S, start with an upper bound UB(S), found by Definition 11. Recall that by Theorem 1, we can use any lower bound for V ∗ in conjunction with UB(S) to rule out which guesses could not be the starting guess of an optimal strategy. Theorem 6 gives us this lower bound for V ∗ .
2. Rule out any guess g for which V1(g, S) > UB(S), then rule out any for which V2(g, S) > UB(S), and so on. Do this until there is one guess left, or Vn(g, SW) ≥ UB(S) for all the remaining guesses (in which case we have multiple optimal starting guesses, as shown by Theorem 8), or up until calculating V2|S|+1 (by Theorem 7).

5 Application

We demonstrate using the general method and theorems of Section 4 on Wordle to test if our best Wordle strategy found in Section 3.2 by Definition 11 is optimal.

In Table 2, the best TOTAL for Wordle we found was 7920, so MINTOTAL(SW) ≤ 7920 where SW is the secret set of Wordle. We then applied the method summarized at the end of the previous section to determine the optimal starting word, as well as the true value of MINTOTAL(SW).

We present our results in Table 4. After applying V5, only one guess remained, SALET. This agrees with our strategy found in Section 3, in which the starting guess was indeed SALET. Although V5(SALET, SW ) = 7919, one further iteration showed that V6(SALET, SW) = 7920, so not only did we find the optimal starting word, but the strategy found in Section 3 is a provably optimal strategy for minimizing the TOTAL.

This process of filtering by Vi to determine MINTOTAL was repeated for FFXIVrdle and Mininerdle, all having shown that the strategy found was optimal.

6 Conclusion

This paper produced two main contributions. First, we used combined valuations to leverage information in determining good strategies for guessing games. Second, we presented several theorems that led to a general theory for mathematically proving a certain strategy optimal, thereby avoiding a complete and exhaustive search. As stated in the introduction, the concrete results produced in this paper were focused on Wordle, but the theory and methodology apply to any game that fits the definition of a general guessing game.

We further hope that these theorems can help in applications of guessing games [Focardi and Luccio, 2012] as well as add mathematical rigour to studying optimal context representations in the field of meta-reasoning [Filman et al., 1983]. Our results could also assist with developing predicates for practical guessing games [Thomason et al., 2016], or possibly help an AI to learn such predicates. Our theorems could be adapted to enable an AI to determine, out of a set of possible predicates, which are the most 'discriminatory'.

In terms of future work, we would like to see this work expanded to guessing games in much looser restrictions, for example in situations where the answering function is nondeterministic. We would also like to find estimating functions that converge to the true answer in fewer iterations, and are faster to compute.

Acknowledgments

We thank Abdallah Saffidine for his suggestions and input throughout the duration of this work.