Ещё одно решение игры Wordle на Python25.01.2022 22:02

В начале 2022 года мир захватила головоломка Wordle и почти сразу стали появляться варианты решения. На Хабре уже появилось описания двух вариантов решения, но они мне не понравились, поэтому я изобретаю свой собственный велосипед. Ссылки на предыдущие решатели:

1) https://habr.com/ru/company/skillfactory/blog/645653/ — перевод решателя от Mickey Petersen, написано на идеальном Питоне, использует статистический анализ букв английского алфавита и вполне успешно справляется с задачей.

2) https://habr.com/ru/post/647391/ — перевод решателя от Tom Lockwood, который решает англоязычную игру в 99,4% случаев. Автор исследовал внутренности игры и постарался максимально использовать полученную информацию о возможных загаданных словах и возможных вводимых словах, но по итогу всё сводится к статистическому анализу. Возможно, в будущем я воспользуюсь извлечённой из игры информацией для улучшения своего алгоритма.

О чём игра?

Я рассуждал иначе. Что мы получаем, вводя слово в игру? Мы получаем информацию, причём количество информации может различаться в зависимости от вводимого слова. Так, например, введя слово «fuzzy» мы вряд ли сильно сузим круг поиска. Но какой ход сильнейший? Нам нужно слово, которое может «разрезать» весь список возможных слов на как можно меньшие подсписки. Будем называть маской цветовую комбинацию, которую возвращает игра после ввода слова. Теоретически возможно всего различных масок. Таким образом каждое новое слово в идеальном случае делит множество всех возможных загаданных слов на 243 подсписка.

Слово «tears» предлагает множество разных масок из 243 возможных. Я обновил страницу https://www.wordleunlimited.com/ пять раз и получил пять разных масок

На самом деле из-за особенностей естественных языков не всё так радужно: разрезание на подсписки неравномерное и получается их на самом деле не 243, а значительно меньше и различается для разных слов. Идея моего решателя состоит как раз в том, чтобы на каждом шаге выбирать слово, которое делит словарь на как можно большее число кучек.

Моя модель игры такова:

1. Словарь допустимых для ввода слов и словарь возможных загаданных слов одинаковы и совпадают со словарём из /usr/share/dict/american-english (как в статье по первой ссылке).

2. Разбиение, получаемое на каждом шаге, близко к равномерному и размеры каждой кучи слов примерно одинаковы (предположение, очевидно, наивное: ведь для маски «пять зелёных букв» соответствует кучка из всего одного слова).

Пишем код

Подгрузка словаря:

dictpath = "/usr/share/dict/american-english"
# Словарь как в первом решателе
allwords = open(dictpath, "r").read().split('\n')

validwords = set()

letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZйцукенгшщзхъфывапролджэячсмитьбюЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ'

for w in allwords:
    if("'" in w):
        continue
    if(len(w) != 5):
        continue
    for i in range(6):
        if(i < 5 and w[i] not in letters):
            break
        elif(i == 5):
            validwords.add(w.lower())

try:
    validwords.remove('clint')  # Игра такое слово не принимает
    validwords.remove('garbo')  # Игра такое слово не принимает
    validwords.remove('galen')  # Игра такое слово не принимает
    validwords.remove('abner')  # Игра такое слово не принимает
    validwords.remove('aldan')  # Игра такое слово не принимает
except BaseException:
    pass

validwords = list(validwords)

В сухом остатке имеем 5904 англоязычных слов. Определим несколько полезных функций:

Проверка, что слово может быть загаданным по введённым в игру данным:

def isThisSecretAvailable(testword, mask, secret):
    '''
    mask: G,Y,N -- green, yellow, none
    Return True if secret can be secret word with this testword and mask
    '''
    for i in range(len(mask)):
        if(mask[i] == 'N' and testword[i] not in secret):
            continue
        if(mask[i] == 'G' and testword[i] == secret[i]):
            continue
        if(mask[i] == 'Y' and testword[i] in secret and testword[i] != secret[i]):
            continue
        return False
    return True

Получить маску для пары введённого (testword) и загаданного (secret) слова:

def getMask(testword, secret):
    '''
    Returns mask of NYG symbols for typed testword and secretword
    '''
    mask = ""
    for i in range(len(testword)):
        if(testword[i] == secret[i]):
            mask += "G"
        elif(testword[i] in secret):
            mask += "Y"
        else:
            mask += "N"
    return mask

Получить подсписок возможных загаданных слов по имеющимся данным из списка (wordlist), эта функция будет использоваться для сужения круга поиска:

def getAvailableWordsByMask(testword, mask, wordlist):
    '''
    Return list of available words by typed testword and mask
    '''
    validsecrets = []
    for w in wordlist:
        if(isThisSecretAvailable(testword, mask, w)):
            validsecrets.append(w)
    return validsecrets

А теперь выясним, какие же слова ближе всего к математическому пределу разбития на 243 подсписка:

testwordmasks = dict()  # Сделаем словарь: слово -> множество возможных масок
for i in validwords:
    testwordmasks[i] = set()
    for s in validwords:
        testwordmasks[i].add(getMask(i, s))

masksvariances = []  # Сделаем лист с информацией о количестве разных масок
for i in validwords:
    masksvariances.append(len(testwordmasks[i]))

maxmasksvariances = max(masksvariances)
maxvariancewords1 = []
for i in range(len(validwords)):
    if(masksvariances[i] == maxmasksvariances):
        print(validwords[i])
        maxvariancewords1.append(validwords[i]) # И выпишем лучшие слова

У меня этот код проработал 37 секунд и выдал такой результат: maxvariancewords1=['tares', 'tears'], maxmasksvariances=188.

Теперь заворачиваю эту логику поиска лучших вариантов в отдельную функцию и пишем минималистичный пользовательский интерфейс:

def getBestSteps(wordlist, allwords=None):
    '''
    Get best step for find word in wordlist by allwords dictionary
    HardMode on if allwords=None or allwords=wordlist
    '''
    if(allwords is None):
        allwords = wordlist
    testwordmasks = dict()
    for i in allwords:
        testwordmasks[i] = set()
        for s in wordlist:
            testwordmasks[i].add(getMask(i, s))
    masksvariances = []
    for i in allwords:
        masksvariances.append(len(testwordmasks[i]))
    maxmasksvariances = max(masksvariances)
    print("Different masks:", maxmasksvariances)
    maxvariancewords = []
    maxvariancewords2 = []
    maxvariancewords3 = []
    for i in range(len(allwords)):
        if(masksvariances[i] == maxmasksvariances):
            print(allwords[i])
            maxvariancewords.append(allwords[i])
            if(maxmasksvariances == 1):
                break
        elif(masksvariances[i] == maxmasksvariances - 1):
            # На случай, если в maxvariancewords будет всего одно слово и его
            # не будет в словаре игры
            maxvariancewords2.append(allwords[i])
        elif(masksvariances[i] == maxmasksvariances - 2):
            maxvariancewords3.append(allwords[i])
    # Среди лучших вариантов я бы поставил на первое место те, в которых буквы
    # не повторяются
    maxvariancewords.sort(key=lambda x: -len(set(x)))
    maxvariancewords2.sort(key=lambda x: -len(set(x)))
    maxvariancewords3.sort(key=lambda x: -len(set(x)))
    return maxvariancewords + maxvariancewords2 + maxvariancewords3

def mainloop():
    print("Enter one of next words:", maxvariancewords1)
    newwordlist = getAvailableWordsByMask(
        input("What word did you type: ").lower(),
        input("What mask did you get: ").upper(),
        targetlist)
    print("Found", len(newwordlist), "available words")
    beststeps = getBestSteps(newwordlist, validwords)
    if(len(beststeps) > 7):
        beststeps = beststeps[:7]
    print("Please, type one of next words:", beststeps)
    while(len(newwordlist) > 1):
        newwordlist = getAvailableWordsByMask(
            input("What word did you type: ").lower(),
            input("What mask did you get: ").upper(),
            newwordlist)
        print("Found", len(newwordlist), "available words")
        if(len(newwordlist) == 1):
            break
        beststeps = getBestSteps(newwordlist, validwords)
        if(len(beststeps) > 7):
            beststeps = beststeps[:7]
        print("Please, type one of next words:", beststeps)
    print("Your word is", newwordlist)

Весь код можно посмотреть и скачать здесь.

Теперь попробуем и поиграть:

Я бы потратил ещё пару попыток на исследование гласных, а машина с двух попыток нашла решениеНа третьей итерации интерфейс выбросил первое попавшееся слово и вышел из цикла, сообщив отгадку

Я сыграл ещё несколько игр на сайте https://www.wordleunlimited.com/ и программа отгадала слово «gamma» с 5-й попытки, «heard» — с 4-й, «pores» — с 3-й попытки, «amber» — с 4-й, «peace» — с 3-й. На первой итерации после слова «tears» программа сужает поиск с 5904 слов до менее чем сотни (от 17 до 98 слов).

Что ещё можно сделать:

• Взять русскоязычный словарь (например, отсюда) и испытать алгоритм на русскоязычном Wordle (спойлер: слово 25 января программа взяла с третьей попытки, а лучшим первым ходом машина считает слово «порка»)

• Загрузить в программу словари, описанные в статье Тома Локвуда, на которую я сослался в начале

• Исследовать, за какое максимальное число попыток алгоритм отгадывает слова? Каков процент выигрышей он может гарантировать?

• Исследовать, улучшит ли ситуацию смена тактики с выбора слов, которые режут словарь на максимальное число подсписков, на выбор слов, которые режут на примерно равные подсписки, но в меньшем количестве? Или какой-то промежуточный вариант? Какой вариант статистически выигрышнее?

• Исследовать качество игры в hard mode, когда надо выбирать слова, которые попадают под все подсказки (спойлер: программа успешно решила десятки примеров)

© Habrahabr.ru