Hackenbush
Hackenbush es un juego para dos jugadores inventado por el matemático John Horton Conway.[1][2] 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".
Jugabilidad editar
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). Según la convención de juego normal de la teoría de juegos combinatorios, el primer jugador que no pueda moverse pierde.
Los tableros de Hackenbush pueden constar de un número finito de segmentos de línea (en el caso de un "tablero finito") o infinitos (en el caso de un "tablero infinito"). 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 sólo 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 editar
En la versión folclórica original de Hackenbush, cualquier jugador puede cortar cualquier borde: como este es un juego imparcial, es relativamente sencillo dar un análisis completo usando el teorema de Sprague-Grundy. Por lo tanto, las versiones de Hackenbush de interés en la teoría de juegos combinatorios son juegos partisanos 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 consigue 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 Hackenbush azul-rojo, con la estipulación adicional de que cualquier jugador puede cortar segmentos de línea verde.
Hackenbush Azul-Rojo es simplemente un caso especial de Hackenbush azul-rojo-verde, pero vale la pena señalarlo por separado, ya que su análisis suele ser mucho más simple. Esto se debe a que Hackenbush Azul-Rojo es un juego llamado frío, lo que significa, esencialmente, que nunca puede ser una ventaja tener el primer movimiento.
Análisis editar
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 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 surreales 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 valores más generales que no son ninguno. 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 detallado del juego utilizando la teoría de grafos considerando el tablero como una colección de vértices y aristas y examinando los caminos 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, indicando 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 nim suma. 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 se puede interpretar como un simple gráfico de tallo de bambú. Combinando 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 los dos puntos editar
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 H1 y H2 árboles (o gráficos) arbitrarios que tienen el mismo valor de Sprague-Grundy. Considérese las dos gráficas G1 = Gx : H1 y G2 = Gx : H2, donde Gx : Hi representa el gráfico construido uniendo el árbol Hi 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 G1 y G2 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 de 0. En otras palabras, debemos demostrar que la suma G1 + G2 es una posición P. Se garantiza que un jugador ganará si es el segundo jugador en moverse G1 + G2. Si el primer jugador se mueve cortando uno de los bordes en G en uno de los juegos, el segundo jugador corta el mismo borde en G en el otro juego. (Este par de movimientos puede eliminar H1 y H2 de los juegos, pero de lo contrario H1 y H2 no se alteran). Si el primer jugador se mueve cortando un borde en H1 o H2, entonces los valores de Sprague-Grundy de H1 y H2 ya no son iguales, por lo que existe un movimiento en H1 o H2 que mantiene iguales los valores de Sprague-Grundy. De esta forma siempre se tendrá una respuesta a cada movimiento que realice. Esto significará hacer el último movimiento y ganar.[4]
Referencias editar
- ↑ Fraenkel, Aviezri S. (1978). «Review: On numbers and games, by J. H. Conway; and Surreal numbers, by D. E. Knuth». Bull. Amer. Math. Soc. 84 (6): 1328-1336. doi:10.1090/s0002-9904-1978-14564-9.
- ↑ What is Hackenbush? at geometer.org
- ↑ R., Berlekamp, Elwyn (2001–2004). Winning ways for your mathematical plays. Conway, John H. (John Horton), Guy, Richard K. (2nd edición). Natick, Mass.: A.K. Peters. ISBN 9781568811420. OCLC 45102937.
- ↑ Ferguson, Thomas S. (Fall 2000). «Game Theory».
Enlaces externos editar
Wikimedia Commons alberga una categoría multimedia sobre Hackenbush.
En inglés:
Datos: Q5637225- Multimedia: Hackenbush game / Q5637225
