Solitario de rayas VIII: Record con 110 rayas

Usando el primer acotador, tras 2,1 días de CPU, y buceando hasta el nivel 134 del árbol binario, se ha encontrado este bicho con 110 rayas:

Se exploraron 10.201.449.392 vértices, se llamó al acotador 1.886.323.606 veces, y se podaron 1.459.117.650 ramas. La posición de esta figura en el árbol es 1111111111 1111111111 1111111111 0111111011 1110110111...; es decir, apenas se ha avanzado, tras dos días de CPU sigue en el bit 44 (42 efectivos), luego a este ritmo puede tardar unos 25.300 millones de años en acabar. Antes parecía que iba a bastar con la edad del universo, pero esto está empeorando.

Solitario de rayas VII: El primer acotador

Tengo que empezar admitiendo que medio he hecho trampas al poner este título; en realidad, ya he probado el primer acotador, así que ahora ya sé que habrá (al menos) un segundo acotador.

La idea es simple; este acotador funcionará en dos etapas:

1. añadir todos los puntos que se pueda.
2. averiguar el número máximo de rectas que pueden cubrir los puntos.

Ese "todos los puntos que se pueda" se complica un poquito. En realidad, el criterio que usa este acotador no es para añadir puntos, sino para añadir rayas; lo que pasa es que en cuanto decida añadir una raya, se va a olvidar de ella y va a añadir sus puntos. Éste es el criterio exacto:

1. Las rayas añadidas no pueden "pisar" las rayas que había puestas antes de llamar al acotador (sí pueden pisar las rayas puestas por el acotador)
2. Si la raya que se va a añadir tenía exactamente cuatro puntos marcados anteriormente, ninguno de estos puntos puede satisfacer:
   1. haber sido añadido por el acotador;
   2. tener todos sus enlaces usados en la dirección de la raya (en cualquiera de los dos sentidos);
   3. y tener al menos uno de esos enlaces pisado por la raya.

Como siempre, un ejemplo dejará claro qué quiere decir esto. Imaginemos que tenemos que acotar el número de rayas que se pueden añadir a esta figura:

Podríamos añadir una raya que cogiese el punto de la derecha, o otra que cogiese el de la izquierda, pero no ambas rayas. Bueno, pues este acotador en realidad no recuerda si ha añadido una raya o no, lo que ve es que podría añadir cualquiera de ellas, y va a añadir los dos puntos.

Hay que aclarar una cosa; si vemos sólo los puntos, ahora parecería que podríamos añadir dos rayas más, y luego otras dos, y luego otras dos... pero claro, esto haría que añadiésemos infinitos puntos, y no sería muy útil que nuestro acotador dijera siempre "como mucho puedes añadir infinitas rayas". Así que el acotador tiene que recordar cuándo no debe continuar añadiendo puntos. El criterio retorcido de arriba impide esto (si fuésemos a añadir una nueva raya, nos encontraríamos con que tendría 4 puntos marcados previamente y los puntos ahora en los extremos habrían sido añadidos por el acotador, tendrían su único enlace usado en la misma dirección de la nueva raya, y este enlace sería pisado por la nueva raya).

Entonces viene la segunda etapa del acotador. Tenemos seis puntos en fila; ¿cuántas rayas puede haber ahí? Obviamente, sólo una. Para poder poner dos rayas tendría que haber 9 puntos en fila.

Y ya hemos acabado; la cota es uno.

Lo bonito de este algoritmo es que hemos acotado el número de rayas que podemos añadir sin haber decidido qué rayas añadir. Lo malo es que a veces esta estimación va a ser muy mala. Veamos un ejemplo en que el acotador nos cuela una raya de propina; empezamos con esta figura:

El primer punto que añadiremos será S; de hecho, podemos hacerlo de dos formas, uniendo P-R o Y-N. Supongamos que unimos los puntos P-R, y por tanto el acotador recuerda (por el criterio) que no puede continuar añadiendo puntos en esa dirección, así que, de momento, U no se puede añadir.

Una vez hemos añadido S, resulta que podemos añadir T, uniendo Z-S.

Y sorpresa, ahora el criterio nos deja añadir U, porque resulta que ahora no todos los enlaces usados de S están en la misma dirección. Es decir; mientras conocíamos una única forma de llegar a S, el criterio nos impedía continuar en esa dirección; pero una vez hemos llegado a S en dos direcciones (desde N y R), como no se puede saber cual es "la primera", tenemos que dejar continuar en las dos direcciones.

Total, estamos en que el acotador ha descubierto que puede llegar a los puntos S, T y U. Esto es correcto, salvo por el detalle de que por las incompatibilidades entre rayas, se puede añadir o bien T o bien U, pero no ambos. Da igual, este acotador no recuerda incompatibilidades entre rayas. Así que a continuación decide que también puede añadir X; lo único que hay que hacer es añadir la raya T-X. Lo cual es falso...

Y entonces el acotador llega a su segunda etapa; estos son los puntos alcanzables:

que pueden albergar como mucho tres rayas; una horizontal (que se podría escoger de dos formas), una vertical, y una diagonal (que se podría escoger de dos formas). De forma que el acotador dirá que se pueden añadir como mucho 3 rayas cuando, en realidad, el máximo son dos rayas.

¿Es esto muy malo? Bueno, ya sabemos que un acotador rápido no puede ser muy preciso, así que si este acotado nos clavase sólo una raya de más estaríamos muy contentos. El problema es que una vez que empieza a añadir rayas incorrectamente se desboca y acaba añadiendo infinitas rayas incorrectas. Veamos un ejemplo "real"; empezamos con esta figura:

         *        *         
         |\      /|         
         | \    / |         
      *--#--#--#--#         
         |   \/   |         
         |   /\   |         
         #  *  *  #         
         | /    \ |         
         |/      \|         
         #        #         
        /|        |\        
       / |        | \       
#  #  #  #        #  #  #  #
                            
                            
#                          #
                            
                            
#                          #
                            
                            
#  #  #  #        #  #  #  #
                            
                            
         #        #         
                            
                            
         #        #         
                            
                            
         #  #  #  #         

(Perdón por volver a los gráficos en ASCII, pero es que la salida del acotador no la preparado para matlab...)

Vale, el acotador hace una primera pasada y encuentra que podría añadir 37 puntos:

            B        B            
            |\      /|            
            | \    / |            
         B--#--#--#--#            
            | / \/ \ |            
            |/  /\  \|            
         @--#--B--B--#--@         
           /| /    \ |\           
          / |/      \| \          
   @     B  #        #  B     @   
   |    /  /|        |\  \    |   
   |   /  / |        | \  \   |   
@--#--#--#--#--B--B--#--#--#--#--B
   | /                      \ | / 
   |/                        \|/  
   #                          #   
  /|                         /|\  
 / |                        / | \ 
@  #        @        B--B--B--#--B
   |\       |        |    /  /|   
   | \      |        |   /  / |   
@--#--#--#--#--B--B--#--#--#--#--@
   |   \    |     |  | /  /   |   
   |    \   |     |  |/  /    |   
   @     B--#--B--B--#--B--B--B--@
          \ |     | /| /          
           \|     |/ |/           
            #     B  #            
            |\   /| /|            
            | \ / |/ |            
         @--#--#--#--#--@         
            | / \/|  |            
            |/  /\|  |            
         @--B--B--B--B--@         

Pero claro, una vez ha añadido estos puntos, podría usarlos para añadir nuevas rectas; en la segunda pasada, el acotador cree que puede añadir estos 132 puntos:

            B  B  @  B  B               
            |\/|\  \/|\/|               
            |/\| \ /\|/\|               
            B--#--#--#--#  @            
           /|  |\/ \/|\/|\ |            
          / |  |/\ /\|/\| \|            
   B--B--B--B--#--B--B--#--B--B  B  B  @
    \ | /   |\/|\/ \/|\/|\/|\/| /| /| / 
     \|/    |/\|/\ /\|/\|/\|/\|/ |/ |/  
@     B--B--B--#--B--B--#--B--B--B--B--B
 \   /|\ |\/|\/|\/|\/|\/|\/|\/|\/| /| / 
  \ / | \|/\|/\|/\|/\|/\|/\|/\|/\|/ |/  
@--B--#--#--#--#--B--B--#--#--#--#--B--B
  / \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/| / 
 /   \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/  
B--B--#--B--B--B--B--B--B--B--B--#--B--B
 \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/| /|
  \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/ |
B--B--#--B--B--B--B--B--B--B--B--#--B--B
 \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
  \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--#--#--#--#--B--B--#--#--#--#--B--B
 \/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
 /\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--B--B--B--#--B--B--#--B--B--B--B--B
|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--B--B--B--#--B--B--#--B--B--B--B--B
| /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\ |
|/ |/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\| \|
B--B--B--B--B--#--#--#--#--B--B--B--B--B
| /| /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\ |\ |
|/ |/ |/\|/\|/\|/\|/\|/\|/\|/\|/\| \| \|
B--B--B--B--B--B--B--B--B--B--B--B--B--B
| /| /| /|\/|\/|\/|\/|\/|\/|\/|\ |\ |\ |
|/ |/ |/ |/\|/\|/\|/\|/\|/\|/\| \| \| \|
B--B--B--B--B--B--B--B--B--B--B--B--B--B

La razón por la que esto tiene forma cuadrada es que el acotador busca nuevas rectas dentro de un cuadrado, que va ampliando según sea necesario. Como hace la búsqueda de arriba abajo y de izquierda a derecha, las nuevas rayas aparecen "barridas" hacia abajo a la izquierda. En las siguientes pasadas el cuadrado se va ampliando y las rayas acaban invadiendo todo el plano, así que cuando el acotador cree que puede añadir más de 200 rayas nuevas abandona y en vez de devolver una cota sobre el número de rayas devuelve un -1, que viene a decir "NPI".

Bueno, el que el acotador no acote ocasionalmente no es un problema demasiado grave; simplemente exploraremos ramas del árbol que quizás nos podríamos haber ahorrado. El problema sería que no consiguiese acotar con mucha frecuencia.

¿Pero cómo funciona en la práctica? Continuará...

Solitario de rayas VI: Acotadores

La única esperanza de resolver el problema en un tiempo razonable es que no es necesario explorar todo el árbol, sino que a veces podremos podar algunas de sus ramas.

Por usar un poco de jerga; el algoritmo del que hemos hablado hasta ahora para recorrer todo el árbol (ver primero qué pasa si incluímos una raya, y ver luego qué pasa si la excluímos) es un ejemplo de Backtracking (Wikipedia lo traduce como "Vuelta atrás" pero a mí no me acaba de gustar esta traducción), y ahora queremos cambiarlo a Ramificación y poda, también llamado Ramificación y acotación, o Branch and bound.

Aunque en la Wikipedia lo explican de forma general y abstracta, la idea es sencilla: si tenemos un récord con 200 rayas, estamos en un vértice con 50 rayas, y sabemos que como mucho podremos añadir 50 rayas más, entonces no tenemos que explorar la rama que empieza en ese vértice, porque hagamos lo que hagamos no batiremos el récord. Si podamos muchas ramas y son grandes, podemos ahorrarnos cantidades enormes de trabajo.

El problema está, obviamente, en estimar el número máximo de rayas que se podrán añadir; en la jerga, "acotar el número de rayas".

En muchos problemas hay alguna forma relativamente sencilla de acotar algo; con frecuencia simplemente se calcula una fórmula matemática. En nuestro caso no tenemos tanta suerte; tendremos que usar un programa (una función en realidad) algo complicadillo al que llamaremos acotador.

Un acotador ideal tendría estas dos cualidades:

1. rapidez
2. precisión (la cota proporcionada debería estar muy cerca del máximo)

Desgraciadamente, las dos cosas son mutuamente excluyentes. Un extremo: como sabemos que ninguna figura tendrá más de 966 rayas, podríamos escribir un acotador velocísimo que, sin mirar siquiera a la figura, dijese que como mucho se le pueden añadir 966 rayas, y sería correcto, pero nada preciso, y absolutamente inútil, porque nunca serviría para podar una rama. El otro extremo sería escribir un acotador muy preciso que explorase toda la rama y devolviese el máximo exacto de rayas que se pueden añadir, pero entonces sería absurdamente lento; mucho más lento que usar el programa sin acotador. De hecho, no tiene sentido usar un acotador que dé la respuesta exacta y que sea rápido, porque entonces lo usaríamos directamente para resolver el problema. La gracia está en encontrar un punto medio, una forma fácil de encontrar una cota que pode mucho.

En nuestro caso, las llamadas al acotador costarán bastante tiempo, así que, para empezar, lo usaremos sólo cuando el número de rayas incluidas sea mayor que 20 y múltiplo de cinco. Lo más probable es que en el futuro decidamos cambiar esta condición.

Solitario de rayas V: Simetrías

He modificado el programa para que vaya escribiendo en un fichero el vértice del árbol que está explorando cada vez que explore diez millones de vértices (esto es unos dos o tres minutos). Así puedo interrumpir y rearrancar la búsqueda. Uno podría pensar que esto es necesario por si los apagones, pero no, la experiencia demuestra que el factor limitante aquí son las actualizaciones de Windows: cada semana mi ordenador se tiene que bajar una actualización de seguridad crítica doble rojo fosforito, y luego se reinicia.

El poder empezar a calcular a partir de una figura guardada en disco tiene una importante ventaja, y es que seleccionando varias figuras desde las que empezar podemos recorrer sólo las soluciones realmente diferentes del problema, en vez de recorrer todo el árbol ocho veces a causa de las simetrías.

Por "simetrías" me refiero a dos reflexiones (horizontal y vertical) y una la rotación de 90 grados (rotar 180 grados equivale a reflejar primero horizontalmente y luego verticalmente).

Es decir, estas dos figuras no son iguales entre sí porque no se puede convertir la una en la otra aplicando simetrías

pero estas ocho sí:

porque podemos convertir cualquiera de ellas en las otras aplicando simetrías.

(Por cierto, ¿habrá alguna figura no trivial que bajo una traslación vaya a parar a alguna figura simétrica? Es decir, que permanezca esencialmente invariante bajo una traslación. Es una pregunta tan inútilmente retorcida que lo mismo la pensaré; parte del problema será definir qué significa "no trivial", porque hay figuras así con hasta cuatro rayas.)

La mayoría de las figuras aparecerá por octuplicado, pero algunas figuras tienen alguna simetría (es decir, al aplicarles una de las simetrías caen exactamente sobre sí mismas) y aparecerán cuatro, dos, o incluso una única vez; por ejemplo:

Lo que interesa para ahorrar tiempo es no encontrar ocho veces las figuras que no tienen ninguna simetría; parece razonable pensar que las figuras con alguna simetría serán una minoría minúscula, y por tanto no nos preocuparemos de ellas.

¿Qué tiene todo que ver con leer de un fichero en el disco duro la posición desde la que se debe continuar la búsqueda? Bueno, imaginemos que queremos buscar algo en todas las figuras que tienen exactamente una de las ocho rayas de la izquierda (se ven sólo "cuatro rayas largas" porque las ocho se solapan a pares). Entonces arrancaríamos el programa empezando desde la posición de la izquierda, en la que la raya verde estaría incluida y las seis rayas negras estarían excluidas, es decir, en la lista de rayas que no se deben incluir:

Cualquier figura que tenga exactamente una de las ocho rayas podrá ser rotada y reflajada de una única manera para coincidir con estas condiciones. No es necesario indicar que la última raya (arriba a la derecha) no debe ser incluida, porque al tener que incluir la de la izquierda ya lo impedimos.

Esto funciona muy bien para el caso en que haya una única raya de esas ocho, ¿pero qué ocurre si hay dos o más, o ninguna? Me equivoqué al decir que debería ser fácil evitar todas las figuras duplicadas, porque los otros casos han resultado ser complicadillos, y hay que empezar a subdividirlos.

Es decir: el problema general, buscar en todas las figuras, primero lo dividimos en cinco casos, y cada uno de estos casos lo subdividimos en los subcasos que sean necesarios:

1. Las figuras que tienen exactamente una de las ocho rayas. Es el caso bonito, analizado arriba, y sólo requiere un subcaso sin simetrías.
2. Las figuras que no tienen ninguna de las ocho rayas. Tiene un subcaso muy trivial en el que no ganamos nada porque todas sus figuras siguen apareciendo por octuplicado.
3. Las figuras que tienen exactamente dos de las ocho rayas. Tiene cinco subcasos, cuatro de ellos con simetrías, mencionados más abajo.
4. Las figuras que tienen exactamente tres de las ocho rayas. Tiene tres subcasos sin simetrías.
5. Las figuras que tienen exactamente cuatro de las ocho rayas. Tiene cuatro subcasos, uno con una simetría y otro con dos.

(No es posible tener más de cuatro de esas rayas porque cada vez que incluimos una, excluimos otra.)

Por ejemplo, el caso en que haya exactamente dos de esas ocho rayas puede ser subvidivido ineficientemente en estos cinco subcasos, de los que cuatro tienen simetrías (indico en azul el eje de simetría):

Obviamente, es malo que los subcasos que vayamos a usar tengan simetrías, porque permitirán que algunas figuras encajen en ellas de varias maneras.

Una forma de arreglar esto sería dividir estos subcasos con simetrías en más sub-subcasos, pero de todas formas no nos acabamos de librar de las simetrías.

¿Es esto muy malo? He echado unas cuentas suponiendo que la probabilidad de que aparezca una línea en un par de líneas solapadas es 1/3, y la probabilidad de que no aparezca ninguna es 1/3. Esto es muy discutible, pero como he construido los casos usando las primeras líneas, que "normalmente se ponen", no parece del todo equivocado. Me sale esta tabla, donde "m" se refiere al trabajo mínimo, es decir, el número de vértices que se explorarían si se evitasen todas las epeticiones:

número de casos	trabajo total	trabajo repetido
1 caso	m * 8	m * 7
14 casos	m * 1,4321	m * 0,4321
36 casos	m * 1,1728	m * 0,1728
93 casos	m * 1,0795	m * 0,0795
235 casos	m * 1,0387	m * 0,0387
579 casos	m * 1,0192	m * 0,0192

Uf. Bueno, a pesar de sean números aproximados, sugieren que el trabajo duplicado es proporcional al logaritmo del número de casos dividido entre el número de casos.

No me veo arrancando un programa 579 veces para ahorrarme un 2% de trabajo, hay algo contradictorio en esta frase. De repente, la opción de dejar que el ordenador trabaje por octuplicado no parece tan mala. A menos que aparezcan cientos de voluntarios pidiendo ramas para buscar en paralelo, me parece que intentaré dividir el problema en 14 casos, y ya está.

Quizás las cosas no tengan que ser tan complicadas; yo he examinado los casos a partir de esas ocho rayas iniciales, pero ¿sería posible escoger otras rayas que hiciesen más fácil el análisis? Quién sabe; yo las he buscado y no las he encontrado. Por feo que parezca todo esto, me temo que es lo que hay.

Solitario de rayas IV: Record de 17 puntos

Hace una semana que no escribo ninguna entrada, así que lo mismo empieza a parecer que he abandonado el problema. ¡En absoluto! Es simplemente que me he entretenido jugando en vez de escribir. Como prueba exhibo este espécimen capturado por uno de mis programas exploradores, que en una inmersión de 12 horas descendió a las profundidades abisales de un árbol binario de 121 niveles buscando un ejemplar cuya distancia entre cuernos superase el record anterior de 16 puntos.