Wordle

[rockclimber]

wrest в сообщении #1547272 писал(а):

rockclimber в сообщении #1547271 писал(а):

Если хочется быстро играть, выключив мозг, то SLATE + FOUND + BIRCH + VAMPY покрывают 19 из 26 букв, с 4 - 5 попытки практически любое слово угадывается. Частенько - с третьей. Я даже в словарь почти не заглядываю.

Так и прогоните по всем 2315 если уже программа есть.

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

mihaild в сообщении #1547275 писал(а):

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

Спорить с этим утверждением сложно. Но с другой стороны, нужно взять каждое из 16000 слов, и для каждого из 2315 слов проверить, какие слова останутся. Довольно затратный алгоритм получается, имхо. Насколько сильно ухудшится результат, если начинать со slate?

mihaild в сообщении #1547275 писал(а):

Если выбирать слово, для которого максимальный размер множества минимален - то получается $3.805$ попыток в среднем, $5$ в худшем случае, первое слово aesir.

Тут я не успеваю следить за вашей мыслью. Что значит "слово, для которого максимальный размер множества минимален"? Мы берем тестовое слово, пробуем, получаем ответ (какие буквы серые, какие желтые, и какие - зеленые), потом делим исходное множество на два (слова, которые подходят, и слова, которые не подходят), и, вроде бы мне тут кажется очевидным, что лучшее слово - это то, у которого будет самый короткий список "подходящих" слов. Или я не прав?

mihaild в сообщении #1547275 писал(а):

Если вместо этого максимизировать энтропию разбиения очередного слова

А что это такое? И кстати, как вы ваши оценки получали? Я так понял, у вас нет полного решения...

zykov в сообщении #1547279 писал(а):

Тогда и свою программу писать не надо.

Именно! Я еще на прошлой странице дал ссылку. Надо только кликнуть на нее, и всё. Не надо ничего никуда сохранять, редактировать, и т. д.

kotenok gav в сообщении #1547280 писал(а):

По-английски, конечно, тяжелее...

А мне почему-то по-английски проще Но я до этого неделю или больше залипал в hellowordl, и даже программировать пытался. С русской версией такого не было. Каждый раз отгадываю с невероятными мучениями.

ozheredov в сообщении #1547505 писал(а):

Тогда зачем по-вашему слово одно на всех и довольно долго ждать следующего? Дефицит слов?

Я не имею ни малейшего понятия, зачем так сделано. Как по мне, так это тупо и неинтересно. Вот вышеупомянутый hellowordl - это "головоломка здорового человека". Дурацких ограничений нет, можно угадывать слова длиной от 4 до 30 букв. Но если б я каждую непонятную лично мне вещь в мире объяснял бы каким-нибудь заговором, я бы давно свихнулся. А я и без этого-то едва держусь.

[mihaild]

rockclimber в сообщении #1547924 писал(а):

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

32 миллиона пар, говорить не о чем.

rockclimber в сообщении #1547924 писал(а):

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

Мы же не знаем, какое слово отгадываем, так что не знаем заранее, какого размера множество получится для нашего слова.
Модель простая: у нас есть текущий список возможных слов. Любое слово задает разбиение этого списка на множества, соответствующие разным реакциям на это слово (одно множество - если все буквы серые, второе - если третья желтая, четвертая зеленая, и т.д., потенциально $3^5$ множеств, реально естественно далеко не все варианты реализуются).
Пусть $W$ - некоторое множество слов. Обозначим за $f_i(x, W)$ множество слов из $W$, дающих $i$-ю реакцию на слово $x$, а $t(W)$ - минимальное число шагов, за которое можно угадать слово, если мы знаем, что оно принадлежит $W$ (и больше ничего не знаем). Тогда очевидно $t(W) = \min_x \max_i t(f_i(x, W)) + 1$ (ну и для среднего числа попыток аналогичная рекуррента).
Но естественно мы честно посчитать $t$ для всех подмножеств не можем, поэтому заменим в правой части его на $t'$ - что-то предположительно примерно монотонное по $t$. Алгоритм, соответственно, "зная текущее множество возможных слов $W$, спросить слово $\argmin_x \max_i t'(f_i(x, W))$" - и если $t'$ считается легко, то мы для наших размеров задачи можем точно найти необходимое число шагов.

rockclimber в сообщении #1547924 писал(а):

А что это такое?

По сути - энтропия случайной величины "какие цвета мы получим". Считается как сумма размеров множеств из разбиения умноженных на логарифмы их размеров, деленных на $|W|$.

rockclimber в сообщении #1547924 писал(а):

И кстати, как вы ваши оценки получали?

Лобовой эмуляцией https://gist.github.com/0e7760f8be2ef7f ... f96a200117

[zykov]

rockclimber в сообщении #1547924 писал(а):

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

Это конечно важный фактор, но думаю, тут ещё есть пространство для улучшения.
У него в программе из 2315 слов например есть 7 таких:

Цитата:

shake
shame
shade
share
shape
shale
shave

Допустим, загадано было одно из этих 7, и допустим вам повезло первой попыткой протестировать другое слово из этих 7.
Сразу получили 4 зелёных буквы, только буква номер 4 неизвестна. Если будете перебирать оставшиеся 6 слов по одному, то есть риск (1 из 6), что не угадаете за 6 попыток.
С другой стороны можно протестировать слово, которое точно не подходит, но которое даст информацию по более чем одной букве из списка "kmdrplv" (например "milky").

Так что наверно лучше максимизировать какое-то "количество информации" полученное от теста нового слова. Тут ещё надо формализовать это "количество информации".

[eugensk]

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

[zykov]

eugensk
Да, в большинстве случаев так работает.
Но можно наткнуться на паталогический случай, как эти 7 слов. Тогда лучше поменять тактику.
(Так, вообще речь шла не про решение человеком, а про оптимальное решение машиной - совсем другое дело.)

[eugensk]

zykov
Да, головоломка иногда может не сойтись, как пасьянс. Т.е. можно загадывать желания :)

[wrest]

О существовании сегодняшнего слова даже не знал... На последние два хода остался перебор из двух вариантов **12* и **21* ну угадал на предпоследнем 5-м ходе, если б не угадал то на последнем бы точно.
Как-то "не заводит" игра, слишком простой кажется даже в английском варианте.

[gris]

wrest, я вчера как раз пошутил насчёт вчерашнего общего слова SHARD в своей вчерашней теме . А мне игра, вернее, её реализация, понравилась при некоторых ограничениях: не использовать ранее использованные слова разве что в качестве финального слова, не готовиться, не крякать для безудержной игры. Если бы были разные слова каждый день, то можно было бы числить печеньки. Надоела бы. Раз в день занятная и немного полезная процедура типа чистки зубов или подобного.

[eugensk]

гугл предложил статью
https://aperiodical.com/2022/02/a-mathe ... to-wordle/

[zykov]

eugensk в сообщении #1548049 писал(а):

гугл предложил статью https://aperiodical.com/2022/02/a-mathe ... to-wordle/

Смешно:

Цитата:

VOZHD (a supreme leader in Russia)

(Оффтоп)

https://youtu.be/WjK5rovb3JQ?t=3150

[rockclimber]

mihaild в сообщении #1547927 писал(а):

rockclimber в сообщении #1547924 писал(а):

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

32 миллиона пар, говорить не о чем.

Я имел в виду, что если буквы считать, то это будет $O(n)$, а если как у вас - то $O(n^2)$.

mihaild в сообщении #1547927 писал(а):

rockclimber в сообщении #1547924 писал(а):

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

Мы же не знаем, какое слово отгадываем, так что не знаем заранее, какого размера множество получится для нашего слова.

Да, этот момент я не додумал, но вообще я думал примерно в таком направлении: для каждого тестового слова (из полного набора в 16К слов) берем каждое из набора для загадывания (2315 слов), и считаем, сколько слов отсеется для этой комбинации (загаданное + тестовое). Потом для каждого тестового слова суммируем его результаты. Хотя, кажется, это будет сильно более ресурсоемкий алгоритм...

zykov в сообщении #1547938 писал(а):

rockclimber в сообщении #1547924 писал(а):

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

Это конечно важный фактор, но думаю, тут ещё есть пространство для улучшения.
У него в программе из 2315 слов например есть 7 таких:

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

eugensk в сообщении #1548049 писал(а):

гугл предложил статью
https://aperiodical.com/2022/02/a-mathe ... to-wordle/

Хороший тамада и конкурсы интересные: Nerdle

[mihaild]

rockclimber в сообщении #1548190 писал(а):

Я имел в виду, что если буквы считать, то это будет $O(n)$, а если как у вас - то $O(n^2)$.

Да, но при таких размерах входа это неважно.

rockclimber в сообщении #1548190 писал(а):

Потом для каждого тестового слова суммируем его результаты

Если я правильно понял ваше описание, то я ровно так и делал: для каждого тестовго слова проверял, на какие множества оно разбивает загадываемые (где слова попадают в одно множество если на них для данного тестового слова одинаковые ответы).

[zykov]

rockclimber в сообщении #1548190 писал(а):

не читаете, что я пишу. Потому что я еще на первой странице приводил похожий пример, да еще и с картинкой.

Это не важно.
Я вообще не про это.

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

Так и тут. Можно конечно сделать один ход и применить эвристику. Но возможно это будет не лучший ход с точки зрения следющей попытки. Можно было бы оптимизировать первый ход с учётом результата следующего хода. Но почему только два? По-хорошему - нужно тогда уж до конца последовательность попыток оптимизировать. Что конечно вычислительно проблемно.

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

[miser]

Русская игра Wordle от 14, Февраль, 2022, ответ.

(Оффтоп)

https://ibb.co/kg1dSDq

[miser]

Today I was incredibly lucky to guess the English word on just the second try.

(Оффтоп)

https://ibb.co/F6L3LbS

(Оффтоп)