Извращенная проблема палача

Question

Perverse Hangman - игра, похожая на обычного Hangman, с одним важным отличием: выигрышное слово определяется домом в зависимости от того, какие буквы были угаданы.

Например, скажем, у вас есть доска _ A I L и 12 оставшихся догадок. Поскольку есть 13 различных слов, оканчивающихся на AIL (залог, провал, град, тюрьма, кейл, почта, гвоздь, ведро, рельс, парус, хвост, склеп, вопль), дом гарантированно выиграет, потому что независимо от того, какие 12 букв вы угадаете , дом будет утверждать, что выбранное слово было тем, о котором вы не догадывались. Однако, если доска была _ I L M , вы загнали дом в угол, так как FILM - единственное слово, оканчивающееся на ILM.

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

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

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

В качестве примера игрушки рассмотрим словарь:

bat
bar
car

Если вам разрешено 3 неправильных предположения, игрок выигрывает со следующим деревом:

Guess B
NO -> Guess C, Guess A, Guess R, WIN
YES-> Guess T
      NO -> Guess A, Guess R, WIN
      YES-> Guess A, WIN

Answer 1

Это почти идентично "как мне найти нечетную монету при повторном взвешивании?" проблема. Основная идея заключается в том, что вы пытаетесь максимизировать объем информации, которую вы получаете от своих предположений.

Жадный алгоритм построения дерева решений выглядит следующим образом: - для каждого предположения выберите предположение, для которого ответ «истинный», а ответ «ложный» максимально приближен к 50-50, поскольку теоретически эта информация дает наибольшую информацию.

Пусть N - размер набора, A - размер алфавита, а L - количество букв в слове.

Итак, все ваши слова в комплекте. Для каждой позиции буквы и для каждой буквы в вашем алфавите подсчитайте, сколько слов имеют эту букву в этой позиции (это можно оптимизировать с помощью дополнительной хэш-таблицы). Выберите количество, которое ближе всего по размеру к половине набора. Это O (L * A).

Разделите набор на две части, взяв подмножество, в котором эта буква находится в этой позиции, и сделайте так, чтобы две ветви перешли к дереву. Повторите для каждого подмножества, пока у вас не будет всего дерева. В худшем случае это потребует O (N) шагов, но если у вас есть хороший словарь, это приведет к O (logN) шагам.

Answer 2

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

Таким образом, со словарем, который вы дали, он сначала угадал бы a правильно. Тогда он будет угадывать r, также правильно, затем b (неверно), затем c.

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

Словарь:

mar
bar
car
fir
wit

В этом случае он сначала неправильно угадывает r и остается только с остроумием. Если бы wit были заменены в словаре на sir, то было бы правильно угадать r, затем a, что исключило бы больший набор, затем w или f наугад неправильно, а затем другой для последнее слово только с 1 неправильным предположением.

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