algorithm - muse - Algoritmo para clasificar las palabras para los niveles de dificultad del ahorcado como "Fácil", "Medio" o "Difícil"

algorithms book

Question

¿Qué es un buen algoritmo para determinar la "dificultad" de una palabra para un juego del ahorcado, de modo que el juego pueda seleccionar palabras para que coincidan con un nivel de dificultad específico?

La dificultad parece estar relacionada con el número de conjeturas requeridas, la frecuencia relativa del uso de letras (por ejemplo, palabras con muchas letras poco comunes puede ser más difícil de adivinar) y, potencialmente, la longitud de la palabra.

También hay algunos factores subjetivos que (intentar) compensar, como la probabilidad de que una palabra esté en el vocabulario del jugador, y se pueden reconocer, lo que permite pasar de una estrategia de adivinación basada solo en frecuencias de letras a adivinar según la lista de palabras coincidentes conocidas.

Mi intento por ahora está debajo en ruby. ¿Alguna sugerencia sobre cómo mejorar la categorización?

def classify_word(w)
  n = w.chars.to_a.uniq.length # Num. unique chars in w
  if n < 5 and w.length > 4
    return WordDifficulty::Easy
  end
  if n > w.length / 2
    return WordDifficulty::Hard
  else
    return WordDifficulty::Medium
  end
end

Estoy escribiendo un juego del ahorcado que me gustaría que jueguen mis hijos; Soy demasiado mayor para intentar "tareas", que puede ser la razón por la cual la pregunta es recibir tantos votos a la baja ... Las palabras se extraen aleatoriamente de las bases de datos de palabras grandes, que incluyen muchas palabras oscuras y están siendo filtradas por el nivel de dificultad determinado por la palabra.

Answer 1

1. Introducción

Aquí hay una manera de abordar este problema de forma sistemática: si tiene un algoritmo que desempeña bien al ahorcado, puede tomar la dificultad de cada palabra para que sea el número de conjeturas erróneas que su programa tomaría si adivinara esa palabra.

2. Aparte de la estrategia del verdugo

Hay una idea que está implícita en algunas otras respuestas y comentarios, que la estrategia óptima para el solucionador sería basar sus decisiones en la frecuencia de las letras en inglés, o en la frecuencia de las palabras en algún corpus. Esta es una idea seductora, pero no es del todo correcta. El solucionador funciona mejor si modela con precisión la distribución de las palabras elegidas por el colocador , y un organismo humano bien puede elegir palabras basándose en su rareza o en evitar las letras de uso frecuente. Por ejemplo, aunque E es la letra más utilizada en inglés, si el colocador siempre elige de las palabras JUGFUL , RHYTHM , SYZYGY y ZYTHUM , entonces un solucionador perfecto no comienza adivinando E !

El mejor enfoque para modelar al setter depende del contexto, pero supongo que algún tipo de inferencia inductiva bayesiana funcionaría bien en un contexto donde el solucionador juega muchos juegos contra el mismo setter, o contra un grupo de setters similares.

3. Un algoritmo verdugo

Aquí voy a delinear un solucionador que es bastante bueno (pero lejos de ser perfecto). Modela que el colocador elige palabras de manera uniforme de un diccionario fijo. Es un algoritmo codicioso : en cada etapa adivina la letra que minimiza el número de errores, es decir, las palabras que no contienen la suposición. Por ejemplo, si hasta ahora no se han realizado conjeturas, y las posibles palabras son DEED , DEAD y DARE , entonces:

• si adivinas D o E , no hay errores;
• si adivina A , hay una señorita ( DEED );
• si DEED R , hay dos errores ( DEED y DEAD );
• si adivinas alguna otra carta, hay tres errores.

Entonces D o E son una buena suposición en esta situación.

(Gracias al Coronel Panic en los comentarios por señalar que las suposiciones correctas son gratuitas en el verdugo, ¡lo olvidé por completo en mi primer intento!)

4. Implementación

Aquí hay una implementación de este algoritmo en Python:

from collections import defaultdict
from string import ascii_lowercase

def partition(guess, words):
    """Apply the single letter ''guess'' to the sequence ''words'' and return
    a dictionary mapping the pattern of occurrences of ''guess'' in a
    word to the list of words with that pattern.

    >>> words = ''deed even eyes mews peep star''.split()
    >>> sorted(list(partition(''e'', words).items()))
    [(0, [''star'']), (2, [''mews'']), (5, [''even'', ''eyes'']), (6, [''deed'', ''peep''])]

    """
    result = defaultdict(list)
    for word in words:
        key = sum(1 << i for i, letter in enumerate(word) if letter == guess)
        result[key].append(word)
    return result

def guess_cost(guess, words):
    """Return the cost of a guess, namely the number of words that don''t
    contain the guess.

    >>> words = ''deed even eyes mews peep star''.split()
    >>> guess_cost(''e'', words)
    1
    >>> guess_cost(''s'', words)
    3

    """
    return sum(guess not in word for word in words)

def word_guesses(words, wrong = 0, letters = ''''):
    """Given the collection ''words'' that match all letters guessed so far,
    generate tuples (wrong, nguesses, word, guesses) where
    ''word'' is the word that was guessed;
    ''guesses'' is the sequence of letters guessed;
    ''wrong'' is the number of these guesses that were wrong;
    ''nguesses'' is len(guesses).

    >>> words = ''deed even eyes heel mere peep star''.split()
    >>> from pprint import pprint
    >>> pprint(sorted(word_guesses(words)))
    [(0, 1, ''mere'', ''e''),
     (0, 2, ''deed'', ''ed''),
     (0, 2, ''even'', ''en''),
     (1, 1, ''star'', ''e''),
     (1, 2, ''eyes'', ''en''),
     (1, 3, ''heel'', ''edh''),
     (2, 3, ''peep'', ''edh'')]

    """
    if len(words) == 1:
        yield wrong, len(letters), words[0], letters
        return
    best_guess = min((g for g in ascii_lowercase if g not in letters),
                     key = lambda g:guess_cost(g, words))
    best_partition = partition(best_guess, words)
    letters += best_guess
    for pattern, words in best_partition.items():
        for guess in word_guesses(words, wrong + (pattern == 0), letters):
            yield guess

5. Resultados de ejemplo

Usando esta estrategia es posible evaluar la dificultad de adivinar cada palabra en una colección. Aquí considero las palabras de seis letras en mi diccionario del sistema:

>>> words = [w.strip() for w in open(''/usr/share/dict/words'') if w.lower() == w]
>>> six_letter_words = set(w for w in words if len(w) == 6)
>>> len(six_letter_words)
15066
>>> results = sorted(word_guesses(six_letter_words))

Las palabras más fáciles de adivinar en este diccionario (junto con la secuencia de suposiciones necesarias para que el solucionador las adivine) son las siguientes:

>>> from pprint import pprint
>>> pprint(results[:10])
[(0, 1, ''eelery'', ''e''),
 (0, 2, ''coneen'', ''en''),
 (0, 2, ''earlet'', ''er''),
 (0, 2, ''earner'', ''er''),
 (0, 2, ''edgrew'', ''er''),
 (0, 2, ''eerily'', ''el''),
 (0, 2, ''egence'', ''eg''),
 (0, 2, ''eleven'', ''el''),
 (0, 2, ''enaena'', ''en''),
 (0, 2, ''ennead'', ''en'')]

y las palabras más difíciles son estas:

>>> pprint(results[-10:])
[(12, 16, ''buzzer'', ''eraoiutlnsmdbcfg''),
 (12, 16, ''cuffer'', ''eraoiutlnsmdbpgc''),
 (12, 16, ''jugger'', ''eraoiutlnsmdbpgh''),
 (12, 16, ''pugger'', ''eraoiutlnsmdbpcf''),
 (12, 16, ''suddle'', ''eaioulbrdcfghmnp''),
 (12, 16, ''yucker'', ''eraoiutlnsmdbpgc''),
 (12, 16, ''zipper'', ''eraoinltsdgcbpjk''),
 (12, 17, ''tuzzle'', ''eaioulbrdcgszmnpt''),
 (13, 16, ''wuzzer'', ''eraoiutlnsmdbpgc''),
 (13, 17, ''wuzzle'', ''eaioulbrdcgszmnpt'')]

La razón por la cual son difíciles es porque después de haber adivinado -UZZLE , todavía tienes siete posibilidades:

>>> '' ''.join(sorted(w for w in six_letter_words if w.endswith(''uzzle'')))
''buzzle guzzle muzzle nuzzle puzzle tuzzle wuzzle''

6. Elección de la lista de palabras

Por supuesto, al preparar listas de palabras para sus hijos, no comenzaría con el diccionario del sistema de su computadora, comenzaría con una lista de palabras que usted cree que probablemente conozcan. Por ejemplo, puede echar un vistazo a las listas de Wiktionary de las palabras usadas con mayor frecuencia en varios corpus ingleses.

Por ejemplo, entre las 1.700 palabras de seis letras de las 10.000 palabras más comunes del Proyecto Gutenberg a partir de 2006 , las diez más difíciles son las siguientes:

[(6, 10, ''losing'', ''eaoignvwch''),
 (6, 10, ''monkey'', ''erdstaoync''),
 (6, 10, ''pulled'', ''erdaioupfh''),
 (6, 10, ''slaves'', ''erdsacthkl''),
 (6, 10, ''supper'', ''eriaoubsfm''),
 (6, 11, ''hunter'', ''eriaoubshng''),
 (6, 11, ''nought'', ''eaoiustghbf''),
 (6, 11, ''wounds'', ''eaoiusdnhpr''),
 (6, 11, ''wright'', ''eaoithglrbf''),
 (7, 10, ''soames'', ''erdsacthkl'')]

(Soames Forsyte es un personaje de la saga Forsyte de John Galsworthy ; la lista de palabras se ha convertido en minúsculas, por lo que no me fue posible eliminar rápidamente los nombres propios).

Answer 2

¡Solo hazlo! Juega al ahorcado contra la palabra. Cuente cuántas pérdidas (es decir, conjeturas incorrectas) se necesitan para vencer.

Necesitarás una estrategia para jugar. Aquí hay una estrategia humana (ish). Del diccionario, tache todas las palabras que no se ajustan a lo revelado hasta el momento. Adivina la letra más frecuente entre las palabras restantes.

Si su estrategia es aleatorizada, puede definir su medida como la cantidad esperada de pérdidas y estimarla empíricamente.

Otra estrategia determinista, de un ahorcado bot que escribí hace unos años. Adivina la letra que minimiza el número de palabras restantes en el caso de que la suposición sea incorrecta (es decir, optimice el peor de los casos). Hoy no me gusta esta estrategia por ser demasiado mecánica, prefiero la anterior.

Answer 3

Bueno, potencialmente podría haber muchas cosas involucradas:

1. Como todos dijeron, la frecuencia de las letras individuales;
2. La longitud de una palabra definitivamente debe contar, pero no de forma lineal: una palabra larga puede hacer que las suposiciones casuales toquen las letras, mientras que una breve puede ser difícil de obtener;
3. Además, las palabras en sí deben ser consideradas: "bipartito" podría ser una palabra para las personas en SO, pero tal vez no para la población no técnica.

En realidad, podría tratar de co-evolucionar varias estrategias , la mitad de ellas para decidir el valor de una palabra, y la mitad de ellas para tratar de ganar el juego. El último grupo intentará maximizar el puntaje mientras que el primero intentará minimizar el puntaje. Después de un tiempo puede haber un patrón y luego la mitad para decidir el valor de una palabra puede darte algunos puntos de referencia.

Answer 4

Calcule el valor de cada letra de una palabra en los puntos de Scrabble: E = 1, D = 2, V = 4, X = 8 y así sucesivamente. Suma y divídelos por el número de letras para obtener un valor de letra promedio, y úsalo para anotar la palabra. Calcule el promedio de cada palabra en un diccionario grande y determine los puntos de quiebre entre cuartiles. Las palabras de las palabras en el cuartil más bajo son "fáciles", las palabras en los dos cuartiles medios "medianas" y las palabras en el cuartil más alto "duras".

Answer 5

Comience con una Lista de palabras y lance una búsqueda de Google para cada una. Deje que The number of Hits sirva como un proxy (grosero) de la dificultad del término.

En una versión refinada, agrupar palabras por un sinónimo Relación basada en un diccionario de sinónimos y determinar la palabra más difícil de una categoría contando los resultados de las búsquedas de Google.

Tomando la noción de n-Grams Un paso más allá, la dificultad de una palabra podría calificarse por la frecuencia de sus sílabas en prosa. Depende de la calidad de las estadísticas de la sílaba, por supuesto. Probablemente tendrías que Diferenciar entre Lexemas y Palabras funcionales (determinantes, conjunciones, etc.) y Normalizar por número de sílabas en la Palabra (Se siente como Overkill cuando escribo ...).

Answer 6

Discusión similar previa sobre el mismo tema: determinar la dificultad de una palabra en inglés

Me gusta la respuesta al final del enlace ^. Para un juego de ahorcado para niños, solo aplica un enfoque como scrabble.

Asigne un valor de punto a cada letra, luego solo agregue las letras.

Answer 7

Estás recibiendo votos desfavorables porque nos pides que construyamos un algoritmo muy complejo para ti.

¿Por qué no creas tres arreglos (fácil, medio y difícil) y llenas cada uno con un centenar de palabras? Tardaría unos 20 minutos.

Prometo que tus hijos se aburrirán del ahorcado mucho antes de que se quemen unos cientos de juegos ...: D

Answer 8

Hace un tiempo escribí un solucionador de ahorcado usando el algoritmo obvio: dado un diccionario inicial de todas las palabras posibles, en cada turno elegimos la letra que aparece en la mayoría de las palabras restantes en el diccionario, luego eliminamos palabras que no coinciden (dependiendo de la respuesta) del diccionario.

El algoritmo no es tan sencillo como este, ya que a menudo hay varias letras que aparecen en el mismo número de palabras en el diccionario. En este caso, la elección de la letra puede marcar una diferencia significativa en la cantidad de conjeturas que se requieren para una palabra. Seleccionamos los valores máximos en los que la información resultante sobre la ubicación de esa letra (si está realmente en la palabra) proporciona la información máxima sobre el sistema (la letra con la máxima entropía de información ). por ejemplo, si las dos palabras posibles restantes son ''enciclopedia'' y ''enciclopédica'', la letra ''c'' tiene la misma probabilidad de aparecer como e, n, y, l, o, p, e, d, i (es decir, se garantiza que está en la palabra), pero deberíamos preguntar acerca de ''c'' primero, ya que tiene una entropía de información distinta de cero.

Fuente (C ++, GPL) está here

El resultado de todo esto es una lista de palabras, con el número de conjeturas requeridas para cada una: difficulty.txt (630 KB). La palabra más difícil para encontrar este algoritmo es "voluntad" (con 14 conjeturas fallidas); el i y el doble l se adivinan bastante rápido, pero las opciones incluyen bill, eill, fill, gill, hill, kill, mill, pill, rill, till, will, y desde ese momento la única opción es adivinar cada letra en giro. De manera un tanto intuitiva, las palabras más largas son mucho más fáciles de adivinar (simplemente no hay ninguna que pueda elegir).

Por supuesto, en un juego humano de ahorcado, la psicología (y la amplitud del vocabulario) juegan un papel mucho más importante de lo que explica este algoritmo para ...

Answer 9

Me gusta la idea de construir un algoritmo que aprenda y cambie dependiendo de los usuarios. Al principio, puede implementar cualquiera de los algoritmos sugeridos para crear la lista, luego, a medida que más personas juegan, asigna un peso a cada una de las palabras según el número de conjeturas (que también se rastrea y calcula continuamente ) Esto evita que la cuestión de las palabras complejas pero populares tenga una clasificación difícil, pero es bien conocida por las personas.

Answer 10

Primero, por supuesto, generarías una lista de letras únicas. Luego, clasifique por frecuencia (en inglés o en cualquier idioma, hay listas para esto ), con letras menos frecuentes que tienen una dificultad mayor.

Luego debe decidir si combina las puntuaciones agregando, multiplicando o usando algún otro esquema.

Answer 11

Puede usar el Método Monte Carlo para estimar la dificultad de una palabra:

• Simule un juego adivinando una letra al azar cada vez, ponderado por la frecuencia de la letra en su idioma de destino, y cuente cuántas suposiciones le tomó al jugador aleatorizado para llegar a una solución. Tenga en cuenta que dado que cada intento elimina una letra, este proceso es finito y devuelve un número del 1 al 26, inclusive.
• Repita este proceso 2*N veces, donde N es el número de letras únicas en su palabra,
• Calcule el puntaje promediando los resultados de 2*N carreras,
• Determine el nivel de complejidad: los puntajes menores de diez indican una palabra fácil, y los puntajes superiores a dieciséis indican una palabra difícil; todo lo demás es medio.

Answer 12

Una forma realmente simple sería calcular una puntuación basada en la falta de vocales en la palabra, el número de letras únicas y el carácter común de cada letra:

letters = ''etaoinshrdlcumwfgypbvkjxqz''
vowels = set(''aeiou'')

def difficulty(word):
    unique = set(word)
    positions = sum(letters.index(c) for c in word)

    return len(word) * len(unique) * (7 - len(unique & vowels)) * positions

words = [''the'', ''potato'', ''school'', ''egypt'', ''floccinaucinihilipilification'']

for word in words:
    print difficulty(word), word

Y el resultado:

432 the
3360 potato
7200 school
7800 egypt
194271 floccinaucinihilipilification

A continuación, puede anotar las palabras con:

        score < 2000   # Easy
 2000 < score < 10000  # Medium
10000 < score          # Hard