Алгоритм для выбора случайных букв для слова ищет игру, которая позволяет многим словам быть записанными
Я делаю подобную испугу словесную игру. Пользователю дают сетку букв как это:
O V Z W X
S T A C K
Y R F L Q
Пользователь выбирает слово с помощью любых смежных цепочек букв, как слово "СТЕК" через среднюю строку. Используемые буквы тогда заменяются машиной, например, (новые буквы в нижнем регистре):
O V Z W X
z e x o p
Y R F L Q
Заметьте, что можно теперь записать "ПЕРЕПОЛНЕНИЕ" при помощи новых букв. Моя проблема: Какой алгоритм я могу использовать для выбора новых букв, который максимизирует количество длинных слов по буквам, которые может произнести пользователь? Я хочу, чтобы игра была забавой и иногда включала написание, например, 6 слов буквы, но при выборе плохих букв игры вовлекают пользователя, просто произносящего 3 слова по буквам буквы и не получающего шанс найти большие слова.
Например:
Вы могли просто случайным образом выбрать новые буквы от алфавита. Это не работает хорошо.
Аналогично, я нашел выбор случайным образом, но использование частот буквы от скрэббла не работало хорошо. Это работает лучше в скрэббле, я думаю, поскольку Вы менее ограничиваетесь о порядке, в котором Вы используете буквы.
Я пытался иметь ряд списков, каждый представляющий одно из умирания от игры Испуга, и каждая буква будет выбрана от случайного, умирают сторона (я также задаюсь вопросом, могу ли я по закону использовать эти данные в продукте). Я не заметил эту работу хорошо. Я предполагаю, что стороны игры в кости Испуга были выбраны некоторым разумным способом, но я не могу найти, как это было сделано.
Некоторые идеи я рассмотрел:
Сделайте таблицу того, как часто пары буквы происходят вместе в словаре. Ради аргумента скажите, что E замечен рядом с 30% времени. При выборе новой буквы я случайным образом выбрал бы букву на основе частоты этой буквы, происходящей рядом со случайным образом выбранной смежной буквой на сетке. Например, если бы соседняя буква была E, то новая буква составила бы "A" 30% времени. Должен означает, что существует много достойных пар для использования рассеянный вокруг карты. Я мог, возможно, улучшить это путем создания таблиц вероятности буквы, происходящей между двумя другими буквами.
Так или иначе сделайте поиск, какие слова по буквам могут быть произнесены на текущей сетке, беря новые буквы, чтобы быть подстановочными знаками. Я тогда заменил бы подстановочные знаки буквами, которые позволили самым большим словам быть записанными. Я не уверен, как Вы сделали бы это эффективно как бы то ни было.
Любые другие идеи ценятся. Интересно, существует ли распространенный способ решить эту проблему и что используют другие словесные игры.
Править: Спасибо за большие ответы до сих пор! Я забыл упоминать, я действительно стремлюсь к низким требованиям памяти/CPU, если это возможно, я, вероятно, собираюсь использовать словарь SOWPODS (приблизительно 250 000) и моя сетка составят способный 6 x 6.
7 ответов
Вот простой метод:
Напишите быстрый решатель для игры, используя тот же список слов, который будет использовать игрок. Сгенерируйте, скажем, 100 различных возможных досок в случайном порядке (использование частот букв, вероятно, здесь хорошая идея, но не обязательно). Для каждой доски подсчитайте все слова, которые могут быть сгенерированы, и оцените доску на основе количества найденных слов или подсчета, взвешенного по длине слова (то есть общей сумме длин слов всех найденных слов). Затем просто выберите лучшую доску для подсчета очков из 100 возможных и отдайте ее игроку.
Кроме того, вместо того, чтобы всегда выбирать доску с наивысшими оценками (то есть самую простую доску), вы можете установить разные пороги очков, чтобы усложнить игру для экспертов.
Незначительный вариант подхода с парой букв: используйте частоту появления пар букв в длинных словах - скажем, 6 букв или более - поскольку это ваша цель. Вы также можете разработать взвешивание, включающее все соседние буквы, а не только случайную.
Эта игра со словами , которую я придумал некоторое время назад, ведет себя очень похоже на то, что вы описываете, использует английские таблицы частот для выбора букв, но сначала решает генерировать ли гласные или согласные, что позволяет мне обеспечить заданное количество гласных на доске. Кажется, это работает достаточно хорошо.
Вы можете посмотреть на эту реализацию Java алгоритма Jumble , чтобы найти наборы букв, которые переставляются в несколько словарные слова:
$ java -jar dist/jumble.jar | sort -nr | head 11 Orang Ronga angor argon goran grano groan nagor orang organ rogan 10 Elaps Lepas Pales lapse salep saple sepal slape spale speal 9 ester estre reest reset steer stere stree terse tsere 9 caret carte cater crate creat creta react recta trace 9 Easter Eastre asteer easter reseat saeter seater staree teaser 9 Canari Carian Crania acinar arnica canari carina crania narica 8 leapt palet patel pelta petal plate pleat tepal 8 laster lastre rastle relast resalt salter slater stelar 8 Trias arist astir sitar stair stria tarsi tisar 8 Trema armet mater metra ramet tamer terma trame ...
Я не знаю заранее подготовленного алгоритма для этого, но ...
В UNIX есть файл словаря, и я полагаю, что в нем что-то есть аналогичные доступны на других платформах (может быть, даже в библиотеках java? - погуглите). В любом случае используйте файлы, которые использует проверка орфографии.
После того, как они произнесут слово, и оно выпадет, у вас есть существующие буквы и пробелы.
1) От каждой существующей буквы идите вправо, влево, вверх, вниз (вам необходимо понимать рекурсивные алгоритмы). Пока строка, которую вы создали до сих пор, находится в начале слова или в обратном направлении от конца слова в файле словаря, продолжайте. Когда вы встретите пустое место, посчитайте, сколько букв вам нужно в следующий раз. Используйте самые частые буквы.
Это не гарантирует слово, поскольку вы не проверили соответствующее окончание или начало, но я думаю, что это было бы намного проще реализовать, чем исчерпывающий поиск, и получить довольно хорошие результаты.
Я думаю, это даст вам на шаг ближе к пункту назначения: http://en.wikipedia.org/wiki/Levenshtein_distance
Вам следует изучить n-граммирование и марковские модели.
Ваша первая идея очень слабо связана с марковскими алгоритмами. В принципе, если у вас есть большой корпус текстов, скажем, из 1000 слов. Вы можете проанализировать каждую букву и создать таблицу, чтобы узнать вероятность того, что определенная буква последует за текущей.
Например, я знаю, что буква Q из моих 1000 слов (всего 4000 букв) используется только 40 раз. Затем я вычисляю, какие вероятные буквы следуют за ней, используя мою хэш-таблицу Маркова.
Например, QU встречается 100% времени, поэтому я знаю, что если Q будет случайным образом выбрана вашим приложением, то мне нужно убедиться, что буква U также включена. Затем, буква "I" используется 50% времени, "A" - 25% времени и "O" - 25% времени.
На самом деле это очень сложно объяснить, и я уверен, что есть другие объяснения, которые намного лучше, чем это.
Но идея заключается в том, что при наличии достаточно большого корпуса текстов можно создать цепочку из X букв, которые, вероятно, соответствуют английскому языку и поэтому должны быть легкими для пользователей, чтобы составить из них слова. Вы можете ориентироваться на значение n-граммы, чем выше число, тем проще вы можете сделать свою игру. Например, при n-грамме, равной двум, вероятно, будет очень трудно создавать слова больше 6, но при n-грамме, равной 4, это будет очень легко.
Википедия объясняет это очень плохо, поэтому я бы не стал ей следовать.
Взгляните на этот генератор Маркова: