Selection of guesses

The task described in the discourse discussion mentioned in the previous tutorial was to determine an optimal first guess in Wordle, using the criterion of minimizing the expected pool size after the guess is scored.

First attach the packages that will be used

In the Wordle game shown on the Wikipedia page the first guess is "arise".

Before the guess is scored the size of the target pool is 2315. The score for this guess in this game is 01011 as a base-3 number or 31 as a decimal number. Of all the targets in the target pool, only 20 will return this score.

To verify this, first create a GamePool from the wordle targets.

Then determine the index of "arise" in the guess pool.

Here, findall returns a vector of all positions in wordle.guesspool that return true from the anonymous function checking if the argument, x, is equal to ('a', 'r', 'i', 's', 'e'). The only function checks that there is only one such index and, if so, returns it.

The anonymous function to compare an element of wordle.guesspool to ('a','r','i','s','e') can be written more compactly as ==(('a','r','i','s','e')).

The score for the guess "arise" on the target "rebus" is 31 as a decimal number.

Next, check how many of the pre-computed scores in the 106th column of wordle.allscores are equal to 31.

A view provides access to a subarray of an array without copying the contents. In this case the subarray is all the rows (the : argument in the rows position) and the 106th column. The comparison function ==(31) will return true or false, values that will be converted for 1 or 0 for the summation function sum. Thus sum(==(31), v) returns the number of elements of v that are equal to 31.

The distribution of scores for a guess

In this case the first guess reduced the size of the target pool from 2315 to 20, after this guess was scored. Ideally we want a guess to reduce the size of the target pool as much as possible but we don't know what the score is going to be. However, we can evaluate the distribution of pool sizes that will result from a particular guess.

To do this we "bin" the scores for a guess on the active targets into the 243 possible values for an NTuple{5,Char}.

The i'th element of this vector is the number of targets that will give a score of i - 1 for guess = wordle.guesspool[106], which is "arise"

The most common score is 0 which is returned for 168 of the 2315 targets currently in the target pool.

Collecting the bin sizes and the corresponding scores in a data frame allows us to sort them by decreasing count size and eliminate the scores that give counts of zero.

A bar plot of the bin sizes, ordered from largest to smallest is

The Wordlegames package provides two algorithms of choosing a guess based on the distribution of the scores.

function optimalguess(gp::GamePool{N,S,MaximizeEntropy}) where {N,S}
    gind, xpctd, entrpy = 0, Inf, -Inf
    for (k, a) in enumerate(gp.active)
        if a
            thisentropy = entropy2(bincounts!(gp, k))
            if thisentropy > entrpy
                gind, xpctd, entrpy = k, expectedpoolsize(gp), thisentropy
            end
        end
    end
    return gind, xpctd, entrpy
end

function optimalguess(gp::GamePool{N,S,MinimizeExpected}) where {N,S}
    gind, xpctd, entrpy = 0, Inf, -Inf
    for (k, a) in enumerate(gp.active)
        if a
            thisexpected = expectedpoolsize(bincounts!(gp, k))
            if thisexpected < xpctd
                gind, xpctd, entrpy = k, thisexpected, entropy2(gp)
            end
        end
    end
    return gind, xpctd, entrpy
end

The first method is to maximize the entropy of the distribution, which is an information-theory concept that measures how "spread out" the distribution is. It depends only on the probabilities of the scores, not on the scores themselves. The base-2 entropy, measured in bits, of a discrete distribution with probabilities $p_i, i=1,\dots,n$ is defined as

$$H_2(X) = - \sum_{i=1}^n p_i\,\log_2(p_i)$$

The Wordlegames package exports the entropy2 function that returns this quantity from the current counts.

function entropy2(counts::AbstractVector{<:Real})
    countsum = sum(counts)
    return -sum(counts) do k
        x = k / countsum
        xlogx = x * log(x)
        iszero(x) ? zero(xlogx) : xlogx
    end / log(2)
end

entropy2(gp::GamePool) = entropy2(gp.counts)

or, equivalently

The

... do k
   ...
end

block, called a "thunk", in this code - yet another way of writing an anonymous function - is described later.

Roughly, the numerical result means that the distribution of target pool sizes after an initial guess of "arise" is, according to this measure, about as spread out as a uniform distribution on 56.5 possible responses.

The second method is to minimize the expected pool size after the guess is scored.

By definition this is the sum of the bin size (or count) for each of the bins multiplied by the probability of the target being in the bin. But that probability is the bin size divided by the total number of active targets. Thus the expected pool size after the guess can be evaluated from the bin sizes alone.

function expectedpoolsize(gp::GamePool)
    return sum(abs2, gp.counts) / sum(gp.counts)
end

which is available as expectedpoolsize

This is a measure of how successful an initial guess of "arise" will be. On average it will reduce the target pool size from 2315 to 63.73.

The best initial guess?

We can choose an initial guess (and, also, subsequent guesses) to maximize the entropy of the distribution of scores or to minimize the expected pool size for the next guess.

For both of these criteria, a slight modification on "arise", exchanging the first two letters to form "raise", at index 1535, is a bit better than "arise".

It turns out that "raise" is the best initial guess for both of these criteria, if we restrict outselves to guesses from the initial target pool.

One of the parameters of the GamePool type is the method of choosing the next guess, either MaximizeEntropy, the default, or MinimizeExpected,

allowing for automatic game play.

That game ended suspiciously quickly but notice that, after the first guess, "raise", is scored as 🟩🟫🟫🟨🟨 in tiles or 166 in decimal, the target pool size is reduced to 2,

giving a 50% chance of a correct second guess.

In the case of ties like this the target with the lowest index in the targetpool is returned. This strategy can result in long series of guesses trying to isolate a single letter if that letter is toward the end of the alphabet

but it is not clear that any other strategy will be more successful across all possible targets. (This target did occur on the official Wordle web site in March of 2022.)

To play by the MinimizeExpected strategy requires specifying this as the guesstype when creating the GamePool.

There are no differences between the two strategies in these games.

However, if we play all possible games using each of the two strategies and count the number of guesses to solution we can see that the two strategies do not always give the same length of game.

For example,

is different from

The mean and standard deviation of the game lengths are smaller when maximizing the entropy than when minimizing the expected pool size.

The counts of the game lengths under the two strategies and a comparative barplot show the shift toward shorter game lengths when maximizing the entropy.

Wordle-like games

Wordle has spawned many similar games, one of which is Primel, where the targets are 5-digit prime numbers. Because leading zeros are not allowed in these primes, the targets are prime numbers between 10,000 and 99,999.

To play a game with a random, but reproducible, target, we initialize a random number generator and pass it as the second argument to showgame!.

The size of the target pool is larger than for Wordle

but the number of possible characters at each position (9 for the first position, 10 for the others) is smaller than for Wordle, leading to a larger mean number of guesses but a smaller standard deviation in the number of guesses.

As for Wordle, the strategy of choosing guesses to minimize the expected pool size is less effective than maximizing the entropy.

Some Julia syntax used in this code

Several Julia syntax features have been used in the code for this tutorial. For example, the code block defining gamelengths is a let block. This is similar to a begin/end block in that it groups multiple expressions, including assignments, so that they function as a single expression evaluation. The difference between let and begin is that assignments within a let block are local to the block.

For example, allcounts is given a value within that block because it is used in several places when creating the DataFrame but it is not needed outside that block.

Notice also the expressions like get!(entropy, k, 0). This is extraction by key from a collection, like entropy[k] or, equivalently, getindex(entropy, k) except that it provides a default, 0 in this case, if there is no key k in the collection. Furthermore, it modifies the collection by inserting the default value for key k.

An ellipsis, "...", is used with arguments as in string(wordle.guesspool[1535]...). This use is called a "splat" (and there is another use of an ellipsis called a "slurp" - the designers of this language are very serious-minded folk). As a "splat" the ellipsis expands an argument such as a vector or, in this case, the tuple ('r','a','i','s','e') to multiple arguments, in this case, 5 Char arguments.

Another fun name for a construct is a "thunk", which is a way of specifying an anonymous function. For example there are two methods defined for the entropy2 generic

function entropy2(counts::AbstractVector{<:Real})
    countsum = sum(counts)
    return -sum(counts) do k
        x = k / countsum
        xlogx = x * log(x)
        iszero(x) ? zero(xlogx) : xlogx
    end / log(2)
end

entropy2(gp::GamePool) = entropy2(gp.counts)

In the first method we wish to evaluate $-\sum_{i}p_i\,\log_2(p_i)$ which is sometimes called an xlogx function. There is a sum(f, itr) method where f is a function and itr is an iterator, such as an AbstractVector. In this case we want a function that evaluates x = k / countsum then xlogx(x) but xlogx requires some care. If x is zero, the result should be zero but of the same type as x * log(x) for non-zero x. That's why x * log(x) is evaluated first - to get the value type. It will return NaN for x = 0, which is then converted to a zero but of the type that is consistent with the other values of xlogx.

For example, to evaluate the base-2 entropy for the initial guess in the BigFloat extended precision type, we convert from

to

The second method definition for entropy2 shows the compact form for defining "one-liner" methods. It is a common idiom to have one method for a generic function that "does the work" and others that simply re-arrange the arguments to the form required by this "collector" method.