sábado, 18 de abril de 2009

El Juego de la Vida


El Emblema Hacker, una subestructura del Juego de la Vida, llamada glider

Los autómatas celulares son estructuras que tienen toda la apariencia de estar vivas. Algunas de las subestructuras que se pueden encontrar dentro de los autómatas nacen, crecen, se reproducen y mueren. Otras viven en el intérin vidas muy dinámicas. A veces pelean batallas entre ellas. Y la mayor parte del tiempo la pasan embelleciéndose, haciéndose más simétricas.
Pero los autómatas celulares no están vivos, no en la definición común que damos para lo que está vivo. Aún menos sus subestructuras. Los autómatas celulares son programas de computadora. También se pueden hacer a mano, por cierto, pero nos demoraríamos toda la vida y no llegaríamos a ver nada vivo en ellos. El número de operaciones que se necesitarían hacer simplemente sobrepasa a la capacidad humana.
Un autómata celular es una rejilla con celdas. Cada celda puede asumir un color: negro o blanco, pero al comienzo todas las celdas comienzan siendo de blanco. Se pinta entonces cualesquiera cantidad de celdas que se decidan de color negro. Acá se acaba la intervención humana. Hay un conjunto de reglas que decidirá, a partir de ese momento, cómo se pintarán las otras celdas. Y desde ahí arranca la computadora a utilizar dichas reglas -hechas por el programador- que se aplicarán a cada instante a toda la rejilla de celdas. Y si las reglas son adecuadas, se puede ver un comportamiento que parece biológico. En pocas palabras, el programador planta la semilla, y luego la computadora se encarga de hacerla crecer de una forma que nadie humanamente podría predecir.
Hoy en día, la ciencia de los autómatas celulares es enseñada en varias universidades del primer mundo, en las especialidades de Biología, Ciencias de la Computación, Física y Matemática. Hay también una literatura enorme sobre el tema. Se pueden encontrar 4600 libros sólo en Amazon tipeando "cellular automata". Las aplicaciones son muchas y variadas: desde la modelación del desarrollo urbano hasta la creación de códigos de seguridad, pasando por el crecimiento de cristales. Es justamente estudiando esto último que se descubrieron los autómatas celulares.
El descubrimiento fue hecho por Stanislaw Ulam y John von Neumann, ambos matemáticos, mientras trabajaban en el Proyecto Manhattan, allá por la década de los 40's. Ellos lograron inventar, trabajando por separado, lo que se llamó después un Constructor Universal de von Neumann, una máquina que se replicaba a sí misma en medio de un ambiente de autómata celular (como un programa de computadora, no en la vida real), y que requería unos 63 mil millones de pasos para hacer la primera copia de sí misma (una computadora haciendo mil pasos por segundo demoraría dos años en ver la duplicación, pero ahora se hacen minutos por la mayor agilidad de procesamiento).
El autómata celular más famoso que existe es el Juego de la Vida, creado por el matemático John Conway en 1970, y popularizado por Martin Gardner, en su columna de juegos matemáticos de la revista Scientific American. La rejilla en este caso es rectangular, con tantas celdas (llamadas células) como se desee, y el pintado (o la vida y la muerte) de las celdas sigue estas reglas:

- Una célula muerta (o celda blanca) con exactamente 3 células vecinas vivas "nace" (al turno siguiente estará viva, o pintada de negro).
- Una célula viva con 2 ó 3 células vecinas vivas sigue viva, en otro caso muere o permanece muerta (por "soledad" o "sobrepoblación").

Las llamadas "células vecinas" son las 8 células que rodean a una célula cualquiera. Y eso es todo. Desde el nacimiento del Juego de la Vida, han habido varias variantes (con más colores, con menos células vecinas, con diferentes reglas, etc.), y la invención de Conway es simbolizada como 23/2 (porque 2 o 3 células vecinas vivas mantienen una célula viva, y 3 reviven una célula muerta). En la página web http://www.ibiblio.org/lifepatterns/ pueden ver varias de estas variantes, incluída la original, gratuitamente (hay miles de páginas similares, pero sucede que primero me topé con ésta). Hacen click en "Enjoy Life", y si tienen instalado Java les aparecerá una pantalla donde dibujan cualquier cosa con el mouse (puede ser su nombre o una carita feliz), y luego hacen click en "Go" para ver cómo evolucionan los patrones. Pueden elegir la velocidad de evolución de los patrones haciendo click en "Speed", las reglas (o variantes) de juego en "Rules", un patrón de inicio determinado en "Open", y reiniciar la evolución en "Clear". Enjoy it.

Hay algo más sobre el Juego de la Vida. Puede, en teoría, comportarse como una Máquina de Turing Universal. ¿Qué es eso? Bueno, es el modelo sobre el que se basan todas las computadoras que ha hecho el ser humano desde que comenzó a hacerlas (y de hecho, y aunque seguramente los constructores no lo sabían, cualquier máquina que se haya hecho hasta el día de hoy). Una Máquina de Turing Universal puede computar cualquier cosa que sea computable, y puede hacer lo que haga cualquier máquina, y dejémoslo ahí por el momento, pues ahi mucha información sobre el tema en Internet que los interesados pueden leer.
En el Juego de la Vida hay subestructuras que se forman y que tienen la capacidad de funcionar como sentencias lógicas del tipo "y", "o" y "no". Entonces, se cree que, dado un patrón inicial, y con todo el tiempo del mundo, se puede programar algo tan complejo como el Microsoft Word, dentro de el Juego de la Vida. De hecho, el mismo Conway y sus estudiantes han descubierto un patrón usando diez billones de celdas, y que se comporta como una Máquina Universal de Turing. Desde ese entonces se han buscado y encontrado patrones que se comporten como máquinas de Turing. Éste un ejemplo de una de esas máquinas, hecha por Paul Rendell en el año 2000 (la vista es alejada con muchísimo zoom negativo):

5 comentarios:

  1. Really ineresting... Good work :D

    ResponderEliminar
  2. necesito un codigo en c++ o java

    ResponderEliminar
  3. Esto lo puedo hacer pero quedare loco :)

    ResponderEliminar
  4. Yo estoy usando un framework en python para implementar unos juegos evolutivos: https://github.com/marcoscravero2175/teoria_de_juegos_evolutivos_individuos_grandes_y_chicos_que_comparten_o_pelean

    ResponderEliminar