Wordle-player - An optimal player for Wordle. Based on a rough understanding of information theory

Overview

Wordle Player

Just for fun, my attempt at making an optimal player for Wordle. Based on a rough understanding of information theory, and the idea that the best guess for a given turn is the one that gives you the most information.

Usage

wordle.py will feed you the guesses for a game of Wordle. If you run python wordle.py, you'll be launched into an interactive session, where the program outputs guesses and you just need to give it the outputs of each guess. Here's an example session where the word was PIANO:

$ python wordle.py
> TARES (15918 words)
? .y...
> ALOIN (999 words)
? y.yyy
> OMINA (5 words)
? y.ygy
> PIANO (1 words)
? ggggg

User input occurs on the lines starting with ?. Each . represents a letter that isn't in the word at all, a y represents a letter that is in the word but in the wrong place, and a g represents a letter in the right place. Along with the guess, the program outputs the number of words remaining that it can choose from.

The default wordlist has some pretty obscure words in it, which might not be valid for your game of Wordle. If so, just enter a blank line to fetch the next-best guess:

$ python wordle.py
> TARES (15918 words)
? .y...
> ALOIN (999 words)
? 
> ANOIL (998 words)
? 
> ANOLI (997 words)
...

You can also play with other word sizes using the -k flag:

$ python wordle.py -k 11
> PERCOLATING (37539 words)
? .yy.y.gggy.
> ENUMERATION (29 words)
...

Background: Entropy

From information theory, the entropy H(X) of a random variable X with n possible events is defined as:

H(X) = -sum{ P(x_i) * log2(P(x_i)) } for 1 <= i <= n

H(X) roughly means the amount of information* it takes to describe the outcome of X. For example, the entropy of a fair (50/50) coin flip is

H(fair coin) = -[1/2*log2(1/2) + 1/2*log2(1/2)] = 1.

But the entropy of flipping a horribly weighted coin is

H(unfair coin) = -[1/10*log2(1/10) + 9/10*log2(9/10)] = 0.47.

The fair coin takes exactly 1 bit to describe one of two outcomes, which makes sense. A flip of the unfair coin takes less information to describe because the same thing happens most of the time, and every now and then you'll need some extra bits to describe the more unlikely event.

*Measured in bits, since we use log2 - you can use any base you want, though.

Modeling a game of Wordle

Let's assume that every "target" word in Wordle is equally likely (drawn from a dictionary of k-letter words). When we play some word w, we get some outcome (in the form of each letter being green, yellow, or gray) - this will be our random variable X_w. By carefully choosing the word we play, we get different expected outcomes for X_w, and thus get different entropies. It's kind of like choosing the weights of our coin toss, but for a much more complex event. Our goal is to find the w that maximizes H(X_w), in order to make sure that when we observe the outcome, we gain as much information as possible.

To calculate H(X_w), we can check each possible target word in the dictionary and see what the outcome of playing w gets. There are 3^5 = 243 possible outcomes (different combinations of green, yellow, and gray), and each of these will get an associated probability depending on how many target words they map to. Calculating H(X_w) is then straightforward, we can use the formula from earlier:

H(X_w) = -sum{ P(r) * log2(P(r)) } for each possible outcome r.

Now we've chosen a word to play. When we play it, we'll observe the outcome of X_w. This will eliminate many words from our dictionary - we can throw out any word that wouldn't have lead to the observed outcome. Doing this iteratively should eventually lead to us either guessing the target word or leaving exactly 1 word in the dictionary.

Speed

This will work to find the optimal word, but it's an expensive calculation: given a dictionary with n words with k letters each, this will take O(k * n^2) time to run. I'm lazy so I wanted to find a fast approximation.

Instead of playing an entire word at a time, we can play a single character c in position i and observe its outcome Y_ci. Then, we can estimate H(X_w) by adding H(Y_ci) for each character of w. Now, this would give us exactly H(X_w) if each of Y_ci were independent random events, but this obviously isn't the case - for instance, there are way more words that start with SH___ than words that start with HS___. (Following this strategy to calculate H(X_w), the optimal starting word I got was SAREE, which isn't a great starter because it has two of the same letter. Playing E anywhere is a high-entropy play, because it's a very common letter.)

So instead, we can use this estimate as a filter, and just calculate the actual value of H(X_w) for the top a% of words. Using this strategy with a = 3, the optimal starting word I got for 5-letter words was TARES. I precomputed all of these for between 4 and 11 letters and saved them in starting_words.pickle. The wordle.py program uses these by default.

Pseudocode

k := number of letters per word
D := dictionary of k-letter words
a := the retry percentage we choose
H := the entropy function, which takes a distribution and returns its entropy

function guess(W) {
    n = size of W

    -- H(Y_ci)
    HY := empty map of (char, number) -> number
    for each c in the alphabet:
        for each i in [0, k):
            Y := map of possible outcomes (green, yellow, or gray) -> 0
            for each t in W:
                r := the outcome of playing c in position i on target word t
                Y[r] += 1/n
            HY[(c, i)] = H(Y)

    -- Estimated H(X_w)
    EHX := empty map of string -> number
    for each w in D:
        EHX[w] = sum of HY[(w[i], i)] for i in [0, k)
    
    -- Eligible words
    D' := a% of words in D with the highest EHX[w]

    -- Actual H(X_w)
    HX := empty map of string -> number
    for each w in D':
        X := map of possible outcomes -> 0
        for each t in W:
            r := the outcome of playing w on target word t
            X[r] += 1/n
        HX[w] = H(X)
    
    return the word in D' with the maximum HX[w]
}

References

Owner
Neill Johnston
Neill Johnston
user friendly python script who is able to catch fish in the game New World

new-world-fishing-bot release 1.1.1 click img for demonstration Download guide Click at latest release: Download and extract bot.zip: When you run fil

297 Jan 08, 2023
A small module for creating a card deck, used for making card games

card-deck This module can be used to create small card games such as BlackJack etc.. To initialize the deck, use: Deck() To shuffle the deck, use: Dec

4 Dec 31, 2021
Synthesizer based on Conway's Game of Life

Conway Synth Synthesizer based on Conway's Game of Life Trying to avoid step sequencer fashions that have been done before and basing it on actual cel

Giacomo Loparco 4 Mar 15, 2022
This is a basic virtual quiz game using opencv-python

Basic Virtual-Quiz-Game This is a basic structure of a virtual quiz game using opencv-python. As the camera window opens up we can see the questions a

2 Dec 11, 2021
Algorithm to solve Wordle correctly 100% of the time within 6 attempts.

WordleSolver © Zulkarnine, 2022. Algorithm to solve Wordle 100% of the time within 6 attempts. You can go ahead and run main.py to run it for all 2315

Zulkarnine Mahmud 69 Dec 11, 2022
Disables the chat in League of Legends for Windows.

Disables the chat in League of Legends for Windows. If you simply can't stop yourself from typing LeagueStop will play KEKW.mp3 each time you try. The sound will stack & becomes horribly annoying.

1 Nov 24, 2021
The Turtle Race Game built in Python with Turtle module.

Turtle Race Game The Turtle Race Game built in Python with Turtle module. Installation If you don't have Turtle module on your computer. You can downl

Aytaç Kaşoğlu 1 Nov 09, 2021
WORDLE Helper and Solver

WORDLE Helper and Solver There is a pupular game around WORDLE The game could be hard for non-English speaking people so I started to think of a helpe

1 Jan 24, 2022
XPlaneROS is a ROS wrapper for the XPlane-11 flight simulator.

XPlaneROS XPlaneROS is a ROS wrapper for the XPlane-11 flight simulator. The wrapper provides functionality for extracting aircraft data from the simu

AirLab Stacks 26 Dec 04, 2022
🍦 Cheat for cs:go written in Python.

Cs::Fuck 🍦 Cheat for cs:go written in Python. You can show a video here: https://vimeo.com/642730650 Feature. TriggerBot Glow Esp NoFlash Setup. 0. p

Ѵιcнч 10 Sep 23, 2022
Dontdie-minecraft - A python program that causes your computer to bluescreen whenever you die in Minecraft

Don't Die - A Python Program A python program that causes your computer to blues

3 Apr 19, 2022
Replicating Minecraft World Generation in Python

Minecraft World Generation in Python This is an attempt to replicate Minecraft world generation in Python. This is part of an article published on Med

Bilal Himite 159 Dec 19, 2022
An automation bot to play Myuu Discord game

Auto selfbot Myuu is a self Discordbot, meaning it will use your TOKEN to logged as your account and take commands from yourself to play the game.

6 Dec 15, 2022
Dueling Platform for Competitive Programming. Learn through Games.

CP-Dueling Dueling Platform for Competitive Programming. Learn through Games. Setting Up Minimum Python version needed = 3.9.9 Install Virtualenv and

Bhavesh 3 Feb 07, 2022
Wordle-Python - A simple low-key clone of the popular game WORDLE made with python and a 2D Graphics module Pygame

Wordle-Python A simple low-key clone of the popular game WORDLE made with python

Showmick Kar 7 Feb 10, 2022
This is a simple game made using pygame.

Ball breaker This is a simple game made using pygame game view The game view have been updated wait for the new view to be uploaded Game_show.mp4 Lear

Rishikesh Kumar 3 Nov 05, 2021
You want to uto-update your private minecraft client? Give this to developer and enjoy!

minecraft-hack-installer You want to uto-update your private minecraft client? Give this to developer and enjoy! Steps to do: Install libraries: pip i

EuropeStudio 1 Jun 03, 2022
The game company we work for has two events that we want to track: buy an item and join a guild. Each of them has metadata characteristic of such events.

The game company we work for has two events that we want to track: buy an item and join a guild. Each of them has metadata characteristic of such events.

Caro Arriaga 1 Feb 04, 2022
Simple Game created using Python & PyGame, as my Beginner Python Project!

Space Invaders This is a simple SPACE INVADER game create using PYGAME whihc have sound and lot's of keyboard functions. Prerequisites More Experience

Gaurav Pandey 2 Jan 08, 2022
Snake game mixed with Conway's Game of Life

SnakeOfLife Snake game mixed with Conway's Game of Life The rules are the same than a normal snake game but you have to avoid cells created by Conway'

Aidan 5 May 26, 2022