Используйте Google BigQuery, чтобы найти три слова, которые позволят вам доминировать в Wordle.
Wordle — это удивительно захватывающая словесная игра от Josh Wardle, которая покорила Интернет. Это вызвало множество подражателей, несколько подделок, и игра на других языках определенно возможна: испанский, немецкий, португальский, валлийский… Клингонский кто-нибудь?
Забавный факт: аббревиатура названия этой статьи — красивое слово: ПОТОКИ. Жаль, что нельзя решить игру. Продолжайте читать, чтобы узнать, почему.
Поиграв в нее некоторое время (читай: пристрастившись) и изучив множество статей о том, какая стратегия игры лучше всего или какое слово лучше всего использовать в качестве первого хода, я решил выяснить, смогу ли я придумать с чем-то своим.
Я видел, как люди используют общие языки программирования (JavaScript, Python, C++…) или электронные таблицы (Google Таблицы, Excel…) для разработки Wordle, поэтому я решил попробовать что-то другое: я собираюсь использовать базу данных. Я перейду в полностью бессерверный режим и буду использовать Google BigQuery для выполнения тяжелой работы, Google Cloud Shell для выполнения всех операций командной строки и Google Data Studio для визуализаций.
Отказ от ответственности: эта стратегия может испортить ваш опыт работы с Wordle. Пожалуйста, будьте осторожны.
Как правило, как только появляется 🟨 или 🟩, рекомендуется не повторять эту букву, а вместо этого попробовать новые буквы, чтобы изучить как можно больше. Особенно это касается 🟩. Повторное использование результатов 🟩, как и ожидалось, в тех же 🟩 в тех же позициях: ничего нового не узнал.
Количество новой информации (называемой энтропией в теории информации) максимизируется с использованием разных букв на каждом ходу.
Два игрока решают одно и то же Wordle:
Поэтому лучше использовать слова с как можно большим количеством разных букв, в идеале со всеми 5, чтобы максимально увеличить количество новой информации, получаемой за ход.
Следуя этой идее, 4 слова ранжируются от «лучшего» (больше энтропии) до «худшего» (наименьшей энтропии):
- GROUP тестирует 5 разных букв: G, R, O, U и P.
- LIMIT проверяет 4 разные буквы: L, I, M и T.
- ARRAY проверяет 3 разные буквы: A, R и Y.
Но есть несколько слов из 5 букв с уникальными буквами: BEGIN, BREAK, FALSE, FETCH, OUTER, RAISE, RANGE, RIGHT, TABLE, UNTIL, USING, WHILE…
Можно ли узнать, является ли одно слово «лучше» другого? Давай выясним!
Wordle использует две разные группы слов:
- Решения:слова, которые нужно угадать, в основном повседневные слова.
- Догадки: слова, которые вы можете использовать, чтобы угадать слово, но они никогда не являются решением, некоторые из них неясны.
Чтобы найти решение и угадать слова, я обратился к исходникам TypeScript игры в GitHub:
wordlist.ts ['cigar','rebut','sissy', … ,'artsy','rural','shave'] validGuesses.ts ['aahed','aalii','aargh, … ,'zygon','zymes','zymic']
Извлечь и сохранить их в файл CSV очень просто:
Результат:
First three solution words: "cigar","solution" "rebut","solution" "sissy","solution" Last three guess words: "zygon","guess" "zymes","guess" "zymic","guess" Number of words per type: 2315 "solution" 10657 "guess" 12972 wordle.csv
Лексикон Wordle включает 12 972 слова, которые вы можете использовать в игре: 2 315 решений и 10 657 догадок.
Я создам новый набор данных Google BigQuery под названием wordle, чтобы все было аккуратно. Затем я загружу эти слова в таблицу (raw_words), чтобы начать исследование.
Позвольте мне быстро проверить, что все данные были правильно загружены в Google BigQuery:
Поскольку Wordle использует все заглавные буквы, а извлеченные слова — строчные, я быстро создам новую таблицу (normalized_words) со всеми словами в верхнем регистре, чтобы все выглядело красиво. Я сохраню исходное слово, потому что хранилище в Google BigQuery дешевое:
Следующим шагом является создание таблицы поиска (letters) со всеми различными буквами, присутствующими во всех словах (как решение, так и предположение).
Я предварительно вычислю число (letter_bitmask) для каждой буквы. Это облегчит мне жизнь в будущем.
Эта таблица будет выглядеть примерно так:
Как вы можете видеть на изображении выше, исходный Wordle использует 26 букв, так что думайте о битовой маске букв как о последовательности из 25 0 и ровно одной 1, которая перемещается.
Если я рассматриваю эти 0 и 1 как двоичное число и преобразовываю их в десятичные числа, я получаю битовую маску буквы:
A = 0000000000000000000000000000001 = 1 B = 0000000000000000000000000000010 = 2 C = 0000000000000000000000000000100 = 4 D = 0000000000000000000000000001000 = 8 E = 0000000000000000000000000010000 = 16 F = 0000000000000000000000000100000 = 32 ................................................ X = 0010000000000000000000000000000 = 8,388,608 Y = 0100000000000000000000000000000 = 16,777,216 Z = 1000000000000000000000000000000 = 33,554,432
Теперь я могу приступить к анализу лексики Wordle. Сначала я посчитаю несколько вещей:
- Длина: в оригинальном Wordle это всегда будет 5. Здесь нет ничего удивительного.
- Битовая маска слова: это число, которое кодирует, какие уникальные буквы используются в слове.
- Уникальные буквы: сколько разных букв использует слово.
Позвольте мне кратко объяснить, как вычисляется битовая маска слова.
Я начинаю разделять 5 букв, составляющих слово, затем удаляю все дубликаты (за меня это делает GROUP BY letter) и, наконец, добавляю индивидуальные маски оставшихся букв. Некоторые примеры:
BITMASK(ADDED) → {A,D,D,E,D} → {A,D,E} → {1,8,16} → 25
BITMASK(FADED) → {F,A,D,E,D} → {A,D,E,F} → {1,8,16,32} → 57
BITMASK(FACED) → {F,A,C,E,D} → {A,C,D,E,F} → {1,4,8,16,32} → 61
BITMASK(DECAF) → {D,E,C,A,F} → {A,C,D,E,F} → {1,4,8,16,32} → 61
Обратите внимание, что FACED и DECAF имеют одинаковую битовую маску слова, потому что они оба используют одни и те же буквы, хотя и в разном порядке. Это единственные два слова с A, C, D, E и F в лексиконе Wordle:
Забавный факт: Wordle позволяет вам играть с 14 словами, которые можно составить, комбинируя и повторяя буквы A, D, E и R. Сколько вы знаете? (полный список в конце)
Подсчитать, сколько уникальных букв использует слово, очень просто: мне просто нужно посчитать, сколько единиц содержится в битовой маске слова.
В Google BigQuery есть функция BIT_COUNT(expression), которая делает именно то, о чем говорит ее название: подсчитывает, сколько единиц присутствует в expresion .
Давайте возьмем несколько битовых масок слов, их двоичные эквиваленты и посчитаем единицы:
BIT_COUNT(BITMASK(ADDED) = BIT_COUNT(25) = BIT_COUNT(0b011001) = 3 BIT_COUNT(BITMASK(FADED) = BIT_COUNT(57) = BIT_COUNT(0b111001) = 4 BIT_COUNT(BITMASK(FACED) = BIT_COUNT(61) = BIT_COUNT(0b111101) = 5 BIT_COUNT(BITMASK(DECAF) = BIT_COUNT(61) = BIT_COUNT(0b111101) = 5
Посмотрим, сколько слов-решений с учетом количества уникальных букв:
Эта информация может быть полезна, когда у вас остался только один ход, и вы не можете решить, будете ли вы ДЕЛАТЬ или ИДИТЕ в качестве своего последнего слова.
Для каждых 3 слов вероятность того, что 2 будут иметь 5 уникальных букв, а 1 — 4. Следовательно, наиболее вероятным ответом будет ДЕЛАТЬ: слово с 5 уникальными буквами.
Может быть, это только я, но чем меньше уникальных букв в слове, тем сложнее мне его разгадать.
Забавный факт: существует только одно решение, в котором используются две разные буквы. Не волнуйся, я не испорчу сюрприз.
Теперь я позаимствую прием из криптоанализа и проведу быстрый частотный анализ букв, чтобы определить, как буквы используются в лексиконе Wordle, но только в словах-решениях:
Чаще всего в решениях Wordle используются буквы E, A, R, O и T, поэтому хорошее начальное слово должно состоять из всех этих букв.
Реже всего встречаются буквы Z, X, Q и J. Скорее всего, вы не встретите слов, в которых они используются.
Забавный факт: из 2315 решений только в 27 словах используется буква J (наименее используемая), то есть на 2 порядка меньше. Так что да, довольно редко.
Найти все слова, в которых 5 верхних букв есть только один раз, очень просто, используя битовую маску слова:
BITMASK(EAROT) → {E,A,R,O,T} → {A,E,O,R,T} → 671761
К сожалению, ни одно из этих слов не является решением, поэтому, даже если они являются оптимизированными догадками, решить Wordle с первого хода не получится. ☝
Это хорошие стартовые слова, и все три имеют одинаковую вероятность раскрыть 🟨 при первом ходе.
Но… можем ли мы сделать лучше? 🤔
Определенно!
Получить 🟨 это очень хорошо, но получить 🟩 еще лучше! У какого-либо из этих слов больше шансов раскрыть 🟩?
Чтобы ответить на этот вопрос, мне нужно распространить частотный анализ букв на положение каждой буквы в словах-решениях:
Возвращаясь к ORATE, OATER и ROATE, давайте узнаем частоту каждой буквы в каждой позиции:
O не очень популярна в качестве первой буквы, поэтому кажется, что ORATE не лучший выбор. Тем не менее, A является наиболее эффективной третьей буквой, а E как пятая буква в два раза эффективнее, чем R в этой позиции.
Чтобы понять, насколько «хорошо» слово раскрывается 🟩, мне нужно придумать некоторую формулу, которая учитывает все эти частоты и выводит число, которое я могу использовать для простого сравнения эффективности двух слов.
Позвольте мне определить некоторые вещи.
Во-первых, Позиционный вес буквы (сокращенно PLW) — это количество раз, которое буква присутствует в определенной позиции. Я обозначу это как:
PLW(letter, position_in_word)
Итак, PLW(O, 1) = 41, потому что O встречается 41 раз в качестве первой буквы. Точно так же PLW(E, 5) = 424, потому что E встречается 424 раза в качестве пятой буквы.
Далее я собираюсь определить вес слова (сокращенно WW) как сумму весов каждой позиционной буквы. WW может быть легко определено с точки зрения PLW как:
WW(word) = PLW(1st_letter, 1) + PLW(2nd_letter, 2) + PLW(3rd_letter, 3) + PLW(4th_letter, 4) + PLW(5th_letter, 5)
Теоретически, чем выше значение WW, тем более вероятно, что слово раскроет один или несколько 🟩. Возвращаясь к словам-кандидатам:
WW(ROATE) = PLW(R,1) + PLW(O,2) + PLW(A,3) + PLW(T,4) + PLW(E,5) WW(ROATE) = 105 + 279 + 307 + 139 + 424 = 1,254 WW(ORATE) = 41 + 267 + 307 + 139 + 424 = 1,178 WW(OATER) = 41 + 304 + 111 + 318 + 212 = 986
Похоже, ROATE — самое «тяжелое» слово, и поэтому у него больше шансов раскрыть 🟩’s.
Но… можем ли мы сделать лучше? 🤔
Я так думаю!
ROATE был выбран исключительно на основании того факта, что эти буквы чаще всего использовались в словах-решениях в любой позиции.
Теперь, когда у меня есть частота позиционных букв для всех букв, позвольте мне вычислить вес для всех 12 972 слов и проверить, действительно ли ROATE является лучшим начальным словом:
- Самое тяжелое слово в целом - САРИ (1575) и состоит из 4 уникальных букв.
- Самое сложное угадываемое слово с 5 уникальными буквами — SAINE (1542).
- Самое тяжелое слово-решение — SLATE (1437).
Я бы отказался от SAREE, потому что в нем всего 4 уникальных буквы (помните, я хочу максимизировать энтропию, используя 5 разных букв), и я бы предпочел SLATE, а не SAINE, просто потому, что их вес очень похож, и SLATE может дать мне удовлетворительную мгновенную победу! 🎯
Если вам интересно, ROATE занимает 160 место 🤦🏻♂ в списке взвешенных слов с 5 уникальными буквами. Это выглядит не так хорошо, если мы забудем об общей частоте букв и вместо этого будем учитывать позиционную частоту букв и вес слова.
Забавный факт: "худшее" начальное слово, которое вы можете использовать, – это "ИМШИ" (австралийский военный сленг: уходи, уходи). Мало того, что оно имеет наименьший вес (191), это слово-угадка, поэтому оно никогда не станет решением ежедневной головоломки. Это похоже на игру 2–7 разной масти в техасском холдеме… вам действительно нужно быть Дойлом Брансоном из Wordle, чтобы справиться с этим. ♥♠♦♣
Большой! У нас есть оптимизированное первое предположение: SLATE. Надеюсь, Wordle покажет некоторые 🟨 и 🟩.
Но… можем ли мы сделать лучше? 🤔
Полностью!
С первым поворотом уже определились. Wordle представил некоторые ⬛, 🟨 и 🟩. Что теперь?
Оптимизация первого слова — это здорово. Но вряд ли (1 из 2370) я решу Wordle за 1 ход. Мне нужна стратегия. И чем проще, тем лучше: я не хочу запоминать сложные деревья решений, таблицы, проценты или бесконечный список слов.
Использование первого хода для проверки букв (S, L, A, T и E) позволило мне покрыть 37,40%. Это немного меньше, чем 39,69%, которые занимают верхние 5 букв (см. прямоугольник ① на изображении ниже).
Что, если я использую два движения, чтобы проверить 10 верхних букв (E, A, R, O, T, L, I, S, N и C)? Я бы покрыл 66,57% (прямоугольник ② на изображении ниже), и у меня осталось бы еще 4 витка. Аккуратный.
Следуя этой логике, использование трех ходов для проверки первых 15 букв (E, A, R, O, T, L, I, S, N, C, U, Y, D, H и P) увеличивает покрытие до 84,20. % (прямоугольник ③ на изображении ниже), и у меня останется 3 хода, чтобы завершить игру. Мне нравятся эти шансы. 🎲
Расширение этой логики для проверки первых 20 букв (E, A, R, O, T, L, I, S, N, C, U, Y, D, H, P, M, B, G, F и K). ) не очень интересно, так как при вложении дополнительного хода отдача уменьшается: покрытие подскакивает только до 95,84% (прямоугольник ④ на изображении ниже), но мне осталось всего 2 хода, чтобы завершить игру. Чрезвычайно рискованно.
Соглашусь на 3 оборота. Это означает, что я буду тестировать первые 15 букв. Давайте узнаем, сколько слов с 5 уникальными буквами содержат эти 15 лучших букв. Еще раз, используя BIT_COUNT() с пользой:
Google BigQuery легко обрабатывает данные и показывает, что из 12 972 слов 2760 содержат 5 уникальных букв из первых 15 букв: 527 решений и 2233 предположения. Хороший.
Следующим шагом будет проверка всех перестановок 3 слов (троек), в которых верхние 15 букв используются ровно один раз. Например: (ВЗРОСЛЫЙ, ГИПЕР, ЗВУКОВОЙ). Вычисление и проверка всех перестановок может быть сложной задачей, поскольку потенциально Google BigQuery должен исследовать:
2,760 X 2,759 X 2,758 = 21,001,728,720 triplets
Это «большое» число, но определенно ничего такого, с чем Google BigQuery не справится.
Снова воспользовавшись функцией BIT_COUNT(), выполнив некоторые побитовые операции и применив некоторую творческую обрезку, мы получим ответ менее чем за 4 секунды: 299 544 триплета.
Любая из этих троек является хорошим выбором для первых трех попыток:
Но… можем ли мы сделать лучше? 🤔
Конечно!
Есть некоторые вещи, которые все еще можно сделать для дальнейшей оптимизации.
Во-первых, я могу отбросить все триплеты, в которых есть слова-угадывания, и оставить только те, в которых есть 3 слова-решения. Это сужает число троек с 299 544 до 2 730.
Во-вторых, я могу выбрать тройки с наибольшим общим весом, так как это даст мне больше шансов выявить 🟩 как можно раньше. Оказывается, есть только 6 троек с общим весом 3505, образованных перестановкой этих 3 слов: CURLY, POINT и SHADE.
Лучшая тройка в целом (COUDE, PRINT, SHALY) имеет общий вес 3588, а лучшая тройка, образованная только словами-решениями (CURLY, POINT, SHADE), равна 3505. Их веса настолько похожи, что стоит отбросить тройки с угадывающими словами и пойти на дырку в одной! ⛳
В-третьих, чтобы как можно быстрее раскрыть как можно больше информации, эти слова можно воспроизвести в порядке убывания веса:
Вот оно!
Играйте ТЕНЬ в качестве первого хода.
Скорее всего, вам понадобится больше информации: сыграйте POINT на втором ходу.
Скорее всего, вам все еще нужно больше 🟨 и 🟩. Используйте CURLY на третьем ходу.
После первых 3 ходов нужно просто использовать 🟩 и переставлять 🟨, чтобы решить слово в четвертом ходу.
Если у меня недостаточно информации для решения на четвертом ходу, мне нужно будет изучить больше букв. У меня есть 3 конкретных слова, которые я люблю использовать в 4-м повороте, включая буквы G, M и B (следующие 3 самые популярные буквы) и любые 🟨 гласные из первых 3 ходов, чтобы попытаться превратить их в 🟩. Любое из этих слов увеличивает охват до 92,04%.
Точно так же есть 5 слов для пятого хода, включающих два из F, K, W, V и любые 🟨 гласные из прошлых ходов, чтобы покрыть до 95,84%.
Я не буду вдаваться в подробности, потому что уверен, что уже слишком испортил вам игру… 🤦🏻♂
Но… можем ли мы сделать лучше? 🤔
Я точно уверен!
Я не думаю, что эта стратегия оптимальна, так как она, скорее всего, не решается за наименьшее количество ходов. Наоборот, его легко запомнить, и в большинстве случаев он решает игру🤞.
Думайте об этом как о чем-то похожем на метод для начинающих (например, слой за слоем) для сборки кубика Рубика: очень мало коротких алгоритмов для запоминания, но очень медленный по сравнению с методом Фридриха, используемым в спидкубинге.
Конечно, эта стратегия является обычной для первых 3 ходов, но превращает Wordle в логическую головоломку на 6-м ходу, а не в удачу все время.
Счастливый словесник!
Стратегия в движении:
Забавный факт разгадан: 14 слов, в которых используются A, D, E и R:
