Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 52
Попробовал первую попавшуюся онлайновую версию, что выдал 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. Добавление слова "мамон" в словарь не меняет ни первого кандидата, ни множества проблемных слов. Вероятность выигрыша разве что незначительно повышается :-)
Я только начинающий, поэтому я очень рад, что моя деятельность принесла кому-то пользу, спасибо за обратную связь!)
Я думаю можно.
Алгоритм представленный здесь похож на минимакс. Отличие заключается лишь в том, что оппонент (в виде самой игры) никак не может своим ходом повлиять на игру. Поэтому, расчет в глубину нужно вести только от своих ходов.
То, про что Вы говорите как раз и является тем же подходом, но не с глубиной 1 - а с глубиной 2.
Для первого кандидата сложность будет порядка 
.
Для второй попытки уже может быть значительно меньше (если мы выбрали слово "норка"): 
, но всё ещё достаточно большой.
Ещё один вариант, который приходит мне в голову: это помими среднего ещё и подсчитать несмещённую оценку дисперсии. Тогда, применив правило "трех сигм" можно оценить насколько широкий разброс. Правда дальше я пока не думал.
Когда один популярный банк некоторое время назад (больше года, но не помню, когда именно) сделал игру 5Букв, я задался вопросом о самом выгодном первом слове. Написал скрипт, взял за основу открытый словарь существительных. У меня получилось другое самое выгодное слово (если кому интересно, это слово "икота"), а "катера" даже в топе не было. Может, словари разные, не знаю... Но даже если просто подумать, три популярные гласные выгоднее двух, поэтому "икота" выглядит более правдоподобно. На втором месте с минимальным отрывом была "икона", кстати, и её я в один из первых дней придумал в качестве базового слова безо всякого скрипта.
Я реализовывал подбор с учётом частоты нахождения буквы в каждой позиции и оптимальным первым словом у меня получилось "ПОРКА"
По поводу сокращения словаря: да, действительно так и работает.
Вот немного сухой статистики.
Метрика слова "норка": 101 слов. Статистика: 53 проблемных слова.
Метрика слова "порка": 118 слов. Статистика: 44 проблемных слова.
Метрика слова "икона": 146 слов. Статистика: 66 проблемных слов.
Метрика слова "океан": 146 слов. Статистика: 61 проблемное слово.
Метрика слова "коран": 111 слов. Статистика: 42 проблемных слова.
Лидер по минимальному количеству проблемных слов: "коран". В общем-то, это то, о чем я говорил в статье: жадность не 100% решение, так как можно упереться в локальный минимум.
Когда остается две или три неотгаданные буквы, лучше не подбирать слова с сохранением угаданных, а выбрать слово, содержащее максимум букв из возможных отставшихся вариантов. Тогда исключается сценарий потери нескольких ходов в попытках подбора. Теряется только один ход.
Играю таким способом в "octordle" на сайте britannica.com
Поленился писать код.
Первый раз поиграл мозгом. Верный ответ нашел, но было тяжко.
Почесал репу, и выработал такой подход:
Сначала ввожу четыре слова, которые подобраны так, чтоб перебрать все гласные без повтора букв.
Далее этого пробую искать пятое слово по вхождению и исключению букв из первых четырех, вот этот сервис неплохо подходит. Зачастую на этом этапе правильный ответ очевиден.
Но если поиск возвращает много результатов, то для его сужения выбираю слово с другими согласными с помощью того же сервиса, после чего снова повторяю поиск по вхождению и исключению.
Одна неудача за всё время. Времени на сей комментарий потратил больше, чем на 5 раундов игры.
Вот в этом комментарии выяснилось, что мой словарь (2068 слов) несколько ограничен. По более полному словарю (3474 слова) моё топовое слово: "норка". Интересно, что "норка" и "коран" являются палиндромами. Для Вашего метода метрика этих двух слов одинаковая. Моя модель считает, что "норка" всё же лучше. Правда насколько я сейчас не могу сказать. Но можно поэкспериментировать. Видимо нужно ввести 4 режим работы: подсчет метрики для конкретного слова.
Значение моей метрики для слова "норка": 352401.
Значение моей метрики для слова "коран": 386809.
Смотрите, метрика учитывает только одно: сколько подходящих слов останется в среднем (после получения обратной связи от игры). Те значения, которые я привел выше нужно еще поделить на размер словаря.
Итого:
Для "норка":
слово.Для "коран":
слов.
Я добавил четвертный режим работы: вычисления метрики для слова. Можно теперь проделывать эти эксперименты самостоятельно.
Вот в этом комментарии выяснилось, что ограниченный. Для более полного словаря (3474 слов) это слово: "норка".
Здесь. Поделитесь, пожалуйста, своим.
Я никак не учитываю частоту букв. Положение букв учитываю в ограничениях:
жёлтый: точное совпадение
белый: присутствие буквы и отсуствие ее на позиции
серый: отсутствие букву
Рекомендую подсчитать еще статистики и обратить внимание на количество проблемных слов.
Что касается Вашей метрики - она совсем другая. Вероятнее всего тоже имеет место быть.
Ну ... и ничего страшного. Еще и слова "тренд" нет. Оба добавил. Едем дальше.
Проанализировал Ваш словарь - он в точности повторяет мой, за исключением слов, которые я добавил: коран и мамон. +Теперь еще бренд и тренд.
P.S. Сегодняшнее слово все равно отгадал :-)
В общем, считаю задачу на 100% решеной.
Мои начальные слова такие: Стенд, кварц, Олимп, гуашь.
Подбирал по сервису исходя из двух факторов:
1) частота букв
2) старался не использовать топ гласных в начале, чтобы на последующие слова было больше вариантов
Уверен, что возможно это не самые оптимальные слова, но не угадывать слова с ними у меня ещё ни разу не получилось)
Подкрутил немного метрику и теперь отгадываются все 100% слов словаря в рамках 6 попыток. Соответствующий коммит.
Тут уже много говорили о том, что при угадывании 3-4 букв может начаться "информационный голод". Пример из одного комментария: весть, жесть, месть, лесть, честь.
Идея в том, что нужно подобрать такое слово, чтобы как можно больше таких вариантов отсеить за раз.
Что доделано в итоге.
Каждая попытка теперь может использовать все слова из словаря, а не только из оставшихся.
Мы предполагаем, что слова загадываются из словаря и поэтому должно остаться хотя бы одно слово. Если слово вычеркивает все оставшиеся слова (оно теперь может это делать), то получает не нулевое значение метрики, а наоборот - самое наибольшее. Самое наибольшее значение - это количество оставшихся слов.
Отдельно нужно обработать случай когда осталось одно слово - и тут в качестве кандидата нужно его просто вернуть. Это нужно отдельно обрабатывать, так как в противном случае метрика (после всех изменений выше) будет одинакова для всех слов словаря. Это происходит по причине того, что подходящее слово имеет значение метрики в рамках одного предположения всегда 1, так как оно: либо все слова отсеивает и получает значение 1, либо оставляет только загаданное слово и получает тоже значение 1.
Сделал из спортивного интереса тоже себе решатель, отгадывает 100% слов. Заодно и сама игра тоже есть - два в одном. Доступно оналйн: https://alexbobrow.github.io/five-js/
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Механика и стратегия игры «5букв»