Habana (juego de mesa)

Ejemplos de las tres estructuras ganadoras en Havannah, en un tablero base-8. De izquierda a derecha, son los tenedor, el anillo y el puente.

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, 10 celdas hexagonales por lado.

El juego fue publicado durante un tiempo en Alemania por Ravensburger, con un tablero de base 8 más pequeño adecuado para principiantes. Hoy en día solo lo produce Hexboards.

Reglas del juego

Un jugador juega con negras; 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 o cambian de otra manera.
• Un jugador gana cuando completa una de las tres estructuras diferentes de líneas no rotas, o caminos, de piedras conectadas, todo su color:
  • A anillo es un bucle alrededor de una o más células (no importa si las células circunscritas están ocupadas por cualquier jugador o vacías);
  • A puente, que conecta cualquiera de las seis celdas de la junta;
  • A tenedor, que conecta los tres bordes de la tabla; los puntos de esquina no se consideran partes de un borde.

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 en moverse en Havannah tiene una clara ventaja, la regla del pastel generalmente se implementa por equidad. 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.

Los jugadores de diferente fuerza aún pueden jugar un juego interesante cuando al jugador más débil (como el blanco) se le permite colocar dos o más piedras en el primer turno.

Diferencia en comparación con hexadecimal

En Hex, cuando el tablero esté completamente lleno, exactamente un jugador tendrá una conexión ganadora; en Havannah, un tablero completamente lleno suele tener 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, 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 Habana

En 2002, Freeling ofreció un premio de 1000 euros, disponible hasta 2012, por cualquier programa de computadora que pudiera vencerlo en un solo juego de un partido de diez juegos. Durante muchos años, los programas de computadora 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 árbol de Monte Carlo, 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 juego Havannah más fuertes disponibles, jugando (al menos) un juego con negras y otro 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 seguían siendo 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 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 del tamaño de la placa gracias a redes neuronales totalmente convolucionales (como en U-Net) y agrupación global. Esto permite arquitecturas en crecimiento, 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 circulares para representar el gráfico geográfico. En detalle, dado que Lichtenstein y Sipser han demostrado que la geografía generalizada siguió siendo PSPACE-hard incluso si el gráfico es solo bipartito y de grado máximo 3, solo queda construir una posición de Havannah equivalente a partir de dicho gráfico, lo que se logra mediante la construcción de varios aparatos en La Habana.

Reseñas

• Jeux " Stratégie #9