Hex (juego)

De Wikipedia, la enciclopedia libre
Hex

Hex - The Zig-Zag Game - Parker Brothers - 1950
Jugadores 2-4
Preparación 1 minuto
Duración 15 minutos (en un tablero de 11x11)
Complejidad Media
Estrategia Alta
Azar Ninguno
Habilidades Táctica, estrategia, posición
[editar datos en Wikidata]

Hex [1]​ es un juego de mesa abstracto de estrategia para dos jugadores en el que los jugadores intentan conectar los lados opuestos de un tablero con forma de rombo compuesto de celdas hexagonales. Hex fue inventado por el matemático y poeta Piet Hein en 1942 y más tarde redescubierto y popularizado por John Nash.

Tradicionalmente, se juega en un tablero de rombo de 11x11 celdas, aunque los tableros de 13x13 y 19x19 también son populares. 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 tratar de 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 logra conectar sus lados juntos 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 profundas bases matemáticas. El juego fue publicado 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ó en Dinamarca como un juego de mesa bajo el nombre de Con-tac-tix, y Parker Brothers comercializó una versión 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 hexagonal.

Historia[editar]

Fue inventado por el matemático danés Piet Hein[2]​ en 1942 y, de forma independiente, por el matemático John Forbes Nash a finales de los años 40.

El juego fue redescubierto en 1948 o 1949 por el matemático John Nash en la Universidad de Princeton.[3]​[4]​ Según Martin Gardner, quien presentó Hex en su columna "Juegos Matemáticos" de julio de 1957, los compañeros de juego de Nash llamaban al juego Nash o John, siendo este último nombre una referencia al hecho de que el juego podía jugarse con baldosas hexagonales de baño.[3]​ Nash insistió en que descubrió el juego de forma independiente a Hein, pero existe cierta duda al respecto, ya que se sabe que había daneses, incluido Aage Bohr, que jugaban Hex en Princeton en la década de 1940, por lo que Nash podría haber captado la idea de forma subconsciente. Hein escribió a Gardner en 1957 expresando su duda de que Nash descubriera Hex de forma independiente. Gardner no pudo verificar ni refutar independientemente la afirmación de Nash.[5]​ Gardner escribió en privado a Hein: "Lo discutí con el editor, y decidimos que lo caritativo era darle a Nash el beneficio de la duda. ... El hecho de que inventaste el juego antes que nadie es indiscutible. Cualquier número de personas puede llegar después y decir que pensaron en lo mismo en una fecha posterior, pero esto significa poco y a nadie le importa realmente".[6]​: 134  En una carta posterior a Hein, Gardner añadió: "Solo entre tú y yo, y sin que quede registrado, creo que acertaste cuando te referiste a un 'destello de una sugerencia' que llegó al Sr. Nash desde una fuente danesa, y que más tarde olvidó. Parece la explicación más probable."[6]​: 136 

Reglas[editar]

Diagrama de un tablero de hex de tamaño 11x11 sin ninguna casilla ocupada. Se distinguen con distinto color los laterales.
Diagrama de un tablero de hex de tamaño 11x11 con una partida terminada. Las negras han formado una línea que conecta sus laterales (sombreados en negro) y ganan.

Inicialmente el tablero está vacío. A cada jugador se le asigna un color de fichas y dos laterales opuestos del tablero que tendrá que intentar conectar con sus fichas siguiendo las reglas del juego.

Los jugadores van colocando fichas por turnos sobre el tablero en casillas desocupadas.

Gana el primer jugador que consigue formar una línea de sus fichas que conecte sus dos laterales. No son posibles los empates.

Generalmente se añade una regla adicional para contrarrestar la ventaja que supone el mover en primer lugar. Consiste en que el segundo jugador en mover puede decidir en ese turno intercambiar los colores o no. Si los intercambia, la primera ficha colocada pasa a ser su primera ficha y el jugador que movió en primer lugar vuelve a mover, pero ahora con los nuevos colores; si no, la partida continúa normalmente. Sólo es posible decidir el intercambio de colores en ese turno.

El tablero[editar]

El tablero es un rombo formado por hexágonos, los dos lados opuestos del rombo esta indicados en un mismo color, el número de hexágonos es variable, si bien suele rondar los diez por lado.

En la figura se pueden ver cuarto ejemplos de tablero de 9, 10, 11 y 12 hexágonos por lado.

Las fichas[editar]

Las fichas son de un color por jugador, y del mismo color que los lados opuestos del rombo. En el ejemplo se puede ver dos lados del tablero de color rojo y los otros dos lados de color verde, las fichas son de ese mismo color.

Cada ficha se coloca por orden en uno de los hexágonos del tablero, y una vez colocada no se puede mover.

Tipo de juego[editar]

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 los juegos de conexión.[6]​ Puede ser clasificado como un juego de Maker-Breaker,[6]​: 122  un tipo particular de juego posicional. Debido a que el juego nunca puede terminar en empate,[6]​: 99 , Hex es también un juego determinado.

Hex es un caso especial de la versión "nodo" del juego de conmutación de Shannon.

Teoría matemática[editar]

Determinación[editar]

No es difícil demostrar que Hex no puede terminar en empate, es decir, no importa cómo se llene el tablero con piedras, siempre habrá un único jugador que ha conectado sus bordes. Este hecho fue 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.[6]​: 29 Hein también afirmó este hecho como "una barrera para tu oponente es una conexión para ti".[6]​: 35  John Nash escribió una demostración de este hecho alrededor de 1949,[7]​ pero aparentemente no publicó la demostración. Su primera exposición aparece en un informe técnico interno en 1952,[8]​ en el que Nash afirma que "la conexión y el bloqueo del oponente son actos equivalentes". Una demostración más rigurosa fue publicada por John R. Pierce en su libro de 1961 Symbols, Signals, and Noise.[9]​ En 1979, David Gale publicó una demostración que también mostraba que podía usarse para demostrar el teorema del punto fijo de Brouwer en dos dimensiones, y que la determinación de variantes de mayor dimensión demuestra el teorema del punto fijo en general.[10]​

Estrategia ganadora del primer jugador[editar]

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 demostrar que el primer jugador siempre puede ganar en teoría, es decir, si pudiera ver el final de todas las posibles líneas de juego".[6]​: 42 

Todas las pruebas conocidas de este hecho son no 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.[3]​ La prueba funciona para varios juegos, incluido Hex, y se ha denominado el argumento de robo de estrategia.

Dado que es imposible que el juego termine en un empate (ver arriba), o el primer o el segundo jugador deben ganar. Como Hex es un juego de información perfecta, debe haber una estrategia ganadora para el primer o el segundo jugador. Supongamos que el segundo jugador tiene una estrategia ganadora. Ahora el primer jugador puede adoptar la siguiente estrategia. Hacen un movimiento arbitrario. A partir de entonces, juegan la estrategia ganadora del segundo jugador asumida anteriormente. Si al jugar esta estrategia, se les exige 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. Esta pieza extra no puede interferir con la imitación de la estrategia ganadora del primer jugador, ya que una pieza extra siempre es una ventaja[aclaración requerida] y nunca una desventaja. Por lo tanto, el primer jugador puede ganar. Debido a que ahora hemos contradicho nuestra suposición de que hay una estrategia ganadora para el segundo jugador, concluimos que no hay una estrategia ganadora para el segundo jugador. En consecuencia, debe haber una estrategia ganadora para el primer jugador.

Complejidad computacional[editar]

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.[11]​ Reisch demostró una versión más fuerte de este resultado al reducir el problema de fórmula booleana cuantificada en forma normal conjuntiva a Hex.[12]​ En la teoría de la complejidad computacional, se cree ampliamente que los problemas PSPACE-completos no pueden resolverse con algoritmos eficientes (de tiempo polinómico). Este resultado limita la eficiencia de los algoritmos posibles cuando se consideran 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.

La máquina Hex de Shannon[editar]

Alrededor de 1950, Claude Shannon y E. F. Moore construyeron una máquina analógica para jugar Hex, que era esencialmente una red de resistencias con resistores para las aristas y bombillas para los vértices.[13]​ El movimiento a realizar correspondía a un punto de silla especificado en la red. La máquina jugaba un juego de Hex razonablemente bueno. Más tarde, los investigadores que intentaban resolver el juego y desarrollar algoritmos para computadoras para jugar Hex emularon la red de Shannon para crear jugadores de computadora fuertes.[14]​

Véase también[editar]

Enlaces externos[editar]

Referencias[editar]

  1. ↑ VV.AA (2003). ENCICLOPEDIA DE LOS JUEGOS (1 edición). Editorial Paidotribo. p. 341. 
  2. ↑ Ferrero de Pablo, Luis (1991). El juego y la matemática. Aula abierta (5 edición). Editorial La Muralla. 
  3. ↑ a b c Gardner, M. (1959). The Scientific American Book of Mathematical Puzzles & Diversions. N.Y., N.Y.: Simon and Schuster. pp. 73–83. ISBN 0-226-28254-6. (requiere registro). 
  4. ↑ Nasar, Sylvia (13 de noviembre de 1994). «The Lost Years of a Nobel Laureate». The New York Times. Consultado el 23 de agosto de 2017. 
  5. ↑ Hayward, Ryan B.; Toft, Bjarne (2019). Hex, inside and out : the full story. Boca Raton, Florida: CRC Press. pp. 127-138. ISBN 978-0367144258. 
  6. ↑ a b c d e f g h Hayward, Ryan B.; Toft, Bjarne (2019). Hex, Inside and Out: The Full Story. CRC Press. 
  7. ↑ Hayward, Ryan B.; Rijswijck, van, Jack (6 de octubre de 2006). «Hex and combinatorics». Discrete Mathematics 306 (19–20): 2515-2528. doi:10.1016/j.disc.2006.01.029. 
  8. ↑ Nash, John (feb. de 1952). Rand Corp. informe técnico D-1164: Some Games and Machines for Playing Them. https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf Archivado el 21 de enero de 2017 en Wayback Machine.
  9. ↑ Hayward, Ryan B.; Toft, Bjarne (2019). Hex, inside and out : the full story. Boca Raton, Florida: CRC Press. p. 99. ISBN 978-0367144258. 
  10. ↑ David Gale (1979). «The Game of Hex and Brouwer Fixed-Point Theorem». The American Mathematical Monthly (Mathematical Association of America) 86 (10): 818-827. JSTOR 2320146. doi:10.2307/2320146. 
  11. ↑ Even, S.; Tarjan, R. E. (1976). «A Combinatorial Problem Which is Complete in Polynomial Space». Journal of the ACM 23 (4): 710-719. S2CID 8845949. doi:10.1145/321978.321989. 
  12. ↑ Stefan Reisch (1981). «Hex ist PSPACE-vollständig (Hex is PSPACE-complete)». Acta Informatica 15 (2): 167-191. S2CID 9125259. doi:10.1007/bf00288964. 
  13. ↑ Shannon, C. (1953). «Computers and Automata». Proceedings of the Institute of Radio Engineers 41 (10): 1234-41. S2CID 51666906. doi:10.1109/jrproc.1953.274273. 
  14. ↑ Anshelevich, V. (2002). A Hierarchical Approach to Computer Hex.
Obtenido de «https://es.wikipedia.org/w/index.php?title=Hex_(juego)&oldid=159535091»