Boggle probabilidad de letras

Question

¿Cómo distribuir las letras del alfabeto inglés entre los dados del juego Boggle? ¿Cómo hacer rodar por ejemplo la letra "A" más a menudo que otras? ¿Cómo elegir cuántas copias de cada letra hacer, y cuántas copias de ellas poner en un dado? ¿Puede responder a estas preguntas?

Answer 1

Creo que la pregunta que intentas hacer es: "¿cómo puedo distribuir mis letras entre las caras de los (16) dados Boggle para que coincidan aproximadamente con las probabilidades inglesas?". En realidad es una pregunta más interesante de lo que parece a primera vista, porque la aproximación de primer orden es fácil, pero los sutiles efectos "no lineales" se cuelan más allá de esa primera aproximación, y no estoy seguro de cuál es la mejor manera de manejarlos (he codificado un pequeño puñado de juegos de palabras, y mi respuesta ha sido tradicionalmente "fingirlo").

Para empezar, ten en cuenta que tienes 96 (16 $\times$ 6) caras con las que jugar; además (y este es el punto clave de esa primera aproximación), en realidad no importa en qué caras pongas qué letras. Tanto si pintas las seis caras de un dado con la letra "A", como si pintas una cara de cada uno de los seis dados diferentes, el número medio de "A" en el tablero (promediado a lo largo de muchas tiradas) será el mismo: la probabilidad de que cualquier cara sea una A (6/96) multiplicada por el número de caras visibles en una tirada (16) - es decir, de media tendrás exactamente 1 "A" por tirada. Por tanto, en una primera aproximación, puedes multiplicar las frecuencias básicas de las letras (que puedes encontrar en cualquier sitio, o incluso haciendo un análisis de diccionario por tu cuenta) por el número de ranuras que hay que rellenar (96 para el problema clásico de Boggle) y, redondeando adecuadamente, obtener un número apropiado de fichas para cada letra; una vez que las tengas, no importa cómo las asignes a las caras del dado.

Pero, de nuevo, por supuesto... esto es "a primera aproximación", con los supuestos de que las probabilidades de las letras son independientes entre sí; que la probabilidad de que una palabra contenga dos A es el cuadrado de la probabilidad de que contenga una A, o que la probabilidad de que una palabra contenga una A y una S es el producto de las probabilidades individuales de las letras P(A) y P(S). Pero, por supuesto, esto no es cierto; las combinaciones de letras en inglés están muy correlacionadas. Por ejemplo, la Q aparece tanto más a menudo con la U que sin ella que prácticamente todos los juegos de palabras ingleses (con la rara y notable excepción del Scrabble) las combinan en un solo glifo. También hay muchos otros ejemplos: muchas consonantes (y un par de vocales) tienen más probabilidades de aparecer en múltiplos de lo que dictarían las probabilidades de una sola letra; las "H" suelen ir emparejadas con "T" y "S", las "G" con "N", etc. Además, estas correlaciones son extremadamente difíciles de modelizar, porque ni siquiera está claro cuál es la medida adecuada: ¿se quiere saber la probabilidad de que dos letras aparezcan una al lado de la otra, o simplemente la probabilidad de que aparezcan en la misma palabra, o algo totalmente distinto? Y por otro lado, los valores explícitos de la probabilidad de que dos letras aparezcan juntas en la cuadrícula son difíciles de calcular con algo que no sea una simple enumeración de todas las posibilidades. El mejor enfoque puede ser algo parecido a lo que menciona Dan Brumleve del recocido simulado: empezar con una "disposición" arbitraria (una asignación de 96 fichas a los 6 $\times$ 16 caras de tu dado) y luego ejecuta unos cuantos miles de simulaciones para obtener la probabilidad conjunta de todas las combinaciones de dos letras (o de un conjunto convenientemente elegido). A continuación, modifique la distribución, realice otra simulación y, si las probabilidades conjuntas se acercan más a las "correctas" que en la primera distribución, acepte el cambio; repita el proceso hasta obtener una distribución que ofrezca probabilidades conjuntas razonablemente buenas.

Por desgracia, incluso este todavía en realidad no da cabida a todas las correlaciones relevantes que se dan en la lengua inglesa. Por ejemplo, la probabilidad de que al menos un La probabilidad de que una vocal aparezca en una palabra es mucho, mucho mayor de lo que se estimaría a partir de las probabilidades de cada letra o de las probabilidades conjuntas de dos letras, hasta el punto de que (de nuevo) los juegos de palabras basados en dados a menudo se aseguran de tener uno o dos dados que sean todo vocales (y al contrario, algunos dados que sean todo consonantes) para garantizar que aparezca al menos una vocal y que la varianza en la proporción consonante:vocal sea menor (ya que es relativamente baja en inglés). Se trata de un problema en el que se necesita un poco de conocimiento específico del campo y en el que no hay una respuesta rápida y definitiva.

Answer 2

Vamos a trabajar con fichas de Scrabble (sin espacios en blanco) en lugar de dados de Boggle, para simplificar al máximo las cosas. (Al final, puedes hacer tus dados Boggle pegando las fichas Scrabble en ellos). Supongamos que tenemos $n$ azulejos, con $n \ge 26$ y una tabla de frecuencias de letras (por ejemplo, éste ), que convertimos en probabilidades dividiendo por 100.

Lo primero que hay que hacer es elegir cada letra una vez (suponiendo que quieras que todas las letras aparezcan al menos una vez). A continuación, reste $1/n$ de cada frecuencia de letras para tenerlo en cuenta, y establecer $n = n - 26$ . Esto puede hacer que algunas de las frecuencias de las letras sean negativas, por lo que descartamos esas letras y renormalizamos las frecuencias restantes para que sumen $1$ (es decir, si $S$ es la suma de las frecuencias restantes, multiplicamos cada frecuencia por $1/S$ .)

Ahora sólo tienes que hacer lo siguiente ( Actualizado funcione correctamente):

for (i = 1 to n) {
  Pick the letter L with the largest frequency
  Subtract 1/n from L's frequency
}

Así es como yo lo haría, de todos modos.

Answer 3

Suponiendo que quieras que coincida aproximadamente con la distribución de las letras en las palabras inglesas, puedes generar un histograma con algo como esto:

cat /usr/share/dict/words |perl -pe 's/[^a-z]//gs' |perl -e 'print join(" \n ", split //, <>) . " \n "' |sort |uniq -c

Convierte estos valores en probabilidades dividiendo por el total, multiplica por el número total de dados, multiplica por 6 y luego redondea a un número entero para que tengas al menos una instancia de cada letra. Cambia los números para que el total sea divisible por 6. A continuación, etiqueta cada cara con esas letras de forma que minimices el número de letras duplicadas en cada dado.

Si concretamos más el problema, probablemente haya una forma mejor (pero más complicada). Si realmente quieres maximizar el número esperado de palabras que aparecen en el tablero de Boggle, creo que tendrás que usar algún tipo de recocido simulado para optimizarla.

Answer 4

Acabo de escribir un sencillo programa en python para hacer esto, y estoy buscando las letras reales que aparecen en los dados.

Quieres un array de 16 elementos, cada uno de los cuales es un array de 6 elementos de ints.

import array
lets = [array.array('i',[0]*6)]*16

construye la matriz requerida. A continuación, se introducen los códigos de caracteres correspondientes. (O algo así -- no puedo recordar los códigos de tipo de matriz aparte de i, así que sólo usé eso, junto con

import random
lets[i][j] = random.randrange(26) + 'A'.encode('UTF-8')[0]

esto da a cada letra la misma probabilidad. Luego hay que sustituir esta línea por algo que, para cada i y j, obtenga la letra correcta para un juego Boggle real.

Entonces haces

a = []
for i in range(16):
    a.append(random.choice(lets[i]))

para obtener una matriz de 16 letras.

Por fin,

for i in range(16):
    print(a[i],end=' ')
    if i % 4 == 3:
         print()

imprimirá una bonita cuadrícula de 4x4, como

I O S O 
C O O S 
C C U P 
S U I U

y este último ejemplo muestra por qué es necesario establecer manualmente las opciones de letras en lugar de elegir letras al azar del alfabeto.

http://thewikiman.allsup.co/BogglePlay tiene un script completo en Python para esto.