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

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

La dificultad parecería estar relacionada con el número de conjeturas requeridas, la frecuencia relativa de uso de letras (por ejemplo, las palabras con muchas letras poco comunes pueden ser más difíciles 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 pueda ser reconocida, lo que permite pasar de una estrategia de adivinación basada solo en frecuencias de letras a una adivinación basada en una lista de palabras coincidentes conocidas.

Mi intento por ahora está abajo en rubí. ¿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 jugaran mis hijos; Soy demasiado mayor para intentar hacer "deberes", que puede ser la razón por la que la pregunta recibe tantos votos en contra ... Las palabras se extraen al azar de grandes bases de datos de palabras, que incluyen muchas palabras oscuras, y se filtran por nivel de dificultad determinado por la palabra.

1. Introducción

Aquí hay una manera de abordar este problema de manera sistemática: si tiene un algoritmo que juega bien al ahorcado, entonces puede tomar la dificultad de cada palabra como el número de conjeturas incorrectas que su programa tomaría si adivina esa palabra.

2. Aparte de la estrategia del ahorcado

Hay una idea implícita en algunas de las 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 del todo correcta. El solucionador lo hace mejor si modela con precisión la distribución de las palabras elegidas por el colocador , y un colocador humano puede estar eligiendo palabras basándose en su rareza o evitando las letras de uso frecuente. Por ejemplo, aunque Ees la letra más frecuentemente utilizado en Inglés, si el colocador elige siempre de las palabras JUGFUL, RHYTHM, SYZYGY, y ZYTHUM, a continuación, un programa de solución perfecta no se inicia al adivinar E!

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

3. Un algoritmo del ahorcado

Aquí describiré un solucionador que es bastante bueno (pero lejos de ser perfecto). Modela al colocador eligiendo palabras uniformemente de un diccionario fijo. Es un algoritmo codicioso : en cada etapa adivina la letra que minimiza el número de errores, es decir, palabras que no contienen la conjetura. Por ejemplo, si no se han realizado conjeturas hasta ahora y las palabras posibles son DEED, DEADy DARE, entonces:

• si adivinas Do E, no hay errores;
• si adivinas A, hay un error ( DEED);
• si adivinas R, hay dos fallos ( DEEDy DEAD);
• si adivina cualquier otra letra, hay tres fallos.

Entonces, Do Ees una buena suposición en esta situación.

(Gracias al coronel Panic en los comentarios por señalar que las suposiciones correctas son gratis en el ahorcado; ¡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. Ejemplos de resultados

Con esta estrategia es posible evaluar la dificultad de adivinar cada palabra en una colección. Aquí considero las palabras de seis letras en el diccionario de mi 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 conjeturas 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 que estos son difíciles es porque después de haber adivinado -UZZLE, todavía te quedan 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 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 cree que es probable que conozcan. Por ejemplo, puede echar un vistazo a las listas de Wiktionary de las palabras más utilizadas en varios corpus en inglés.

Por ejemplo, entre las 1,700 palabras de seis letras en las 10,000 palabras más comunes en el Proyecto Gutenberg a partir de 2006 , las diez más difíciles son estas:

[(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 Forsyte Saga de John Galsworthy ; la lista de palabras se ha convertido a minúsculas, por lo que no me fue posible eliminar rápidamente los nombres propios).

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 lo 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 la salida:

432 the
3360 potato
7200 school
7800 egypt
194271 floccinaucinihilipilification

Luego, podría calificar las palabras con:

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

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

• Simule un juego adivinando una letra aleatoria cada vez, ponderada por la frecuencia de las letras en su idioma de destino, y cuente cuántas conjeturas le tomó a su jugador aleatorio llegar a una solución. Tenga en cuenta que dado que cada conjetura elimina una letra, este proceso es finito y devuelve un número del 1 al 26, inclusive.
• Repita este proceso 2*Nveces, donde Nestá el número de letras únicas en su palabra,
• Calcule la puntuación promediando los resultados de las 2*Ncarreras,
• Determine el nivel de complejidad: las puntuaciones inferiores a diez indican una palabra fácil y las puntuaciones superiores a dieciséis indican una palabra difícil; todo lo demás es mediano.

Discusión anterior similar 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, simplemente aplique un enfoque como lo hace Scrabble.

Asigne un valor en puntos a cada letra, luego sume las letras.

Hace un tiempo escribí un solucionador del 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 que quedan en el diccionario, luego eliminamos las 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. Elegimos los máximos donde la información resultante sobre la ubicación de esa letra (si de hecho está en la palabra) da la máxima información 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, es garantizado que está en la palabra), pero deberíamos preguntar primero sobre 'c' ya que tiene una entropía de información distinta de cero.

La fuente (C ++, GPL) está aquí

El resultado de todo esto es una lista de palabras, con el número de conjeturas necesarias para cada una: dificultad.txt (630KB). La palabra más difícil de encontrar para este algoritmo es "voluntad" (con 14 suposiciones fallidas); la iy la doble l se adivinan con bastante rapidez, pero luego las opciones incluyen factura, eneldo, relleno, agalla, colina, matar, moler, pill, rill, till, will, y a partir de entonces la única opción es adivinar cada letra en giro. Algo contrario a la intuición, las palabras más largas se adivinan mucho más rápido (simplemente no hay tantas para elegir).

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

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

Necesitarás una estrategia para jugar. Aquí hay una estrategia humana (ish). Del diccionario, tacha todas las palabras que no se ajusten a las revelaciones hasta ahora. Adivina la letra más frecuente entre las palabras restantes.

Si su estrategia es aleatoria, puede definir su medida como el número esperado de decomisos y estimarlo empíricamente.

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

Primero, por supuesto, generaría una lista de letras únicas. Luego ordene por frecuencia (en inglés o en cualquier idioma; hay listas para esto ), y las letras menos frecuentes tienen una mayor dificultad.

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

Te votan negativamente porque nos estás pidiendo que creemos un algoritmo muy complejo para ti.

¿Por qué no crea simplemente tres matrices (fácil, medio y difícil) y las llena con un centenar de palabras? Tardaría unos 20 minutos.

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

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 debería contar, pero no de forma lineal: una palabra larga puede hacer que las suposiciones al azar lleguen a las letras, mientras que una corta puede ser difícil de conseguir;
3. Además, deben tenerse en cuenta las palabras en sí mismas: "bipartito" podría ser una palabra para personas en SO, pero tal vez no para la población no técnica.

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

Comience con una lista de palabras y realice una búsqueda en Google para cada una. Deje que el número de golpes sirva como un proxy (aproximado) de la dificultad del término.

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

Llevando la noción de n-gramos 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 las sílabas, por supuesto. Probablemente tenga que diferenciar entre Lexemas y palabras de función (determinantes, conjunciones, etc.) y normalizar por número de sílabas en la palabra (se siente como Overkill mientras escribo ...).

Me gusta la idea de construir un algoritmo que aprenda y cambie según 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 en función del número de conjeturas (que también se rastrea y calcula continuamente ). Esto evita el problema de las palabras complejas pero populares que reciben una calificación difícil pero que son bien conocidas por la gente.

Calcule el valor de cada letra de una palabra en puntos de Scrabble: E = 1, D = 2, V = 4, X = 8 y así sucesivamente. Súmelos y divídalos por la cantidad de letras para obtener un valor promedio de letras, y utilícelo para calificar la palabra. Calcule el promedio de cada palabra en un diccionario grande y determine los puntos de ruptura entre los cuartiles. Llame a las palabras en el cuartil más bajo "fácil", a las palabras en los dos cuartiles medios "medio" y a las palabras en el cuartil más alto "difícil".