foreign
welcome back everybody
our second speaker in this block this
morning is the inevitable uh inimitable
uh Chris neugebauer indomitable I'm not
sure
unavoidable yes
um he is here today to speak to us about
uh taking a swim in your kitchen sink
while swearing no I'll leave it up to
him to explain what's going on everyone
please welcome Chris nog about at the
stage hello
all right
uh I've never been described as
inevitable before
that is quite a long word given the the
topic of today's talk today we're going
to be talking about five letter words
and I don't know how many letters are
inevitable at the moment
um yeah so uh before I begin uh Wordle
is owned by the New York Times I'm not
from the New York Times uh I will be
using their trademark quite a bit during
this talk it's uh
unavoidable given the subject matter
um so today we are going to talk about
uh a few things we're going to talk
about uh Wordle itself we're going to
talk a bit about concurrency in Python
and where things are at with that and
also some things that are related to
either Wordle and or concurrency
um so I play wordal most days uh
everyone else play Wordle
wait who here is just here to watch me
speak
who's here for concurrency stuff
okay right so all the people who are who
are here for either of the two things in
the middle will be slightly disappointed
um so mediocre talk about Wordle a Medio
could talk about concurrency hopefully
two things together will be interesting
I play wordal most days I play in hard
mode I'm comfortably average at it
um I usually take three or four guesses
uh here's a picture from me playing on
Wednesday where I managed to get it in
two so I'm just making myself look
better than I am my starting word these
days is tears which I know for a fact is
not a possible answer in Wordle as
you'll see later it's what my solver
thinks is the best possible starting
word and who am I to argue with code
that I've written
uh my old starting word was irate uh if
you play Wordle you'll know that that
was an answer within the last month uh
which is really disappointing because I
started using the word Tears by then
um anyway there's no actual spoilers in
this talk I wrote most of the slides
earlier this week I might have looked at
wordlebot around then I wrote all the
slides before I knew what today's word
was and I've already forgotten what
today's word was and also I think it's
important to mention this talk probably
won't change how you approach Wordle as
a human being which I believe most of
you are Beno
um yeah exactly
um I'd hate to spoil your enjoyment of a
thing that's generally quite a pleasant
thing that some of us
um
derive some level of enjoyment from
so uh I don't think Wordle are solving
world as a human uh resembles solving
word or like a computer would because
we're really not good as human beings at
reasoning about a large amount of data
in our heads and what do I mean by a
large amount of data well according to
the uh yet another word list word list
that uh that a number of word games use
there's
12036 ish English language five letter
words
the solver that I use uses this word
list and even if you filter out obvious
plurals which uh Wordle itself does for
its answer list there's still in excess
of
8 000-ish words it's really hard to keep
that many words in your brain and reason
about that sort of problem space now
even after you make a good first guess
which most people will have a good first
guess there's there's normally somewhere
between 60 and 500 Words left in the
problem space to make your last five
guesses with and
even with that in mind it's really
difficult to memorize which 60 to 500
words are going to be left in in the
list because every word will split that
that set of English language words
differently and so the way that most
people go about solving Wordle is to uh
basically just just do what everyone
else does
um
and just to give you an idea of how well
we can see how everyone else plays at
Wordle uh the New York Times uh sometime
after they bought out the the game they
started collecting statistics because
they're a tech company and they
collected statistics and they made a
site called wordlebot which is both a
Wordle solver itself but also a site
that will give you player statistics for
playing Wordle and if you check in on
wordlebot you get some interesting
information particularly uh if you're an
Australian person or somewhere on this
side of the International Date Line you
can join in on worldbot basically the
moment people have started playing this
is a screen grab from wordlebot on
Wednesday morning uh here in Australia I
took it at six a.m a dedication to
Preparing slides and so really you've
only got the early Rises and people from
New Zealand here included in the stats
and you can see that most people who
play World earlier in that that 48 hour
time window
they they pick uh edu as their first
word
um why do people pick a year as their
first word uh it's because it's got a
lot of vowels in it and people think
that figuring out which vowels will help
them solve word or quickly and this is
sort of a strategy that people latched
on to very very early uh in the in the
days of Wordle
if you take a screen grab at 6am my time
I live in California at the moment so I
play wordal 17 hours later in California
than I would in Australia and you can
see that the most popular word is least
a jerk is still up there it's number two
um
but what do you think has changed
between uh between those 17 hours
okay you've got everybody who subscribes
to New York Times which nobody does in
Australia uh who's looked at wordlebot
and know that least is a better word
than endure because the New York Times
says so and they use it as their
starting word New York Times actually no
longer says that they say slate is the
best starting word and that's now number
three
um
and so once you make your first guess
generally it's really just down to
remembering a few good second guesses
remembering some patterns and then the
further you get into the game it's
really just down to how much you can
make educated guesses about
um
about what the answer is so yeah we we
really don't have the mental capacity to
play word or like a computer at all uh
Wordle can play a lot closer to
optimally
um Wordle is a guessing game and and the
way to play a guessing game is to make a
guess of uh I guess that we think will
reveal the most information about a
solution space
to a problem and thankfully information
is a Lo uh is a formal term and we can
use that formal term to figure out how
to build a solver for for Wordle but I'm
not going to build a solver for word or
firstly I'm going to discuss a simpler
game to play which is the guessing game
where you have to guess a number between
one and a thousand and the game will
tell you if the answer is higher or
lower so what's our first guess
right you guess the number in the middle
and then immediately the solution space
gets halved and then you can guess the
middle of that space and you'll have the
solution every single time
and with this game you can play
optimally and you know like unless you
accidentally happen on one of those
answers you will know exactly how many
guesses it will take you to get to the
correct answer
so so back to this idea of information
every time you halve the solution space
the the base two log of the size of the
solution space reduces by about one
um if there were 1024 spaces it would
Reduce by one uh every single time so we
described this halving of the solution
space as gaining one bit of information
so the idea of expected Information Gain
Is that the base two log of the solution
space less the expected base two log of
the solution space after guess is your
expected Information Gain so for our
guessing game that expected Information
Gain is always going to be basically one
bit
so what about Wordle
we can we can sort of apply these
theories to Wordle but the difference is
with Wordle you can't actually play
optimal you can't be guaranteed to play
optimally uh the same guess is going to
reveal different amounts of information
depending on what the actual answer is
so the best thing that you can do is
make an estimate and so we can also
figure out how good our estimate needs
to be we can see that the solution space
for
um for the set of five letter words in
English language is about 14 bits and
that means that we need to reveal about
2.33 bits of information per guess which
means
um somewhere between splitting the
solution space into a quarter to an
eighth somewhere in that sort of space
you need to do each guess in order to
get in guess the solution in six guesses
or less so back to my starting starting
word here is a worked example from a few
weeks ago uh I took my my solving codes
uh preferred first word and I got a
green tea and a yellow a
so if I guess the word today depending
on the information revealed to me I
might end up with three potential
answers or I might end up with only one
potential solution remaining so that's
13 potential answers in that solution
space it gets split up into seven groups
and so the expected number of solutions
I have after the guess is going to be
1.86 words and that's a gain of 2.81
bits of information which is better than
the 2.33 we need
on the other hand if I had guessed the
word Titan I'll still end up with either
three words or one word remaining but
there's far more ways for me to end up
with just one word uh than three and so
that's 13 words split up into nine
groups which means I have an expected
number of solutions of 1.44 which is a
gain of 3.17 bits of information
so that gives us a strategy for playing
Wordle the idea is to pick the word with
the smallest expected solution space
size uh make a guess with that word and
then eliminate all those words from a
set of answers and repeat that and
repeat that and repeat that until only
one word remains
so let's look at some python code this
is a python conference after all here's
what the main Loop of my Wordle solver
looks like we make a guess and then we
classify the guess that we've made
against the actual Target word and then
we filter the solution space against the
classification that we get just as an
aside I structure a lot of my code like
this with a high level with a high level
top level function that can be split out
into easily testable functions only one
of these things is going to be subjected
to concurrency later on which is uh
which is Handy so let's take a look at
the second of those two steps uh this is
a classification routine I'm using in a
num to describe whether the letter is in
the solution or not and numbers are
great you should use them
um it says whether the letter is yellow
or green and then it just returns a five
Tuple of these classification objects
which can then be used as keys in a
dictionary you'll see why being used
these used whether why these should be
used as keys in a dictionary uh that's
important kind of later on which is is
it here no it's not uh here's the
implementation of the filtering function
it takes those classification uh five
tubules and it runs them against every
word in the solution space and it
returns only the words in the solution
space that match the classification
I've written this solver three times and
and every single time I've written a a
four else block here
um
with like I've had the opportunity to
decide not to do that and it's always
been the right idea as far as the code
I've written
um sometimes it's justifiable
so here's the point where we actually
make a guess
so the first function that we're going
to try to do to make guesses is just to
Loop through the space of possible
guesses find the potential gas with the
lowest potential score which is the the
number of
um the number of groups of words also
the average number of answers in each
group there's no tie break facility here
which means it might not always make an
ideal guess you'll you'll see the effect
of that later on
and then the scoring function there's
there's another for Loop in that we go
through every potential answer classify
our guess as if the potential answer is
the actual answer and then see how that
guess would split the solution space so
the more groups the smaller the solution
space is likely to be after the guess
and we just average that for every
potential answer
so uh I guess the first question is does
this approach actually work well does
this solve the problem that we have so
I'm using the target word snake and you
can see that it solves the word or in
Easy Mode in five guesses a lot of these
words are really really obscure and
probably not ones that I would guess
personally uh spelled means to Splinter
or chip
uh before I move on there's one code
simplification that I suggest using this
is what my actual code does uh here's
our make guess function it's a lot of
python code it can be Rewritten like
this which has the nice effect of
running the outer loop in C code it
makes things somewhat but not
importantly faster so there we go we can
solve Wordle in about three minutes on
my M1 MacBook here so can we do better
in Python
so the first place you might start is
looking at thread pools threads are
chains of execution that exist within
the same process segment on your system
here is our make guess function and
again we have this Loop and we do
exactly the same thing every single time
without modifying any data structures
and then the inside of that Loop is also
quite resource intensive you there's
there's two nested for Loops
um
so there's that and so we can we can
pull this out and this is where the
concurrent Futures Library comes in in
Python it is often my first Port of Call
for any sort of asynchronous programming
even before using async await
um it's I find it somewhat easier to
conceptually put things together that
way your mileage may vary uh it's
definitely much easier than writing raw
threads in Python if you have a problem
that's amenable to threading so you can
think in terms of of calling functions
and waiting for a result rather than
working with things like locks which I
think are a bit tedious and and prone to
getting those things wrong uh so here's
what our make guess function looks like
with a thread pool
we submit each potential guess to the
thread pool which returns a future which
is an object that will eventually hold
the result of the guests that we made
and then we're going to associate that
future with the word that we use to
submit it so we can actually get a score
back and know which word it was that
generated the best result we're still
using that Min built in that I used in
that that code Improvement we grab each
result as it comes out of the thread
pool complete and by you we do that by
using the the as completed function
which is in the concurrent Futures
Library
so we can set up a thread pool with
eight workers I have only eight cores in
my machine so we won't get more than an
eight-time speed up
and we can go from our looping code
which takes 185 seconds to make its
first guess oh uh Vemma by the way a
westphalian vigilante Society
and here's our threaded code which takes
181 seconds to make a guess
uh why
the Gill yeah
um so this is where I point out that
python has a global interpreter lock uh
the global interpreter lock is a it's a
it's a lock it prevents multiple threads
from having access to any piece of state
that is held by the python interpreter
um in practice this means that only one
python thread can execute it once
I think it's actually quite interesting
to note here that the guild basically
prevents concurrency but it's very very
very efficient at preventing concurrency
we don't actually get any slowdown from
various threads having to acquire and
release the guild here we it runs in
basically exactly the same amount of
time it's like five seconds difference
that difference is down to me running
Chrome on my computer at the same time
don't do that if you're trying to do
scientific analysis of your your speed
up that's a really bad idea
um
so are our threads useful in Python with
with the girl uh yes if you have
parallel code that's not written in
Python and you can release the Gill on
each thread if your parallel code is IO
bound but only up to a certain amount
only to a certain extent async is much
better for that if you can run your code
on Pi Pi and things will be better it's
really not good for writing a wordal
solver uh so the next thing we can try
is a thing called process pools so
processors are spaces of execution that
are managed by your operating system and
they have their own memory they don't
share memory between uh between multiple
processors uh in practice it's really
only possible to communicate between
processes over things like sockets or
files or specially declared shared
memory that your operating system
manages for you the good news about
processes is that there's one Gill per
python process so if you have multiple
processes you only uh have you have one
deal per process and you should actually
see some speed up and if you're using
the concurrent Futures Library
the only real difference between using
threads and processors is defining what
sort of pool you use so I'm using a
process pool executor instead of a
thread pool executor
and to remind you our single threaded
code talk 185 seconds to make a guess
with processpool executor it it took 38
seconds which is actually a speed up
which is cool it's about 4.8 times
so what if we wanted to see if we can
get more speed up well we can change
this Max worker's parameter to eight uh
from 8 to 16 and it goes from 38 seconds
under eight workers to more than 38
seconds this again is because I have
I have only eight cores on my laptop so
my laptop only has eight cores which is
obviously the maximum speed up I can get
16 processors can't run on eight cores
at once but I only got 4.8 times speed
up uh with uh with switching to a
process pool
um this is where I go into our uh into
our undergraduate computer science
curriculum and talk about amdel's law if
you know about that you can you can
check it off now but for everyone else
the quick explanation is that a
programming task can be split into Parts
the Wordle solver has three you can
score every word you need to do that you
need to find the minimum by looking at
every single word and then you need to
filter the list of solutions the scoring
task can be split up into chunks and you
can run all those bits in parallel
the bits that run in sequence cannot be
run in parallel because they run in
sequence and that establishes a limit on
the amount our program can be sped up
but also in reality there's a bunch of
work the operating system needs to do in
order to coordinate all these processes
to deal with shared memory those sorts
of things that gets added into our
execution time and that coordination
actually increases as we start to add
more processes beyond the number of
cores that we have on our system and
that's where that extra slowdown came on
so maybe there are other bits that we
can run in parallel maybe we can run the
filtering operation
um it turns out that really just doesn't
do much it actually in fact slightly
slows down things because there's not a
whole lot of well there's actually too
much inter-process communication going
on in that filter operation
so to get a task from one process to
another it actually has to be explicitly
communicated and that takes time that's
this sort of os coordination thing I
showed in that diagram earlier uh
processes they work best process pools
work best if you can have longer running
tasks that don't need to communicate
very often and that gives us another
insight into how to make things a bit
faster
so instead of submitting thousands of
relatively small tasks into the process
pool if we spend some time actually
breaking up our problem space into as
many cores that we have and running
those sequentially we can solve the
problem locally within each of the each
chunk of the problem space and then find
the global solution afterwards
so we're actually just making use of the
the make guess with Loop function that
we wrote earlier and we're only doing 16
pieces of inter-process communication
instead of the 24 000 pieces of
inter-process communication that we were
doing with the obvious way of chunking
things up and so here's our version
without chunking up the inputs this is
the one with lots of inter-process
communication because we're submitting
small tasks uh 24 000 small tasks into
16 no 12 000 small tasks into the
process pool
um it takes that long uh here's the
version where we're only doing eight
submissions into the process pool you'll
also notice that the opening word is
different this is because our
tie-breaking behavior is not really
deterministic it really depends on what
thing comes first out of the process
pool so instead of Tears we have hairs
um it is faster by a noticeable margin
uh Sports by the way it means brittle
so uh process pools they are good if you
have a small number of large but CPU
bounded tasks it takes a lot more work
to set these up efficiently you need to
think about how you split your problem
space up such that you reduce the amount
of inter-process communication you have
this is different to how you would deal
with threads in a language like C or
Java and it's reasonably good for
writing a word or solver I included the
word async in the title of the talk
um
that's only because I need the third
five letter word that was relevant to
concurrency
um
it has it has the it has the same
problem as thread pools in that
everything runs within the same um uh
within the same process space as python
so you'd always end up with uh you'd
always end up with something related to
the Gill if you had a different event
Loop that did allow for thread based
concurrency if you dealt with process
based concurrency well you're dealing
with a whole lot of language level
complication that would make things
slower
finally let's talk about no Gill because
as I mentioned python has a gill it's
always had a girl and people have always
wanted the guild to go away because it
gets in the way of using threads
efficiently there is a new effort called
nogill which is about the fifth effort
that I've seen in the last 10 years and
it seems to be making some level of
progress
um
in terms of making like using
concurrency in Python without the guild
actually usable you can install no Gill
very easily if you have pione on your
machine just go power and install nogill
3 9 10-1
it is only supported in Python three
nine
um
this is important because in Python 311
uh the there's a team at Microsoft
running the faster C python project and
the faster C python project did a lot of
work to make C python faster and they
actually succeeded and all their work
landed in Python 311. so our first guess
in Python 39 under nogill in a single
threaded uh
um a single threaded sort of context uh
took about 40 seconds longer to run than
it did in Python 311 so our first useful
lesson like if you need to make your
code faster and you're still running
python 310 or earlier
upgrade to python 311 it will get faster
for free basically
um
what takes even longer than running our
single threaded version in nogill is
running with a thread pull executor
um
which so instead of taking about the
same amount of time as a single threaded
version as it took in the Gill uh with
the Gill it now takes about one to six
1.6 times longer than it did in a single
threaded execution as I was mentioning
earlier the Gill is actually really
really really efficient and this is why
all these Gill removal projects have
sort of faltered over the years
um there's not really any slowdown from
acquiring releasing the Gill in in
normal python on the other hand once you
start adding a lot more locks and things
like finely grained thread safety into
the the memory allocator in Python
things get really really slow
um
1.6 times slower as it turns out you may
be asking whether or not nogil is worth
it from this one example I've given you
first up
yeah slowing down only 1.6 times is a
huge Improvement on previous versions of
trying to remove the Gill especially
since the authors actually have an idea
of how to make this get even faster
secondly there are actually demos on on
the nogill readme that demonstrates a
CPU bound function that parallelizes
basically with the number of cores you
have in the number of threads you give
it it's a really contrived example it
doesn't touch any data structures but it
demonstrates that you can run threaded
python code in AC Python and get
unbounded speed up which is which is
very impressive there is a pep to remove
the Gill There is a guarantee of
sponsorship to do the real work to make
it faster I would not be surprised if
the Gill goes away in the next three to
five years and that would be really
incredible
so to finish up we're finished talking
about concurrency in Python let's get
back to talking about Wordle which is
what I'm actually interested in firstly
all the examples I've shown you have
been in Easy Mode I play in hard mode
it's probably interesting to see what it
would take to make the solver work in
hard mode uh it's really just a matter
of changing one line at the bottom of
the main Loop very small so we're now
instead of guessing with the entire set
of English language words we're just
solving with the set of answers that we
get after each step and it very slightly
changes the guesses it makes it
significantly reduces the last the
amount of time the subsequent guesses
beyond the first
takes that's because there's fewer words
to choose from it takes less time to run
uh cpal is the parts of the calyx of a
flower
and finally how good is this solver at
actual Wordle before the New York Times
took over the full set of answers to
Wordle was visible in the JavaScript
source of the game so you could you
could basically strip that out and and
use it as an answer list there are
copies of this all over the Internet
because it's the internet
uh there's about 2 300 words in that
answer list and we can run our solve
against all of them firstly to establish
a baseline let's see what the behavior
is like if we just guess randomly from
the set of all possible solutions it
solves the game correctly in about 90
percent of the time
and there are three words that that
trigger a bug I think this is just due
to their not being an answer in the
guest list and I haven't just done
enough error correction in the code to
account for it properly
code first talk
um in Easy Mode uh there's those three
bug cases that we saw in the random
guessing thing it successfully solves
all but one puzzle in six guesses or
less and it does well in more than uh it
does well more than half of the uh of
the words in four guesses so
I basically play about as well as my
solver does personally which is cool uh
the one word that it can't guess is
Joker it takes seven guesses uh via a
bunch of really quite obscure words
including aflage which is a type of
irrigation system originating in Oman
we can run the same exhaustive solver in
hard mode as well and it fails to solve
in hard mode a lot more than an easy
mode which you've probably experienced
if you play in hard mode yourself
there's a lot of cases where you
accidentally get locked into a sequence
of equally likely answers where an
impossible answer you know might split
up the options so for example this this
word curvy here if you could make the
word if you could guess the word venz on
the third guess you would guarantee a
solution for those curvy Kearney Kerdi
or you get a choice between curly and
Curry so you get one or two guesses you
can't use vans in hard mode because it's
already said that S and E aren't in the
solution so you can't use that
um and so we failed to solve in about 91
cases now uh there are four words and
unless again bugs I don't know unsure
what's going on there it manages to
solve about 96 of cases in hard mode uh
finally one small optimization you can
make to the word list which is to remove
plurals the nyt removes words that end
in s or ES if they're plurals or
transitive verbs it changes the opening
guess from tears to perch which means
lively and we now solve in 97.5 percent
of cases but now there's seven words
where it's uh where the answers aren't
in the guest list
so to recap it's reasonably easy to make
a good word or solver it was a fun
exercise I encourage you to do it or you
can copy my code whichever you prefer
threads aren't great for Wordle style
problems but process pools are my
sources get another word list uh which
you can download to make your own word
games the original version of Wordle by
Josh Wardle for the actual answers list
uh the uh introduction to the wordlebot
algorithm from The New York Times They
explain how all of that works and if you
want to read my own code and point and
poke holes at it
it's available on my GitHub thanks
everyone
thank you