Havannah - Havannah
Havannah es un juego de mesa de estrategia abstracta para dos jugadores inventado por Christian Freeling . Pertenece a la familia de juegos comúnmente llamados juegos de conexión ; sus parientes incluyen Hex y TwixT . Havannah tiene "una estrategia sofisticada y variada" y se juega mejor en un tablero hexagonal de base 10, con 10 casillas hexagonales por lado.
El juego fue publicado durante un período en Alemania por Ravensburger , con un tablero de base 8 más pequeño adecuado para principiantes. Hoy en día solo es producido por Hexboards.
Reglas del juego
Un jugador juega como negro; el otro juega como blanco. Las blancas comienzan, después de lo cual se alternan los movimientos. Las reglas son las siguientes:
- Cada jugador coloca una piedra de su color en el tablero por turno.
- Las piedras nunca se mueven, capturan ni cambian de ninguna otra manera.
- Un jugador gana cuando completa una de las tres estructuras diferentes de líneas o caminos continuos de piedras conectadas, todas de su color:
- Un anillo es un bucle alrededor de una o más celdas (sin importar si las celdas rodeadas están ocupadas por algún jugador o vacías);
- Un puente , que conecta dos de las seis celdas de las esquinas del tablero;
- Un tenedor , que conecta tres bordes de la tabla; los puntos de las esquinas no se consideran partes de una arista.
Arriba se muestra un ejemplo de las tres combinaciones ganadoras. La estructura en el centro del tablero es un anillo; la estructura del lado izquierdo es una bifurcación; la estructura del lado derecho es un puente.
Dado que el primer jugador que se mueve en Havannah tiene una clara ventaja, la regla del pastel generalmente se implementa por razones de equidad. Esta regla permite al segundo jugador elegir si cambiar de posición con el primer jugador después de que el primer jugador hace el primer movimiento.
Los jugadores de diferente fuerza aún pueden jugar un juego interesante cuando al jugador más débil (como las blancas) se le permite colocar dos o más piedras en el primer turno.
Diferencia en comparación con Hex
En Hex, cuando el tablero está completamente lleno, exactamente un jugador tendrá una conexión ganadora; en Havannah, un tablero completamente lleno normalmente tendrá más de una estructura ganadora (pero el juego termina con la primera estructura ganadora).
A diferencia de Hex, en Havannah los sorteos son técnicamente posibles, en la práctica son extremadamente raros. Ha habido un empate conocido entre jugadores humanos. Las tácticas son mucho más fáciles de dominar que la estrategia y las diferencias en el nivel de juego son considerables.
Computadora Havannah
En 2002, Freeling ofreció un premio de 1000 euros, disponible hasta 2012, por cualquier programa de computadora que pudiera vencerlo incluso en un juego de un partido de diez juegos. Durante muchos años, los programas informáticos quedaron muy por detrás de los jugadores humanos. Sin embargo, desde 2010, varios programas de juego de Havannah han aplicado técnicas de búsqueda de árboles de Montecarlo, lo que ha dado como resultado una mejora notable en la fuerza de juego. El "Havannah Challenge 2012" se llevó a cabo del 15 al 19 de octubre de 2012 durante el cual Freeling jugó diez juegos contra tres de los programas de Havannah más fuertes disponibles, jugando (al menos) un juego con negras y una con blancas contra cada oponente. Freeling perdió el desafío cuando tuvo que renunciar a un juego con blancas contra el programa Lajkonik.
Hasta 2019, los mejores humanos todavía eran mucho más fuertes que las computadoras. Sin embargo, MetaTotoro , basado en Polygames (un proyecto de código abierto, inicialmente desarrollado por Facebook Artificial Intelligence Research y varias universidades), ganó cuatro veces seguidas en el tablero de tamaño 8 contra el jugador humano con el mejor rango ELO en LittleGolem . quien también fue el ganador de varios torneos.
Este resultado se logró con el mismo programa que se usó para vencer a los mejores humanos en Hex . Es un algoritmo basado en aprendizaje cero, como en AlphaZero, pero con novedades: invariancia de tamaño de tablero gracias a redes neuronales totalmente convolucionales (como en U-Net) y pooling global. Esto permite el crecimiento de arquitecturas, lo que significa que el programa puede aprender en un tablero pequeño y luego extrapolar en un tablero grande.
Complejidad computacional
Resolver Havannah es PSPACE completo con respecto al tamaño del gráfico de entrada. La prueba es una reducción de la geografía generalizada y se basa en el uso de amenazas de anillo para representar el gráfico de geografía. En detalle, dado que Lichtenstein y Sipser han demostrado que la geografía generalizada sigue siendo PSPACE-hard incluso si el gráfico es solo bipartito y de grado como máximo 3 , solo queda construir una posición de Havannah equivalente a partir de dicho gráfico, lo cual se logra construyendo varios gadgets en La Habana.
Referencias
enlaces externos
- Sitio oficial MindSports.nl
- Artículo de Havannah sobre la biblioteca de Sensei
- Havannah en BoardGameGeek