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".
Como se Juega
El juego comienza con los jugadores dibujando una línea de "suelo" (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 modo que cada segmento de línea esté conectado al suelo, 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 a tierra.
En su turno, un jugador "corta" (borra) cualquier segmento de línea de su elección. Cada 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 de Hackenbush pueden constar de un número finito (en el caso de un "tablero finito") o de 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 un período de tiempo finito, siempre que solo haya un número finito de segmentos de línea que "toquen" directamente el suelo. En un tablero infinito, según el diseño del tablero, el juego puede continuar para siempre, asumiendo que hay infinitos puntos 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 dar 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 disponibles para el otro jugador si fuera su turno de moverse dada la misma posición. . Esto se logra de dos formas:
- Hackenbush original: todos los segmentos de línea son del mismo color y cualquiera de los jugadores puede cortarlos. Esto significa que los pagos son simétricos y que cada jugador tiene las mismas operaciones según la posición a bordo (en este caso, la estructura del dibujo).
- Hackenbush azul-rojo : cada segmento de línea es de color rojo o azul. Un jugador (generalmente el primer jugador o el izquierdo) solo puede cortar segmentos de línea azul, mientras que el otro jugador (generalmente el segundo jugador o el derecho) solo puede cortar segmentos de línea roja.
- Hackenbush azul-rojo-verde : cada segmento de línea es de color rojo, azul o verde. Las reglas son las mismas que para Blue-Red Hackenbush, con la estipulación adicional de que cualquier jugador puede cortar segmentos de línea verde.
Blue-Red Hackenbush es simplemente un caso especial de Blue-Red-Green Hackenbush, pero vale la pena señalarlo por separado, ya que su análisis suele ser mucho más simple. Esto se debe a que Blue-Red Hackenbush es un juego llamado frío , lo que significa, esencialmente, que nunca puede ser una ventaja tener el primer movimiento.
Análisis
Hackenbush se ha utilizado a menudo como un juego de ejemplo para demostrar las definiciones y conceptos en la teoría de juegos combinatorios , comenzando con su uso en los libros Sobre números y juegos y Maneras ganadoras para sus juegos matemáticos de algunos de los fundadores del campo. En particular, Blue-Red Hackenbush se puede usar para construir números surrealistas como nimbers : los tableros finitos Blue-Red Hackenbush pueden construir números racionales diádicos , mientras que los valores de infinitos tableros Blue-Red Hackenbush representan números reales , ordinales y muchos más valores que no son ninguno. Blue-Red-Green Hackenbush 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 detallado del juego utilizando la teoría de grafos considerando el tablero como una colección de vértices y aristas y examinando las rutas a 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 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 se puede analizar directamente como tal. Los segmentos divergentes, o árboles, agregan una arruga adicional al juego y requieren el uso del principio de dos puntos que 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 su suma mínima. 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 con raíces arbitrarias. Al usar el principio de fusión, podemos afirmar que todos los vértices de cualquier ciclo pueden fusionarse sin cambiar el valor del gráfico. [2] Por lo tanto, cualquier gráfico convergente también se puede interpretar 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.
Prueba del principio de colon
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 su suma nim. Considere un gráfico fijo pero arbitraria, G , y seleccionar un vértice arbitrario, x , en G . Sean H 1 y H 2 árboles (o gráficos) arbitrarios que tienen el mismo valor de Sprague-Grundy. Considerar los dos gráficos G 1 = G x : H 1 y G 2 = G x : H 2 , donde G x : H i representa el gráfico construido uniendo el árbol H i al vértice x de la gráfica G . El principio de los dos puntos establece que los dos gráficos G1 y G2 tienen el mismo valor de Sprague-Grundy. Considere la suma de los dos juegos como en la figura 5.4. La afirmación de que G 1 y G 2 tienen el mismo valor de Sprague-Grundy es equivalente a la afirmación de que la suma de los dos juegos tiene el valor de Sprague-Grundy 0. En otras palabras, debemos demostrar que la suma G 1 + G 2 es una posición P. Un jugador tiene la garantía de ganar si es el segundo jugador en moverse en G 1 + G 2 . Si el primer jugador se 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. (Este par de movimientos puede eliminar H 1 y H 2 de los juegos, pero de lo contrario, H 1 y H 2 no se ven afectados). Si el primer jugador se mueve cortando un borde en H 1 o H 2 , entonces el Sprague-Grundy los valores de H 1 y H 2 ya no son iguales, por lo que existe un movimiento en H 1 o H 2 que mantiene los valores de Sprague-Grundy iguales. De esta forma siempre tendrás una respuesta a cada movimiento que realice. Esto significa que harás el último movimiento y ganarás. [3]
Referencias
- ^ ¿Qué es Hackenbush? en geometer.org
- ^ R., Berlekamp, Elwyn (2001-2004). Formas ganadoras para tus jugadas matemáticas . Conway, John H. (John Horton), Guy, Richard K. (2ª ed.). Natick, Mass .: AK Peters. ISBN 9781568811420. OCLC 45102937 .
- ^ Ferguson, Thomas S. (otoño de 2000). "Teoría de juegos" (PDF) .
- John H. Conway, Sobre números y juegos , segunda edición, AK Peters, 2000.