Comments 49
Попробовал первую попавшуюся онлайновую версию, что выдал Bing, и на первое же слово из пяти букв оно мне сказало, что такого слова нет :D Как так-то: сущность есть, а слова нет :D
Если серьёзно, то мне пришло в голову словарь всё-таки изначально отсортировать по критерию насколько часто в слове встречаются в полном словаре входящие в него буквы. Детально пока что не продумывал, но, поломаю голову - тема интересная.
В словаре действительно могут быть не все слова. В ту игру, которую играю я (ссылка в статье) тоже загадала пару раз слова, которых нет (об этом кстати написано в статье). Постепенно словарь можно наращить. Merge requests are welcome :-)
Как так-то: сущность есть, а слова нет :D
Жопа есть, а слова нет (с)
В случае канона
Если б словаре было слово например Кавун
Там подбором идёт? Пока не совпадает?
Меня смущает скорость поиска в 2 минуты - кажется что просто подход через последовательную фильтрацию исходного словаря (а потом фильтрацию результатов) означает всего несколько тысяч сравнений, это должно вообще за доли секунды работать.
Ну что вы начинаете, в реальной жизни алгоритмы никому не нужны же :)
Подсчет метрики - это кубический алгоритм. Поэтому там для текущего словаря (2068 слов) и первой попытки - это 2068^3 операций. На вторую попытку остаетс около 100 слов и там поиску уже идем "мгновенно". Остальные попытки - разумеется еще быстрее.
Статья уже была написана и готова к публикации как вдруг игра загадала слово “канон”
дайте угадаю, речь про тиньков идет? У них есть такая игра в банковском клиенте. Там как раз и скула последнее слово, и канон был пару дней назад.
Я тоже сделал что-то похожее на статью - взял отфильтрованный по длине словарь hunspell, для каждой буквы посчитал, в каком количестве слов она встречается, и назначил каждому слову скор как сумму скоров для его букв, не считая повторов. Для каждого запроса скрипт на питоне выводит список подходящих слов, отсортированный по скору. Топовое начальное слово - икота, но я предпочитаю океан. Работает достаточно хорошо, например "океан" -> "акрил" -> "скула". За все время проиграл только один раз: получилось "*есть", но первую букву (весть, жесть, месть, лесть, честь) выяснить не удалось.
А вообще смысл игры в том, чтобы угадывать без помощи компьютера :)
Проверил словарь на наличие слов: "весть", "жесть", "месть", "лесть", "честь". Все на месте, кроме слова "честь". Его я добавил в словарь. Слово "катер" осталось неизменным лидером в качестве первого кандидата. Ни одно из вышеупомянутых слов не стало проблемным. В списке проблемных так и остались только 2 слова: гряда, щепка.
[UPD]: Речь идет действительно про Тинькофф. Мне казалось, что это будет понятно по предоставленным ссылкам :)
Я решил эту игру играть вот так: с помощью нейросети подобрал 5 слов, которые используют 19 уникальных букв. После ввода всех 5 слов всё еще остается пространство для подумать, т.е. поиграть. Отгадано 24 из 25 слов.
Я тоже сделал себе решатель с системой ранжирования слов. Интерфейс постарался повторить как в игре, для смены состояния буквы нужно дважды на нее кликнуть. Система ранжирует слова таким образом чтобы сперва были те слова, которые позволят исключить как можно больше слов в зависимости от текущей ситуации. Если кому-то интересно вот ссылка
https://valyashmelev.github.io/wordle-helper/
Забрал у Вас словарь, спасибо )
Итого теперь 3473 слова.
В качестве первой попытки теперь должно быть слово: "норка" (3 минуты для получения).
Проблемных слов теперь 53: бабка, вояка, дачка, дежка, заика, замор, запор, качка, койка, ласка, лачка, мекка, мочка, мошка, наход, пайка, палка, пилка, пучка, сайка, самка, сивка, силка, симка, сотка, сошка, сушка, терка, тетка, течка, точка, турка, фаска, феска, хамка, хатка, холка, цапка, цацка, чайка, чалка, чарка, чашка, через, честь, четка, чурка, шайка, шитье, шишка, щетка, щурка, щучка.
Вероятность выигрыша по этому словарю составляет 98,4%.
В Вашем словаре отсутствуют следующие слова: жилое, любое, рябая, сытая, умная, чалая, худое, мамон. Все, кроме "мамон", скажем так, как минимум прилагательно-подобные. Скорее их надо удалить из моего словаря. А вот слово "мамон" кажется надо добавить в Ваш.
Теперь есть повод задуматься на тем, что игра дает больше информации, чем использует модель.
P.S. Добавление слова "мамон" в словарь не меняет ни первого кандидата, ни множества проблемных слов. Вероятность выигрыша разве что незначительно повышается :-)
Я только начинающий, поэтому я очень рад, что моя деятельность принесла кому-то пользу, спасибо за обратную связь!)
кстати, а можно ли проблемные слова исключать какими-то словами - сборными, например за 2 хода?
Я думаю можно.
Алгоритм представленный здесь похож на минимакс. Отличие заключается лишь в том, что оппонент (в виде самой игры) никак не может своим ходом повлиять на игру. Поэтому, расчет в глубину нужно вести только от своих ходов.
То, про что Вы говорите как раз и является тем же подходом, но не с глубиной 1 - а с глубиной 2.
Для первого кандидата сложность будет порядка 
.
Для второй попытки уже может быть значительно меньше (если мы выбрали слово "норка"): 
, но всё ещё достаточно большой.
Ещё один вариант, который приходит мне в голову: это помими среднего ещё и подсчитать несмещённую оценку дисперсии. Тогда, применив правило "трех сигм" можно оценить насколько широкий разброс. Правда дальше я пока не думал.
Hidden text
Hidden text
Добавьте для таких как я в решателе мелким шрифтом что переключение типа буквы происходит двойным кликом )
Когда один популярный банк некоторое время назад (больше года, но не помню, когда именно) сделал игру 5Букв, я задался вопросом о самом выгодном первом слове. Написал скрипт, взял за основу открытый словарь существительных. У меня получилось другое самое выгодное слово (если кому интересно, это слово "икота"), а "катера" даже в топе не было. Может, словари разные, не знаю... Но даже если просто подумать, три популярные гласные выгоднее двух, поэтому "икота" выглядит более правдоподобно. На втором месте с минимальным отрывом была "икона", кстати, и её я в один из первых дней придумал в качестве базового слова безо всякого скрипта.
Я реализовывал подбор с учётом частоты нахождения буквы в каждой позиции и оптимальным первым словом у меня получилось "ПОРКА"
тут вопрос в том сколько слов будет исключено, например "норка" и "икона", разница в позициях и только в одной букве, вполне вероятно использование буквы "р" сократит словарь например на 70%, а использование буквы "и" только на 68%, думаю в этом смысл. Но тут лучше мнение автора услышать.
По поводу сокращения словаря: да, действительно так и работает.
Вот немного сухой статистики.
Метрика слова "норка": 101 слов. Статистика: 53 проблемных слова.
Метрика слова "порка": 118 слов. Статистика: 44 проблемных слова.
Метрика слова "икона": 146 слов. Статистика: 66 проблемных слов.
Метрика слова "океан": 146 слов. Статистика: 61 проблемное слово.
Метрика слова "коран": 111 слов. Статистика: 42 проблемных слова.
Лидер по минимальному количеству проблемных слов: "коран". В общем-то, это то, о чем я говорил в статье: жадность не 100% решение, так как можно упереться в локальный минимум.
Когда остается две или три неотгаданные буквы, лучше не подбирать слова с сохранением угаданных, а выбрать слово, содержащее максимум букв из возможных отставшихся вариантов. Тогда исключается сценарий потери нескольких ходов в попытках подбора. Теряется только один ход.
Играю таким способом в "octordle" на сайте britannica.com
да, я тоже такого же мнения, когда остаётся 3 хода, то есть половина, я два хода делаю максимально "пустые" с одной целью - минимизировать набор оставшихся вариантов. То есть первый ход например "норка" сильно режет словарь, а потом уже цель 5 ходов резать словарь еще сильнее, а не угадывать слово. Тут падаёт качество отгадывания применительно к числу попыток, но зато например можно попытаться исключить "сложные" слова.
Поленился писать код.
Первый раз поиграл мозгом. Верный ответ нашел, но было тяжко.
Почесал репу, и выработал такой подход:
Сначала ввожу четыре слова, которые подобраны так, чтоб перебрать все гласные без повтора букв.
Далее этого пробую искать пятое слово по вхождению и исключению букв из первых четырех, вот этот сервис неплохо подходит. Зачастую на этом этапе правильный ответ очевиден.
Но если поиск возвращает много результатов, то для его сужения выбираю слово с другими согласными с помощью того же сервиса, после чего снова повторяю поиск по вхождению и исключению.
Одна неудача за всё время. Времени на сей комментарий потратил больше, чем на 5 раундов игры.
Идея решения
ну вот, а я как раз хотел написать такую статью )
Вашу пока не читал, сейчас нет времени, озвучу свой принцип. Интуитивно я пишу всегда первое слово "КОРАН", а потом уже смотрю куда двигаться. Сегодня для статьи проводил подготовительные действия, в частности сделал вот такую таблицу по корпусу русских слов:
Как видно - моя интуиция не подвела, слово "КОРАН" содержит практически весь топ частот букв. Но позже я сделал поиск по частотам и получил слово "КРОАТ" (да, такое слово есть). Не думаю что это принципиально, но вариант хороший.
Вот в этом комментарии выяснилось, что мой словарь (2068 слов) несколько ограничен. По более полному словарю (3474 слова) моё топовое слово: "норка". Интересно, что "норка" и "коран" являются палиндромами. Для Вашего метода метрика этих двух слов одинаковая. Моя модель считает, что "норка" всё же лучше. Правда насколько я сейчас не могу сказать. Но можно поэкспериментировать. Видимо нужно ввести 4 режим работы: подсчет метрики для конкретного слова.
Значение моей метрики для слова "норка": 352401.
Значение моей метрики для слова "коран": 386809.
Я правильно понимаю что метрика учитывает не только вес (частоту) буквы, но и ее положение в слове?
Смотрите, метрика учитывает только одно: сколько подходящих слов останется в среднем (после получения обратной связи от игры). Те значения, которые я привел выше нужно еще поделить на размер словаря.
Итого:
Для "норка":
слово.Для "коран":
слов.
Я добавил четвертный режим работы: вычисления метрики для слова. Можно теперь проделывать эти эксперименты самостоятельно.
Первое слово, которое нужно ввести в игру: катер
Это слово по всему корпусу слов или какой-то ограниченный словарь?
Вот в этом комментарии выяснилось, что ограниченный. Для более полного словаря (3474 слов) это слово: "норка".
понял, у меня 3483, так что сопоставимо, кстати где вы брали словарь?
как я выше написал, слово "кроат" должно быть более эффективным, скачал ваш проект и по метрикам оно даже хуже "коран":
>5LettersBin.exe metric altrussian5.txt коран
Loaded 3475 words.
Word: коран, Metric 386809. Mean number of words: 111.
>5LettersBin.exe metric altrussian5.txt норка
Loaded 3475 words.
Word: норка, Metric 352401. Mean number of words: 101.
>5LettersBin.exe metric altrussian5.txt кроат
Loaded 3475 words.
Word: кроат, Metric 418793. Mean number of words: 121. Вопрос - вы всё же учитываете положение букв?
Мне кажется нужно частоту буквы умножать на частоту позиции в слове, например (дальше все цифры придуманы) для слова "коран" для буквы "а" например по словарю имеем такие коэффициенты для каждого места:
1.7, 2.1, 1.9, 2.2, 1.95
таки образом для слов "норка" и "коран" для буквы "а" будет разный вес, например при частоте "а" в 1900 для "коран" это будет 1900*2.2, а для "норка" 2200*1.95. (повторюсь еще раз, числа придуманы и не соответствуют действительности, это просто пример).
Что даст этот механизм подсчёта? Мы будем стараться выбирать слово таким образом, чтобы символ оказывался как можно ближе к более популярной позиции в слове.
Я никак не учитываю частоту букв. Положение букв учитываю в ограничениях:
жёлтый: точное совпадение
белый: присутствие буквы и отсуствие ее на позиции
серый: отсутствие букву
Рекомендую подсчитать еще статистики и обратить внимание на количество проблемных слов.
Что касается Вашей метрики - она совсем другая. Вероятнее всего тоже имеет место быть.
Посчитал с учетом положения букв в слове, получилось так
тут те слова что обсуждались в комментариях, как видно "норка" и "порка" лидируют по положению букв в словах, хотя уступают по наличию в слове. И тут вопрос - как эта информация может быть полезна для выбора слов?
кстати слово "серка" по вашей метрике
Word: серка, Metric 417199. Mean number of words: 120.
с самым высоким рейтингом исходя из позиций букв в слове.
мне кажется точная позиция должна давать сильный буст, а вот просто факт наличия в слове не должен сильно сказываться на рейтинге, попробую уменьшить его в 10 раз например.
с понижением рейтинга в 10 раз всплыло слово "кайло"
Word: кайло, Metric 680355. Mean number of words: 196.
Видимо я копаю не в ту сторону. Я просто пытаюсь нащупать границу между "найти загаданное слово" и "исключить ненужные слова и тогда останется только загаданное слово".
Сегодня слово "бренд" и его нет в наших словарях, нет его и в сервисе, который в одном из первых комментах указан
Я сам, еще до того как добрался до ПК в голове подбором слово "бренд" получил, но как-то сомневался. Но по сути это оказался наверное единственный вариант, проверял по другому из сервисов тоже из комментария
Hidden text
Ну ... и ничего страшного. Еще и слова "тренд" нет. Оба добавил. Едем дальше.
Проанализировал Ваш словарь - он в точности повторяет мой, за исключением слов, которые я добавил: коран и мамон. +Теперь еще бренд и тренд.
P.S. Сегодняшнее слово все равно отгадал :-)
В общем, считаю задачу на 100% решеной.
Мои начальные слова такие: Стенд, кварц, Олимп, гуашь.
Подбирал по сервису исходя из двух факторов:
1) частота букв
2) старался не использовать топ гласных в начале, чтобы на последующие слова было больше вариантов
Уверен, что возможно это не самые оптимальные слова, но не угадывать слова с ними у меня ещё ни разу не получилось)
Подкрутил немного метрику и теперь отгадываются все 100% слов словаря в рамках 6 попыток. Соответствующий коммит.
Тут уже много говорили о том, что при угадывании 3-4 букв может начаться "информационный голод". Пример из одного комментария: весть, жесть, месть, лесть, честь.
Идея в том, что нужно подобрать такое слово, чтобы как можно больше таких вариантов отсеить за раз.
Что доделано в итоге.
Каждая попытка теперь может использовать все слова из словаря, а не только из оставшихся.
Мы предполагаем, что слова загадываются из словаря и поэтому должно остаться хотя бы одно слово. Если слово вычеркивает все оставшиеся слова (оно теперь может это делать), то получает не нулевое значение метрики, а наоборот - самое наибольшее. Самое наибольшее значение - это количество оставшихся слов.
Отдельно нужно обработать случай когда осталось одно слово - и тут в качестве кандидата нужно его просто вернуть. Это нужно отдельно обрабатывать, так как в противном случае метрика (после всех изменений выше) будет одинакова для всех слов словаря. Это происходит по причине того, что подходящее слово имеет значение метрики в рамках одного предположения всегда 1, так как оно: либо все слова отсеивает и получает значение 1, либо оставляет только загаданное слово и получает тоже значение 1.
Механика и стратегия игры «5букв»