Hex (también llamado Nash ) es un juego de mesa de estrategia abstracta para dos jugadores en el que los jugadores intentan conectar los lados opuestos de un tablero en forma de rombo hecho de celdas hexagonales . Hex fue inventado por el matemático y poeta Piet Hein en 1942 y luego redescubierto y popularizado por John Nash .
Tradicionalmente se juega en un tablero de rombos de 11×11, aunque también son populares los tableros de 13×13 y 19×19. El tablero está compuesto de hexágonos llamados celdas o hexágonos . A cada jugador se le asigna un par de lados opuestos del tablero, que deben intentar conectar colocando alternativamente una piedra de su color en cualquier hexágono vacío. Una vez colocadas, las piedras nunca se mueven ni se retiran. Un jugador gana cuando conecta con éxito sus lados a través de una cadena de piedras adyacentes. Los empates son imposibles en Hex debido a la topología del tablero de juego.
A pesar de la simplicidad de sus reglas, el juego tiene una estrategia profunda y tácticas agudas. También tiene fundamentos matemáticos profundos relacionados con el teorema de punto fijo de Brouwer , los matroides y la conectividad de grafos . El juego se publicó por primera vez con el nombre de Polygon en el periódico danés Politiken el 26 de diciembre de 1942. Más tarde se comercializó como un juego de mesa en Dinamarca con el nombre de Con-tac-tix , y Parker Brothers comercializó una versión del mismo en 1952 llamada Hex ; ya no se fabrican. Hex también se puede jugar con papel y lápiz en papel cuadriculado de rayas hexagonales.
Hex es un juego de información perfecta finito para 2 jugadores y un juego de estrategia abstracta que pertenece a la categoría general de juegos de conexión . [1] Se puede clasificar como un juego Maker-Breaker , [1] : 122 un tipo particular de juego posicional . Dado que el juego nunca puede terminar en empate , [1] : 99 Hex también es un juego determinado .
Hex es un caso especial de la versión de "nodo" del juego de conmutación de Shannon . [1] : 122 Hex se puede jugar como un juego de mesa o como un juego de papel y lápiz .
_flipped.jpg/1280px-HEX_11x11_(47)_flipped.jpg){kind=spacer}
El juego Hex se juega en una cuadrícula rómbica de hexágonos, normalmente de tamaño 11×11, aunque también son posibles otros tamaños. Cada jugador tiene un color asignado, convencionalmente rojo y azul, o negro y blanco. [2] A cada jugador también se le asignan dos bordes opuestos del tablero. Los hexágonos en cada una de las cuatro esquinas pertenecen a ambos bordes adyacentes del tablero.
Los jugadores se turnan para colocar una piedra de su color en una sola celda del tablero. La convención más común es que Rojo o Negro empiecen primero. Una vez colocadas, las piedras no se mueven, reemplazan ni retiran del tablero. El objetivo de cada jugador es formar un camino conectado con sus propias piedras que una los dos bordes del tablero. El jugador que complete dicha conexión gana el juego.
Para compensar la ventaja del primer jugador, normalmente se utiliza la regla del intercambio (también llamada regla del pastel). Esta regla permite al segundo jugador elegir si cambia de posición con el primer jugador después de que este último haga el primer movimiento.
Cuando ambos jugadores tienen claro quién ganará la partida, es habitual, aunque no obligatorio, que el jugador perdedor abandone la partida. En la práctica, la mayoría de las partidas de Hex terminan con la renuncia de uno de los jugadores.
El juego fue inventado por el matemático danés Piet Hein , quien lo presentó en 1942 en el Instituto Niels Bohr . Aunque Hein más tarde lo rebautizó como Con-tac-tix, [3] [4] se hizo conocido en Dinamarca con el nombre de Polygon debido a un artículo de Hein en la edición del 26 de diciembre de 1942 del periódico danés Politiken , la primera descripción publicada del juego, en la que utilizó ese nombre.
El juego fue redescubierto en 1948 o 1949 por el matemático John Nash en la Universidad de Princeton . [2] [5] Según Martin Gardner , quien presentó Hex en su columna Mathematical Games de julio de 1957 , los compañeros de juego de Nash llamaban al juego Nash o John, y el último nombre se refería al hecho de que el juego podía jugarse en baldosas hexagonales de baño. [2] Nash insistió en que descubrió el juego independientemente de Hein, pero hay algunas dudas sobre esto, ya que se sabe que hubo daneses, incluido Aage Bohr , que jugaron Hex en Princeton en la década de 1940, por lo que Nash pudo haber recogido inconscientemente la idea. Hein le escribió a Gardner en 1957 expresando sus dudas de que Nash descubriera Hex de forma independiente. Gardner no pudo verificar o refutar de forma independiente la afirmación de Nash. [6] Gardner le escribió en privado a Hein: "Lo hablé con el editor y decidimos que lo más caritativo era darle a Nash el beneficio de la duda... El hecho de que usted inventó el juego antes que nadie es indiscutible. Cualquier cantidad de personas pueden venir después y decir que pensaron en lo mismo en una fecha posterior, pero esto significa poco y a nadie le importa realmente". [1] : 134 En una carta posterior a Hein, Gardner también escribió: "Entre usted y yo, y extraoficialmente, creo que dio en el clavo cuando se refirió a una 'sugerencia fugaz' que le llegó al Sr. Nash de una fuente danesa y que luego olvidó. Parece la explicación más probable". [1] : 136
Inicialmente, en 1942, Hein distribuyó el juego, que entonces se llamaba Polygon, en forma de cuadernos de juego de 50 hojas. Cada hoja contenía un tablero vacío de 11 × 11 en el que se podía jugar con lápices o bolígrafos. [1] En 1952, Parker Brothers comercializó una versión del juego con el nombre "Hex", y el nombre se mantuvo. [2] Parker Brothers también vendió una versión con el nombre "Con-tac-tix" en 1968. [3] Hex también se publicó como uno de los juegos de la serie de juegos de papel 3M de 1974; el juego contenía un tablero de 5+1 ⁄ 2 por 8+Bloc de 50 hojas de cuadrículas hexagonales de 1 ⁄ 2 pulgada (140 mm × 220 mm). Actualmente, Nestorgames publica Hex en tamaños de 11 × 11, 14 × 14 y 19 × 19. [7]
Alrededor de 1950, Claude Shannon y EF Moore construyeron una máquina de juego de Hex analógica, que era esencialmente una red de resistencias con resistencias como aristas y bombillas como vértices. [8] El movimiento que se debía realizar correspondía a un punto de silla específico en la red. La máquina jugaba una partida de Hex razonablemente buena. Más tarde, los investigadores que intentaban resolver el juego y desarrollar algoritmos informáticos para jugar Hex emularon la red de Shannon para crear jugadores informáticos fuertes. [9]
Hein ya sabía en 1942 que el Hex no puede terminar en empate; de hecho, uno de sus criterios de diseño para el juego era que "exactamente uno de los dos jugadores pueda conectar sus dos lados". [1] : 29
Hein también sabía que el primer jugador tiene una estrategia ganadora teórica. [1] : 42
En 1952, John Nash escribió una prueba de existencia de que en tableros simétricos, el primer jugador tiene una estrategia ganadora. [1] : 97
En 1964, el matemático Alfred Lehman demostró que Hex no puede representarse como un matroide binario , por lo que no estaba disponible una estrategia ganadora determinada como la del juego de cambio de Shannon en una cuadrícula rectangular regular. [10]
En 1981, Stefan Reisch demostró que Hex es PSPACE-completo. [11]
En 2002, se describió la primera estrategia ganadora explícita (una estrategia de tipo reducción) en un tablero de 7×7.
En la década del 2000, mediante el uso de algoritmos informáticos de búsqueda de fuerza bruta , se han resuelto por completo tableros hexagonales de tamaño hasta 9×9 (a partir de 2016).
A partir de 2006, el campo del hexadecimal informático pasó a estar dominado por métodos de búsqueda de árboles de Monte Carlo tomados de implementaciones informáticas exitosas de Go. Estos reemplazaron a las implementaciones anteriores que combinaban la heurística de juego de hexágonos de Shannon con la búsqueda alfa-beta . En cuanto al primer hexadecimal informático, las primeras implementaciones notables incluyen Hexmaster de Dolphin Microware , publicado a principios de la década de 1980 para computadoras Atari de 8 bits . [12]
Hasta 2019, los humanos seguían siendo mejores que las computadoras al menos en tableros grandes como el 19x19, pero el 30 de octubre de 2019 el programa Mootwo ganó contra el jugador humano con el mejor ranking Elo en LittleGolem, también ganador de varios torneos (el juego está disponible aquí). Este programa se basó en Polygames [13] (un proyecto de código abierto, desarrollado inicialmente por Facebook Artificial Intelligence Research y varias universidades [14] ) utilizando una mezcla de: [15]
A partir de la prueba de una estrategia ganadora para el primer jugador, se sabe que el tablero hexagonal debe tener un tipo complejo de conectividad que nunca se ha resuelto. El juego consiste en crear pequeños patrones que tengan un tipo de conectividad más simple llamado "conectados de forma segura", y unirlos en secuencias que formen un "camino". Finalmente, uno de los jugadores logrará formar un camino conectado de forma segura de piedras y espacios entre sus lados del tablero y ganará. La etapa final del juego, si es necesario, consiste en llenar los espacios vacíos en el camino. [17]
Un patrón "conectado de forma segura" está compuesto por piedras del color del jugador y espacios abiertos que se pueden unir para formar una cadena, una secuencia ininterrumpida de piedras adyacentes por los bordes, sin importar cómo juegue el oponente. [18] Uno de los patrones más simples es el puente, que consiste en un diamante de dos piedras del mismo color y dos espacios vacíos, donde las dos piedras no se tocan. [19] Si el oponente juega en cualquiera de los espacios, el jugador juega en el otro, creando una cadena contigua. También hay patrones conectados de forma segura que conectan las piedras con los bordes. [20] Hay muchos más patrones conectados de forma segura, algunos bastante complejos, formados por otros más simples como los que se muestran. El oponente puede alterar los patrones y los caminos antes de que se completen, por lo que la configuración del tablero durante una partida real a menudo parece un mosaico en lugar de algo planeado o diseñado. [17]
Hay tipos de conectividad más débiles que la "conexión segura", que existen entre piedras o entre patrones conectados de forma segura que tienen múltiples espacios entre ellos. [21] La parte media del juego consiste en crear una red de estas piedras y patrones débilmente conectados [21] que, con suerte, permitirá al jugador, al completar los eslabones débiles, construir solo un camino conectado de forma segura entre los lados a medida que avanza el juego. [21]
Para tener éxito en Hex se necesita una habilidad particular para visualizar la síntesis de patrones complejos de manera heurística y estimar si dichos patrones están conectados "lo suficientemente fuerte" como para permitir una victoria final. [17] La habilidad es algo similar a la visualización de patrones, la secuenciación de movimientos y la evaluación de posiciones en ajedrez. [22]
No es difícil convencerse a sí mismo mediante la exposición de que el hex no puede terminar en tablas, lo que se conoce como el "teorema del hex". Es decir, no importa cuántas piedras esté llena el tablero, siempre habrá un solo jugador que haya conectado sus bordes. Este hecho era conocido por Piet Hein en 1942, quien lo mencionó como uno de sus criterios de diseño para Hex en el artículo original de Politiken. [1] : 29 Hein también afirmó este hecho como "una barrera para tu oponente es una conexión para ti". [1] : 35 John Nash escribió una prueba de este hecho alrededor de 1949, [23] pero aparentemente no publicó la prueba. Su primera exposición aparece en un informe técnico interno en 1952, [24] en el que Nash afirma que "la conexión y el bloqueo del oponente son actos equivalentes". Una prueba más rigurosa fue publicada por John R. Pierce en su libro de 1961 Símbolos, señales y ruido . [25] En 1979, David Gale publicó una prueba de que la determinación de Hex es equivalente al teorema de punto fijo bidimensional de Brouwer, y que la determinación de variantes de n jugadores de dimensiones superiores prueba el teorema de punto fijo en general. [26]
Una prueba informal de la propiedad de no empate de Hex puede esbozarse de la siguiente manera: considere el componente conectado de uno de los bordes rojos. Este componente incluye el borde rojo opuesto, en cuyo caso Rojo tiene una conexión, o no la tiene, en cuyo caso las piedras azules a lo largo del límite del componente conectado forman un camino ganador para Azul. El concepto de un componente conectado está bien definido porque en una cuadrícula hexagonal, dos celdas solo pueden encontrarse en un borde o no encontrarse en absoluto; no es posible que las celdas se superpongan en un solo punto.
En Hex sin la regla de intercambio en cualquier tablero de tamaño n x n , el primer jugador tiene una estrategia ganadora teórica. Este hecho fue mencionado por Hein en sus notas para una conferencia que dio en 1943: "a diferencia de la mayoría de los otros juegos, se puede demostrar que el primer jugador en teoría siempre puede ganar, es decir, si pudiera ver hasta el final de todas las líneas de juego posibles". [1] : 42
Todas las pruebas conocidas de este hecho no son constructivas, es decir, la prueba no da ninguna indicación de cuál es la estrategia ganadora real. Aquí hay una versión condensada de una prueba que se atribuye a John Nash alrededor de 1949. [2] La prueba funciona para varios juegos, incluido Hex, y ha llegado a llamarse el argumento del robo de estrategia .
En 1976, Shimon Even y Robert Tarjan demostraron que determinar si una posición en un juego de Hex generalizado jugado en grafos arbitrarios es una posición ganadora es PSPACE-completo . [27] Reisch demostró un fortalecimiento de este resultado al reducir el problema de fórmula booleana cuantificada en forma normal conjuntiva a Hex. [28] Este resultado significa que no existe un algoritmo eficiente (tiempo polinomial en tamaño de tablero) para resolver una posición Hex arbitraria a menos que haya un algoritmo eficiente para todos los problemas PSPACE, lo que se cree ampliamente que no es el caso. [29] Sin embargo, no descarta la posibilidad de una estrategia ganadora simple para la posición inicial (en tableros de tamaño arbitrario), o una estrategia ganadora simple para todas las posiciones en un tablero de un tamaño particular.
En 11×11 Hex, la complejidad del espacio de estados es aproximadamente 2,4×10 56 ; [30] frente a 4,6×10 46 para ajedrez. [31] La complejidad del árbol de juego es aproximadamente 10 98 [32] frente a 10 123 para ajedrez. [33]
En 2002, Jing Yang, Simon Liao y Mirek Pawlak encontraron una estrategia ganadora explícita para el primer jugador en tableros hexagonales de tamaño 7×7 utilizando un método de descomposición con un conjunto de patrones locales reutilizables. [34] Extendieron el método para resolver débilmente el par central de aperturas topológicamente congruentes en tableros de 8×8 en 2002 y la apertura central en tableros de 9×9 en 2003. [35] En 2009, Philip Henderson, Broderick Arneson y Ryan B. Hayward completaron el análisis del tablero de 8×8 con una búsqueda por computadora, resolviendo todas las aperturas posibles. [36] En 2013, Jakub Pawlewicz y Ryan B. Hayward resolvieron todas las aperturas para tableros de 9×9 y un movimiento de apertura (el más central) en el tablero de 10×10. [37] Desde que Gardner postuló por primera vez en su columna en Scientific American en 1957, aunque de manera engañosa, que cualquier primera jugada en la diagonal corta es una jugada ganadora, [38] para todos los tableros de juego resueltos hasta n=9, ese ha sido efectivamente el caso. Además, para todos los tableros excepto n=2 y n=4, ha habido numerosos primeros movimientos ganadores adicionales; el número de primeros movimientos ganadores generalmente es ≥ n²/2.
Otros juegos de conexión con objetivos similares pero estructuras diferentes incluyen el juego de intercambio de Shannon (también conocido como Gale y Bridg-It) y TwixT . Ambos tienen cierto grado de similitud con el antiguo juego chino Go .
El juego se puede jugar en una cuadrícula rectangular como un tablero de ajedrez, damas o go, teniendo en cuenta que los espacios (intersecciones en el caso del go) están conectados en una dirección diagonal pero no en la otra. El juego se puede jugar con papel y lápiz sobre una matriz rectangular de puntos o papel cuadriculado de la misma manera, utilizando dos lápices de colores diferentes.
Otras dimensiones populares además del estándar 11×11 son 13×13 y 19×19 como resultado de la relación del juego con el antiguo juego Go . Según el libro A Beautiful Mind , John Nash (uno de los inventores del juego) recomendó 14×14 como el tamaño óptimo.
La variante miseria de Hex se llama "Rex", en la que cada jugador intenta obligar a su oponente a hacer una cadena. Rex es más lento que Hex ya que, en cualquier tablero vacío con dimensiones iguales, el jugador perdedor puede retrasar una pérdida hasta que todo el tablero esté lleno. [39] En tableros con dimensiones desiguales, el jugador cuyos lados estén más separados puede ganar independientemente de quién juegue primero. [40] En tableros con dimensiones iguales, el primer jugador puede ganar en un tablero con un número par de casillas por lado, y el segundo jugador puede ganar en un tablero con un número impar. [41] [42] En tableros con un número par, uno de los movimientos ganadores del primer jugador es siempre colocar una piedra en la esquina aguda. [39]
Hex tuvo una encarnación como el tablero de preguntas del programa de televisión Blockbusters . Para jugar un "movimiento", los concursantes tenían que responder una pregunta correctamente. El tablero tenía 5 columnas alternas de 4 hexágonos; el jugador en solitario podía conectar de arriba a abajo en 4 movimientos, mientras que el equipo de dos podía conectar de izquierda a derecha en 5 movimientos.
El juego Y es Hex y se juega en una cuadrícula triangular de hexágonos; el objetivo es que cada jugador conecte los tres lados del triángulo. Y es una generalización de Hex en la medida en que cualquier posición en un tablero Hex puede representarse como una posición equivalente en un tablero Y más grande.
Havannah es un juego basado en Hex. [43] También tiene un espacio de tablero compuesto de fichas hexagonales, sin embargo, el tablero en sí tiene la forma de un gran hexágono y se obtiene una victoria formando uno de tres patrones.
Projex es una variación de Hex que se juega en un plano proyectivo real , donde los jugadores tienen el objetivo de crear un bucle no contráctil . [44] Al igual que en Hex, no hay empates y no hay ninguna posición en la que ambos jugadores tengan una conexión ganadora.
Dark Hex (también conocido como Phantom Hex) es una versión de información imperfecta de Hex. [45] Los jugadores no están expuestos a las piedras de los demás en ningún momento del juego a menos que las descubran primero. El juego se juega en presencia de un árbitro donde cada jugador verifica primero si el movimiento es una colisión o no. En función de la continuación de este punto, el juego tiene diferentes versiones.
A partir de 2016, se informaron torneos presenciales en Brasil, República Checa, Dinamarca, Francia, Alemania, Italia, Países Bajos, Noruega, Polonia, Portugal, España, Reino Unido y Estados Unidos. [ cita requerida ] Una de las competiciones Hex más grandes es organizada por el Comité Internacional de Juegos Matemáticos en París, Francia, que se celebra anualmente desde 2013. [ cita requerida ] Hex también es parte de la Olimpiada de Computación . [ 46 ] Durante esta competencia se utiliza la regla del pastel.
{{cite web}}: CS1 maint: bot: original URL status unknown (link)