Las marchas del rey

Los caminos del rey

En este capítulo se abordará la cuestión de cuántas rutas puede tomar un rey de ajedrez, partiendo de una casilla específica a otra, utilizando el mínimo número de movimientos. Aunque esta pregunta pueda parecer simple a primera vista, se revelará como una indagación más compleja de lo que inicialmente se podría esperar. Como ilustración de ello, consideremos un tablero estándar de ajedrez de 8x8 y estimemos cuántos movimientos se requerirían para llegar a cada casilla desde una posición inicial del rey en la casilla e5.

Al observar la figura, se pueden hacer varias conclusiones interesantes respecto a cuántas rutas existen para llegar a cada casilla. En primer lugar, vale la pena notar que en las casillas adyacentes al rey - ya sea horizontalmente, verticalmente o en diagonal - solo existe una ruta posible para llegar en el número mínimo de movimientos.

Además de las casillas adyacentes, existen otras marcadas con el número uno, lo que indica que sólo existe una forma de llegar a dicha casilla. Estas son las casillas que se encuentran en las diagonales del rey. Dado que para llegar a estas casillas siempre se deben hacer movimientos en diagonal, es coherente que sólo haya una ruta. De manera más general, es observable que cuánto más lejos esté una casilla del rey, mayor será el número de rutas disponibles para llegar a ella.

Otra cuestión interesante a considerar en relación con este tema es el número mínimo de movimientos que el rey necesita realizar para llegar a una casilla específica. Este problema es considerablemente más sencillo que el anterior y puede resolverse mediante una fórmula simple. Sin embargo, tener conocimiento de este número mínimo de movimientos puede proporcionar información muy valiosa para resolver la pregunta original.

Para simplificar la comprensión de este problema, podemos comenzar examinando las casillas más cercanas al rey. Primero, la casilla en la que se encuentra el rey tiene una distancia de cero. Las casillas adyacentes al rey - tanto en sentido horizontal, vertical como diagonal - tendrán una distancia de uno. Con respecto a las demás casillas, aquellas adyacentes a las casillas con una distancia de uno tendrán esa distancia más uno, es decir, una distancia de dos. Al calcular la distancia de las casillas adyacentes a aquellas cuya distancia ya se conoce, será posible determinar todas las distancias. El mapa de distancias de un tablero de 8x8 ilustra la distancia a cada una de las casillas, considerando al rey situado en la misma casilla en un tablero de igual tamaño.

Además de la estrategia mencionada anteriormente, también es posible recurrir a una fórmula directa que, conociendo la posición del rey y las coordenadas de la casilla objetivo, proporciona el número mínimo de movimientos necesarios para que el rey llegue a ella. La fórmula es la siguiente:

$$\max(\abs{r_0-a_0},\abs{r_1-a_1})$$

Donde $r = (r_0,r_1)$ son las coordenadas del rey, donde $r_0$ representa la fila y $r_1$ la columna, y $a = (a_0,a_1)$ las coordenadas de la casilla cuya distancia se busca calcular, con $a_0$ siendo la fila y $a_1$ la columna de dicha casilla. En el caso de las filas la conversión es directa, pero para la columna se deberá usar la conversión en número de la letra. Es decir, la “a” pasará a ser 1, la “b” 2, etcétera.

Es natural preguntarse de dónde proviene esta fórmula y por qué funciona. En primer lugar, se puede comprobar que para el tablero anterior se obtienen los resultados correctos en todas las casillas, lo que sugiere que la fórmula es confiable. Para garantizar su validez, sería necesario realizar una demostración matemática, pero ya que esto excede el alcance de este libro, tendrás que confiar en mi palabra.

La intuición detrás de esta fórmula se basa en la idea de que el rey tarda el mismo tiempo en moverse a una casilla adyacente, incluso si esta se encuentra en diagonal. Esto no sucede con las distancias más comunes, como la distancia euclidiana (Teorema de Pitágoras) o la distancia Manhattan (donde moverse a una casilla adyacente en diagonal tendría un coste de 2). En nuestra fórmula, lo que sucede es que se calcula cuántas filas y columnas de diferencia existen, y dado que el rey puede moverse en diagonal, la distancia resulta ser el valor máximo entre el número de filas y columnas que separan las dos coordenadas. Esta distancia es conocida como la distancia del tablero de ajedrez o Chebyshov.

Retomando el problema principal tras esta breve digresión, es necesario encontrar una fórmula que nos permita calcular cuántas rutas existen para llegar a una casilla en un número mínimo de movimientos. En primer lugar, debemos enfocarnos en una casilla específica, que en este caso será d1. El número de rutas hacia la casilla d1 muestra cuántas rutas existen para llegar a dicha casilla, junto con una observación reveladora.

Las flechas en la figura apuntan a tres casillas adyacentes, y curiosamente, la suma de los valores de estas casillas es igual al valor de la casilla d1. Podría surgir la pregunta: ¿por qué elegir estas tres casillas adyacentes en lugar de las demás casillas adyacentes? Para responder a esta pregunta, sería útil para el lector volver a observar el mapa de distancias.

La casilla e1 está a una distancia de 4 casillas del rey, mientras que las casillas adyacentes analizadas están a una distancia de una unidad menos, es decir, 3. A partir de este escenario, podemos generalizar que el número de rutas hacia una casilla dada será la suma del número de rutas hacia las casillas adyacentes que están a una distancia de una unidad menos. Si el lector es escéptico acerca de esta afirmación, puede proceder a verificarlo en las figuras previamente mostradas.

El cálculo del número de rutas hacia d1 ilustra el proceso de aplicación continua de esta estrategia hasta alcanzar el valor final.

Por lo tanto, para calcular el número de caminos hacia una casilla específica, debemos conocer cuántas rutas existen hacia las casillas adyacentes más cercanas a la casilla de origen. Esto, a su vez, implica que tendríamos que realizar este mismo cálculo para estas casillas adyacentes utilizando las casillas adyacentes a estas, y así sucesivamente hasta llegar a la casilla inicial. En este último caso, para facilitar los cálculos, establecemos que hay una única forma de ir a la casilla inicial desde la propia casilla inicial. Con esta información, podemos definir la siguiente fórmula matemática que permite ejecutar todo el proceso descrito:

$$f(x, k) = \begin{cases} 1 \text{,} & \text{si } x = k \\ \sum_{c \in C_x} f(c, k) \text{,} & \text{si } x \neq k \end{cases}$$

Donde $f(x, k)$ es la función que indica el número de rutas desde la casilla $k$ hasta la casilla $x$ y $C_x$ son todas las casillas adyacentes más cercanas a la casilla $x$. Por lo tanto, la fórmula devolverá 1 si estamos en la casilla inicial y, en caso contrario, calculará el valor sumando los valores obtenidos por las funciones en las casillas adyacentes.

Después de analizar la fórmula, podemos notar que contiene recursividad; la parte superior de la función a trozos correspondería al caso base, mientras que la parte inferior sería el caso recursivo. Al ser una función recursiva, sería relevante analizar el número de llamadas recursivas que serían necesarias en el caso de un tratamiento informático de la función. Volviendo al cálculo del número de rutas, vemos que algunos valores se calculan varias veces, lo que obviamente es una pérdida de tiempo. Respecto a este punto, podemos analizar el número de llamadas recursivas usando la teoría vista en el tema anterior. En el ejemplo analizado anteriormente, pudimos ver que, dependiendo de la casilla, puede haber 1, 2 o 3 llamadas recursivas si no se trata del caso base y, como ya sabemos, hay que escoger el peor caso, donde hay hasta tres llamadas recursivas. Además, debemos tener en cuenta que, en este caso, el tamaño del problema no será el tamaño del tablero, sino la distancia entre la casilla analizada y el rey. A continuación, se muestra la fórmula que da la complejidad del algoritmo.

$$3^{\max(\abs{x_0-k_0},\abs{x_1-k_1})} \in O(3^n)$$

Retomando el problema de las numerosas llamadas recursivas para el número de casillas que procesamos, el lector avispado se dará cuenta de que algunas flechas apuntan a la misma casilla y esto indica que calculamos el valor de la misma casilla varias veces, lo que claramente no es eficiente. ¿No habría alguna forma de evitar esto? La respuesta es sí, cuando se calcula el valor de una casilla, se puede almacenar su valor en un vector o matriz, dependiendo de la situación, para no tener que volver a calcularlo. Este procedimiento se conoce como programación dinámica.

Programación dinámica vs. las marchas del rey

El concepto de “programación dinámica” puede resultar un tanto misterioso a primera vista, y uno podría preguntarse: ¿cuál es el origen de este nombre tan peculiar? La respuesta a esta pregunta es bastante inusual. Richard Bellman, el inventor del término, lo eligió de manera estratégica para evitar que se cancelara su investigación. Consciente de que un nombre atractivo y vago como “programación dinámica” dificultaría cualquier intento de cancelación, optó por esta designación.

Con el origen del nombre aclarado, es momento de explorar la esencia de la programación dinámica y su utilidad en la resolución de problemas. El principal atractivo de la programación dinámica radica en su habilidad para simplificar problemas de alta complejidad, especialmente aquellos con complejidades exponenciales o superiores, y convertirlos en problemas de complejidad polinómica. Esto es posible gracias a una característica fundamental de la programación dinámica: la capacidad de almacenar y reutilizar soluciones parciales ya calculadas, evitando así el costo de recalculaciones innecesarias. A pesar de ser un concepto simple, su eficacia es extraordinaria y tiene aplicaciones significativas en una amplia gama de problemas.

Ahora que hemos examinado el principio fundamental de la programación dinámica, nos adentraremos en un caso práctico para apreciar su eficacia en la reducción del número de llamadas recursivas. Empezaremos con el tablero que se muestra en el tablero inicial de programación dinámica, enfocándonos en la casilla e1, que se ha utilizado anteriormente.

Al examinar el tablero, se nota que todas las casillas tienen un valor de -1. Este valor es un marcador que indica que aún no se ha calculado la distancia a esa casilla. En la primera fase de resolución, nos enfocamos en el cálculo de las diferentes formas en que podemos llegar a la casilla c2.

En esta primera fase, se ha calculado el valor de la casilla c2, que resulta ser 3. Además, se han determinado los valores de todas las casillas necesarias para obtener el valor de c2. Para evitar cálculos redundantes, todos estos valores se almacenan en una matriz, preparándolos para ser reutilizados en futuras operaciones. De hecho, la necesidad de esta práctica ya se ha puesto de manifiesto en esta fase, ya que el valor de la casilla d4 ha sido requerido tanto para el cálculo de la casilla c3 como para la casilla d3.

Tras concluir la primera fase, nos embarcamos en la segunda, donde se calcula el valor de la casilla d2. Este cálculo corresponde a la segunda llamada recursiva requerida para determinar el valor de la casilla d1. El procedimiento de cálculo de esta fase se ilustra en la segunda fase de programación dinámica.

En esta segunda fase, se hace un uso aún más intensivo de los valores ya calculados, especialmente aquellos que se determinaron en la fase anterior, como las casillas d3 y e4.

Por último, llegamos a la fase final, en la que calculamos finalmente el valor de la casilla d1. Este cálculo se puede apreciar en la fase final de programación dinámica.

El proceso de resolución del problema se intensifica aún más en su uso de los valores de las casillas previamente calculadas. En términos generales, a medida que se avanza en el algoritmo, más cálculos se pueden ahorrar. En este punto, hemos conseguido tal eficiencia que ya no es necesario llegar al caso base.

Para resumir todo lo discutido hasta ahora:

El término “programación dinámica” fue acuñado por Richard Bellman como una estrategia para proteger su investigación de posibles cancelaciones. Este método se caracteriza por su capacidad para simplificar problemas de alta complejidad en problemas de complejidad polinómica. Esto se logra mediante el almacenamiento y la reutilización de soluciones parciales ya calculadas para evitar recalculaciones.

En un ejemplo práctico, analizamos cómo se aplicaba la programación dinámica a un tablero de ajedrez. En la primera fase, se calculó el número de formas de llegar a la casilla c2, almacenando los valores de las casillas necesarias para este cálculo. La segunda fase implicó el cálculo de la casilla d2, haciendo uso intensivo de los valores ya determinados en la fase anterior.

Finalmente, en la última fase, se calculó el valor de la casilla d1, destacando la eficiencia de la programación dinámica, ya que se ahorraron más cálculos a medida que se avanzaba en el algoritmo. Este procedimiento resultó tan efectivo que ni siquiera fue necesario llegar al caso base. En esencia, la programación dinámica demuestra ser un enfoque excepcionalmente eficaz y económico para la resolución de problemas complejos.