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

Я делаю boggle -пользовательскую игру. Пользователю предоставляется сетка таких букв:

O V Z W X
S T A C K
Y R F L Q

Пользователь выбирает слово, используя любые соседние цепочки букв, например, слово "STACK" по средней линии. Затем используемые буквы заменяются машиной, например. (новые буквы в нижнем регистре):

O V Z W X
z e x o p
Y R F L Q

Обратите внимание, что теперь вы можете писать "OVeRFLoW", используя новые буквы. Моя проблема: какой алгоритм я могу использовать для выбора новых букв, которые максимизируют количество длинных слов, которые может произнести пользователь? Я хочу, чтобы игра была забавной и включала правописание, например. 6 буквенных слов иногда, но если вы выбираете плохие буквы, игры включают в себя пользователя, просто написание 3 буквенных слов и не получение возможности найти более крупные слова.

Например:

  • Вы можете просто случайно выбрать новые буквы из алфавита. Это не работает.

  • Аналогично, я обнаружил, что сбор случайно, но использование частот букв от Scrabble не очень хорошо работает. Это лучше работает в Scrabble. Я думаю, поскольку вы менее ограничены в порядке, в котором вы используете буквы.

  • Я пробовал иметь набор списков, каждый из которых представлял один из штампов из игры Boggle, и каждая буква была выбрана со случайной стороны штампа (я также задаюсь вопросом, могу ли я законно использовать эти данные в продукте). Я не заметил, что это хорошо работает. Я полагаю, что стороны кости Боглега были выбраны каким-то разумным образом, но я не могу найти, как это было сделано.

Некоторые идеи, которые я рассмотрел:

  • Сделайте таблицу того, как часто пары букв встречаются вместе в словаре. Ради аргумента, скажем, Е видно около 30% времени. Когда вы выбираете новое письмо, я произвольно выбираю письмо, основанное на частоте этого письма, которое происходит рядом со случайно выбранным смежным письмом на сетке. Например, если соседняя буква E, новая буква будет "A" 30% времени. Это должно означать, что есть много приличных пар для использования, разбросанных по карте. Возможно, я мог бы улучшить это, создав таблицы вероятностей буквы между двумя другими буквами.

  • Как бы то ни было, поиск слов, которые могут быть записаны в текущей сетке, при этом новые буквы будут подстановочными знаками. Затем я заменил подстановочные знаки письмами, которые позволяли писать самые большие слова. Я не уверен, как вы это сделаете эффективно.

Любые другие идеи приветствуются. Интересно, есть ли общий способ решить эту проблему и какие другие игры используют слова.

Редактировать: Спасибо за отличные ответы! Я забыл упомянуть, что я действительно стремлюсь к низким требованиям к памяти/процессору, если это возможно, я, вероятно, буду использовать словарь SOWPODS (около 250 000), и моя сетка сможет 6 x 6.

Ответы

Ответ 1

Вот простой способ:

Напишите быстрый решатель для игры, используя тот же список слов, который будет использоваться игроком. Сгенерируйте, скажем, 100 различных возможных досок в случайном порядке (с использованием частотных частот, вероятно, хорошая идея здесь, но не существенная). Для каждой платы вычисляйте все слова, которые могут быть сгенерированы, и оценивайте доску на основе количества найденных слов или подсчета, взвешенного по длине слова (т.е. Общая сумма слов длины всех найденных слов). Затем просто выберите лучшую гонку за 100 возможностей и передайте ее игроку.

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

Ответ 2

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

Ответ 3

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

Ответ 4

Вы должны искать n-граммовые и марковские модели.

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

Например, я знаю, что буква Q из моих 1000 слов (всего 4000 букв) используется всего 40 раз. Затем я вычисляю, какие вероятные буквы следуют с помощью моей таблицы хэшей марков.

Например, QU происходит в 100% случаев, поэтому я знаю, что если Q будет произвольно выбран вашим приложением, мне нужно убедиться, что буква U также включена. Затем буква "I" используется в 50% случаев, а "А" - 25% времени и "O" - 25% времени.

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

Но идея состоит в том, что с учетом законно большого текстового корпуса вы можете создать цепочку букв X, которые, вероятно, согласуются с английским языком, и поэтому пользователям должно быть легко сделать слова. Вы можете рассчитывать на значение n-грамма, наивысшее число, которое легче сделать вашей игрой. Например, n-грамм из двух, вероятно, затруднит создание слов более 6, но n-грамм из 4 будет очень простым.

Википедия объясняет это очень плохо, поэтому я не буду следовать этому.

Взгляните на этот марковский генератор:

http://www.haykranen.nl/projects/markov/demo/

Ответ 5

Я не знаю о предварительном алгоритме для этого, но...

В UNIX есть файл словаря, и я полагаю, что есть что-то подобное на других платформах (возможно, даже в java-библиотеках? - google it). В любом случае, используйте файлы, которые использует проверка орфографии.

После того, как они произнесут слово, и оно выпадет, у вас есть буквы и пробелы.

1) Из каждой существующей буквы перейдите вправо, влево, вверх, вниз (вам нужно понять рекурсивные алгоритмы). Пока строка, которую вы создали до сих пор, находится в начале слов или назад от конца слов в файле словаря, продолжайте. Когда вы столкнетесь с пробелом, подсчитайте частоту букв, которые вам нужны. Используйте наиболее часто используемые буквы.

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

Ответ 7

Вы можете посмотреть эту реализацию 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 
...