Optimiza

Optimiza

Chuso, de the Big Bang Blog me puso sobre la pista de un juego de mesa que había inventado y publicado en su blog: Optimiza.

El juego es fácil de explicar y, como bien dice su autor, podría substituir al Sudoku en la sección de pasatiempos de cualquier periódico.

Optimiza

El tablero de juego, que se puede generar aleatoriamente, consiste en una cuadrícula NxN en cuyas casillas aparecen N+1 veces los números 1, 2, 3, … N-1 y una única vez el número N.

Con N=4 tenemos 16 casillas con los números del 1 al 3 repetidos 5 veces cada uno y un único 4.

El juego consiste en desplazar una ficha por el tablero para obtener la máxima puntuación posible al final de la partida. Para ello podremos situar la ficha en cualquier casilla al inicio de la partida y moverla a otras casillas siguiendo estas reglas:

  • Consideramos que el tablero es toroidal. Así pues, cuando la ficha sale por arriba aparece por abajo y cuando desaparece por la derecha aparece por la izquierda.
  • La ficha se debe desplazar tantas posiciones como indique la casilla sobre la que está antes de iniciar el movimiento. Se desplaza en linea recta ya sea horizontal, vertical o diagonalmente.
  • La casilla de destino debe tener un número mayor o igual a la casilla de origen.
  • No se puede pasar dos veces por la misma casilla en una misma partida.

La puntuación final es, sencillamente, la suma de las casillas por las que se ha pasado (que, por cierto, es igual al número de pasos dados + puntuación de la casilla inicial).

El objetivo de este solitario es obtener la máxima puntuación posible.

Observaciones

  • Es bastante interesante el uso de la identidad: (N-1) = N²-1 que aparece a la hora de determinar cuantas casillas de cada tipo hay en el tablero.
  • Con N=4 hay 12108096 (=16!/5!5) maneras diferentes de colocar estos números en una cuadrícula. 1513512 si no contamos las 8 simetrías del cuadrado. Así pues, hay entretenimiento para rato pero un ordenador podría analizarlas todas.
  • Con N=5 hay 7214823415800 (=25!/6!6!6!6!8) (¡sin contar posiciones simétricas!) así que podemos afirmar ya que no nos acabaremos jamás ni siquiera las partidas de este tamaño.
  • En un tablero toroidal es lo mismo moverse X casillas que N-X.
  • El juego tiene un (muy) ligero parecido a 22 Manzanas
  • Técnicamente cada tablero diferente da lugar a un grafo dirigido con pesos en sus vértices sobre el cual se puede desplazar la ficha. Este es el que corresponde al tablero que hay arriba.

Optimiza - Grafo

Variantes

  • Se me antoja difícil identifica correctamente los desplazamientos en diagonal. Una variante sencilla del juego podría admitir tan sólo movimientos horizontales y verticales.
  • Otra opción que puede ser interesante es la de permitir pasar más de una vez por la misma casilla a condición de no repetir jamás una arista. Así, sería legal hacer: H-G-L-H-C, donde se pasa dos veces por H pero donde no se repite ningún paso: (H→G), (G→L), (L→H), (H→C).
  • Por otra parte, es interesante el uso que hace el autor del toro como base para el juego. El juego adquiere una gran simetría gracias a ello (las casillas se vuelven indistinguibles si no tenemos en cuenta los números). Podría usarse una botella de Klein para obtener una variante complicada del mismo sin perder la indistinguibilidad de las casillas.
  • Es sencillo pensar en una variante con varios niveles de dificultad: Se publica en la hoja de pasatiempos un tablero y se dan tres valores: X, Y, y Z. X es el valor que obtiene un algoritmo greedy (por ejemplo: situarse en la casilla cuyo valor es N y ir hacia atrás maximizando la suma obtenida). Y sería un valor un poco más sofisticado (por ejemplo: el resultado de aplicar el greedy a una casilla que no sea la anterior y dé mejor resultado). Finalmente, Z sería el óptimo.
  • También es posible pensar en jugar una variante para dos personas: El jugador A coloca la ficha en cualquier casilla y el jugador B decide quien empieza. Se mueve en turnos alternos siguiendo las reglas antes citadas y el jugador que realiza el último movimiento se queda con los puntos.

BOLAEXTRA: ¿Alguien se anima a pensar un algoritmo eficiente para resolver el problema? Estoy seguro de que tiene que salir, con relativa facilidad, usando programación dinámica hacia atrás: Dado el grafo dirigido empezar con las posiciones finales y ir retrocediendo, actualizando vértices y eliminando ramas hasta obtener el resultado. No he pensado los detalles pero parece claro que esa es la manera más eficiente de hacerlo.

También estaría bien encontrar un greedy que funcione bien y evaluar cuanto se equivoca de media.

Escrito en 26/02/10 10:24 por Carlos Luna en las categorías:

Comentarios

Gravatar.com se ha roto

Gracias mister por esta pedazo entrada sobre el “juego”. Empiezo pidiendote disculpas por el correo que nunca respondí (he querido contestarlo habiéndome leído tus enlaces con detenimiento, pero nunca he encontrado el momento).
Después, paso a hacer una aclaración sobre las reglas: al mover la ficha puedes pasar por una casilla que ya habías utilizado. Lo que no puedes es terminar en una casilla que ya utilizaste como origen en algún momento.
Ahora comentarios varios…
1 – el juego puede tener mil y una variantes y de hecho, Martin Gardner ya escribió sobre una de ellas: El circuito de las flechas:http://thebigbangblog.blogspot.com/2010/02/el-circuito-de-las-flechas.html
2 – Un colega, Luis, ha estado trabajando en encontrar las mejores soluciones a base de fuerza bruta y ha encontrado cosas curiosas como que para N=4, N=6, N=8 parece no haber ninguna colocación de números que permita hacer un recorrido usando todas las casillas.

A ratos estoy trabajando en variantes que le den una vuelta de tuerca. Iré informado.

Gracias otra vez por la currada de la entrada. Un abrazo.

Chuso | 26/02/10 15:08 | #
Gravatar.com se ha roto

Fantástico. Lo anoto porque me parece muy bueno y realmente sería muy divertido entre los pasatiempos del periódico.

Un saludo.
Álex

Calamar | 26/02/10 17:16 | #
Gravatar.com se ha roto

Imagino una variante en un tablero hexagonal, donde aparece 1 ficha N, 2 fichas N-1, 3 fichas N-2, … y los movimientos son en las tres direcciones disponibles.

Marcos | 27/02/10 02:34 | #
Gravatar.com se ha roto

El mejor algoritmo que he encontrado, no polinómico, pero seguramente mejorable es:
f(n, mascara_n)
n indica por qué número voy, y mascara_n de los que tienen valor n, por cuales he pasado ya. Devuelve la máxima suma que puedo conseguir. La recurrencia es elemental.

Resulta ser una programación dinámica parecida a la del TSP si se aplica memoization.

Se debe iniciar el recorrido des de cada casilla, pero como solamente hay n*2^(n+1) estados, podemos decir
por lo menos que el algoritmo es O(n*2^n) para un tablero n*n, es decir factible para n<=20.

A ver si alguien consigue algo más eficiente.
Tal como reduces el problema en el enunciado, consiste en encontrar un Longest Path, problema NP completo. Eso me sugiere que debe replantearse. Lo pensaré.

Enric Sanchez Cusell | 02/03/10 03:35 | #
Gravatar.com se ha roto

@Chuso: Gracias a ti por avisar!

@Marcos: No hay manera de pillarte! Siempre encuentras una variante más que el resto! ;-)

@Enric: Mantenme informado de tus progresos.

Y, por cierto, ¿hay más PDF’s de la Serna por ahí? He intentado encontrarlos a través de su web, pero no me deja rebuscar en subdirectorios y no los encuentro linkados por ninguna parte.

Carlos Luna | 02/03/10 13:24 | #

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)