Проблема порочного палача

Question

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

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

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

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

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

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

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

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

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

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

Словарь:

mar 
bar 
car 
fir 
wit 

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

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