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 conectados entre sí por sus extremos y a una línea de referencia. Otras versiones del juego utilizan líneas de diferentes colores.

El juego comienza con los jugadores dibujando una línea de "suelo" (convencionalmente, aunque 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 esté conectado al suelo, ya sea directamente en un extremo o indirectamente, a través de una cadena de otros segmentos conectados por extremos. Cualquier número de segmentos puede confluir en un punto, por lo que puede haber múltiples caminos hacia el suelo.

En su turno, un jugador «corta» (borra) cualquier segmento de línea que elija. Todo segmento de línea que ya no esté conectado al suelo por ningún camino «cae» (es decir, se borra). Según las reglas habituales de la teoría de juegos combinatorios, el primer jugador que no pueda mover pierde.

Los tableros de Hackenbush pueden constar de un número finito (en el caso de un "tablero finito") o infinito (en el caso de un "tablero infinito") de segmentos de línea, siempre que la configuración no viole el supuesto de la teoría de juegos de que el juego puede terminarse en un tiempo finito. En un tablero infinito, en cambio, el juego puede continuar indefinidamente, suponiendo que haya infinitos segmentos tocando el suelo.

Variantes

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 serían necesariamente las mismas que las disponibles para el otro jugador si fuera su turno de mover dada la misma posición. Esto se logra 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 dibujo). También se le conoce como Hackenbush verde. ^{[ 2 ]}
• Hackenbush azul-rojo : Cada segmento de línea está coloreado de rojo o azul. Un jugador (normalmente el primero, o el de la izquierda) solo puede cortar los segmentos de línea azules, mientras que el otro jugador (normalmente el segundo, o el de la derecha) solo puede cortar los segmentos de línea rojos.
• Hackenbush Azul-Rojo-Verde : Cada segmento de línea está coloreado de rojo, azul o verde. Las reglas son las mismas que para Hackenbush Azul-Rojo, con la condición adicional de que cualquiera de los jugadores puede cortar los segmentos de línea verdes.

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

Hackenbush se ha utilizado a menudo como ejemplo de juego 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 del campo. En particular, Hackenbush Azul-Rojo se puede utilizar para construir números surrealistas : los tableros finitos de Hackenbush Azul-Rojo pueden construir números racionales diádicos , mientras que los valores de los tableros infinitos de Hackenbush Azul-Rojo representan números reales y, en el caso transfinito, ordinales , y muchos más valores generales que no son ninguno de los dos. Hackenbush Azul-Rojo-Verde permite la construcción de juegos adicionales cuyos valores no son números reales, como estrella y todos los demás nimbers .

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 hay problema en identificar todos los puntos del suelo juntos , en lugar de como una línea en el grafo).

En la versión imparcial de Hackenbush (la que no tiene colores especificados por el jugador), se puede pensar en el uso de montículos 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, añaden una complejidad 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 por un tallo sin ramificaciones 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 grafos que se pueden crear son los convergentes, también conocidos como grafos con raíz arbitraria. Usando el principio de fusión, podemos afirmar que todos los vértices de cualquier ciclo pueden fusionarse sin cambiar el valor del grafo. ^{[ 3 ]} Por lo tanto, cualquier grafo convergente también puede interpretarse como un simple grafo de tallos de bambú. Al combinar los tres tipos de gráficos, podemos añadir complejidad al juego, sin cambiar nunca la suma de Nim del juego, permitiendo así que el juego adopte las estrategias de Nim.

El principio de los dos puntos establece que cuando las ramas se unen en un vértice, se pueden reemplazar las ramas por un tallo sin ramificaciones de longitud igual a su suma de nim. Consideremos un grafo fijo pero arbitrario, _G , y seleccionemos un vértice arbitrario, x , en G. Sean H1 y H2 árboles (o grafos) arbitrarios que tengan el mismo valor de Sprague-Grundy. Consideremos los dos grafos G1 = Gx: H1 y G2 = Gx: H2, donde Gx _{: Hi representa} el grafo construido _al adjuntar _el árbol Hi al vértice x del _{grafo G.} El principio _de los dos puntos establece que los _{dos grafos} G1 y G2 tienen el mismo valor de Sprague-Grundy. Consideremos 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 moverse en G ₁ + G _2. Si el primer jugador se mueve cortando una de las aristas en G en uno de los juegos, entonces el segundo jugador corta la misma arista en G en el otro juego. (Tal par de movimientos puede eliminar H ₁ y H ₂ de los juegos, pero por lo demás H ₁ y H ₂ no se ven afectados). Si el primer jugador se mueve cortando una arista 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 forma siempre tendrás una respuesta para cada movimiento que él pueda hacer. Esto significa que harás el último movimiento y, por lo tanto, ganarás. ^{[ 4 ]}   

• 
  Un ejemplo en el que el juego se puede simplificar utilizando el Principio de Colon.

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

• Hackenstrings y 0,999... vs. 1
• Hackenbush sobre los juegos de lápiz y papel