five-letters

Репозиторий с исследованием игры "5-букв" (аналог Wordle)

Описание исследования

Вся подробная информация об исследовании оформлена в виде статьи на Хабре

В рамках этой статьи можно найти:

• Как формировались словари для исследования
• Как реализованы разные алгоритмы (оптимальный; "человеческий"; со стартом из нескольких слов с уникальными буквами)
• Примеры работы алгоритмов на реальных играх в приложении Т-Банка
• Подробное описание результатов исследования
• Выводы, применимые человеком в реальных играх

Устройство репозитория

В репозитории есть несколько папок:

• dictionaries - словари, используемые для исследования и для интерактивных игр
• research_results - подробные результаты исследования
• src - непосредственно, код проекта

Репозиторий рассчитан только на то, чтобы запускать код из IDE

Есть несколько запускаемых файлов:

• org.example.fiveletters.wordsparsing - пакет с функциональностью для формирования словарей
  • opencorpora.OpenCorporaApplication - парсинг слов с ресурса OpenCorpora.org
  • poiskslov.PoiskSlovApplication - парсинг слов с ресурса поиск-слов.рф
  • textometr.TextometrApplication - парсинг информации о частотности слов с ресурса textometr.ru
• org.example.fiveletters.solving - пакет с функциональностью для взаимодействия с игрой
  • beginningsearch.BeginningSearchApplication - поиск оптимальных стартов для игры
  • cli.FiveLettersCliApplication - CLI для интерактивного прохождения игры
  • research.ResearchApplication - исследование прохождения игры на разных словарях и разных алгоритмах решения

Особенности реализации

• Используемые технологии
  • В проекте не используется никаких фреймворков, в том числе нет DI - всё создается руками
  • Добавлено базовое логирование на основе SLF4J Simple Provider
  • Для HTTP-запросов используется синхронный клиент Apache HttpClient 5.4
  • Для JSON- и XML-сериализации используется jackson (ObjectMapper и XmlMapper)
  • Для HTML-парсинга используется jsoup
• Особенности логики
  • Активно используется работа с битами, потому что 32 уникальные буквы русского алфавита (при условии, что е == ё) отлично помещаются в битовую маску Integer
  • Отдельно учтены кейсы, когда одна и та же буква в слове встречается несколько раз. И, кажется, это сделано максимально корректно
• Оптимизации
  • В рамках исследования производится много вычислений, и эти вычисления занимают довольно много времени, поэтому в коде реализованы многопоточные вычисления на базе ForkJoinPool
  • Я постарался максимально оптимизировать вычисления, но при этом оставить код поддерживаемым. За счет этого все вычисления возможно выполнить на локальном ПК, но некоторые вычисления все-таки занимают довольно много времени - на моем 12-ядерном процессоре самое долгое вычисление заняло у меня около суток

Nice-to-have фичи

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

• Написать тесты. Потому что сейчас тестов почти нет
• Реализовать ретраи для textometr.ru, потому что иногда запросы отваливаются с 500 Internal Server Error, и вся программа падает с ошибкой
• Реализовать поиск частотности слов не через textometr.ru, а по корпусу текстов в OpenCorpora.org, потому что, кажется, это более достоверный источник

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

Все вычисления выполнены на тэге habr-article

Стартовые слова

Статистику для всех стартовых слов можно посмотреть в файле research_results/beginnings/2066_4109.md

Пока что статистика собрана только для одного набора словарей (2066 ответов | 4109 всех слов) и только для стартов из одного слова

Работа алгоритмов

Эвристика по среднему: минимизация среднего кол-ва оставшихся ответов

Алгоритмы \ словари	Оптимальный	Уникальные символы				"Человеческий"
		2 слова	3 слова	4 слова	5 слов
2066 | 6826	3.4458 (0)	3.6066 (0)	4.1764 (0)	5.0514 (0)	6.0102 (35)	3.6003 (15)
2066 | 4109	3.4942 (0)	3.6110 (0)	4.1813 (0)	5.0563 (0)	6.0146 (44)	3.6003 (15)
2066 | 2066	3.5214 (0)	3.6183 (0)	4.1885 (0)	5.0674 (0)	6.0228 (62)	3.6003 (15)
4109 | 6826	3.7243 (0)	3.7786 (0)	4.2697 (0)	5.0923 (0)	6.0370 (166)	3.8686 (61)
4109 | 4109	3.7362 (0)	3.7827 (0)	4.2799 (0)	5.1010 (3)	6.0380 (171)	3.8686 (61)
6826 | 6826	3.9076 (0)	3.9527 (0)	4.3626 (0)	5.1322 (5)	6.0532 (378)	4.0951 (166)

Эвристика по максимуму: минимизация максимального кол-ва оставшихся ответов

Алгоритмы \ словари	Оптимальный	Уникальные символы				"Человеческий"
		2 слова	3 слова	4 слова	5 слов
2066 | 6826	3.5194 (0)	3.6178 (0)	4.1725 (0)	5.0490 (0)	6.0102 (35)	3.6202 (16)
2066 | 4109	3.5286 (0)	3.6207 (0)	4.1813 (0)	5.0698 (0)	6.0146 (44)	3.6003 (16)
2066 | 2066	3.5485 (0)	3.6188 (0)	4.1968 (0)	5.0674 (0)	6.0228 (62)	3.6003 (15)
4109 | 6826	3.7474 (0)	3.8630 (0)	4.2921 (0)	5.0923 (0)	6.0370 (166)	3.8789 (63)
4109 | 4109	3.7633 (0)	3.8696 (0)	4.2977 (0)	5.1052 (3)	6.0380 (171)	3.8789 (63)
6826 | 6826	3.9615 (0)	4.0210 (3)	4.3859 (0)	5.1407 (4)	6.0532 (378)	4.0975 (136)

Легенда таблиц:

• 2066 | 4109
  • 2066 - кол-во возможных ответов
  • 4109 - кол-во слов, допустимых для ввода
• 3.5286 (0)
  • 3.5286 - Среднее кол-во шагов для прохождения игры
  • (0) - Кол-во поражений