Parte III · Lo incierto
La matemática del Rummikub
Se construye sobre: Probabilidad, Optimización
El Rummikub parece un juego tranquilo: fichas de colores, un atril, alguien que se demora demasiado pensando. Pero cada turno esconde un problema matemático serio. Con las fichas que tengo, ¿cuál es la mejor manera de bajarlas? ¿Me alcanza para abrir? ¿Conviene jugar ya o robar y esperar? Detrás de esas preguntas hay conteo, probabilidad y optimización, y una de ellas fue un problema de investigación hasta hace pocos años.
Las reglas, en números
El juego lo inventó Ephraim Hertzano, un rumano judío que se fue a vivir a Israel y vendía él mismo los primeros juegos. Las fuentes no se ponen de acuerdo en el año, pero coinciden en que lo armó a mitad del siglo XX inspirado en los juegos de cartas tipo rummy, y que la empresa que montó con su familia lo convirtió en un éxito mundial. En 1980 ganó el Spiel des Jahres, el premio alemán al juego de mesa del año.

Las piezas son 106 fichas: los números del 1 al 13 en cuatro colores, con dos copias de cada una (eso da ), y dos comodines. Cada jugador empieza con 14. En la mesa solo se pueden poner dos clases de jugadas, siempre de al menos tres fichas:
- un grupo: el mismo número en colores distintos, como 7 rojo, 7 azul y 7 negro (tres o cuatro fichas, porque solo hay cuatro colores);
- una escalera: números seguidos del mismo color, como 4, 5 y 6 amarillos. El 13 no da la vuelta al 1.

La primera vez que bajas tienes que sumar al menos 30 puntos solo con fichas tuyas; el comodín vale lo que represente. A eso se le llama abrir. Después puedes reorganizar libremente lo que hay en la mesa, siempre que al final del turno todo quede formando jugadas válidas. Gana quien vacía primero el atril, y a los demás se les descuenta lo que les quedó; un comodín atrapado cuesta 30.
Contar las manos
¿Cuántas manos iniciales distintas hay? Depende de qué cuentes como distinto. Si cada una de las 106 fichas fuera única, el número de maneras de recibir 14 es un coeficiente binomial:
Pero las dos copias del 7 rojo son idénticas: a nadie le importa cuál de los dos le tocó. Si cuento las manos como las ve el jugador, de cada uno de los 52 tipos de ficha puedo tener cero, una o dos. Hay un truco precioso para contar eso: multiplicar 52 veces el polinomio . Cada factor es un tipo de ficha, y el exponente que escoges de cada uno es cuántas copias tienes. Al multiplicar, el coeficiente de cuenta todas las maneras de que esas cantidades sumen 14:
Son unos 37 billones de manos distintas sin comodín. Ninguna persona va a ver dos veces la misma en su vida, a menos que juegue mucho más de lo razonable.
Los comodines merecen su propia cuenta, porque cambian el juego. Recibir ninguno es elegir las 14 fichas entre las 104 numeradas; dos, es recibir los dos y 12 más:
Lo que queda, un 23,1 %, es la probabilidad de empezar con exactamente uno. Una de cada cuatro manos trae al menos un comodín.
Cuántas jugadas existen
Antes de buscar la mejor manera de bajar, conviene saber entre qué se escoge. Los grupos son fáciles: para cada uno de los 13 números hay cuatro maneras de escoger tres colores y una de usar los cuatro, así que son .
Las escaleras parecen muchas más, pero aquí aparece una observación que simplifica todo: nunca hace falta una escalera de más de cinco fichas. Una de seis se parte en dos de tres; una de siete, en una de tres y una de cuatro; en general, cualquier escalera de seis o más se puede cortar en dos que siguen siendo válidas. Para saber qué se puede bajar basta con escaleras de 3, 4 y 5. De cada color hay 11 de tres, 10 de cuatro y 9 de cinco: 30 por color, 120 en total. Con los grupos, el menú completo es de 185 jugadas básicas. Cualquier mesa de Rummikub, por enredada que se vea, es una combinación de ellas.

El problema de cada turno
Ahora sí, la pregunta central. Te doy un montón de fichas (las de tu atril, o las de tu atril más todas las de la mesa, si ya abriste): ¿cuál es la mayor cantidad de puntos que puedes formar con jugadas válidas? Si la respuesta usa todas las fichas, ganaste.
La fuerza bruta es desesperante. Cada ficha puede ir a una escalera, a un grupo o quedarse en el atril, así que con fichas hay del orden de repartos que revisar. Con 14 fichas son unos cinco millones, todavía manejable; con las 40 que puede haber entre la mesa y el atril a mitad de partida, son unos 12 trillones: un número de veinte cifras.
En 2006, Dick den Hertog y Paul Hulshof, en Tilburg, lo plantearon como un problema de programación entera. La traducción es natural: una variable por cada jugada posible, que dice cuántas veces la pones (0, 1 o 2, porque hay dos copias de cada ficha). Si vale 1 cuando la jugada usa la ficha , son los puntos de la jugada y cuántas fichas de tipo tienes:
Es la panadería otra vez, con 185 productos en lugar de dos y fichas en lugar de horno y queso. Con eso, cualquier programa de optimización entera encuentra la mejor jugada. Pero la programación entera, como vimos, es la familia de los problemas difíciles, y los autores advertían que el número de combinaciones era enorme. Quedaba la duda: ¿el Rummikub es de verdad difícil, o solo estaba disfrazado?
Ir número por número
La respuesta llegó en 2015, de Jan van Rijn, Frank Takes y Jonathan Vis, en la Universidad de Leiden. Es programación dinámica, y la idea es recorrer las fichas no de a una sino por números: primero todos los 1, después todos los 2, y así hasta el 13.
Al llegar a un número, cada ficha de ese valor tiene tres destinos: continuar una escalera de su color, entrar en un grupo con fichas del mismo número o quedarse en el atril. Los grupos se deciden ahí mismo, porque solo involucran ese número. Lo único que hay que recordar del pasado son las escaleras que vienen en camino. Y aquí está el detalle bonito: de una escalera en construcción no importa qué números trae, solo cuántas fichas lleva, y ni siquiera eso del todo. Basta distinguir si lleva 0, 1, 2, o 3 o más. Con tres o más ya es válida y cada ficha nueva solo suma su valor; con menos, todavía necesita crecer para contar.
Como hay dos copias de cada ficha, cada color puede tener a lo sumo dos escaleras abiertas a la vez. Las parejas posibles de longitudes, sin importar el orden, son : diez. Con cuatro colores, el estado completo al llegar a un número es uno de , y con 13 números, el problema entero tiene menos de 130.000 estados. Cada uno se resuelve una sola vez y se guarda. Lo que la fuerza bruta veía como trillones de repartos, la programación dinámica lo ve como una tabla que cabe en cualquier celular.
El resultado formal es que, con cuatro colores y dos copias fijos, el tiempo crece de forma lineal con la cantidad de números: el problema está en P, en el sentido de algoritmos y complejidad. También crece de forma polinomial con el número de copias. El único parámetro que el método no domestica es el número de colores, porque el estado se multiplica por diez con cada color nuevo. Si un Rummikub con cientos de colores es NP-difícil o no, los autores lo dejaron como pregunta abierta.
Juega con una mano
El interactivo usa una búsqueda parecida, más fácil de escribir que la de Leiden: toma la ficha más baja que quede, prueba dejarla en el atril o meterla en cada jugada posible que la contenga (rellenando huecos con comodines, si hay), y guarda cada situación ya resuelta para no repetirla. Para manos de jugador es instantánea.
Tu atril (14 fichas)
Lo máximo que puedes bajar
39abre: llega a 30
grupo · 9
escalera · 30
Se quedan en el atril 8 fichas.
La mano con la que arranca no trae comodín, y aun así abre con 39: el grupo de treses y la escalera amarilla 9-10-11. Fíjate en las fichas que se quedan: hay un 9 y un 11 amarillos repetidos que no encuentran pareja. Roba algunas fichas y mira cómo el total se reorganiza; a veces una sola ficha nueva cambia el arreglo completo, porque libera otra para una jugada mejor. Eso es lo que hace difícil jugar a ojo.
¿Qué tan probable es abrir?
Con el solucionador puedo contestar algo que todo jugador se pregunta en los primeros turnos. Repartí 40.000 manos de 14 fichas al azar y resolví cada una. El 49 % puede abrir de entrada: casi la mitad de las veces, el problema del primer turno no es si puedes, sino si quieres mostrar tus fichas tan pronto. El promedio de lo máximo que se puede bajar es de 29 puntos, justo al borde de la regla, lo que hace pensar que el 30 no se escogió al azar.
El comodín lo cambia todo. De las manos sin comodín abre el 34 %. De las que traen uno, el 94 %. Con los dos, todas. Un comodín multiplica casi por tres la probabilidad de abrir, y por eso los buenos jugadores lo cuidan tanto: no es una ficha más, es una ficha que puede ser cualquiera de las 52.
Cada ficha robada ayuda, y la curva se puede medir. Con 2.000 manos simuladas por tamaño:
| Fichas en el atril | Pueden abrir | Puntos máximos (promedio) |
|---|---|---|
| 14 | 49 % | 29 |
| 15 | 58 % | 34 |
| 16 | 64 % | 39 |
| 18 | 77 % | 50 |
| 20 | 87 % | 62 |
| 22 | 93 % | 75 |
| 25 | 98 % | 96 |
Es un experimento, no un cálculo exacto: el porcentaje de cada fila puede moverse un par de puntos si se repite con otras manos. Pero la ley de los grandes números garantiza que con suficientes repeticiones el porcentaje observado se acerca al verdadero, y para decidir cuándo jugar basta con saber que la mitad de las manos abre y que con cuatro fichas robadas ya abren tres de cada cuatro.
Ganar de un solo golpe
La pregunta opuesta es más dramática: ¿qué tan probable es bajar las 14 fichas en la primera jugada? En el mismo trabajo, el grupo de Leiden contó cuántas de las 37 billones de manos sin comodín se pueden bajar completas. Son 10.232.524: una de cada 3,7 millones. En mis 40.000 manos simuladas no salió ninguna, como era de esperar. (Un detalle fino: ese conteo trata igual a todas las manos distintas, pero no todas son igual de probables al repartir, porque una mano con fichas repetidas se puede formar de menos maneras. El orden de magnitud, de todos modos, es ese.)
Su tabla trae una sorpresa. Con 15 fichas, la fracción de manos que se bajan completas es casi el doble que con 14, y también más alta que con 16. Y se repite el patrón: suben un poco en 18, en 21, en 24. La explicación es que todas las jugadas tienen tres fichas o más, así que los múltiplos de tres se pueden partir en tríos sin que sobre nada. Tener más fichas no siempre ayuda a terminar; tener la cantidad justa, sí.
Lo que la matemática no resuelve
Todo lo anterior es el Rummikub como rompecabezas: dadas unas fichas, cuál es la mejor jugada. El juego de verdad es otra cosa. Hay otros jugadores, y cada ficha que bajo les da opciones a ellos para reorganizar la mesa. A veces lo óptimo es no jugar: guardar fichas, robar, esperar a poder bajar todo de un golpe. Eso ya no es optimización sino teoría de juegos con información oculta, y los mismos autores dejaron abierto qué tan difícil es en general.
Me gusta que un juego de sala tenga esta profundidad. En una sola mesa están el conteo con polinomios, la probabilidad de los comodines, la programación entera que usan las aerolíneas, una idea de programación dinámica que vuelve fácil lo que parecía imposible, y una pregunta que todavía nadie ha cerrado. La próxima vez que alguien se demore mucho en su turno, tal vez no esté indeciso. Tal vez esté resolviendo un problema que a los matemáticos les tomó años entender.