01.06.2024 22:36
apodavalov 44 2800 Источник

Введение

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

После каждой попытки буквы окрашиваются в следующие цвета.

  • Серый – означает, что буквы нет в слове.

  • Белый – означает, что буква есть в слове, но её нет в данной позиции.

  • Жёлтый – означает, что буква есть в данной позиции слова.

Очевидно, что если слово угадано, то все буквы окрашиваются в жёлтый цвет.

Буква Ё в игре не используется, вместо неё используется буква Е.

Далее ситуации соответствующие цветам будем просто обозначать этими цветами.

Подготовка и постановка цели и задач

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

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

  • Игра использует слова из найденного словаря.

  • Игра не сопоставляет слову какой-либо вес (например: популярность слова). Выбор каждого слова из словаря равновероятен.

  • Слова между играми могут повторяться.

После обработки вышеуказанного файла получилось 2068 слов. 

Примечание: по каким-то причинам исходный словарь не содержал следующие слова кошка, скула, хмель. Эти слова добавлены вручную.

Цель и задачи: 

  • Придумать стратегию игры, позволяющую выигрывать с вероятностью 99,9% в рамках полученного словаря.

  • Интерактивное консольное приложение для взаимодействия с игрой. Игра предлагает слово для ввода, а пользователь вводит ответ игры.

Идея решения

В качестве хода в игре используется слово. Чтобы понять какое слово использовать, необходимо ввести его числовую метрику. 

Пусть словарь w_kсодержит n, n>0, которые которые уже удовлетворяют требованиям предыдущих k-1попыток. Пусть некоторое слово с индексом j,j=\overline{0;n-1}выбрано игрой (далее: слово j). Пусть игрок делает предположение некоторого слова с индексом i,i=\overline{0;n-1} (далее: слово i). Сколько слов останется, если выбрано слово i, а игра загадала слово j? Моделирование процесса позволит отфильтровать слова из словаря w_k для любой пары (i,j).

В рамках одного слова i, но всех возможных слов j можно найти количество оставшихся слов для каждой пары (i,j) и, получить их среднее арифметическое. Это и будет нашей метрикой, которую будем называть метрикой совпадений. Чем ближе метрика к 0 – тем лучше.

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

Реализация

Поиск лучшего кандидата

Сердце реализации – это функция получения лучших предположений. В ней действительно будет 3 вложенных цикла. Для всего словаря необходимо 2068^3=8844058432 операций по выяснению удовлетворения словом ограничений. Возможно цифра покажется большой, но (забегая вперед) даже программирование “в лоб” позволяет найти лучшего кандидата примерно за 2 минуты.

Тем не менее попробуем ещё ускорить. Заметим, что в рамках одной попытки фигурирует один и тот же набор слов – словарь w_k. При поиске минимума используется сравнение среднего арифметического, при вычислении которого последняя операция это всегда деление на одно и тоже число – размер словаря, т. е. |w_k|. Поэтому среднее арифметическое можно заменить простой суммой (как бы умножив его снова на размер словаря). Что это даст? Во-первых: никаких чисел с плавающей точкой. Во-вторых, теперь мы можем поймать момент когда оценка для текущего предположения стала больше, чем хранимый текущий минимум. Это означает, что предположение точно хуже и поэтому отбросить его можно “досрочно”. Чем меньше становится минимум – тем быстрее поиск.

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

Структуры данных для ограничений

Для хранения ограничений будем использовать два массива.

  • Массив состояний каждой буквы алфавита. Каждый элемент может принимать одно из следующих значений: неизвестно, обязательно присутствует в слове, обязательно отсутствует в слове. Размер: 32 элемента. Далее сам массив будем называть массивом букв.

  • Массив состояний каждой позиции. Каждый элемент может принимать следующие значения: неизвестно, известно. В состоянии известно дополнительно хранится информация о какой букве идет речь и признак присутствия (жёлтая ситуация) или отсутствия (белая ситуация) этой буквы на позиции. Размер: 5 элементов.  Далее сам массив будем называть массивом позиций. Массив позиций располагает информацией только о жёлтых и белых ситуациях.

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

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

Маска представляет из себя 5 упорядоченных элементов. Каждый элемент это одно из трех значений: серый, белый, жёлтый.

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

  • Получение состояния по предполагаемому и загаданному словам (для имитации игры).

  • Получение состояния по слову и маске.

  • Проверка удовлетворяет ли слово состоянию.

Получение состояния по двум словам.

  1. Объявить массив букв, в котором все элементы в состоянии неизвестно. Объявить массив позиций, в котором все элементы в состоянии неизвестно.

  2. Пометить в массиве букв как отсутствующие все буквы предполагаемого слова.

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

  4. Организовать цикл прохода по массиву позиций. Каждую позицию обновить по следующим правилам.

    1. (Жёлтая ситуация) Если буквы в текущем позиции загаданного слова и предполагаемого слова совпадают, то позиция переходит в состояние известно с соответствующей буквой из предполагаемого слова и признаком присутствия.

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

Получение состояния по слову и маске.

  1. Объявить массив букв, в котором все элементы в состоянии неизвестно. Объявить массив позиций, в котором все элементы в состоянии неизвестно.

  2. Организовать цикла прохода по буквам слова и соответствующим элементам маски параллельно.

    1. Элемент маски серый. Пометить букву в массиве букв как отсутствующую.

    2. Элемент маски белый. Пометить букву в массиве букв как присутствующую. Записать в соответствующий элемент массива позиций известно вместе с соответствующей буквой слова и признаком её отсутствия на позиции.

    3. Элемент маски жёлтый. Пометить букву в массиве букв как присутствующую. Записать в соответствующий элемент массива позиций известно вместе с соответствующей буквой слова и признаком её присутствия на позиции.

Проверка подходит ли слово под ограничения.

  1. Если хотя бы одна из букв слова помечена как отсутствующая в массиве букв – слово не подходит. Конец.

  2. Если хотя бы одна из букв не подходит под ограничение соответствующего элемента в массиве позиций – слово не подходит. Конец.

  3. Если количество уникальных букв слова помеченных как присутствующие в массиве букв меньше, чем общее количество букв помеченных как присутствующие в массиве букв – слово не подходит. Конец.

  4. Достижение этого пункта сигнализирует о том, что слово подходит.

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

Режимы работы приложения

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

  • Вычисление первого предположения.

  • Интерактивный режим работы с пользователем.

  • Сбор полной статистики по всем словам.

Интерактивный режим подразумевает работу следующего сценария.

  1. Приложение предлагает слово для ввода в игру.

  2. Пользователь вводит это слово в игру. Игра окрашивает буквы в цвета.

  3. Пользователь вводит маску в приложение. Маска состоит из 5 символов, где каждый символ это: y – цвет буквы жёлтый, w – цвет буквы белый, g – цвет буквы серый.

  4. Программа предлагает следующее слово для ввода в игру и процесс повторяется до тех пор пока пользователь не введёт yyyyy.

Сбор полной статистики имитирует раунды игры. Количество раундов соответствует количеству слов в словаре. Каждое слово из словаря загадывается ровно один раз. В процессе определяются следующие величины.

  • Максимальное количество попыток.

  • Количество проигрышей (и сами загаданные слова).

Результаты

Весь код можно найти тут. 

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

Сбор полной статистики тоже занимает около минуты. Два слова, которые не могут быть отгаданы за 6 попыток: гряда и щепка. Для них требуется 7 попыток. Итого, вероятность выигрыша составляет2066 \div 2068=0,999=99,9\%.

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

Примеры отгаданных слов

Слово

Цвета (реакция игры)

К

А

Т

Е

Р

Б

Б

С

С

С

С

О

Л

К

А

Ж

С

Б

Б

Ж

С

К

У

Л

А

Ж

Ж

Ж

Ж

Ж

Слово

Цвета (реакция игры)

К

А

Т

Е

Р

С

С

С

Б

С

С

Е

Л

И

Н

С

Б

Б

С

С

П

Л

Е

М

Я

С

Б

Ж

Б

С

Х

М

Е

Л

Ь

С

Ж

Ж

Ж

Ж

Ш

М

Е

Л

Ь

Ж

Ж

Ж

Ж

Ж

Слово

Цвета (реакция игры)

К

А

Т

Е

Р

С

Б

С

С

Б

П

У

Р

Г

А

Ж

Ж

Ж

Ж

Ж

Заключение

Статья уже была написана и готова к публикации как вдруг игра загадала слово “канон”. Процесс отгадывания проиллюстрирован на рисунке.

Слово

Цвета (реакция игры)

К

А

Т

Е

Р

Ж

Ж

С

С

С

К

А

Л

А

Н

Ж

Ж

С

С

Ж

К

А

М

И

Н

Ж

Ж

С

С

Ж

К

А

Н

О

Н

Ж

Ж

Ж

Ж

Ж

Стоит обратить внимание, что на второй попытке одна буква А подсвечена желтым, а другая – серым. Правилам игры допускают повторение букв в слове, но как игра такие буквы раскрашивает, они не раскрывают. Всего скорее упрощенный алгоритм раскрытия букв примерно следующий.

  1. Раскрыть все совпадающие буквы (жёлтая ситуация) и убрать их из дальнейшего рассмотрения.

  2. Для каждой уникальной буквы (из оставшихся) загаданного слова построить ассоциативный массив: буква \rightarrowколичество.

  3. Пройтись по всем буквам предполагаемого слова. Для каждой буквы проверить есть ли она в ассоциативном массиве. Если есть, и количество не достигло нуля, то покрасить букву в белый цвет и уменьшить количество на единицу. Во всех остальных случаях покрасить букву в серый цвет.

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

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

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

  • Помечаем букву в массиве букв как отсутствующую только тогда, когда в массиве букв она не помечена присутствующей.

  • Обработка серой ситуации дополняется обновление массива позиций аналогично белой ситуации.

Таким образом, ранее рассмотренные серые буквы могут стать белыми и для этого нужно только обновить массив букв. Буква, став однажды белой, остается белой “навсегда”.

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

P. S.

Статьи в подобном стиле, разбирающие различные алгоритмы и структуры данных, можно найти на моём Telegram канале (https://telegram.me/GetHiredByFAANG).

Комментарии (44)


  1. nronnie
    01.06.2024 23:17
    #26889629
    +1

    Попробовал первую попавшуюся онлайновую версию, что выдал Bing, и на первое же слово из пяти букв оно мне сказало, что такого слова нет :D Как так-то: сущность есть, а слова нет :D

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


    1. apodavalov Автор
      01.06.2024 23:17
      #26889637

      В словаре действительно могут быть не все слова. В ту игру, которую играю я (ссылка в статье) тоже загадала пару раз слова, которых нет (об этом кстати написано в статье). Постепенно словарь можно наращить. Merge requests are welcome :-)


    1. Dolios
      01.06.2024 23:17
      #26892161

      Как так-то: сущность есть, а слова нет :D

      Жопа есть, а слова нет (с)


      1. apodavalov Автор
        01.06.2024 23:17
        #26892163

        Ваше слово на букву Ж состоит из 4 букв, а не из 5. Поэтому и нет :)


        1. Dolios
          01.06.2024 23:17
          #26892165

          Игра, которую вы описали, более известна как "Быки и коровы" и вот в её классическом варианте как раз слова из 4 букв были :)


          1. apodavalov Автор
            01.06.2024 23:17
            #26892171

            Да я просто пошутить (тоже?) хотел :)


            1. Dolios
              01.06.2024 23:17
              #26892177

              Не время улыбаться!


  1. LeshaRB
    01.06.2024 23:17
    #26889961

    В случае канона
    Если б словаре было слово например Кавун
    Там подбором идёт? Пока не совпадает?


    1. apodavalov Автор
      01.06.2024 23:17
      #26891137

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


  1. Mox
    01.06.2024 23:17
    #26890015
    +2

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


    1. ToSHiC
      01.06.2024 23:17
      #26890553
      +1

      Ну что вы начинаете, в реальной жизни алгоритмы никому не нужны же :)


    1. apodavalov Автор
      01.06.2024 23:17
      #26890957

      Подсчет метрики - это кубический алгоритм. Поэтому там для текущего словаря (2068 слов) и первой попытки - это 2068^3 операций. На вторую попытку остаетс около 100 слов и там поиску уже идем "мгновенно". Остальные попытки - разумеется еще быстрее.


  1. lrrr11
    01.06.2024 23:17
    #26890771
    +1

    Статья уже была написана и готова к публикации как вдруг игра загадала слово “канон”

    дайте угадаю, речь про тиньков идет? У них есть такая игра в банковском клиенте. Там как раз и скула последнее слово, и канон был пару дней назад.

    Я тоже сделал что-то похожее на статью - взял отфильтрованный по длине словарь hunspell, для каждой буквы посчитал, в каком количестве слов она встречается, и назначил каждому слову скор как сумму скоров для его букв, не считая повторов. Для каждого запроса скрипт на питоне выводит список подходящих слов, отсортированный по скору. Топовое начальное слово - икота, но я предпочитаю океан. Работает достаточно хорошо, например "океан" -> "акрил" -> "скула". За все время проиграл только один раз: получилось "*есть", но первую букву (весть, жесть, месть, лесть, честь) выяснить не удалось.

    А вообще смысл игры в том, чтобы угадывать без помощи компьютера :)


    1. apodavalov Автор
      01.06.2024 23:17
      #26890975

      Проверил словарь на наличие слов: "весть", "жесть", "месть", "лесть", "честь". Все на месте, кроме слова "честь". Его я добавил в словарь. Слово "катер" осталось неизменным лидером в качестве первого кандидата. Ни одно из вышеупомянутых слов не стало проблемным. В списке проблемных так и остались только 2 слова: гряда, щепка.

      [UPD]: Речь идет действительно про Тинькофф. Мне казалось, что это будет понятно по предоставленным ссылкам :)


  1. seregadomain
    01.06.2024 23:17
    #26890981
    +2

    Я решил эту игру играть вот так: с помощью нейросети подобрал 5 слов, которые используют 19 уникальных букв. После ввода всех 5 слов всё еще остается пространство для подумать, т.е. поиграть. Отгадано 24 из 25 слов.


  1. N1O2I3N4O5
    01.06.2024 23:17
    #26890983

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

    https://valyashmelev.github.io/wordle-helper/


    1. apodavalov Автор
      01.06.2024 23:17
      #26891133

      Забрал у Вас словарь, спасибо )

      Итого теперь 3473 слова.

      В качестве первой попытки теперь должно быть слово: "норка" (3 минуты для получения).

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

      Вероятность выигрыша по этому словарю составляет 98,4%.

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

      Теперь есть повод задуматься на тем, что игра дает больше информации, чем использует модель.

      P.S. Добавление слова "мамон" в словарь не меняет ни первого кандидата, ни множества проблемных слов. Вероятность выигрыша разве что незначительно повышается :-)


      1. N1O2I3N4O5
        01.06.2024 23:17
        #26891141
        +2

        Я только начинающий, поэтому я очень рад, что моя деятельность принесла кому-то пользу, спасибо за обратную связь!)


      1. Zara6502
        01.06.2024 23:17
        #26896117

        кстати, а можно ли проблемные слова исключать какими-то словами - сборными, например за 2 хода?


        1. apodavalov Автор
          01.06.2024 23:17
          #26897979

          Я думаю можно.

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

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

          Для первого кандидата сложность будет порядка 3475^6=1760876321572509765625.

          Для второй попытки уже может быть значительно меньше (если мы выбрали слово "норка"): 101^6=1061520150601, но всё ещё достаточно большой.

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


          1. Zara6502
            01.06.2024 23:17
            #26898119

            я очень далек от математики, но я как-то не вижу таких огромных цифр, возможно если речь про оптимальное решение, но мне кажется это больше для разминки ума всё тех же математиков, а работающий практический алгоритм для 99% ситуаций быстрый и простой. ИМХО.


    1. Zara6502
      01.06.2024 23:17
      #26896077

      Hidden text

      Hidden text

      Добавьте для таких как я в решателе мелким шрифтом что переключение типа буквы происходит двойным кликом )


  1. a6pakcac
    01.06.2024 23:17
    #26890985
    +1

    Когда один популярный банк некоторое время назад (больше года, но не помню, когда именно) сделал игру 5Букв, я задался вопросом о самом выгодном первом слове. Написал скрипт, взял за основу открытый словарь существительных. У меня получилось другое самое выгодное слово (если кому интересно, это слово "икота"), а "катера" даже в топе не было. Может, словари разные, не знаю... Но даже если просто подумать, три популярные гласные выгоднее двух, поэтому "икота" выглядит более правдоподобно. На втором месте с минимальным отрывом была "икона", кстати, и её я в один из первых дней придумал в качестве базового слова безо всякого скрипта.


    1. amphasis
      01.06.2024 23:17
      #26892737

      Я реализовывал подбор с учётом частоты нахождения буквы в каждой позиции и оптимальным первым словом у меня получилось "ПОРКА"


    1. Zara6502
      01.06.2024 23:17
      #26896103

      тут вопрос в том сколько слов будет исключено, например "норка" и "икона", разница в позициях и только в одной букве, вполне вероятно использование буквы "р" сократит словарь например на 70%, а использование буквы "и" только на 68%, думаю в этом смысл. Но тут лучше мнение автора услышать.


      1. apodavalov Автор
        01.06.2024 23:17
        #26898061

        По поводу сокращения словаря: да, действительно так и работает.

        Вот немного сухой статистики.

        • Метрика слова "норка": 101 слов. Статистика: 53 проблемных слова.

        • Метрика слова "порка": 118 слов. Статистика: 44 проблемных слова.

        • Метрика слова "икона": 146 слов. Статистика: 66 проблемных слов.

        • Метрика слова "океан": 146 слов. Статистика: 61 проблемное слово.

        • Метрика слова "коран": 111 слов. Статистика: 42 проблемных слова.

        Лидер по минимальному количеству проблемных слов: "коран". В общем-то, это то, о чем я говорил в статье: жадность не 100% решение, так как можно упереться в локальный минимум.


  1. Willy64
    01.06.2024 23:17
    #26891041
    +2

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

    Играю таким способом в "octordle" на сайте britannica.com


    1. Zara6502
      01.06.2024 23:17
      #26896115

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


  1. moonster
    01.06.2024 23:17
    #26892055

    Поленился писать код.

    Первый раз поиграл мозгом. Верный ответ нашел, но было тяжко.

    Почесал репу, и выработал такой подход:

    Сначала ввожу четыре слова, которые подобраны так, чтоб перебрать все гласные без повтора букв.

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

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

    Одна неудача за всё время. Времени на сей комментарий потратил больше, чем на 5 раундов игры.


  1. Zara6502
    01.06.2024 23:17
    #26893815

    Идея решения

    ну вот, а я как раз хотел написать такую статью )

    Вашу пока не читал, сейчас нет времени, озвучу свой принцип. Интуитивно я пишу всегда первое слово "КОРАН", а потом уже смотрю куда двигаться. Сегодня для статьи проводил подготовительные действия, в частности сделал вот такую таблицу по корпусу русских слов:

    Как видно - моя интуиция не подвела, слово "КОРАН" содержит практически весь топ частот букв. Но позже я сделал поиск по частотам и получил слово "КРОАТ" (да, такое слово есть). Не думаю что это принципиально, но вариант хороший.


    1. apodavalov Автор
      01.06.2024 23:17
      #26894351

      Вот в этом комментарии выяснилось, что мой словарь (2068 слов) несколько ограничен. По более полному словарю (3474 слова) моё топовое слово: "норка". Интересно, что "норка" и "коран" являются палиндромами. Для Вашего метода метрика этих двух слов одинаковая. Моя модель считает, что "норка" всё же лучше. Правда насколько я сейчас не могу сказать. Но можно поэкспериментировать. Видимо нужно ввести 4 режим работы: подсчет метрики для конкретного слова.


      1. apodavalov Автор
        01.06.2024 23:17
        #26894417

        • Значение моей метрики для слова "норка": 352401.

        • Значение моей метрики для слова "коран": 386809.


        1. Zara6502
          01.06.2024 23:17
          #26895813

          Я правильно понимаю что метрика учитывает не только вес (частоту) буквы, но и ее положение в слове?


          1. apodavalov Автор
            01.06.2024 23:17
            #26895859

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

            Итого:

            • Для "норка": 352401/3475\approx101слово.

            • Для "коран": 386809/3475\approx111слов.

            Я добавил четвертный режим работы: вычисления метрики для слова. Можно теперь проделывать эти эксперименты самостоятельно.


  1. Zara6502
    01.06.2024 23:17
    #26893843

    Первое слово, которое нужно ввести в игру: катер

    Это слово по всему корпусу слов или какой-то ограниченный словарь?


    1. apodavalov Автор
      01.06.2024 23:17
      #26894355

      Вот в этом комментарии выяснилось, что ограниченный. Для более полного словаря (3474 слов) это слово: "норка".


      1. Zara6502
        01.06.2024 23:17
        #26895991

        понял, у меня 3483, так что сопоставимо, кстати где вы брали словарь?


        1. apodavalov Автор
          01.06.2024 23:17
          #26898071

          Здесь. Поделитесь, пожалуйста, своим.


          1. Zara6502
            01.06.2024 23:17
            #26898103

            у меня всё сырое и на коленках, в цикле убираю всё отсюда, лень отдельным файлом оформить, всё что делаю я работает доли секунды, просто эксперименты.


      1. Zara6502
        01.06.2024 23:17
        #26896043

        как я выше написал, слово "кроат" должно быть более эффективным, скачал ваш проект и по метрикам оно даже хуже "коран":

        >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. (повторюсь еще раз, числа придуманы и не соответствуют действительности, это просто пример).

        Что даст этот механизм подсчёта? Мы будем стараться выбирать слово таким образом, чтобы символ оказывался как можно ближе к более популярной позиции в слове.


        1. apodavalov Автор
          01.06.2024 23:17
          #26898133

          Я никак не учитываю частоту букв. Положение букв учитываю в ограничениях:

          • жёлтый: точное совпадение

          • белый: присутствие буквы и отсуствие ее на позиции

          • серый: отсутствие букву

          Рекомендую подсчитать еще статистики и обратить внимание на количество проблемных слов.

          Что касается Вашей метрики - она совсем другая. Вероятнее всего тоже имеет место быть.


  1. Zara6502
    01.06.2024 23:17
    #26897153

    Посчитал с учетом положения букв в слове, получилось так

    тут те слова что обсуждались в комментариях, как видно "норка" и "порка" лидируют по положению букв в словах, хотя уступают по наличию в слове. И тут вопрос - как эта информация может быть полезна для выбора слов?


    1. Zara6502
      01.06.2024 23:17
      #26897231

      кстати слово "серка" по вашей метрике

      Word: серка, Metric 417199. Mean number of words: 120.

      с самым высоким рейтингом исходя из позиций букв в слове.

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

      с понижением рейтинга в 10 раз всплыло слово "кайло"

      Word: кайло, Metric 680355. Mean number of words: 196.

      Видимо я копаю не в ту сторону. Я просто пытаюсь нащупать границу между "найти загаданное слово" и "исключить ненужные слова и тогда останется только загаданное слово".


      1. apodavalov Автор
        01.06.2024 23:17
        #26898143

        Как я уже написал выше: рекомендую обратить внимание на статистику.

        • Слово "серка": 51 проблемное слово.

        • Слово "кроат": 49 проблемных слов (близко к лидеру!)

        • Слово "кайло": 36 проблемных слов (а вот и лидер, который обогнал "коран"!)