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. [1]
El juego fue publicado durante un tiempo en Alemania por Ravensburger , con un tablero más pequeño, de base 8, adecuado para principiantes. En la actualidad, solo lo produce Hexboards. [2]
Un jugador juega con las negras y el otro con las blancas. Las blancas empiezan y después se van alternando los movimientos. Las reglas son las siguientes:
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 un tenedor; la estructura del lado derecho es un puente.
Dado que el primer jugador que mueve en Havannah tiene una clara ventaja, generalmente se aplica la regla del pastel para que haya equidad. Esta regla permite que el segundo jugador elija si cambia de posición con el primer jugador después de que este último haga el primer movimiento. [4]
Los jugadores de diferente fuerza aún pueden jugar una partida interesante cuando al jugador más débil (como las blancas) se le permite colocar dos o más piedras en el primer turno.
En Hex, cuando el tablero está completamente lleno, exactamente un jugador tendrá una conexión ganadora; en Havannah, un tablero completamente lleno tendrá generalmente más de una estructura ganadora (pero el juego termina con la primera estructura ganadora).
A diferencia de Hex, en Havannah los empates son técnicamente posibles, pero en la práctica son extremadamente raros. Se ha conocido un empate entre jugadores humanos. [5] Las tácticas son mucho más fáciles de dominar que la estrategia y las diferencias en el nivel de juego son considerables.
En 2002, Freeling ofreció un premio de 1000 euros, disponible hasta 2012, para cualquier programa informático que pudiera vencerlo en al menos una partida de un partido de diez partidas. Durante muchos años, los programas informáticos se quedaron muy por detrás de los jugadores humanos. Sin embargo, desde 2010, varios programas que juegan a Havannah han aplicado técnicas de búsqueda de árboles de Monte Carlo, lo que dio como resultado una mejora notable en la fuerza de juego. El "Desafío Havannah 2012" se celebró del 15 al 19 de octubre de 2012, durante el cual Freeling jugó diez partidas contra tres de los programas que juegan a Havannah más fuertes disponibles, jugando (al menos) una partida con negras y una con blancas contra cada oponente. [6] Freeling perdió el desafío cuando tuvo que rendirse en una partida con blancas contra el programa Lajkonik.
Hasta 2019, los mejores humanos seguían siendo mucho más fuertes que los ordenadores. Sin embargo, MetaTotoro, basado en Polygames [7] (un proyecto de código abierto, desarrollado inicialmente por Facebook Artificial Intelligence Research y varias universidades [8] ), ganó cuatro veces seguidas en el tablero de tamaño 8 contra el jugador humano con el mejor ranking ELO en LittleGolem, que también fue el ganador de varios torneos.
Este resultado se logró con el mismo programa que se utilizó para vencer a los mejores humanos en Hex . Es un algoritmo basado en aprendizaje cero, como AlphaZero, pero con novedades: invariancia del tamaño de la placa gracias a redes neuronales completamente convolucionales (como en U-Net) y agrupamiento global. Esto permite arquitecturas en crecimiento, lo que significa que el programa puede aprender en una placa pequeña y luego extrapolar a una placa grande. [9]
Havannah es un juego recurrente en las Olimpiadas de Computadoras . Se juega en un tablero de base 8 y, a veces, también en un tablero de base 10. Durante esta competencia se utiliza la regla del pastel.
La solución de Havannah es PSPACE-completa con respecto al tamaño del grafo de entrada. [10] La prueba es mediante una reducción a partir de la geografía generalizada y se basa en el uso de amenazas de anillo para representar el grafo de geografía. En detalle, dado que Lichtenstein y Sipser han demostrado que la geografía generalizada sigue siendo PSPACE-difícil incluso si el grafo es solo bipartito y de grado como máximo 3 , solo queda construir una posición de Havannah equivalente a partir de dicho grafo, lo que se logra construyendo varios dispositivos en Havannah.