Árbol del juego

Los árboles de juego representan una estructura fundamental para la conceptualización de estrategias en juegos como el ajedrez. Esta herramienta estratégica se originó por primera vez en el siglo XIX, atribuyéndose a Charles Babbage las primeras incursiones matemáticas en este campo [Monnens, 2013]. No obstante, es a Von Neumann a quien generalmente se le concede el crédito por la creación de este concepto [v. Neumann, 1928]. A pesar de ello, el primer análisis riguroso de los juegos competitivos utilizando este método fue desarrollado por Emilie Borel [Borel, 1921]. En su trabajo, Von Neumann demostró el teorema minimax (que se explicará en detalle en la siguiente sección), sugiriendo que en teoría, uno podría identificar la mejor jugada en una posición de ajedrez utilizando este enfoque.

El concepto principal que subyace en el árbol de juego es el análisis exhaustivo de todas las posibles jugadas desde una posición dada, y a su vez, de todas las respuestas posibles del oponente en cada una de las posibles nuevas posiciones resultantes. Este proceso iterativo se repite hasta alcanzar un estado final para cada una de las ramificaciones. Una vez construido este árbol de juego, es necesario recorrerlo de manera específica para determinar la jugada más óptima en cada una de las posiciones; para ello, se empleará el algoritmo minimax.

A continuación, se presenta un ejemplo ilustrativo de un árbol de juego. Esta representación será notablemente similar a la de una partida de ajedrez real, lo cual no es coincidencia, ya que el árbol de juego es, en esencia, una simulación de una partida que toma en consideración todos los movimientos posibles.

En este escenario, sólo se consideran tres movimientos potenciales de las blancas, aunque en realidad existen más opciones, como Rf2, Da2, Cf7, entre otros. De las tres movidas blancas, sólo se continúa con Dg8, mientras que las otras dos jugadas permiten diversas respuestas por parte de las negras. En contraposición, frente a Dg8, las negras deben responder de manera forzada con Txg8 (capturando a la dama), y las blancas a su vez responderán con Cf7, lo cual resulta en jaque mate al rey negro (las negras no disponen de un movimiento que alivie al rey del ataque), otorgando la victoria a las blancas.

La generación de este árbol sigue un procedimiento semejante al Backtracking presentado en el primer capítulo. En cada posición, se enumeran todas las posiciones resultantes posibles y se continua recursivamente con el mismo proceso hasta llegar a un estado final. Debido a la similitud con el Backtracking, este método comparte el problema del crecimiento exponencial de las posiciones a revisar. En el ajedrez, este crecimiento es particularmente acentuado dada la alta cantidad de movimientos posibles desde una determinada posición. Por ejemplo, en la posición inicial, las blancas pueden ejecutar 20 movimientos distintos y esta cifra puede aumentar aún más en el mediojuego o apertura. Sin embargo, existen posiciones donde solo es posible un movimiento (jugada forzada). Debido a estas variaciones, el cálculo de la complejidad del árbol de juego del ajedrez resulta altamente complejo. Afortunadamente, el célebre matemático Shannon llevó a cabo este cálculo por nosotros, proporcionando una estimación del número de posiciones en el árbol de juego (el número de Shannon) y del número de partidas diferentes de ajedrez, ambos íntimamente relacionados.

Según Shannon, el número $10^{120}$ representa una cota inferior para el número de posiciones distintas en el ajedrez (es decir, el número de posiciones podría ser aún mayor, pero no menor que este límite). Respecto a la cota inferior del número de partidas de ajedrez, se estima en torno a $900^{40}$, suponiendo que hay treinta movimientos posibles por cada posición y que cada turno implica un movimiento por bando, es decir $30*30=900$, asumiendo también que la duración media de una partida es de 40 movimientos, obteniendo el resultado anterior [Claude E. Shannon, 1950].

Al tener en cuenta la complejidad de este problema, queda claro que es inviable generar el árbol de juego completo, por lo que se recurre al uso de estimaciones o heurísticas. Estas heurísticas indicarán qué tan favorable es un estado, permitiendo que solo sea necesario generar una fracción reducida del árbol de juego.

Además, para que el árbol de juego ofrezca información útil, es necesario recorrerlo de una manera específica. El algoritmo que se utilizará para este propósito es el minimax, junto con su versión mejorada con la poda alfa-beta. Estos conceptos se tratarán en las siguientes secciones.