Ещё одно решение игры Wordle на Python

В начале 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 подсписка.

На самом деле из-за особенностей естественных языков не всё так радужно: разрезание на подсписки неравномерное и получается их на самом деле не 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') # Игра такое слово не принимает
except: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

#isThisSecretAvailable("price","GGGNG","prize")
#returns 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

#getMask("argon","slang")
#returns "YNYNY"

Получить подсписок возможных загаданных слов по имеющимся данным из списка (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

# Main algorithm:
def mainloop():
	print("Enter one of next words:",maxvariancewords1,"("+str(maxmasksvariances)+" different masks)")
	newwordlist=getAvailableWordsByMask(input("What word did you type: ").lower(),input("What mask did you get: ").upper(),validwords)
	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")
		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, когда надо выбирать слова, которые попадают под все подсказки (спойлер: программа успешно решила десятки примеров)