kadukm 12 апр в 22:22

Исследуем игру «5 букв» от Т-Банка и разные алгоритмы решения

Простой

24 мин

16K

Алгоритмы*Логические игры

Аналитика

Что хотим узнать

В рамках этой статьи мы будем исследовать игру «5 букв»:

Придумаем различные алгоритмы прохождения игры
Посмотрим, как различные алгоритмы проходят игру на разных словарях

При реализации алгоритмов мы будем ориентироваться на версию игры от Т-Банка. За счет этого будем считать, что:

Буквы е и ё — это одна и та же буква
На решение игры дается 6 шагов

Скорее всего, если вы открыли эту статью, то вы и так знаете правила игры «5 букв», но на всякий случай оставлю правила игры ниже:

Правила игры "5 букв"

Суть игры в том, чтобы отгадать загаданное игрой слово. Игра загадывает и принимает на вход существительные русского языка. Игроку дается 6 попыток, и после ввода очередного слова в игру, игра возвращает игроку информацию о том, представлена ли введенная в игру буква в загаданном слове или нет. Данная информация передается цветом:

Серый цвет - буквы нет
Белый цвет - буква есть, но на другой позиции
Желтый цвет - буква есть ровно на этой позиции

Когда загаданное слово будет отгадано, то в результате игра окрасит каждую из букв в желтый цвет, и игра будет считаться пройденной

В статье будут рассмотрены следующие алгоритмы:

Оптимальный алгоритм, который последовательно ищет самое перспективное с точки зрения мат.ожидания следующее слово (про то, что именно будем считать за оптимальность, будет описано позднее в главе «Определение оптимальности»)
Алгоритм, который выбирает для старта слов с неповторяющимися буквами, а затем продолжает работу как оптимальный алгоритм
«Человеческий» алгоритм, который действует как оптимальный, но каждый следующий ввод подстраивается под полученную на прошлых ходах информацию и всегда может подходить как возможный ответ — то есть подходит под маску ответа (в целом, наверное, и так понятно, что имеется в виду под «маской ответа», но более подробное определение будет дано в главе «Определение оптимальности»)

Перед тем, как переходить к, непосредственно, реализации и исследованию алгоритмов, имеет смысл сначала разобраться, какие вообще слова принимает оригинальное приложение Т‑Банка.

Исследование словаря Т-Банка

Дисклеймер: хотя я сам на текущий момент работаю в Т-Банке, никакой инсайдерской информацией я не пользовался. Всю информацию я собирал руками, просто пробуя вводить разные слова в приложение.

Попробовав ввести разные слова в приложение и проанализировав загаданные с 2024 года слова, я пришел к выводу, что приложение использует 2 различных словаря:

Словарь со всеми словами, допустимыми для ввода в приложение. Здесь находится много неочевидных и не очень часто используемых слов (вроде саами, лабаз, нотис или абака)
Словарь с ответами, которые могут быть загаданы приложением. Здесь в подавляющем большинстве используются простые и общеизвестные слова

Тут важно заметить, что еще ни разу загаданные слова не повторялись. Возможно, когда простые слова закончатся, в ход пойдут слова сложнее, но пока что будем считать, что эти 2 словаря все-таки отличаются.

UPD 13.04.25: В комментариях верно заметили, что повторы загаданных слов на самом деле иногда бывают - например, товар было загадано 2 раза. Так что, скорее всего, и правда массово сложные слова загадываться не должны, и разделять все слова на 2 словаря корректно.

На самом деле, для оценки разных алгоритмов это не очень важно, потому что в любом случае мы будем тестировать алгоритмы на разных словарях - не обязательно совпадающих со словарями, используемыми в приложении Т-Банка. Просто интересно зафиксировать, что используется в оригинальном приложении.

Интересные особенности словарей Т-Банка:

Все слова представлены в именительном падеже
Нет слов во множественном числе, когда у слова есть форма в единственном числе
Нет многих слов вида pluralia tantum - то есть слов, которые существуют только во множественном числе. Например, слово тиски есть, но при этом слов щипцы и санки нет
В словаре не содержатся имена собственные
В словаре не содержится матов и многих откровенных ругательств. Хотя есть сучка и шлюха
Присутствует много неочевидных слов-производных от прилагательных. Например, выжиг, запил, выпил
Хотя приложение просит вводить только существительные, на самом деле есть исключения. Например, плохо (наречие), авось (частица), живой (прилагательное). Возможно, это просто баг, который исправят, когда/если заметят

Формирование словарей для игры

Для формирования словарей я использовал разные ресурсы, о которых расскажу ниже.

поиск-слов.рф

Самый простой для парсинга и при этом один из самых объемных по кол-ву слов ресурс - это сайт поиск-слов.рф. На этом сайте можно выбрать 5-буквенные существительные, при этом есть возможность отфильтровать имена собственные.

Особенности парсинга и найденных слов:

Пришлось парсить HTML, так как открытого API я не нашел
Содержатся только слова в именительном падеже
Неизвестен источник, откуда взяты слова
Есть цензура - нет как минимум мата и ругательств
После парсинга получилось 6595 слов

6595 слов - это очень много. Среди слов содержится много сомнительных слов - либо не существительные, либо имена собственные, либо откровенный мусор, который даже не гуглится. Такой результат нам тоже интересен для дальнейшего анализа алгоритмов, но хочется найти и что-то более осмысленное.

OpenCorpora

При поиске какого-то более-менее достоверного источника слов я наткнулся на замечательный ресурс OpenCorpora.

OpenCorpora - это open-source проект, представляющий из себя набор подробно размеченных корпусов текстов на русском языке. Помимо самих, непосредственно, корпусов текстов, ресурс также предоставляет и словарь всех встреченных слов - а это как раз то, что нам нужно.

Особенности парсинга и найденных слов:

Пришлось парсить xml
Нет никакой цензуры, находятся все возможные слова
Пришлось учесть много свойств слов, чтобы найти именно существительные и при этом отсеять имена собственные и неподходящие формы слова
После парсинга получилось 4082 слова

После анализа получившихся слов могу сделать вывод, что получившийся словарь максимально похож на словарь слов Т-Банка, которые принимает приложение. Да, некоторые расхождения присутствуют, но по ощущениям эти расхождения очень незначительны и проявляются по большей мере в том, что в словаре OpenCorpora слово есть, а в словаре Т-Банка - нет.

Словарь с ответами

Как мы выяснили ранее, в приложении Т-Банка загадываются по большей мере только часто употребляемые слова, и даже найденный словарь в 4082 слова - это слишком много. Нужно как-то отфильтровать полученные слова и выбрать из них только те слова, что употребляются чаще всего.

Для этой цели я воспользовался ресурсом textometr.ru, который позволяет проверить частотность слова в русском языке. В словаре частотности у этого ресурса есть далеко не все слова, так что будем считать, что если запрошенное слово в словаре частотности представлено, значит оно может быть загадано приложением Т-Банка в качестве ответа.

К моему счастью, textometr.ru предоставляет пусть и не задокументированное, но все-таки открытое и вполне понятное JSON-API, так что фильтрация слов по их частотности не составила особого труда. После фильтрации получилось 2087 слов.

Но это еще не всё. Я решил еще руками доработать получившийся словарь, а именно:

Проверить разные подозрительные слова, и если их не принимает приложение Т-Банка, то удалить их из словаря
Добавить недостающие слова из тех, что уже были загаданы приложением Т-Банка ранее (коих было немного)
Просто руками добавить слова, которые, по моему мнению, могут быть загаданы (тоже немного)

В итоге, после фильтрации и ручных манипуляций получилось 2066 слов.

Итоговые используемые для анализа словари

Итого для анализа алгоритмов будем использовать следующие словари:

Словарь возможных ответов. 2066 слов
Словарь доступных для ввода слов: 4109 слов (по сути, это Словарь возможных ответов + Словарь OpenCorpora, из которого я удалил найденные мной слова, которые не принимаются приложением Т-Банка)
Словарь всех найденных слов. 6826 слов

2066 ответов и 4109 доступных для ввода слов - это тот набор словарей, который больше всего похож на словари, используемые в оригинальном приложении Т-Банка. На этой комбинации словарей мы будем анализировать алгоритмы максимально подробно. Но в конце статьи также проанализируем и другие комбинации словарей, просто менее подробно.

Теперь, имея словари, можем переходить к реализации алгоритмов, которые будут решать игру на разных словарях - каждый по-своему оптимально. Но перед этим нужно разобраться, что мы вообще будем считать оптимальностью.

Определение оптимальности

Для начала введем определение маски ответа. Это понадобится для реализации каждого из алгоритмов - как для гипотетического самого оптимального алгоритма, так и для остальных алгоритмов, применимых на практике:

Пусть мы играем в игру «5 букв». Игрой загадан какой‑то ответ, мы ввели какое‑то кол‑во слов, и теперь у нас есть информация по некоторым буквам: какие‑то буквы в ответе точно не присутствуют, какие‑то буквы есть, но в неизвестном месте, а для каких‑то букв в ответе известна точная позиция. Назовем эту информацию маской ответа

Теперь попробуем описать гипотетический самый оптимальный алгоритм.

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

class Result:
  best_word: str
  average_steps_to_solve: int

def solve(possible_answers: List[str], step: int) -> Result:
  if len(possible_answers) == 0:
    # Ответ найден за step шагов
    return Result(None, step)

  if step == 6:
    # Ответ не найден за 6 шагов
    return Result(None, +infinity)

  min_average_steps_to_solve = +infinity
  best_word = None

  for word in ALL_WORDS:
    sum = 0;

    for answer in possible_answers:
      next_possible_answers = filter(possible_answers, word, answer)
          
      sum += solve(next_possible_answers, step + 1).average_steps_to_solve

    if sum / len(possible_answers) < min_average_steps_to_solve:
      min_average_steps_to_solve = sum / len(possible_answers)
      best_word = word

  return Result(best_word, min_average_steps_to_solve)

# Имитирует ввод в игру слова word: фильтрует возможные на текущем шаге
# ответы answers при допущении, что игрой сейчас загадан ответ answer
# При word != answer возвращает новый список отфильтрованных ответов
# При word == answer возвращает пустой список
def filter(answers: List[str], word: str, answer: str) -> List[str]:
  ...


# Теперь с помощью функции solve можем найти лучшее стартовое слово,
# ввести его в игру и получить от игры маску загаданного ответа.
# По полученной от игры маске мы можем отфильтровать подходящие под маску ответы,
# затем найти следующее оптимальное слово, и так пока не пройдем игру

best_beginning = solve(ALL_ANSWERS, 0)
print(best_beginning.best_word)  # Лучше стартовое слово
print(best_beginning.average_steps_to_solve)  # Среднее кол-во ходов для прохождения игры

Алгоритм выше оптимален с точки зрения среднего потраченного кол-ва шагов для прохождения игры, но имеет одну большую проблему: в реальном мире он будет отрабатывать недопустим долго. Даже учитывая, что мы ограничены 6-ью ходами, и даже при ситуации, когда словари всех возможных слов и всех возможных ответов совпадают и содержат только 2000 слов, в этом алгоритме рекурсивных вызовов будет порядка (на самом деле вызовов будет на несколько порядков больше, потому что - это только рассмотренные на каждом шаге варианты слов для ввода, а для каждого ввода проверяется еще и каждый возможный ответ).

Возможно, этот алгоритм можно как-то оптимизировать, убрав ненужные рекурсивные вызовы или вообще придумав что-то принципиально новое, но я ничего толкового не придумал. Поэтому постараемся изобрести какую-то эвристику оптимальности.

"Жадный" алгоритм

Пусть мы изначально знаем, какие слова теоретически могут быть загаданы. Тогда мы можем отфильтровать возможные ответы по полученной маске ответа - отсеять слова, которые точно не могут быть ответом, и оставить слова, которые под полученную маску подходят. С этими оставшимися ответами далее и будем работать.

Имея возможные оставшиеся ответы, мы можем проверить каждое слово из словаря всех слов: посчитаем, сколько в среднем остается возможных ответов после ввода в игру рассматриваемого слова. То есть для каждого слова из словаря всех слов мы проверяем, как оно влияет на игру при каждом возможном ответе, и считаем среднее арифметическое оставшихся возможных ответов.

При этом важно учесть не только среднее кол-во оставшихся возможных ответов, но и условие, может ли рассматриваемое слово само выступать в качестве ответа. Нужно это для тех случаев, когда оптимальных слов может быть несколько, и тогда нам выгоднее использовать то слово, которое само может быть ответом, чтобы иметь возможность просто случайно угадать верный ответ. Это особенно важно для случаев, когда возможных ответов осталось очень мало (например, два), и оптимальные слова - это чуть ли не половина из всех возможных слов, но при этом если какое-то из оптимальных слов может быть ответом, то есть большая вероятность просто угадать ответ, загаданный игрой.

В итоге на псевдокоде выбор следующего оптимального слова будет выглядеть примерно так:

def find_next_word(possible_answers):
  best_word = None
  min_average_possible_answers = +infinity
  
  for word in ALL_WORDS:
    sum = 0;
    
    for answer in possible_answers:
      next_possible_answers = filter(possible_answers, word, answer)
      sum += len(next_possible_answers)
      
    if (
      sum / len(possible_answers) < min_average_possible_answers
    ):
      min_average_possible_answers = sum / len(possible_answers)
      best_word = word
    else if (
      sum / len(possible_answers) == min_average_possible_answers
      and word in possible_answers
    ):
      best_word = word

  return best_word

# Имитирует ввод в игру слова word: фильтрует возможные на текущем шаге
# ответы answers при допущении, что игрой сейчас загадан ответ answer
# При word != answer возвращает новый список отфильтрованных ответов
# При word == answer возвращает пустой список
def filter(answers: List[str], word: str, answer: str) -> List[str]:
  ...

Почему пишу на псевдокоде, но не прикладываю реальный код?
Код для исследования игры "5 букв" есть. Он написан на Java, и его можно найти в репозитории на github. Просто этот код получился достаточно сложным, и в рамках этой статьи рассматривать реальный код было бы неудобно.
Если интересно, то в репозитории также оформлен README, где описаны особенности реализации и и примененные оптимизации.

Таким образом мы ввели эвристику, предполагающую, что на данном шаге самое оптимальное слово - это такое слово, которое после его ввода в игру в среднем оставляет минимальное кол-во ответов. Жадность при этом заключается в том, что мы ищем оптимальное конкретно на данном шаге слово, не заботясь о том, что будет дальше.

Имея возможность найти следующее оптимальное слово, мы можем для каждого шага, начиная с самого первого, последовательно искать оптимальное продолжение, вводить его в игру, фильтровать по полученной от игры маске оставшиеся возможные ответы, и так пока не пройдем игру.

На самом деле, нам не обязательно ограничиваться только одним словом - мы можем рассматривать сразу несколько слов. То есть мы можем точно так же проверять, сколько в среднем остается возможных ответов после введения слов. Когда уже введено какое-то кол-во слов, рассматривать несколько слов смысла особо нет, но эта возможность будет нам полезна, когда мы будем искать оптимальный старт не из одного слова, а из нескольких.

Плюсом ко всему, можно еще считать не среднее кол-во оставшихся ответов, а максимальное. То есть считать слово оптимальным, если после его ввода в игру максимальное кол-во оставшихся ответов минимально. Оба варианта имеют право на жизнь, и оба варианта мы проанализируем на разных словарях.

Если кому-то так будет удобнее/понятнее, ниже приведено более строгое определение оптимальности.

Более строгое около-математическое определение оптимальности

Пусть:

$\mathbb{D}$ - множество всех слов, принимаемых игрой
$\mathbb{A} \subseteq \mathbb{D}$ - множество всех ответов, которые могут быть загаданы игрой

Определим функцию фильтрации для получения оставшихся возможных ответов после ввода заданных слов:

$filter(W_n, A, a) = A^{'}$ , где:

$W_n = \{w_1, w_2,\ ...\ , w_n\} \subseteq \mathbb{D}$ - слов, которые планируется ввести
$A \subseteq \mathbb{A}$ - оставшиеся возможные на текущем шаге ответы
$a \in A$ - загаданный игрой ответ
$A^{'} \subseteq A$ - оставшиеся возможные ответы после введения слов

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

Функция подсчета среднего кол-ва ответов, которые остаются после ввода заданных слов:

$avg(W_n, A) = \frac{\sum_{a \in A} |filter(W_n, A, a)|}{|A|}$ , где:

$W_n = \{w_1, w_2,\ ...\ , w_n\} \subseteq \mathbb{D}$ - слов, которые планируется ввести
$A \subseteq \mathbb{A}$ - оставшиеся возможные на текущем шаге ответы

Функция подсчета максимального кол-ва ответов, которые остаются после ввода заданных слов:

$max(W_n, A) = max\{\ |filter(W_n, A, a)|\ \}_{a \in A}$

$W_n = {w_1, w_2,\ ...\ , w_n} \subseteq \mathbb{D}$ - слов, которые планируется ввести
$A \subseteq \mathbb{A}$ - оставшиеся возможные на текущем шаге ответы

Теперь можем определить функцию поиска оптимального продолжения из слов:

, где

$A \subseteq \mathbb{A}$ - оставшиеся возможные на текущем шаге ответы
$n \in \mathbb{Z}$ - кол-во искомых слов в оптимальном продолжении
- одна из двух функций для эвристической оценки ( или )
$W_n = \{w_1, w_2,\ ...\ , w_n\} \subseteq \mathbb{D}$ - оптимальное продолжение такое, что:

$\forall\ W_n^{'} = \{w_1^{'}, w_2^{'},\ ...\ , w_n^{'}\} \subseteq \mathbb{D}: \\ 1. \quad f(W_n^{'}, A) \ge f(W_n, A) \\ 2. \quad f(W_n^{'}, A) = f(W_n, A) \quad \& \quad W_n^{'} \cap A \neq \emptyset \implies \\ \implies W_n \cap A \neq \emptyset$

Тогда можем рассмотреть частные случаи:

оптимальный старт из 1 слова , в среднем дающий минимальное кол-во оставшихся возможных ответов:
- $opt(\mathbb{A}, 1, avg) = \{w_1\}$
оптимальный старт из 1 слова , который минимизирует возможное максимальное кол-во оставшихся возможных ответов:
- $opt(\mathbb{A}, 1, max) = \{w_1\}$
оптимальный старт из 4 слов , в среднем дающий минимальное кол-во оставшихся возможных ответов:
- $opt(\mathbb{A}, 4, avg) = \{w_1, w_2, w_3, w_4\}$
оптимальное продолжение из 1 слова , в среднем дающее минимальное кол-во оставшихся возможных ответов:
- $opt(A, 1, avg) = \{w_1\}$ , где $A \subseteq \mathbb{A}$ - подмножество оставшихся на прошлом шаге возможных ответов

Реализованные алгоритмы решения

Перейдем наконец-то от теории к практике: опишем и реализуем конкретные алгоритмы, а также зафиксируем какие-то выводы касательно реализованных алгоритмов.

Описывать алгоритмы будем на примере словарей, максимально похожих на словари, используемые в оригинальном приложении Т-Банка (напомню, это 4109 всех возможных слов и 2066 возможных ответов). Пользоваться при этом будем эвристикой фильтрации слов по среднему кол-ву оставшихся ответов.

Все остальные комбинации словарей, а также эвристика фильтрации слов по максимальному кол-ву оставшихся ответов, тоже будут протестированы, но это уже будет сделано в самом конце и менее подробно.

Оптимальный алгоритм

В принципе, оптимальный алгоритм уже был описан выше, но зафиксируем его еще раз:

Ищем первое самое оптимальное слово
Вводим его в игру
Получаем от игры маску ответа
Фильтруем возможные ответы по полученной маске
Ищем следующее оптимальное слово
И так пока не пройдем игру

Сначала разберемся, как было найдено первое оптимальное слово, а затем зафиксируем результаты оптимального алгоритма.

Лучшее слово для старта

Есть 2 способа, как можно искать самое оптимальное слово для старта:

Честный: перебрать все возможные слова, протестировав их на всех возможных ответах
Эвристический: отталкиваться от частотности букв в ответах

Тестирование всех возможных слов на каждом из ответов - это $4109 \cdot 2066$ итераций. Не очень приятно, но вполне реализуемо, так что воспользуемся все-таки честным способом.

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

Место	Слово	Оставшиеся ответы (average)	Оставшиеся ответы (max)
1	`норка`	60.8247	153
2	`ларек`	62.6125	159
3	`карел`	63.5911	159
4	`лерка`	66.0388	159
5	`парок`	66.2355	173
6	`коран`	66.3993	183
7	`катер`	66.4855	191
8	`корма`	67.1386	181
9	`солка`	68.0059	179
10	`нотка`	68.6803	173
...
132	`океан`	89.6745	215
...
4109	`взмыв`	845.5495	1292

UPD 13.04.25: По просьбе из комментариев разобрать статистику для конкретного стартового слова, которое не входит в топ-10, добавил в репозиторий подобную таблицу со всеми возможными словами.

До этого мне всегда казалось, что океан - чуть ли не лучшее слово для старта, ведь там и 3 гласные, и все буквы достаточно часто употребляемые. Однако, на практике это слово занимает лишь 132-ое место.

Пока я писал код и эту статью, я постепенно изменял используемые словари, имитирующие словари Т-Банка - добавлял и удалял некоторые слова. Топ слов по оптимальности частично менялся, но на первом месте всегда оставалась норка

Итого: самое оптимальное слово для старта - норка

Заметим, что после ввода норка первым словом в среднем отсеивается аж 97.05% возможных ответов ( $100\% - 60.8247 / 2066 * 100\%$ )! А в худшем случае отсеивается 92.59% возможных ответов, что тоже впечатляет.

Также интересно, что если все-таки посчитать частотность букв во всех ответах (важно считать буквы именно в ответах, а не пользоваться информацией из интернета), то все найденные оптимальные слова из топ-10 содержат букву а и в целом содержат как минимум 3 буквы из топ-5 самых частотных букв (а норка содержит все 4 самые частотные буквы):

место	буква	частотность (шт)	частотность (%)
1	`а`	1280	12.40%
2	`о`	944	9.15%
3	`к`	745	7.22%
4	`р`	660	6.40%
5	`е`	615	5.96%
6	`т`	559	5.42%
7	`л`	516	5.00%
8	`и`	504	4.88%
9	`с`	476	4.61%
10	`н`	449	4.35%
11	`у`	350	3.39%
...

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

Примеры решений

Примечание: почти все примеры решений (как для оптимального алгоритма, так и для остальных алгоритмов) были взяты из реальных игр в приложении Т-Банка.
Единственное исключение - это один негативный сценарий для "человеческого" алгоритма, который будет показан позднее.

Часто оптимальный алгоритм справляется с поиском загаданного слова очень успешно:

норка
- В среднем остается 60.82 ответа
- В данном случае осталось 25 ответов
пенис
- В среднем остается 2.88 ответов
- В данном случае остался 1 ответ
шпион

Также часто на 3-ем шаге остается 2-3 подходящих под маску ответа слова - тогда обычно приходится просто перебирать возможные варианты:

норка
- В среднем остается 60.82 ответа
- В данном случае осталось 7 ответов
зажим
- В среднем остается 1.29 ответов
- В данном случае осталось 2 ответа
пенка
- Шанс угадать ответ был 50%, но не повезло
- Остался 1 возможный ответ
лунка

При этом оптимальный алгоритм эффективно использует информацию о том, каких букв в загаданном слове нет. Из-за этого возникают интересные кейсы, когда выбор следующего слова алгоритмом для человека неочевиден: отгадано очень мало букв, но при этом информации о том, каких букв в ответе нет, достаточно для того, чтобы однозначно определить ответ:

абака
- Форсируем использование неоптимального старта
- В среднем остается 267.02 ответа
- В данном случае осталось 6 ответов (блажь, браво, благо, брасс, штамб, брань)
лотос
- В среднем остается 1 ответ
- То есть вне зависимости от загаданного слова, такой ввод всегда будет однозначно находить ответ
брань

Результаты

Протестируем оптимальный алгоритм с несколькими стартовыми словами на всех возможных ответах.

Лучшее стартовое слово норка:

Среднее кол-во шагов для решения: 3.4942
Кол-во проигрышей: 0
Подробная статистика:
- 1 шаг: 1
- 2 шага: 62
- 3 шага: 981
- 4 шага: 958
- 5 шагов: 60
- 6 шагов: 2

Не самое плохое, но и не самое оптимальное стартовое слово океан (топ-132 из 4109):

Среднее кол-во шагов для решения: 3.6032
Кол-во проигрышей: 0
Подробная статистика:
- 1 шаг: 1
- 2 шага: 53
- 3 шага: 838
- 4 шага: 1050
- 5 шагов: 116
- 6 шагов: 6

Худшее стартовое слово взмыв:

Среднее кол-во шагов для решения: 3.9836
Кол-во проигрышей: 0
Подробная статистика:
- 1 шаг: 0
- 2 шага: 33
- 3 шага: 397
- 4 шага: 1218
- 5 шагов: 403
- 6 шагов: 13

Видно, что топ-1 старт от топ-133 старта отличается не сильно; худшее стартовое слово хуже лучшего в среднем примерно на полшага, но в целом тоже отличается от лучшего не критично. При этом для любого стартового слова не допускается поражений.

Старт из слов с уникальными буквами

Алгоритм с использованием нескольких слов с уникальными буквами в начале будет работать как оптимальный алгоритм, за тем лишь исключением, что сначала безусловно будут вводиться какие-тослов, а уже после этого будут искаться оптимальные слова-продолжения.

Такой алгоритм бесполезен с точки зрения оптимальности, потому что он точно будет в среднем работать хуже, чем оптимальный алгоритм - по сути, это как урезанная версия оптимального алгоритма, в которой захардкожены первыеслов. Но этот алгоритм может быть интересен с практической точки зрения для использования человеком при реальной игре. Поэтому проанализируем, насколько вообще этот алгоритм жизнеспособен.

Для начала займемся поиском этихслов для старта.

Лучшие слова для старта

Хочется рассмотреть все возможные старты - от 2 до 5 слов. В примерах ниже будем будем ориентироваться на старт из 4 слов, а для другого кол-ва стартовых слов всё будет сделано аналогично.

Если в случае с оптимальным алгоритмом мы могли себе позволить просто перебрать все возможные слова, то с данным алгоритмом уже возникает порядка 4109^4 вариантов стартовых комбинаций, и обычный перебор не подойдет. Можно попробовать сократить варианты для перебора:

Использовать только слова с уникальными буквами
При переборе не использовать слова, если в предыдущих словах уже была использована какая-то из букв
Игнорировать порядок букв и не рассматривать наборы из разных слов, в которых буквы одинаковые

Когда будут собраны все возможные стартовые комбинации, можно точно так же протестировать эти комбинации на всех ответах и оставить ту комбинацию, что дает лучший средний результат. Возможно, этого будет достаточно, чтобы значительно уменьшить кол-во вариантов в переборе. Посчитаем, сколько теоретически может быть комбинаций из стартовых 4-ех слов:

Всего букв 32 (е = ё)
В 4 словах 20 уникальных букв
Получаем $C_{32}^{20}$ , что равняется

Числа впечатляют, но может показаться, что на практике из реальных слов комбинаций найдется сильно меньше. И действительно, комбинаций находится меньше, но не кардинально - вариантов - и каждый из вариантов нужно проверить на каждом из ответов, то есть в итоге получаем $2.877.543 \cdot 2066$ итераций. Отрабатывать это будет тоже долго, и при этом мы не учитываем порядок букв, так что откажемся от этого подхода, а воспользуемся всё той же частотностью букв - тем более, в случае с поиском оптимального первого слова оказалось, что если опираться на частотность букв, то действительно получаются неплохие результаты.

Использовать частотность букв будем двумя способами:

Просто отберем $5 \cdot n$ самых частотных букв
Отберем все гласные () и оставшиеся $5 \cdot n - 9$ самых частотных букв

В итоге находить комбинации для старта будем так:

Зафиксируем наборы букв:
- Набор из $5 \cdot n$ самых частотных букв
- Набор из всех гласных () и оставшихся $5 \cdot n - 9$ самых частотных букв
Найдем все возможные комбинации слов, подходящие под найденные наборы букв
Протестируем каждую из комбинаций на всех ответах

Посмотрим на лучшие стартовые слова из 2-5 слов, которые получилось найти:

Место	Слова	Оставшиеся ответы (average)	Оставшиеся ответы (max)
2 слова
1	`серна`, `колит`	4.9245	40
2	`сатин`, `колер`	5.0437	23
3	`карел`, `нотис`	5.1532	23
3 слова
1	`метод`, `сплин`, `курва`	1.5311	10
2	`кодла`, `стрим`, `певун`	1.5495	10
3	`плинт`, `демос`, `курва`	1.5553	10
4 слова
1	`гниль`, `сброд`, `пушка`, `взмет`	1.1357	4
2	`скраб`, `гольд`, `шипун`, `взмет`	1.1415	4
3	`вздор`, `булга`, `микст`, `шпень`	1.1541	4
5 слов
1	`кольт`, `бридж`, `взмах`, `пешня`, `сычуг`	1.0446	3
2	`пашня`, `вождь`, `сычуг`, `кхмер`, `битлз`	1.0466	3
3	`князь`, `полба`, `этвеш`, `мюрид`, `сычуг`	1.0466	3

Что интересного тут видим:

Подход с использованием всех возможных гласных не оправдался - слова, найденные таким подходом, есть только в наборе из 5-ти букв, и то только на 3-ем месте
При старте из 4-ех слов в худшем случае остается только 4 возможных ответа - а этого вполне достаточно, чтобы на 6-ом шаге однозначно отгадать ответ. То есть при старте из 4-ех слов алгоритм не проигрывает
Старт из 5 слов часто не находит ответ однозначно, что означает проигрыш. Так что подобный старт точно не подходит
Старт из 3 слов не сильно отличается от старта из 4 слов

Итого: самые оптимальные старты из уникальных букв:

2 слова: серна, колит
3 слова: сплин, метод, курва
4 слова: гниль, сброд, пушка, взмет

Примеры решений

Со стартом из 2 слов никаких проблем нет - он дает довольно много информации, но при этом оставляет пространство для дальнейших вводов и ошибок:

серна, колит
- В среднем остается 4.92 ответа
- В данном случае осталось 3 ответа (уклад, балык, вклад)
уклад
- Шанс угадать 33%. Если не угадаем, то всегда остается только 1 возможный ответ
- В этом случае не повезло, остался 1 ответ
балык

Старт из 3 слов также оставляет пространство для дальнейших вводов, но при этом дает еще больше информации, так что загаданное слово часто находится однозначно:

метод, сплин, курва
- В среднем остается 1.53 ответа
- В данном случае остался 1 ответ
струя

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

гниль, сброд, пушка, взмет
- В среднем остается 1.16 ответов
- В данном случае остался 1 ответ
тайга

Машинный алгоритм активно использует информацию о том, какие буквы в ответе не существуют, и для алгоритма ответ очевиден. Но человеку до этого ответа самостоятельно дойти с первой попытки будет непросто. А попыток при этом осталось всего две.

Учитывая, что старт из 3 слов не сильно отличается от старта из 4 слов, для человека оптимальнее будет использовать старт именно из 3 слов - просто потому, что будет больше попыток для каких-то неправильных, но дающих больше понятной информации вводов.

Результаты

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

2 слова:

Лучшие стартовые слова: серна, колит
Среднее кол-во шагов для решения: 3.6110
Кол-во проигрышей: 0
Подробная статистика:
- 1 шаг: 0
- 2 шага: 0
- 3 шага: 911
- 4 шага: 1047
- 5 шагов: 104
- 6 шагов: 2

3 слова:

Лучшие стартовые слова: метод, сплин, курва
Среднее кол-во шагов для решения: 4.1813
Кол-во проигрышей: 0
Подробная статистика:
- 1 шаг: 1
- 2 шага: 0
- 3 шага: 0
- 4 шага: 1688
- 5 шагов: 373
- 6 шагов: 2

4 слова:

Лучшие стартовые слова: гниль, сброд, пушка, взмет
Среднее кол-во шагов для решения: 5.0563
Кол-во проигрышей: 0
Подробная статистика:
- 1 шаг: 1
- 2 шага: 1
- 3 шага: 1
- 4 шага: 0
- 5 шагов: 1936
- 6 шагов: 125

5 слов:

Лучшие стартовые слова: кольт, бридж, взмах, пешня, сычуг
Среднее кол-во шагов для решения: 6.0146
Кол-во проигрышей: 44
Подробная статистика:
- 1 шаг: 1
- 2 шага: 1
- 3 шага: 1
- 4 шага: 1
- 5 шагов: 0
- 6 шагов: 2016
- 7 шагов: 44

"Человеческий" алгоритм

Модифицируем оптимальный алгоритм таким образом, что каждое следующее слово он будет искать не среди всех возможных слов, а только среди слов, подходящих в качестве ответа. Назвал я этот алгоритм «человеческим» потому, что человеку часто хочется ввести в игру следующим словом такое слово, которое подходит под маску загаданного ответа.

Такой алгоритм не будет интересен ни с точки зрения оптимальности (так как работает хуже оптимального алгоритма), ни с практической точки зрения (так как человеку будет сложно придумывать оптимальное следующее слово, подходящее под текущую маску). Но этот алгоритм будет полезен для того, чтобы оценить, насколько важна возможность вводить слова, не подходящие под маску загаданного ответа.

Примеры решений

Часто «человеческий» алгоритм проходит игру почти так же успешно, как и оптимальный алгоритм:

норка
- В среднем остается 60.82 ответа
- В данном случае осталось 30 ответов
падло
- В среднем остается 2.4 ответа
- В данном случае остался 1 ответ
самбо

Или чуть менее успешный кейс, но тоже вполне успешный:

норка
- В среднем остается 60.82 ответа
- В данном случае осталось 43 ответов
тиара
- В среднем остается 4.63 ответа
- В данном случае осталось 5 ответов (афера, махра, сайра, чадра, жабра)
махра
- В среднем остается 2.2 ответа
- В данном случае остался 1 ответ
афера

Однако, существуют такие слова на которых «человеческий» алгоритм работает крайне неоптимально:

норка
- В среднем остается 60.82 ответа
- В данном случае осталось 113 ответов
палка
- В среднем остается 26.66 ответов
- В данном случае осталось 45 ответов
шутка
- В среднем остается 5.89 ответов
- В данном случае осталось 7 ответов
щетка
- В среднем остается 3.86 ответов
- В данном случае осталось 5 ответов (детка, сетка, метка, ветка, тетка)
детка
сетка
метка

Разберем подробнее, что произошло в этом примере

После ввода в игру слова норка мы получили, что загаданное слово заканчивается на ка и не содержит в начале букв нор. Таких ответов может быть 113 штук — это довольно много и, по‑хорошему, нет смысла пытаться подстраиваться под маску ответа, а лучше ввести какое‑то заведомо неверное, но дающее больше информации слово.

На 4-ом шаге мы ввели слово щетка и выяснили, что загаданное слово заканчивается на етка. Также мы узнали, что загаданное слово не может начинаться на буквы норпалшущдс. Таких слов 5 штук - детка, сетка, метка, ветка, тетка

На этом этапе мы вынуждены просто перебирать возможные ответы. Но при этом у нас осталось только 2 хода, из-за чего в итоге для трех из пяти возможных ответов мы точно будем получать поражение

Пример выше - это единственный пример, который не получилось воспроизвести в реальной игре в приложении Т-Банка, потому что, во-первых, для воспроизведения подобного неудачного кейса подходит только 15 слов, во-вторых, хотелось отобразить больше 6-ти возможных шагов.
В итоге пришлось рисовать имитацию игры руками.

Результаты

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

Среднее кол-во шагов для решения: 3.6003
Кол-во проигрышей: 15
Подробная статистика:
- 1 шаг: 1
- 2 шага: 124
- 3 шага: 879
- 4 шага: 832
- 5 шагов: 173
- 6 шагов: 40
- 7 шагов: 10
- 8 шагов: 3
- 9 шагов: 2

Здесь интересно, что в среднем алгоритм не сильно отличается от оптимального (в среднем 3.6003 шага вместо 3.4942). Но при этом в «человеческом» алгоритме периодически встречаются поражения, что уже критично.

Таким образом получается, что в основном первые 1-2 ввода действительно допустимо подстраивать под маску ответа, известную на конкретном шаге, однако после, если загаданное слово не очевидно, лучше ввести слово, которое не подходит под известную маску, но проверяет больше букв и дает больше информации.

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

Сравнение алгоритмов

Сравним, как каждый из алгоритмов работает с разным набором словарей. Проверим каждый из алгоритмов при использовании двух эвристик:

Минимизация среднего кол-ва оставшихся ответов (эта эвристика использовалась везде в примерах выше). Далее эвристика по среднему
Минимизация максимального кол-ва оставшихся ответов. Далее эвристика по максимуму

Желтым выделен набор словарей, который максимально похож на словари, используемые в оригинальной игре «5 букв» от Т‑Банка.

Под таблицами находится легенда, как читать таблицу

Выше в таблицах представлена только общая информация - о кол-ве ходов, затраченных на прохождение игры, и о кол-ве поражений.

Если интересно посмотреть на результаты подробнее, то это можно сделать в репозитории на github: в README репозитория есть аналогичная таблица со ссылками, где каждая из ссылок ведет на подробную статистику об используемых стартовых словах и о кол-ве игр, пройденных за то или иное кол-во шагов.

Результаты исследования

Эвристика по среднему почти всегда и во всем лучше эвристики по максимуму
- Изначально у меня была гипотеза, что эвристика по максимуму будет работать хуже эвристики по среднему, но при этом позволит допускать меньше поражений на словарях, где поражения вообще возможны. Однако, эта гипотеза не подтвердилась, и эвристика по максимуму не дала преимуществ почти нигде - в том числе и в плане кол-ва поражений
- Возможно, на каких-то других словарях с еще большим кол-вом слов эвристика по максимуму может дать какие-то преимущества, но это уже какие-то совсем нереалистичные словари
Чем больше словарь ответов, тем сложнее игра становится для алгоритмов. И наоборот: чем больше кол-во слов, допустимых для ввода, тем игра становится проще
- Этот результат звучит почти очевидно, но сейчас это явно проверено, и даже можно оценить в цифрах, насколько сложнее или проще для алгоритмов те или иные словари
Даже на самом сложном наборе словарей (6826 ответов | 6826 слов) алгоритм может пройти игру без ошибок
- Из этого следует, что можно не знать точных словарей, которые используются в игре, но при этом все равно всегда выигрывать, если использовать оптимальный алгоритм
Шесть шагов — это необходимый минимум для того, чтобы иметь возможность всегда проходить игру без поражений
- Во всех словарях, кроме самого простого (2066 ответов | 6826 слов), алгоритмы иногда доходят до 6-го шага включительно. То есть если бы шагов было меньше хотя бы на 1, то даже самый оптимальный алгоритм допускал бы поражения
- И в приложении Т‑Банка, и в Wordle допускается именно 6 шагов. Возможно, это просто совпадение, а может быть и заранее продуманная деталь
- В таблице выше статистики по шагам алгоритмов нет, но, напоминаю, ее можно посмотреть в подробных результатах в репозитории на github
Учитывая, что даже машинные алгоритмы доходят до 6-го шага, человеку проходить игру всегда без поражений может быть очень затруднительно
- А учитывая, что человеку, в отличие от алгоритмов, не известны конкретные словари и возможные оставшиеся ответы, я бы сказал, что человеку проходить игру всегда без ошибок наверное даже невозможно
Чем больше стартовых слов, тем хуже алгоритм справляется с прохождением игры
- Каждое дополнительное стартовое слово всё сильнее и сильнее ухудшает результаты: старт из 2-ух слов от старта из 1-го слова отличается незначительно (примерно на 0.1 шага), но вот старт из 4-ех слов уже сильно хуже старта из 3-ех слов (почти на 1 целый шаг)
- Таким образом получается, что нет смысла пытаться проверить как можно больше букв, а нужно подстраиваться под имеющуюся на текущем шаге информацию
Чем сложнее набор словарей, тем меньше слов для старта можно использовать без риска получить поражение
- Старт из 3-ех слов почти всегда может пройти игру без ошибок, но вот старт из 4-ех слов уже иногда начинает допускать поражения
- Старт из 5-ти слов, в свою очередь, допускает ошибки вне зависимости от сложности словарей, так что в таком старте уже нет совсем никакого смысла
«Человеческий» алгоритм допускает много ошибок
- Даже на самом простом словаре ответов (2066 ответов) допускаются ошибки, так что практического смысла в этом алгоритме нет

Практические выводы

Алгоритмы и правда вполне успешно справляются с игрой (а насколько успешно, можно посмотреть выше). Их можно использовать в реальных играх, как помощника, и всегда выигрывать.
В лучшем случае игры в среднем можно проходить примерно за 3.5 шагов. Поэтому, если вы в среднем справляетесь хуже, то это нормально; а если справляетесь лучше, то вы гениальны.
Лучшее слово для старта - норка
Лучшие старты из нескольких слов:
- либо серна, колит
- либо метод, сплин, курва
- Использовать больше стартовых слов смысла нет
Теоретически еще можно использовать старт гниль, сброд, пушка, взмет, но в этом случае не всегда очевидно загаданное слово, а оставшихся вводов остается мало

Заключение

Весь код и материалы, использованные в статье, можно найти в репозитории на github:

Код: формирование словарей, CLI для реальной игры, исследования
Особенности реализации и примененных оптимизаций
Подробные результаты работы алгоритмов
Используемые словари. Словари со временем могут дорабатываться, но те словари, на которых проводилось исследование, зафиксированы на тэге habr-article

Все вычисления получилось выполнить на локальном ПК, хотя это и заняло значительное кол-во времени - на моем 12-ядерном процессоре все вычисления в сумме заняли около 5 суток.

На статью меня вдохновили, во-первых, неприятное ощущение ~~глупости~~ бессилия в попытках вспомнить подходящие слова во время игры, во-вторых, видео ютубера 3Blue1Brown. В своих видео он решал немного другую задачу: не исследование игры в целом, а скорее поиск оптимально алгоритма; плюс там рассматривалась англоязычная версия игры - Wordle. Но что-то общее с этой статьей действительно есть. Вот его видео по теме:

https://youtu.be/v68zYyaEmEA. Изначальное видео, где объясняется идея оптимальности и реализуется оптимальный алгоритм
https://youtu.be/fRed0Xmc2Wg. Следующее видео, где разбирается допущенный довольно критичный баг

На этом всё. Статья получилась довольно объемной (для, честно скажем, не очень серьезной темы), так что спасибо всем, кто дочитал до конца.

Всем удачи в будущих играх!

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

А сколько шагов для прохождения игры «5 букв» в среднем требуется вам?

2.44% Меньше 2 шагов (заранее смотрю ответы)3

2.44% 2-3 шага3

35.77% 3-4 шага44

39.02% 4-5 шагов48

7.32% 5-6 шагов9

3.25% Чаще проигрываю4

9.76% Не играю12

Проголосовали 123 пользователя. Воздержались 15 пользователей.

Теги:

Хабы:

Исследуем игру «5 букв» от Т-Банка и разные алгоритмы решения

Что хотим узнать

Исследование словаря Т-Банка

Формирование словарей для игры

поиск-слов.рф

OpenCorpora

Словарь с ответами

Итоговые используемые для анализа словари

Определение оптимальности

"Жадный" алгоритм

Реализованные алгоритмы решения

Оптимальный алгоритм

Лучшее слово для старта

Примеры решений

Результаты

Старт из слов с уникальными буквами

Лучшие слова для старта

Примеры решений

Результаты

"Человеческий" алгоритм

Примеры решений

Результаты

Сравнение алгоритмов

Результаты исследования

Практические выводы

Заключение

Публикации

Истории

Ближайшие события