Brotes (juego)

Sprouts es un juego de papel y lápiz que se puede analizar por sus propiedades matemáticas. Fue inventado por los matemáticos John Horton Conway y Michael S. Paterson en la Universidad de Cambridge a principios de la década de 1960. La configuración es incluso más sencilla que la del popular juego Dots and Boxes, pero el juego se desarrolla de forma mucho más artística y orgánica.

Reglas

Un juego de 2 puntos de Sprouts. El juego termina cuando el primer jugador es incapaz de dibujar una línea de conexión entre los únicos dos puntos libres, marcados en verde.

El juego lo juegan dos jugadores, comenzando con algunos puntos dibujados en una hoja de papel. Los jugadores toman turnos, donde cada turno consiste en dibujar una línea entre dos puntos (o desde un punto hacia sí mismo) y agregar un nuevo punto en algún lugar a lo largo de la línea. Los jugadores están limitados por las siguientes reglas.

• La línea puede ser recta o curvada, pero no debe tocarse ni cruzarse ni ninguna otra línea.
• El nuevo punto no se puede colocar encima de uno de los puntos finales de la nueva línea. Así el nuevo punto divide la línea en dos líneas más cortas.
• Ningún lugar puede tener más de tres líneas adjuntas a él. Para los propósitos de esta regla, una línea desde el punto a sí misma cuenta como dos líneas adjuntas y nuevos puntos se cuentan como tener dos líneas ya conectadas a ellos.

En el llamado juego normal, gana el jugador que hace el último movimiento. En misère play, el jugador que hace el último movimiento pierde. Misère Sprouts es quizás el único juego combinatorio de misère que se juega de forma competitiva en un foro organizado.

El diagrama de la derecha muestra un juego de 2 puntos de Sprouts de juego normal. Después del cuarto movimiento, la mayoría de los puntos están muertos: tienen tres líneas adjuntas, por lo que no se pueden usar como puntos finales para una nueva línea. Hay dos puntos (que se muestran en verde) que todavía están vivos, con menos de tres líneas adjuntas. Sin embargo, es imposible hacer otro movimiento, porque una línea desde un punto vivo hacia sí mismo haría cuatro conexiones, y una línea desde un punto vivo al otro cruzaría líneas. Por lo tanto, no es posible un quinto movimiento y el primer jugador pierde. Los puntos en vivo al final del juego se denominan supervivientes y juegan un papel clave en el análisis de Sprouts.

Número de movimientos

No es evidente a partir de las reglas de Sprouts que el juego siempre termine, ya que el número de puntos aumenta en cada movimiento. El enfoque correcto es considerar el número de vidas (oportunidades para conectar una línea) en lugar del número de puntos. Entonces, se puede demostrar que si el juego comienza con n puntos, terminará en no más de 3n−1 movimientos y no menos de 2n se mueve.

En las siguientes pruebas, se supone que un juego comienza con n puntos y dura exactamente m movimientos.

Número máximo de movimientos

Un juego de brotes con n puntos iniciales (en azul) que termina en 3n−1 movimientos

Cada lugar comienza con tres vidas y cada movimiento reduce el número total de vidas en el juego en uno (se pierden dos vidas al final de la línea, pero el nuevo lugar tiene una vida). Así que al final del juego hay 3n−m vidas restantes. Cada lugar sobreviviente tiene solo una vida (de lo contrario, habría otro movimiento que uniría ese lugar), por lo que hay exactamente 3n−m supervivientes. Debe haber al menos un sobreviviente, es decir, el lugar agregado en el movimiento final. Entonces 3n−m ≥ 1; por lo tanto, un juego no puede durar más de 3n−1 movimientos.

Este límite superior es en realidad el máximo, y se puede lograr de muchas maneras asegurándose de que solo haya un sobreviviente al final del juego. Por ejemplo, el juego de la derecha tiene un sobreviviente y 3n−1 movimientos.

Lugares vivos (verde) y sus vecinos muertos (negro)

Número mínimo de movimientos

Al final del juego, un punto muerto se llama vecino de un superviviente si está adyacente a ese superviviente o, si el superviviente tiene un bucle, está junto a un punto adyacente al sobreviviente. Esto se ilustra en el diagrama de la derecha. Cada superviviente tiene exactamente dos vecinos muertos. Ningún punto muerto puede ser vecino de dos sobrevivientes diferentes, pues de lo contrario habría un movimiento que uniría a los sobrevivientes. Todos los demás puntos muertos (no vecinos de un sobreviviente) se llaman fariseos (del hebreo para "separados"). Supongamos que hay p fariseos. Después

n+m=3n− − m+2()3n− − m)+p{displaystyle n+m=3n-m+2(3n-m)+p}

desde los puntos iniciales + movimientos = puntos totales al final del juego = supervivientes + vecinos + fariseos. Reordenando da:

m=2n+p/4{displaystyle m=2n+p/4}

En consecuencia, un juego dura al menos 2n movimientos, y el número de fariseos es divisible por 4.

Un juego de brotes con n puntos iniciales que terminan en 2n movimientos

Este límite inferior de la duración de un juego es en realidad el mínimo. El diagrama de la derecha muestra un juego completo de 2n movimientos. Tiene n sobrevivientes, 2n vecinos y 0 fariseos.

Importancia en juegos reales

Los juegos reales parecen convertirse en una batalla sobre si el número de movimientos será k o k+1 con otras posibilidades bastante improbables. Un jugador intenta crear regiones cerradas que contengan sobrevivientes (reduciendo así el número total de movimientos que se jugarán) y el otro intenta crear fariseos (aumentando así el número de movimientos que se jugarán).

Estrategias ganadoras

Dado que Sprouts es un juego finito en el que no es posible dibujar, existe una estrategia perfecta para el primer o el segundo jugador, según el número de posiciones iniciales. La pregunta principal sobre una posición de inicio determinada es determinar qué jugador puede forzar una victoria si juega perfectamente.

Cuando la estrategia ganadora es para el primer jugador, se dice que el resultado de la posición es "ganar", y cuando la estrategia ganadora es para el segundo jugador, se dice que el resultado de la posición es una "pérdida" (porque es una pérdida desde el punto de vista del primer jugador).

El resultado se determina desarrollando el árbol de juego de la posición inicial. Esto se puede hacer a mano solo para una pequeña cantidad de puntos, y todos los nuevos resultados desde 1990 se han obtenido mediante una búsqueda exhaustiva con computadoras.

Versión normal

Winning Ways for your Mathematical Plays informa que Denis Mollison demostró que el juego normal de 6 puntos era una victoria para el segundo jugador, con un análisis hecho a mano de 47 páginas. Permaneció como récord durante mucho tiempo, hasta el primer análisis por computadora, realizado en la Universidad Carnegie Mellon, en 1990, por David Applegate, Guy Jacobson y Daniel Sleator. Alcanzaron hasta 11 lugares con algunos de los mejores hardware disponibles en ese momento.

Applegate, Jacobson y Sleator observaron un patrón en sus resultados y conjeturaron que el primer jugador tiene una estrategia ganadora cuando el número de puntos dividido por seis deja un resto de tres, cuatro o cinco. Esta es una forma matemática de decir que el patrón mostrado por el resultado en la siguiente tabla se repite indefinidamente, con un período de seis puntos.

En 2001, Riccardo Focardi y Flamina Luccio describieron un método para demostrar a mano que el juego normal de 7 puntos es una pérdida.

Luego, Josh Jordan amplió los resultados del cómputo en 2006 hasta 14 puntos. En 2007, Julien Lemoine y Simon Viennot introdujeron un algoritmo basado en el concepto de nimbers para acelerar el cálculo, llegando hasta 32 puntos. Han ampliado el cómputo hasta 44 plazas en 2011, y tres puestos de salida aislados, con 46, 47 y 53 plazas.

Todos los resultados del juego normal hasta ahora son consistentes con la conjetura de Applegate, Jacobson y Sleator.

Versión Misère

El historial de cálculo de la versión misère de Sprouts es muy similar al de la versión normal, con las mismas personas involucradas. Sin embargo, la versión misère es más difícil de calcular y el progreso ha sido significativamente más lento.

En 1990, Applegate, Jacobson y Sleator alcanzaron hasta nueve puestos. Con base en sus resultados, conjeturaron que el resultado sigue un patrón regular del período cinco. Sin embargo, esta conjetura fue invalidada en 2007 cuando Josh Jordan y Roman Khorkov ampliaron el análisis de misère hasta 12 puntos: el juego de misère de 12 puntos es una victoria, y no la pérdida conjeturada. El mismo equipo alcanzó hasta 16 lugares en 2009. El mismo año, Julien Lemoine y Simon Viennot alcanzaron 17 lugares con algoritmos complicados. Pudieron ampliar su análisis hasta 20 puntos en 2011.

Ahora se conjetura que los resultados del juego misère siguen un patrón de longitud seis (con algunos valores excepcionales): el primer jugador gana en misère Sprouts cuando el resto (mod 6) es cero, cuatro o cinco, excepto que el el primer jugador gana el juego de un punto y pierde el juego de cuatro puntos. La siguiente tabla muestra el patrón, con los dos valores irregulares en negrita.

Coles de Bruselas

Un juego de 2 cruces de Bruselas Sprouts siempre dura exactamente ocho movimientos

Una variante del juego, llamada Coles de Bruselas por la verdura crucífera, comienza con una serie de cruces, es decir, puntos con cuatro extremos libres. Cada movimiento implica unir dos extremos libres con una curva, nuevamente sin cruzar ninguna línea existente, y luego aplicar un trazo corto a través de la línea para crear dos nuevos extremos libres. Este juego es finito y el número total de movimientos (y, por lo tanto, el ganador del juego) está predeterminado por el número inicial de cruces: los jugadores no pueden afectar el resultado con su juego.

Cada movimiento elimina dos extremos libres e introduce dos más. Con n cruces iniciales, el número de movimientos será 5n − 2, por lo que un juego que comience con un número impar de cruces será una victoria del primer jugador, mientras que un juego Comenzar con un número par será una victoria del segundo jugador, independientemente de los movimientos.

Para probar esto (asumiendo que el juego termina), denotemos con m el número de movimientos y v, e, f denota el número de vértices, aristas y caras del gráfico plano obtenido al final del juego, respectivamente. Tenemos:

• e = 2m desde cada movimiento, el jugador añade 2 bordes.
• v = n + m desde cada movimiento, el jugador añade un vértice y el juego comienza con n vertices.
• f = 4n ya que hay exactamente un extremo libre en cada cara al final del juego, y el número de cabos libres no cambia durante el juego.

La característica de Euler para grafos planos es 2, por lo que

2=f− − e+v=4n− − 2m+n+m=5n− − m{displaystyle 2=f-e+v=4n-2m+n=5n-m}

por lo tanto

m=5n− − 2{displaystyle m=5n-2}

También se puede jugar una combinación de coles estándar y coles de Bruselas. El juego comienza con un número arbitrario (n) de puntos o cruces. En cada turno, el jugador elige agregar un punto o una cruz a lo largo de la línea que acaba de dibujar. La duración del juego está entre (2n) y (5n - 2), dependiendo del número de puntos o cruces que se hayan añadido.

Para n = 1 que comienza con un punto, el juego terminará después de 2 movimientos. Comenzando con una cruz, terminará después de 2 movimientos si el primer jugador agrega un punto, después de 3 movimientos si agrega una cruz: por lo tanto, el primer jugador tiene una estrategia ganadora tanto para la versión normal como para la misère. Para n > 1 el análisis no está completo.