Juego de la vida
El Juego de la vida es un autómata celular diseñado por el matemático británico John Horton Conway en 1970. Es un juego de cero jugadores, en el que su evolución es determinada por un estado inicial, sin requerir intervención adicional. Se considera un sistema Turing completo que puede simular cualquier otra Máquina de Turing.
Desde su publicación, ha atraído mucho interés debido a la gran variabilidad de la evolución de los patrones. Se considera que el Juego de la vida es un buen ejemplo de emergencia y autoorganización. Es interesante para científicos, matemáticos, economistas y otros observar cómo patrones complejos pueden provenir de la implementación de reglas muy sencillas.
El Juego de la vida tiene una variedad de patrones reconocidos que provienen de determinadas posiciones iniciales. Poco después de la publicación, se descubrieron el pentaminó R, el planeador o caminador (en inglés: glider, conjunto de células que se desplazan) y el explosionador (células que parecen formar la onda expansiva de una explosión), lo que atrajo un mayor interés hacia el juego. Contribuyó a su popularidad el hecho de que se publicó justo cuando se estaba lanzando al mercado una nueva generación de miniordenadores baratos, lo que significaba que se podía jugar durante horas en máquinas que, por otro lado, no se utilizarían por la noche.
Para muchos aficionados, el juego de la vida solo era un desafío de programación y una manera divertida de usar ciclos de la CPU.[1] Para otros, sin embargo, el juego adquirió más connotaciones filosóficas.
El juego
editarSe trata de un juego de cero jugadores, lo que quiere decir que su evolución está determinada por el estado inicial y no necesita ninguna entrada de datos posterior. El "tablero de juego" es una malla plana formada por cuadrados (las "células") que se extiende por el infinito en todas las direcciones. Por tanto, cada célula tiene 8 células "vecinas", que son las que están próximas a ella, incluidas las diagonales. Las células tienen dos estados: están "vivas" o "muertas" (o "encendidas" y "apagadas"). El estado de las células evoluciona a lo largo de unidades de tiempo discretas (se podría decir que por turnos). El estado de todas las células se tiene en cuenta para calcular el estado de las mismas al turno siguiente. Todas las células se actualizan simultáneamente en cada turno, siguiendo estas reglas:
- Nace: Si una célula muerta tiene exactamente 3 células vecinas vivas "nace" (es decir, al turno siguiente estará viva).
- Muere: una célula viva puede morir por uno de 2 casos:
- Sobrepoblación: si tiene más de tres vecinos alrededor.
- Aislamiento: si tiene solo un vecino alrededor o ninguno.
- Vive: una célula se mantiene viva si tiene 2 o 3 vecinos a su alrededor.
Estados finales
editarNormalmente, después de un determinado número de ciclos, se puede llegar a alguno de los siguientes estados finales:
Extinción: Al cabo de un número finito de generaciones desaparecen todos los miembros de la población o células vivas.
Estabilizacion: Al cabo de un número finito de generaciones la población queda estabilizada, ya sea de forma rígida o bien de forma oscilante entre dos o más formas
Crecimiento constante: La población crece turno tras turno y se mantiene así un número infinito de generaciones. En un principio esta evolución solo se contemplo de forma teórica, aunque más tarde se encontrarán patrones que crecían de forma indefinida, durante un número infinito de turnos.
Ejemplos de patrones
editarExisten numerosos tipos de patrones de células que pueden tener lugar en el juego de la vida.
Osciladores
editarLos osciladores son patrones que son predecesores de sí mismos. En otras palabras, son patrones que tras un número finito de generaciones vuelven a su estado inicial. El número de generaciones determina el período del oscilador. Se han descubierto osciladores de todos los períodos, pues hay reglas para generar osciladores de cualquier período deseado.
Los osciladores tienen un rotor y un estátor. El rotor son las células que cambian de estado en algún momento de la evolución del oscilador. El estátor son las células que permanecen vivas durante todas las fases de la evolución del oscilador. Así por ejemplo, en el caso del blinker, el más simple y frecuente de todos los osciladores, el estátor es la célula central, y el rotor son las células izquierda, derecha, arriba y abajo de la célula central.
Vidas estáticas
editarLas vidas estáticas son patrones que no cambian de una generación a la siguiente. Las vidas estáticas se puede considerar como osciladores de período 1. En general se asume que las vidas estáticas son finitas y no vacías. Se las puede dividir en vidas estáticas estrictas y pseudo vidas estáticas. Las vidas estáticas estrictas son aquellas cuyas partes no son estáticas por sí mismas.
Naves espaciales o planeadores
editarLas naves espaciales, también conocidas como planeadores, son patrones que reaparecen en otra posición tras completar su período. Esto es, son patrones que tras un número finito de generaciones vuelven a su estado original pero en una ubicación diferente. La velocidad de una nave es el número de celdas que se desplaza dividido por la longitud de su período. El máximo posible es una celda por generación, velocidad que se conoce como c (metafóricamente, la velocidad de la luz)
Matusalenes
editarLos matusalenes son patrones que pueden evolucionar a lo largo de muchos turnos, o generaciones, antes de estabilizarse. El patrón "Diehard desaparece después de 130 turnos, mientras que "Acorn" tarda 5206 turnos en estabilizarse en forma de muchos osciladores, y en ese tiempo genera 13 planeadores.
Diehard | Acorn |
En la aparición original del juego en la revista, Conway ofreció un premio de 50 dólares por el descubrimiento de patrones que crecieran indefinidamente. El primero fue descubierto por Bill Gosper en noviembre de 1970. Entre los patrones que crecen indefinidamente se encuentran los"cañones" (cannons), que son estructuras fijas en el espacio que generan planeadores u otras naves espaciales; "locomotoras" (puffers), que se mueven y dejan un rastro de basura y "rastrillos" (razors), que se mueven y emiten naves espaciales. Gosper descubrió posteriormente un patrón que crece cuadráticamente llamado "criadero" (breeder), que deja atrás un rastro de cañones. Desde entonces se han creado construcciones más complicadas, como puertas lógicas de planeadores, un sumador, un generador de números primos y una célula unidad que emula el juego de la vida a una escala mucho mayor y una velocidad menor.
El primer cañón de planeadores que se ha descubierto sigue siendo la más pequeña que se conoce:
Se han hallado posteriormente patrones más simples que también crecen indefinidamente. Los tres patrones siguientes crecen indefinidamente. Los dos primeros generan un motor interruptor que deja bloques, mientras que el tercero genera dos. El primero tiene una población mínima de 10 células vivas, el segundo cabe en un cuadrado 5 × 5 y el tercero solo tiene un cuadrado de altura:
Es posible que los planeadores interactúen con otros objetos de forma interesante. Por ejemplo, si se disparan dos planeadores hacia un bloque contra el que chocan de la forma correcta, el bloque se acercará al origen de los planeadores, pero si se disparan tres planeadores de forma correcta el bloque se alejará. Esta "memoria del bloque deslizante" se puede emplear para simular un contador. Es posible construir puertas lógicas AND (y, conjunción), OR (o, disyunción) y NOT (no, negación) mediante el uso de planeadores.
También se puede construir una estructura que actúe como una máquina de estados finitos conectada a dos contadores. Esto tiene la misma potencia computacional que una máquina universal de Turing, así que el juego de la vida es tan potente como un ordenador con memoria ilimitada: por ello es Turing-completo.
Además, una estructura puede contener un conjunto de pistolas que se combinen para construir nuevos objetos, incluso copias de la estructura original. Se puede construir un "constructor universal" que contenga un ordenador Turing-completo y que pueda generar muchos tipos de objetos complejos, incluso nuevas copias de sí mismo. (Vienen descripciones de estas construcciones en Winning Ways for your Mathematical Plays de Conway, Elwyn Berlekamp y Richard Guy)
Propiedades
editarOmniperiodicidad del Juego de la Vida
editarEn la teoría de los autómatas celulares, un oscilador es un patrón que se repite después de un número fijo de generaciones; ese número se llama su periodo. Un autómata celular se llama omniperiódico si existen osciladores de todos los periodos.
El Juego de la Vida de Conway es, con mucho, el autómata celular más famoso. Al comienzo del milenio, solo quedaban doce periodos de oscilador por encontrar: 19, 23, 27, 31, 34, 37, 38, 39, 41, 43, 51 y 53.
Durante las últimas décadas, estos periodos se fueron llenando gradualmente a medida que la velocidad de los ordenadores aumentaba y se aplicaban técnicas de búsqueda más ingeniosas.
Finalmente, la búsqueda ha terminado, con el descubrimiento de osciladores que tienen los dos últimos periodos, 19 y 41. Esto prueba que el Juego de la Vida es omniperiódico.
Además de llenar los periodos faltantes, se da una historia detallada del problema de la omniperiodicidad y las estrategias utilizadas para resolverlo, resumiendo el trabajo de un gran número de personas en las décadas desde la creación del Juego de la Vida.
Aplicaciones
editarEl Juego de la Vida no es solo una curiosidad matemática, sino que también tiene aplicaciones prácticas en diversos campos:
1. Investigación científica: El estudio de autómatas celulares como el Juego de la Vida puede proporcionar ideas sobre fenómenos naturales, la teoría de la complejidad y la autoorganización en sistemas biológicos y sociales.
2. Simulaciones: Se utiliza para simular y estudiar la dinámica de poblaciones, la propagación de enfermedades, la formación de patrones en sistemas físicos, etc.
3. Criptografía: Algunos aspectos de los autómatas celulares como el Juego de la Vida se pueden usar en algoritmos criptográficos.
4. Computación: El Juego de la Vida ha sido fundamental en el desarrollo de conceptos en informática, como los algoritmos paralelos y la teoría de la computación.
Además, ha inspirado muchas variantes y extensiones, y es un objeto de estudio y experimentación en áreas como inteligencia artificial, diseño de algoritmos y arte generativo.
Variantes
editarDesde la creación del juego se han desarrollado nuevas reglas. El juego estándar, en que nace una célula si tiene 3 células vecinas vivas, sigue viva si tiene 2 o 3 células vecinas vivas y muere en otro caso, se simboliza como "23/3". El primer número o lista de números es lo que requiere una célula para que siga viva, y el segundo es el requisito para su nacimiento.
Así, "16/6" significa que "una célula nace si tiene 6 vecinas y vive siempre que haya 1 o 6 vecinas". HighLife ("Alta Vida") es 23/36, porque es similar al juego original 23/3 solo que también nace una célula si tiene 6 vecinas vivas. HighLife es conocida sobre todo por sus replicantes. Se conocen muchas variaciones del juego de la vida, aunque casi todas son demasiado caóticas o demasiado desoladas.
- 23/3 (complejo) «Juego de la Vida de Conway»
- /3 (estable) «Sparks», patrones pequeños que aparecen y desaparecen rápidamente[2]
- 5678/35678 (caótico) diamantes, catástrofes
- 1357/1357 (crece) «Breeder», crecen rápidamente, todo son réplicas[3]
- 1358/357 (caótico) un reino equilibrado de amebas
- 23/36 (caótico) «HighLife» (tiene replicante)
- 2/7 (caótico) «Diffusion Rule» (gliders, guns, puffer trains)[4]
- 235678/3678 (estable) mancha de tinta que se seca rápidamente
- 245/368 (estable) muerte, locomotoras y naves
- 34/34 (crece) «Vida 34»
- 4/2 (crece) generador de patrones de alfombras
- 51/346 (estable) «Larga vida» casi todo son osciladores
- 2,3
Parte de la lista que hay en Life32
Se han desarrollado variantes adicionales mediante la modificación de otros elementos del universo. Las variantes anteriores son para un universo bidimensional formado por cuadrados, pero también se han desarrollado variantes unidimensionales y tridimensionales, así como variantes 2-D donde la malla es hexagonal o triangular en lugar de cuadrada.
Referencias
editar- ↑ «Al principio, Steve Jobs y Steve Wozniak no sabían vender. El fracaso de la primera demo del Apple II y el Juego de la Vida de Conway» (html). ElevenPaths. 9 de junio de 2018. Archivado desde el original el 9 de junio de 2018. Consultado el 9 de junio de 2018. «Ese programa no era nada y nada menos que el Juego de la Vida de Conway. Este programa no es realmente un juego sino más bien una simulación de autómatas celulares creado por John Horton Conway en 1970 y publicado en al revista Scientific American. Este juego trata de la evolución de células digitales en un tablero las cuales dependen de sus vecinas para sobrevivir o no dentro del juego.»
- ↑ Romero Dopico, Manuel. «El juego de la vida». it.uc3m. Archivado desde el original el 2 de agosto de 2021. Consultado el 27 de mayo de 2021.
- ↑ Romero Dopico, Manuel. «El juego de la Vida». it.uc3m. Archivado desde el original el 2 de agosto de 2021. Consultado el 4 de agosto de 2021.
- ↑ «Diffusion Rule». Archivado desde el original el 11 de febrero de 2013. Consultado el 24 de diciembre de 2019.
Véase también
editar- Hormiga de Langton
- El gran diseño de Stephen Hawking.
- Gardner, M. (1970). Mathematical games. The fantastic combinations of John Conway's new solitaire game "life". Scientific American, Vol. 223, No. 4, pp. 120-123.
- Poundstone, W. (2013). The Recursive Universe. Cosmic Complexity and the Limits of Scientific Knowledge. Dover Publications, Inc.
- Durand, B., & Róka, Zs. (1998). The Game of Life: universality revisited. Laboratoire de l'Informatique du Parallélisme, Research Report No. 98-01.
Enlaces externos
editar- Wikimedia Commons alberga una galería multimedia sobre Juego de la vida.
- Explicación de la máquina de Turing implementada en Life por Paul Rendell
- Modelo: juego de la vida de John Conway
- John Conway, el genio mágico
- Simulador de propagación de enfermedades basado en el juego de la vida de Conway
En inglés
editar- 3d game of life simulation inside a 2.5d cellular automaton
- Life Lexicon
- Conway's Game of Life applet software home page
- "Eric Weisstein's Treasure Trove of the Life C.A." - a site by Dr. Eric Weisstein containing many descriptions and animations of Life patterns
- Game of Life applet with source code
- Wonders of Math - The Game of Life
- Color Game of Life Visual Exhibition
- Demonstration of some Variations on Life
- The turing machine, implemented in game of life.
- The Game of Life. - Una introducción sencilla e interesante.
- The Game of Life repository
Software
editar- Virtual Life Game - Versión 2D del juego de la vida con las diferentes reglas y escenarios adaptables.
- Lifemii Wii - Versión 3D del juego de la vida para Wii.
- The Game of Life on Android
- Life Social Game. Un juego social inspirado en el "Juego de la Vida", de John H. Conway
- JuegoVida - Versión GPL (libre) del juego de la vida para dispositivos móviles con Java (MIDP 1.0). Emulador de prueba.
- GTKlife - Versión libre del juego de la vida.
- Vida de VaxaSoftware - Versión freeware del juego de la vida (Español).
- GLTlife - Versión usando las cualidades gráficas de OpenGL del juego de la vida.
- GLlife - Otra Versión con las mismas características que la anterior.
- Life32 Archivado el 4 de septiembre de 2011 en Wayback Machine. - Versión del juego de la vida para Windows
- Conway´s Game Of Life Collection - Descarga gratuita de 16 clones del juego de la vida de Conway.
- Conway´s Game of Life Simulator for Microsoft Windows
- Golly Game of Life - Simulador OpenSource de El Juego de la Vida para Windows, MacOS X y Linux.
Software en línea
editar- PlayGameOfLife Este sitio ofrece una versión con cuadrícula infinita y varios modelos sin necesidad de ningún software externo.
- Game of Life en copy.sh - Javascript
- Game of Live en pmav.eu - Javascript
- Game of Life de Edwin Martin
- El juego de la vida
- Game of Live de Alan Dewar
- Game of Life - JavaScript
- Game of Life de Jake Barnwell, MIT. Archivado el 28 de febrero de 2018 en Wayback Machine.
- Gamoliyas - Versión en línea totalmente en DHTML (JavaScript, CSS y HTML). Licencia GPL. Para ver cómo utilizar el juego incrustado en otras páginas y configurado a medida, ver este ejemplo.
- Orekaria Archivado el 21 de agosto de 2010 en Wayback Machine. - Versión en línea adecuada para una primera toma de contacto. Requiere Silverlight.
- Juego de la vida generalizado Versión en línea en javascript que permite modificar el tamaño de la cuadrícula del juego; modificar las condiciones de nacimiento y muerte mientras el juego evoluciona sin detenerlo; así como establecer dos jugadores y otros parámetros.