Join five (también conocido como solitario morpion, cross 'n' lines o juego de línea ) es un juego de papel y lápiz para uno o dos jugadores, que se juega en una cuadrícula de puntos con forma de cruz. Los orígenes del juego se encuentran probablemente en el norte de Europa. Las primeras referencias al juego aparecieron en publicaciones francesas en la década de 1970. [1] Además de jugarse de forma recreativa, el juego ha sido objeto de estudios teóricos [2] y búsquedas de soluciones por ordenador. [3]
Se dibuja una cuadrícula inicial de puntos: un cuadrado de 4x4 puntos, con un rectángulo de 4x3 añadido a cada lado. La cruz inicial está delineada en algunas versiones del juego.
En cada turno, dibuja una línea recta que tenga exactamente cinco "puntos" de largo, de modo que:
En otras palabras, haz una línea de cinco segmentos a partir de cuatro puntos y dibuja el quinto (a menos que lo guardes para dibujar dos puntos en turnos posteriores).
El juego termina cuando no se pueden dibujar más segmentos en la cuadrícula.
En la versión para dos jugadores, el último jugador que dibuje un segmento de línea es el ganador. En la versión para un jugador, la puntuación se logra contando la cantidad de segmentos dibujados o calculando el área total de la cuadrícula al final del juego.
En la versión esquemática, el número de turnos completados es el puntaje. Esto generalmente se controla mediante el uso de marcas de conteo . No se sabe si esto puede continuar indefinidamente, pero el juego se vuelve progresivamente más difícil (¿hasta cierto punto?) una vez que se ha utilizado por completo la cuadrícula inicial.
La estrategia difiere según se juegue en solitario o contra un oponente. En el primer caso, se optimizan los movimientos para el máximo número de turnos posibles; en el segundo, el objetivo es ser "ineficiente" con la selección de movimientos para limitar los movimientos disponibles del oponente.
Las reglas pueden variar y exigir líneas de 4 puntos marcados en fila en lugar de 5, con una configuración inicial reducida. Además, la variante "disjunta" del juego no permite que dos líneas paralelas compartan un punto final, mientras que la versión estándar "en contacto" sí lo permite. [4]
Para la versión "tocando" del juego con líneas que consisten en 5 puntos marcados, el récord actual de 178 líneas se estableció el 12 de agosto de 2011, utilizando una búsqueda de Montecarlo por el algorítmico Christopher Rosin. [5] [6] Esto es ocho movimientos más que el récord anterior de 1976 de 170 líneas. [3] [5] [7] El récord de 1976 se hizo a mano, y las búsquedas por computadora no habían podido acercarse a este récord [7] a pesar del progreso sustancial, [8] hasta agosto de 2010, cuando Christopher Rosin utilizó una búsqueda de Montecarlo para obtener un resultado de 172 movimientos, superando el récord de 1976, y 178 movimientos un año después. [6]
Para la versión "disjunta" del juego con líneas que constan de 5 puntos marcados, se ha obtenido el récord de 82 líneas [9] mediante una búsqueda por ordenador, también hallado por Christopher Rosin. El récord anterior de 80 líneas lo encontró Tristan Cazenave en 2008. [10] En 2020 se encontró una solución de 67 pasos utilizando un enfoque similar a AlphaZero . [11]
El solitario morpión generalizado, en el que la configuración inicial puede ser cualquier conjunto finito de puntos marcados, es un miembro de la clase de problemas NP-difíciles para los que no se conoce ningún método computacional eficiente para encontrar una solución óptima. Incluso el problema de encontrar una solución aproximadamente óptima para el solitario morpión generalizado es NP-difícil. [2]
Para las versiones estándar del solitario morpión no existen soluciones infinitamente grandes; se han demostrado límites superiores [2] para el número máximo de líneas que se pueden obtener. [12]