JugonesTop

¿Cuáles son las probabilidades en Scrabble de no poder hacer un movimiento legal en el turno de apertura? scrabble juegos-de-mesa

He estado jugando el juego durante 50 años y esto me sucedió recientemente:

Tenía el siguiente estante

 PBQZJDH
 

Y entonces no pude hacer un movimiento legal.

He estado tratando de calcular las probabilidades de que esto ocurra (no hay palabra legal en el primer turno).

Respuestas

Este es el comienzo de una mucho más larga la respuesta, pero me voy a poner aquí por ahora como un marcador de posición y, como parte de los hallazgos iniciales. Esta cuestión también será pesado en ciencias de la computación, debido al hecho de que no somos la fuerza bruta de la respuesta debido a la magnitud del problema en cuestión


Para empezar, un muy débil, pero fácilmente demostrado límite superior para el porcentaje llega a 86.42% de posibilidades. Esta es la probabilidad de no tener ninguna en blanco azulejos en su conjunto inicial de siete fichas. Cualquier conjunto de las baldosas con un espacio en blanco sería capaz de formar por lo menos uno de los dos letra de la palabra. La letra V es la única carta que no tiene legal de dos letras de la palabra que la contiene, y hay sólo 2 de cada baldosa en el juego, por lo tanto, no sería de al menos otros cuatro letras en su conjunto que podría constituir una de dos letras de la palabra.

Mientras que esta enlazado es muy alta, esto servirá como un excelente punto de partida para nuestra respuesta, así como lo que nos permite ignorar cuadrados en blanco para el resto de la respuesta


Estoy utilizando el documento de texto proporcionado en esta respuesta para intentar determinar la respuesta.

Hay 279,496 palabras contenidas en el diccionario.

De esos, podemos descuento todos pero 77,459 de esas palabras, como usted no puede reproducir un 8+ letra de la palabra en la primera jugada del juego, por la naturaleza de tener sólo 7 letras.

De esos, podemos descuento todos pero 181 palabras, debido a otra palabra que contiene la palabra. Por ejemplo, no hay ninguna razón para examinar la palabra "Y" porque la palabra "UN" también puede ser construido.

Estas son las palabras que necesitamos examinar

AA AB AD AE AG AH AI AL AM UN AR COMO EN AVO AW AX AY SER BI BO BRR BUB BUD A GRANEL TORO POR CH CIRRI CIVIC CLY LLORAR CUB CUD CUE BRAZALETE CULL CUZ CWM DE DI ¿ SECO DUD EE EF HUEVO EH EL EM EN ER ES ET EUK EW EX FA La GRIPE FUB A la MIERDA FUD El año FISCAL GHYLL GI IR GRR GU Gyp acto HOLA HM HO HYP HIELO HELADO SI EN IO ES ES IVY IWI JA JEU JIZ JO JUD JUKU KA BARRIL KI KO KUDU KUZU KY LI LO SUERTE LUD LULL LUV LUZ MI MM MO MU MI NO N NU NY OCA OE DE OO OP O OS OU El UJO de BUEY OY PA PE PFFT HTP PI PLY Haga PALANCA PWN PYX QI QUA RHY RIZ SH SLY SPY ST SWY TU A TRATE de TWP TYG TYPP TYPY UH ULU HASTA UR NOSOTROS UT Los rayos UVA VAC VAV VEG VIE VLY Por QUÉ WIZ IRÓNICA WUD WULL WUZ XI XU XILILO VOSOTROS YIRR YU ZA ZE ZO

(Por borrible, hay también únicas combinaciones de letras que se pueden formar palabras, pero no puede hacerse sin el uso de espacios en blanco, y por encima de, cualquier combinación que incluye un espacio en blanco hace que una palabra, por lo que hemos eliminado FUFF, JUJU, KECK, KUKU, SYZYGY, ZIZ, ZUZ, y ZZZ. Esto trae a nuestra total hacia 173.)

Por mi cuenta, hay cuatro 5-letra (XILILO, GHYLL, CIRRI, CÍVICO) y nada más. También, no he tenido tiempo de comprobar, pero es muy probable que todos los "Consonante sólo" las palabras son más probables en esta lista.

#unique.py

words = []

words_in_dictionary = 0
words_short_enough = 0

def i_in_j(arr1, arr2):
   for a in arr1:
      if a in arr2:
         arr2.remove(a)
      else:
         return False
   return True
         

print("loading dictionary")
with open("dictionary.txt", "r") as dictfile:
   for line in dictfile:
      words_in_dictionary = words_in_dictionary + 1
      base_word = line.strip()
      
      if len(base_word) <= 7:
         words_short_enough = words_short_enough + 1
         word = {"base": base_word, "sorted": sorted(base_word)}
         words.append(word)
   
print("total words in dictionary is " + str(words_in_dictionary))   
print("words 7 letters or shorter is " + str(words_short_enough))

i = 0
while i < len(words):
   temp_sorted_working_word = words[i]["sorted"]
   
   j = 0
   while j < len(words):
      if i == j:
         j = j + 1
         continue
         
      if i_in_j(words[i]["sorted"][:], words[j]["sorted"][:]):
         del words[j]
         if i > j:
            i = i - 1
            j = j - 1
         elif j > i:
            j = j - 1
      
      j = j + 1
   i = i + 1

print("unique minimilized word combinations is " + str(len(words)))

(Trabajo en progreso, vuelva más tarde)

He utilizado el comienzo del programa en @DenisS's respuesta para construir la Scrabble diccionario, entonces, yo lo he utilizado para escribir un pequeño monte-carlo programa para estimar la probabilidad de que ninguna palabra puede ser formado con siete aleatoria de las baldosas.

El resultado es una 0.58% +- 0.27% de probabilidad de que ninguna palabra puede ser formado.

Salida

$ python3 get_proba.py 1000 50
loading dictionary
total words in dictionary is 279497
words 7 letters or shorter is 77459
Running for 50 experiments of 1000 draws...
Ran for 50 experiments of 1000 draws.
Successes: [996, 996, 996, 995, 992, 996, 998, 993, 994, 993, 992, 993, 998, 994, 994, 986, 994, 996, 990, 994, 997, 998, 994, 993, 993, 991, 999, 991, 997, 996, 993, 989, 995, 996, 998, 996, 995, 996, 992, 992, 998, 994, 993, 989, 993, 991, 991, 999, 995, 995]
Proba of failure = 0.00582000000000005 +- 0.0027472895733795517

Código

def build_dict():
    words = []
    words_in_dictionary = 0
    words_short_enough = 0
    print("loading dictionary")
    with open("dictionary.txt", "r") as dictfile:
        for line in dictfile:
            base_word = line.strip()
            if len(base_word) > 0:
                words_in_dictionary = words_in_dictionary + 1
                if len(base_word) <= 7:
                    words_short_enough = words_short_enough + 1
                    word = {"base": base_word, "sorted": sorted(base_word)}
                    words.append(word)
    print("total words in dictionary is " + str(words_in_dictionary))
    print("words 7 letters or shorter is " + str(words_short_enough))
    ok_combinations = [''.join(word["sorted"]) for word in words]
    return(ok_combinations)

def flatten(ll):
    return [x for l in ll for x in l]

def build_letter_bag():
    return flatten([['A']*9, ['B']*2, ['C']*2, ['D']*4, ['E']*12, ['F']*2, ['G']*3, ['H']*2, ['I']*9, ['J']*1, ['K']*1, ['L']*4, ['M']*2, ['N']*6, ['O']*8, ['P']*2, ['Q']*1, ['R']*6, ['S']*4, ['T']*6, ['U']*4, ['V']*2, ['W']*2, ['X']*1, ['Y']*2, ['Z']*1, ['*']*2])

dico = build_dict()
letter_bag=build_letter_bag()

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def can_make_word(letters):
    if '*' in letters:
        return True
    return any((''.join(subset) in dico) for subset in powerset(sorted(letters)))

import random

def montecarlo(n):
    nb_ok = 0
    for i in range(n):
        letters = random.sample(letter_bag, 7)
        nb_ok += (1 if can_make_word(letters) else 0)
    return nb_ok

import statistics

def run_experiments(nb_draws, nb_experiments):
    nb_ok_list = [montecarlo(nb_draws) for i in range(nb_experiments)]
    average = statistics.fmean(nb_ok_list)
    stdev = statistics.pstdev(nb_ok_list, mu=average)
    return average, stdev, nb_ok_list

def get_args(argv):
    nb_draws, nb_exp = 1000, 1
    if len(argv) > 1:
        nb_draws = int(argv[1])
        if len(argv) > 2:
            nb_exp = int(argv[2])
    return nb_draws, nb_exp

def main(argv):
    random.seed()
    nb_draws, nb_experiments = get_args(argv)
    print('Running for {} experiments of {} draws...'.format(nb_experiments, nb_draws))
    average, stdev, l = run_experiments(nb_draws, nb_experiments)
    print('Ran for {} experiments of {} draws.'.format(nb_experiments, nb_draws))
    print('Successes:', l)
    print('Proba of failure = {} +- {}'.format((nb_draws - average)/nb_draws, stdev/nb_draws))

import sys
if __name__=='__main__':
    main(sys.argv)

Representación a César:

  • El código en build_dict() es de @DenisS's respuesta;
  • El resto del código es de mí;
  • El archivo dictionary.txt es el 2019 Collins Scrabble Palabras archivo vinculado en esta respuesta a una pregunta relacionada;
  • La justificación de que una mano con un azulejo en blanco siempre se puede puntaje es en @DenisS la respuesta (if '*' in letters: return True en mi código);
  • La idea básica del algoritmo es el uso de un Monte-Carlo método, debido a que la navegación por el diccionario es aceptable, pero probando todas las posibles combinaciones de la mano no es razonable.

91592097 en 16007560800 que es de aproximadamente 0.572% (o 1 en 175).


Algunos de lo que sigue es cubierto ya en @DenisS's respuesta y he usado el mismo diccionario de palabras (Collins Scrabble Palabras (2019)) para facilitar la comparación. Nota, en particular, en esa respuesta el argumento para desestimar los espacios en blanco cuando se busca combinaciones válidas sin palabras (es decir, que la única carta no en una carta del 2 de palabra es una V y los que hay no son suficientes para llenar nuestro 7 azulejos seleccionados) y de las discusiones sobre la poda.

El siguiente método es bastante "rápido y sucio" y se basa en varias herramientas que están disponibles en múltiples plataformas.

En primer lugar, tomé el diccionario y alphabetised las letras en cada palabra. (He quitado los duplicados, causado por las palabras que fueron los anagramas de cada uno de los otros, aunque esto no era necesario. Esto resultó en un diccionario que contiene 247491 palabras.)

La carta del 2 de palabras (93 único alphabetised palabras) fueron retirados y el diccionario de podar de modo que ya no contenía ninguna de las palabras que contiene todas las letras de una de esas palabras. (Por ejemplo, la palabra AE quitado las palabras de la lista incluyendo aquellos en los que las letras eran adyacentes, tales como AESSSY y donde no estaban adyacentes AABCELN).

Esto fue hecho como una simple iteración a través de la 2 de la carta de las palabras en bash uso de grep con algún parámetro de shell expansiones.

for f in $(cat 2LetterWords) ; do grep -v ${f:0:1}".*"${f:1:1} temp > a; rm temp; mv a temp; done

Las 3 de la carta de las palabras (61 único alphabetised palabras) fueron extraídos y el nuevo diccionario de poda en una manera similar. 4 de la carta de las palabras (15) y 5 de la carta de las palabras (4) del mismo modo fueron extraídos. En cada etapa, el puñado de palabras del diccionario que no podía ser formado sin el uso de espacios en blanco también fueron eliminados.

Como todas las otras palabras en el diccionario contienen las letras que nos permiten hacer uno de estos 2 a 5 de la carta de las palabras, estos son los únicos que la necesidad de considerar. I. e. sólo necesitamos encontrar las combinaciones de 7 de azulejos donde no podemos hacer cualquiera de los siguientes 173 palabras:

AA AB AD AE AF AG AH AI AJ AK AL AM UN AP AR COMO EN AW AX AY AZ SER BI BO POR CH DE DI ¿ EE EF EH EL EM EN EO EP ER ES ET EW EX EY EZ FI FO El año FISCAL GI IR GU HOLA HM HO HS HU IK IL IM EN IO IP IQ ES ES IX JO KO KY LO MM MO MU MI NO NU NY OO OP O OS OT OU El UJO de BUEY OY OZ PU RU ST SU TU UX UY ACO ACV AOV AQU AUV AVV BBU BCU El comandante general BFU BRR CDU CEI CEU CIUDAD CLY CMW LLORAR CUZ DDU DFU DJU DLU SECO DUW HUEVO EGK EGV EIV EJU EKU La GRIPE GPY GRR GTY HNT HPT HPY HRY HTY HWY IIW IJZ IRZ IVY IWZ LPY LSY LUU LUV LUZ LVY NPW Haga PALANCA PSY PTW PXY RTY La PISTA SWY UWZ BKLU BLLU CFFU CFKU CKLU CLLU DKUU FFPT IRRY JKUU KUUZ LLLU LLUW PPTY PTYY CCIIV CIIRR GHLLY LLXYY

Hay 16,007,560,800 (100 ° C 7) combinaciones de azulejos que podemos elegir, aunque algunas de estas combinaciones serán indistinguibles unos de otros. Si solo tenemos en cuenta el número de combinaciones que se pueden distinguir estamos reducidos a 3,199,724 que es mucho más manejable valor y, de cualquier distinguibles combinación podemos calcular fácilmente el número de combinaciones diferentes de azulejos que son indistinguibles.

Ese valor puede ser calculado utilizando algunos métodos de fuerza bruta. Un montón de bucles anidados en C, tales como

for (A=0;A<=anMax[0];A++) 
for (B=0;B<=anMax[1];B++) 
for (C=0;C<=anMax[2];C++)
for (D=0;D<=anMax[3];D++)
…

donde la anMax array (offset 0) se establece que el número de fichas por cada carta de luchas, pero un par de corto-circuito de comprobaciones para asegurar que no vaya a más el número necesario de las baldosas

…
for (C=0;C<=anMax[2];C++) if (A+B+C<8)
…

es suficiente para ejecutar el cálculo en un par de segundos. (Mi primer intento, la adición de controles espaciados en el C, E, G, L, O, S y W era lo suficientemente bueno.)

Un poco más de shell scripting en awk, tales como:

awk '{print (substr($0,1,1)" && "substr($0,2,2)") ||"}' 2LetterWords   

con un poco de edición (a cuenta de repetir letras), por ejemplo, (para los dos letra)

if (
    (A>1) || (A && B) || (A && D) || (A && E) || (A && F) || (A && G) || (A && H) || (A && I) || (A && J) || (A && K) || (A && L) || (A && M) || (A && N) ||
    (A && P) || (A && R) || (A && S) || (A && T) || (A && W) || (A && X) || (A && Y) || (A && Z) || (B && E) || (B && I) || (B && O) || (B && Y) || (C && H) ||
    (D && E) || (D && I) || (D && O) || (E>1) || (E && F) || (E && H) || (E && L) || (E && M) || (E && N) || (E && O) || (E && P) || (E && R) || (E && S) ||
    (E && T) || (E && W) || (E && X) || (E && Y) || (E && Z) || (F && I) || (F && O) || (F && Y) || (G && I) || (G && O) || (G && U) || (H && I) || (H && M) ||
    (H && O) || (H && S) || (H && U) || (I && K) || (I && L) || (I && M) || (I && N) || (I && O) || (I && P) || (I && Q) || (I && S) || (I && T) || (I && X) ||
    (J && O) || (K && O) || (K && Y) || (L && O) || (M>1) || (M && O) || (M && U) || (M && Y) || (N && O) || (N && U) || (N && Y) || (O>1) || (O && P) ||
    (O && R) || (O && S) || (O && T) || (O && U) || (O && W) || (O && X) || (O && Y) || (O && Z) || (P && U) || (R && U) || (S && T) || (S && U) || (T && U) ||
    (U && X) || (U && Y)
   ) return 0;

dio algunas condicional simple controles para garantizar la lista de palabras no aparecen.

Hay 309831 distinguibles combinaciones donde ninguno de los 2-letra de las palabras que pueden formarse. 252242 si nos aseguramos de 2 y 3 de la carta de las palabras no puede ser formado. 251180 excluyendo 2,3 y 4 de la carta de las palabras y abajo para 251021 exclusión de la lista completa.

No podemos simplemente mirar 251021 / 3199724 como nuestro probabilidad como diferentes distinguibles combinaciones tienen diferentes números de pieza correspondiente combinaciones. El distinguibles combinaciones de exclusión de la lista de palabras tienden a utilizar las más raras de las baldosas, que significa que tienden a tener menor número de pieza correspondiente combinaciones.

Podemos contar el número de combinaciones que corresponden a un determinado distinguibles combinación mirando el número de maneras en las correspondientes letras podrían haber sido elegido, el cual se calcula como:

Cr(0,A)* nCr(1,B)* nCr(2,C)* nCr(3,D)* nCr(4,E)* nCr(5,F)* nCr(6,G)* nCr(7,H)* nCr(8,I)* nCr(9,J)*
nCr(10,K)* nCr(11,L)* nCr(12,M)* nCr(13,N)* nCr(14,O)* nCr(15,P)* nCr(16,Q)* nCr(17,R)* nCr(18,S)*
nCr(19,T)* nCr(20,U)* nCr(21,V)* nCr(22,W)* nCr(23,X)* nCr(24,Y)* nCr(25,Z)

Esto nos da 91,592,097 combinaciones (de los que hay 251,021 distinguibles conjuntos) de 16,007,560,800.

Voy a hacer una estimación a partir de la siguiente hipótesis:

Cualquier mano que contiene al menos una vocal, y, o un espacio en blanco que permite un movimiento válido. Cualquier mano que contiene completamente consonantes no. Obviamente hay excepciones, pero deben ser suficientemente raro como para tener un efecto insignificante (y el número de falsos positivos y falsos negativos trabajo a cancelar a la otra).

Hay 46 de estos azulejos y 54 que no lo son. La posibilidad de que de forma consecutiva dibujo 7 consonantes es por lo tanto:

54/100 * 53/99 * 52/98 * 51/97 * 50/96 * 49/95 * 48/94

Esto funciona en el 1,11%, o alrededor de 1 en 90 juegos.