Hexadecimal (juego de mesa)

Hex 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.

Se juega tradicionalmente 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 por 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 quitan. Un jugador gana cuando conecta con éxito sus lados a través de una cadena de piedras adyacentes. Los sorteos 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 profundos fundamentos matemáticos. El juego se publicó por primera vez con el nombre Polygon en el periódico danés Politiken el 26 de diciembre de 1942. Más tarde se comercializó como juego de mesa en Dinamarca con el nombre Con-tac-tix, y Parker Brothers comercializó una versión del mismo en 1952 llamada Hex; ya no están en producción. Hex también se puede jugar con papel y lápiz en papel cuadriculado con rayas hexagonales.

Tipo de juego

Hex es un juego finito de información perfecta para 2 jugadores y un juego de estrategia abstracto que pertenece a la categoría general de juegos de conexión. Puede clasificarse como un juego Maker-Breaker, un tipo particular de juego posicional. Dado que el juego nunca puede terminar en empate, Hex también es un juego determinado.

Hex es un caso especial del "nodo" versión del juego de cambio de Shannon. Hex se puede jugar como un juego de mesa o como un juego de papel y lápiz.

Reglas

El final de un juego de Hex en una tabla estándar 11x11. Aquí, el blanco gana el juego.

Hex se juega en una cuadrícula rómbica de hexágonos, típicamente de tamaño 11x11, aunque también son posibles otros tamaños. Cada jugador tiene un color asignado, convencionalmente rojo y azul o blanco y negro. 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 del tablero adyacentes.

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 vayan primero. Una vez colocadas, las piedras no se mueven, reemplazan ni retiran del tablero. El objetivo de cada jugador es formar un camino conectado de sus propias piedras que une los dos bordes del tablero. El jugador que completa dicha conexión gana el juego.

Para compensar la ventaja del primer jugador, normalmente se usa la regla de intercambio. Esta regla permite que el segundo jugador elija si cambia de posición con el primer jugador después de que el primer jugador haga el primer movimiento.

Cuando está claro para ambos jugadores quién ganará el juego, es habitual, pero no obligatorio, que el jugador perdedor renuncie. En la práctica, la mayoría de los juegos de Hex terminan con la renuncia de uno de los jugadores.

Historia

Invención

El juego fue inventado por el matemático danés Piet Hein, quien lo introdujo en 1942 en el Instituto Niels Bohr. Aunque Hein más tarde lo rebautizó como Con-tac-tix, se hizo conocido en Dinamarca con el nombre 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 usó ese nombre.

Afirmación de Nash

El juego fue redescubierto en 1948 o 1949 por el matemático John Nash en la Universidad de Princeton. Según Martin Gardner, quien presentó a Hex en su columna de juegos matemáticos de julio de 1957, los compañeros de juego de Nash llamaron al juego Nash o John, y este último nombre se refiere al hecho de que el juego se podía jugar en azulejos de baño hexagonales. Nash insistió en que descubrió el juego independientemente de Hein, pero hay algunas dudas al respecto, 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 haberlo aprendido inconscientemente. la idea. Hein le escribió a Gardner en 1957 expresando dudas de que Nash descubriera Hex de forma independiente. Gardner no pudo verificar o refutar de forma independiente la afirmación de Nash. Gardner le escribió en privado a Hein: "Lo discutí con el editor y decidimos que lo más caritativo que podíamos hacer era darle a Nash el beneficio de la duda... El hecho de que tú inventaste el juego antes que nadie es indiscutible. Cualquier número de personas puede venir más tarde y decir que pensaron en lo mismo en una fecha posterior, pero esto significa poco y a nadie realmente le importa." En una carta posterior a Hein, Gardner agregó: "Solo entre tú y yo, y extraoficialmente, creo que diste en el clavo cuando te referiste a una 'sugerencia fugaz'". que le llegó al Sr. Nash de una fuente danesa, y que más tarde se olvidó. Parece la explicación más probable."

Juegos publicados

Una edición de Parker Brothers del juego

Al principio, en 1942, Hein distribuyó el juego, que entonces se llamaba Polygon, en forma de blocs de juego de 50 hojas. Cada hoja contenía un tablero vacío de 11x11 vacío en el que se podía jugar con lápices o bolígrafos. En 1952, Parker Brothers comercializó una versión del juego con el nombre 'Hex', y el nombre se mantuvo. Parker Brothers también vendió una versión bajo la marca "Con-tac-tix" nombre en 1968. Hex también se publicó como uno de los juegos de la serie 3M Paper Games de 1974; el juego contenía un 5+1⁄2-by-8+1⁄2-pulgadas (140 mm × 220 mm) Bloc de 50 hojas de cuadrículas hexagonales rayadas. Hex es publicado actualmente por Nestorgames en un tamaño de 11x11 y un tamaño de 14x14.

La máquina hexagonal de Shannon

Alrededor de 1950, Claude Shannon y E. F. Moore construyeron una máquina de juego hexagonal analógica, que era esencialmente una red de resistencia con resistencias para los bordes y bombillas para los vértices. El movimiento a realizar correspondía a un cierto punto de silla especificado en la red. La máquina jugó un juego razonablemente bueno de Hex. Más tarde, los investigadores que intentaban resolver el juego y desarrollar algoritmos informáticos de juego hexadecimal emularon la red de Shannon para crear potentes jugadores informáticos.

Cronología de la investigación

Hein sabía en 1942 que Hex no puede terminar en tablas; de hecho, uno de sus criterios de diseño para el juego fue que "exactamente uno de los dos jugadores puede conectar sus dos lados".

Hein también sabía que el primer jugador tiene una estrategia ganadora teórica.

En 1952, John Nash escribió una prueba de existencia de que en tableros simétricos, el primer jugador tiene una estrategia ganadora.

En 1964, el matemático Alfred Lehman demostró que Hex no se puede representar como un matroide binario, por lo que una estrategia ganadora determinada como la del juego de cambio de Shannon en una cuadrícula rectangular regular no estaba disponible.

En 1981, Stefan Reisch demostró que Hex es PSPACE-completo.

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 de 2000, mediante el uso de algoritmos informáticos de búsqueda de fuerza bruta, los tableros hexagonales de hasta 9 × 9 de tamaño (a partir de 2016) se resolvieron por completo.

Hasta 2019, los humanos seguían siendo mejores que las computadoras al menos en tableros grandes como 19x19, pero el 30 de octubre de 2019 el programa Mootwo ganó contra el jugador humano con el mejor rango de Elo en LittleGolem, también ganador de varios torneos (el juego está disponible aquí). Este programa se basó en Polygames (un proyecto de código abierto, inicialmente desarrollado por Facebook Artificial Intelligence Research y varias universidades) utilizando una combinación de:

• cero aprendizaje como en AlphaZero
• aborda la invariancia gracias a las redes neuronales totalmente convolutivas (como en U-Net) y la agrupación
• y arquitecturas crecientes (el programa puede aprender en un tablero pequeño, y luego extrapolar en un tablero grande, en lugar de justificadas afirmaciones populares sobre métodos de inteligencia artificial anteriores como el AlfaGo original).

Equipo hexadecimal

A principios de la década de 1980, Dolphin Microware publicó Hexmaster, una implementación para computadoras Atari de 8 bits. Se han utilizado varios paradigmas resultantes de la investigación del juego para crear programas de juego hexadecimales de computadora digital a partir del año 2000. Las primeras implementaciones utilizaron funciones de evaluación que emulaban el modelo de circuito eléctrico de Shannon y Moore integrado en un marco de búsqueda alfa-beta con mano Patrones basados en el conocimiento elaborados. Aproximadamente a partir de 2006, se introdujeron los métodos de búsqueda de árbol de Monte Carlo tomados de implementaciones informáticas exitosas de Go y pronto dominaron el campo. Más tarde, los patrones hechos a mano se complementaron con métodos de aprendizaje automático para el descubrimiento de patrones. Estos programas ahora son competitivos contra jugadores humanos calificados. Se han asignado clasificaciones basadas en Elo a los diversos programas y se pueden usar para medir el progreso técnico y evaluar la fuerza de juego contra humanos con clasificación Elo. Las investigaciones actuales a menudo se publican en el ICGA Journal trimestral o en la serie anual Advances in Computer Games (van den Herik et al. eds.).

Estrategia

Aunque se sabe que el primer jugador (sin la regla de intercambio) tiene una estrategia ganadora teórica, no se sabe cuál es esa estrategia, excepto en tableros muy pequeños. Sin embargo, hay una gran cantidad de conceptos tácticos y estratégicos útiles disponibles para los jugadores de Hex.

Conexiones virtuales y plantillas

Diagrama 1: Algunas plantillas interiores

Diagrama 2: Algunas plantillas de borde

Se dice que un conjunto de piedras de un color está virtualmente conectado si las piedras' el propietario puede garantizar conectarlos, sin importar lo que haga el oponente. El ejemplo más simple de una conexión virtual es un puente, que se muestra en el diagrama 1. Aunque las dos piedras rojas del puente no son adyacentes, Red puede garantizar que las conectará: si Blue juega en una de las celdas vacías del puente, entonces Red puede jugar en el otro. Tenga en cuenta que la conexión virtual requiere no solo las dos piedras rojas, sino también las dos celdas vacías del puente. Las celdas (vacías o no) que forman parte de la conexión virtual se denominan carrier de la conexión virtual.

Una plantilla es un patrón de piedras y celdas vacías que está virtualmente conectada y es mínima (es decir, quitar cualquier piedra o celda vacía del soporte rompería la conexión virtual). Las plantillas se pueden caracterizar como plantillas interiores (que garantizan una conexión entre dos o más piedras) y plantillas de borde (que garantizan una conexión entre una o más piedras y un borde de tablero de la misma color). En los diagramas 1 y 2, respectivamente, se muestran algunos ejemplos de plantillas interiores y plantillas de borde.

Teoría matemática

Determinación

No es difícil demostrar que Hex no puede terminar en tablas, es decir, no importa cómo se llene el tablero de piedras, siempre habrá un único jugador que haya conectado sus bordes. Piet Hein conocía este hecho en 1942, quien lo mencionó como uno de sus criterios de diseño para Hex en el artículo original de Politiken. Hein también afirmó este hecho como "una barrera para tu oponente es un conexión para ti". John Nash escribió una prueba de este hecho alrededor de 1949, pero aparentemente no publicó la prueba. Su primera exposición aparece en un informe técnico interno de 1952, en el que Nash afirma que "conectar y bloquear al oponente son actos equivalentes". John R. Pierce publicó una prueba más rigurosa en su libro de 1961 Symbols, Signals, and Noise. En 1979, David Gale publicó una prueba que también mostró que se puede usar para probar el teorema del punto fijo de Brouwer en dos dimensiones, y que la determinación de las variantes de dimensiones superiores prueba el teorema del punto fijo en general.

Una prueba de la propiedad de no dibujar de Hex se puede esbozar de la siguiente manera: considere el componente conectado de uno de los bordes rojos. Este componente incluye el borde rojo opuesto, en cuyo caso Red 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 Blue. El concepto de componente conectado está bien definido porque en una cuadrícula hexagonal, dos celdas solo pueden encontrarse en un borde o no pueden encontrarse; no es posible que las celdas se superpongan en un solo punto.

Estrategia ganadora del primer jugador

En Hex sin la regla de intercambio en cualquier tablero de tamaño nxn, 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 probar que el primer jugador en teoría siempre puede ganar, es decir, si puede ver el final de todas las posibles líneas de juego.".

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 c. 1949. La prueba funciona para una serie de juegos, incluido Hex, y se ha llegado a llamar el argumento del robo de estrategia.

1. Ya que es imposible que el juego termine en un sorteo (ver arriba), ya sea el primer o segundo jugador debe ganar.
2. Como Hex es un juego de información perfecto, debe haber una estrategia ganadora para el primer o segundo jugador.
3. Supongamos que el segundo jugador tiene una estrategia ganadora.
4. El primer jugador ahora puede adoptar la siguiente estrategia. Hacen un movimiento arbitrario. Después juegan la estrategia ganadora del segundo jugador asumida arriba. Si al jugar esta estrategia, están obligados a jugar en la celda donde se hizo un movimiento arbitrario, hacen otro movimiento arbitrario. De esta manera juegan la estrategia ganadora con una pieza extra siempre en el tablero.
5. Esta pieza extra no puede interferir con la imitación del primer jugador de la estrategia ganadora, ya que una pieza extra es siempre un activo y nunca un impedimento. Por lo tanto, el primer jugador puede ganar.
6. Debido a que ahora hemos contradicho nuestra suposición de que hay una estrategia ganadora para el segundo jugador, concluimos que no hay estrategia ganadora para el segundo jugador.
7. En consecuencia, debe haber una estrategia ganadora para el primer jugador.

Complejidad computacional

En 1976, Shimon Even y Robert Tarjan demostraron que determinar si una posición en un juego de hexadecimal generalizado jugado en gráficos arbitrarios es una posición ganadora es PSPACE-completo. Reisch demostró un fortalecimiento de este resultado al reducir el problema de la fórmula booleana cuantificada en forma normal conjuntiva a Hex. En la teoría de la complejidad computacional, se conjetura ampliamente que los problemas completos de PSPACE no se pueden resolver con algoritmos eficientes (tiempo polinomial). Este resultado limita la eficiencia de los mejores algoritmos posibles al considerar posiciones arbitrarias en tableros de tamaño ilimitado, pero no descarta la posibilidad de una estrategia ganadora simple para la posición inicial (en tableros de tamaño ilimitado), o una estrategia ganadora simple para todas las posiciones en un tablero de un tamaño particular.

Árbol de juego de 11 por 11 Hex

En 11×11 Hex, hay aproximadamente 2,4×10⁵⁶ posiciones legales posibles; esto se compara con 4,6 × 10⁴⁶ posiciones legales en el ajedrez.

Estrategias computarizadas para tableros más pequeños

En 2002, Jing Yang, Simon Liao y Mirek Pawlak encontraron una estrategia ganadora explícita para el primer jugador en tableros Hex de tamaño 7×7 utilizando un método de descomposición con un conjunto de patrones locales reutilizables. Extendieron el método para resolver débilmente el par central de aberturas topológicamente congruentes en tableros de 8×8 en 2002 y la abertura central en tableros de 9×9 en 2003. En 2009, Philip Henderson, Broderick Arneson y Ryan B. Hayward completaron el análisis de el tablero de 8×8 con una búsqueda por ordenador, resolviendo todas las aperturas posibles. 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. Para cada N≤10, un primer movimiento ganador en N×N Hex es el más central, lo que sugiere la conjetura de que esto es cierto para cada N≥1.

Variantes

Otros juegos de conexión con objetivos similares pero estructuras diferentes incluyen el juego de cambio de Shannon y TwixT. Ambos tienen cierto grado de similitud con el antiguo juego asiático de Go.

Cuadrículas rectangulares y papel y lápiz

El juego se puede jugar en una cuadrícula rectangular como un tablero de ajedrez, damas o go, considerando que los espacios (intersecciones en el caso de go) están conectados en una dirección diagonal pero no en la otra. El juego se puede jugar con papel y lápiz en una matriz rectangular de puntos o papel cuadriculado de la misma manera usando dos lápices de diferentes colores.

Tamaños de tablero

Las dimensiones populares distintas del estándar 11x11 son 13x13 y 19x19 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) abogó por 14×14 como el tamaño óptimo.

Rex (hexágono inverso)

La variante misère de Hex. 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 las mismas dimensiones, la jugada perdedora puede retrasar una pérdida hasta que se llene todo el tablero. En tableros con dimensiones desiguales, el jugador cuyos lados están más separados puede ganar sin importar quién juegue primero. En tableros de iguales dimensiones, el primer jugador puede ganar en un tablero con un número par de celdas por lado, y el segundo jugador puede ganar en un tablero con un número impar. En tableros con un número par, uno de los movimientos ganadores del primer jugador siempre es colocar una piedra en la esquina aguda.

Éxitos de taquilla

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 solitario podría conectarse de arriba a abajo en 4 movimientos, mientras que el equipo de dos podría conectarse de izquierda a derecha en 5 movimientos.

Y

El juego de Y es Hex se juega en una cuadrícula triangular de hexágonos; el objetivo es que cualquiera de los jugadores 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.

La Habana

Havannah es un juego basado en Hex. Se diferencia de Hex en que se juega en una cuadrícula hexagonal de hexágonos y se logra una victoria formando uno de tres patrones.

Proyecto

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. Al igual que en Hex, no hay empates y no hay una posición en la que ambos jugadores tengan una conexión ganadora.

Competencia

A partir de 2016, se informaron torneos over-the-board de Brasil, República Checa, Dinamarca, Francia, Alemania, Italia, Países Bajos, Noruega, Polonia, Portugal, España, Reino Unido y Estados Unidos. Una de las mayores competencias de Hex está organizada por el Comité Internacional de Juegos Matemáticos en París, Francia, que se lleva a cabo anualmente desde 2013. Hex también forma parte de la Olimpiada Informática.