Hackenbush

Hackenbush es un juego para dos jugadores inventado por el matemático John Horton Conway . ^[1] Se puede jugar en cualquier configuración de segmentos de línea de colores conectados entre sí por sus puntos finales y a una línea de "tierra".

El juego comienza con los jugadores dibujando una línea de "tierra" (convencionalmente, pero no necesariamente, una línea horizontal en la parte inferior del papel u otra área de juego) y varios segmentos de línea de manera que cada segmento de línea esté conectado a tierra, ya sea directamente en un punto final, o indirectamente, a través de una cadena de otros segmentos conectados por puntos finales. Cualquier número de segmentos puede encontrarse en un punto y, por lo tanto, puede haber múltiples caminos hacia tierra.

En su turno, un jugador "corta" (borra) cualquier segmento de línea de su elección. Todo segmento de línea que ya no esté conectado al suelo por ningún camino "cae" (es decir, se borra). De acuerdo con la convención de juego normal de la teoría de juegos combinatorios, el primer jugador que no puede moverse pierde.

Los tableros Hackenbush pueden estar compuestos por un número finito (en el caso de un "tablero finito") o por un número infinito (en el caso de un "tablero infinito") de segmentos de línea. La existencia de un número infinito de segmentos de línea no viola el supuesto de la teoría de juegos de que el juego puede terminarse en una cantidad finita de tiempo, siempre que haya solo un número finito de segmentos de línea que "toquen" directamente el suelo. En un tablero infinito, según la disposición del tablero, el juego puede continuar eternamente, suponiendo que haya un número infinito de puntos que toquen el suelo.

En la versión folclórica original de Hackenbush, cualquier jugador puede cortar cualquier borde: como se trata de un juego imparcial, es relativamente sencillo realizar un análisis completo utilizando el teorema de Sprague-Grundy . Por lo tanto, las versiones de Hackenbush de interés en la teoría de juegos combinatorios son juegos partidistas más complejos , lo que significa que las opciones (movimientos) disponibles para un jugador no necesariamente serían las disponibles para el otro jugador si fuera su turno de mover dada la misma posición. Esto se logra de una de dos maneras:

• Hackenbush original: todos los segmentos de línea son del mismo color y pueden ser cortados por cualquiera de los jugadores. Esto significa que los pagos son simétricos y cada jugador tiene las mismas operaciones según su posición en el tablero (en este caso, la estructura del sorteo). Esto también se llama Hackenbush verde. ^[2]
• Hackenbush azul-rojo : cada segmento de línea está coloreado en rojo o azul. Un jugador (normalmente el primero, o el de la izquierda) solo puede cortar segmentos de línea azules, mientras que el otro jugador (normalmente el segundo, o el de la derecha) solo puede cortar segmentos de línea rojos.
• Hackenbush azul-rojo-verde : cada segmento de línea es de color rojo, azul o verde. Las reglas son las mismas que para el Hackenbush azul-rojo, con la condición adicional de que los segmentos de línea verdes pueden ser cortados por cualquiera de los jugadores.

El Hackenbush Azul-Rojo es simplemente un caso especial del Hackenbush Azul-Rojo-Verde, pero vale la pena mencionarlo por separado, ya que su análisis suele ser mucho más simple. Esto se debe a que el Hackenbush Azul-Rojo es un juego llamado frío , lo que significa, esencialmente, que nunca puede ser una ventaja tener el primer movimiento.

Hackenbush se ha utilizado a menudo como un juego de ejemplo para demostrar las definiciones y conceptos de la teoría de juegos combinatorios , comenzando con su uso en los libros On Numbers and Games y Winning Ways for Your Mathematical Plays de algunos de los fundadores de la disciplina. En particular, el Hackenbush Azul-Rojo se puede utilizar para construir números surrealistas : los tableros Hackenbush Azul-Rojo finitos pueden construir números racionales diádicos , mientras que los valores de los tableros Hackenbush Azul-Rojo infinitos dan cuenta de números reales , ordinales y muchos más valores generales que no son ni lo uno ni lo otro. El Hackenbush Azul-Rojo-Verde permite la construcción de juegos adicionales cuyos valores no son números reales, como la estrella y todos los demás números .

Se puede realizar un análisis más profundo del juego utilizando la teoría de grafos , considerando el tablero como una colección de vértices y aristas y examinando los caminos hacia cada vértice que se encuentra en el suelo (que debe considerarse como un vértice distinguido —no hace daño identificar todos los puntos del suelo juntos— en lugar de como una línea en el gráfico).

En la versión imparcial de Hackenbush (la que no tiene colores especificados por el jugador), se puede pensar en usar montones de nim dividiendo el juego en varios casos: vertical, convergente y divergente. Jugado exclusivamente con pilas verticales de segmentos de línea, también conocidos como tallos de bambú, el juego se convierte directamente en Nim y puede analizarse directamente como tal. Los segmentos divergentes, o árboles, agregan una arruga adicional al juego y requieren el uso del principio de los dos puntos que establece que cuando las ramas se unen en un vértice, se pueden reemplazar las ramas por un tallo no ramificado de longitud igual a su suma nim . Este principio cambia la representación del juego a la versión más básica de los tallos de bambú. El último conjunto posible de gráficos que se pueden hacer son los convergentes, también conocidos como gráficos de raíz arbitraria. Al usar el principio de fusión, podemos afirmar que todos los vértices de cualquier ciclo se pueden fusionar sin cambiar el valor del gráfico. ^[3] Por lo tanto, cualquier gráfico convergente también puede interpretarse como un simple gráfico de tallo de bambú. Al combinar los tres tipos de gráficos podemos agregar complejidad al juego, sin cambiar nunca la suma nim del juego, lo que permite que el juego adopte las estrategias de Nim.

El principio de los dos puntos establece que cuando las ramas se juntan en un vértice, se pueden reemplazar las ramas por un tallo no ramificado de longitud igual a la suma de sus nim. Considere un grafo fijo pero arbitrario, G , y seleccione un vértice arbitrario, x , en G . Sean H ₁ y H ₂ árboles arbitrarios (o grafos) que tienen el mismo valor de Sprague-Grundy. Considere los dos grafos G ₁ = G _x  : H ₁ y G ₂ = G _x  : H ₂ , donde G _x  : H _i representa el grafo construido uniendo el árbol H _i ​​al vértice x del grafo G . El principio de los dos grafos establece que los dos grafos G1 y G2 tienen el mismo valor de Sprague-Grundy. Considere la suma de los dos juegos. La afirmación de que G ₁ y G ₂ tienen el mismo valor de Sprague-Grundy es equivalente a la afirmación de que la suma de los dos juegos tiene un valor de Sprague-Grundy de 0. En otras palabras, debemos demostrar que la suma G ₁ + G ₂ es una posición P. Un jugador tiene garantizada la victoria si es el segundo jugador en mover en G ₁ + G ₂ . Si el primer jugador mueve cortando uno de los bordes en G en uno de los juegos, entonces el segundo jugador corta el mismo borde en G en el otro juego. (Tal par de movimientos puede eliminar H ₁ y H ₂ de los juegos, pero de lo contrario H ₁ y H ₂ no se alteran). Si el primer jugador mueve cortando un borde en H ₁ o H ₂ , entonces los valores de Sprague-Grundy de H ₁ y H ₂ ya no son iguales, de modo que existe un movimiento en H ₁ o H ₂ que mantiene los valores de Sprague-Grundy iguales. De esta manera, siempre tendrás una respuesta a cada movimiento que haga, lo que significa que serás tú quien haga el último movimiento y, por lo tanto, ganarás. ^[4]

• 
  Un caso en el que el juego se puede reducir utilizando el Principio de Colón

• John H. Conway, Sobre números y juegos , 2.a edición, AK Peters, 2000.

Wikimedia Commons tiene medios relacionados con Juego Hackenbush .

• Hackenstrings y 0,999... frente a 1
• Hackenbush sobre juegos con lápiz y papel