Wednesday, April 11, 2012

El juego de la vida de Conway

 

Hay un juego de computadora fascinante, llamado Juego de la Vida, el cual fue diseñado en 1970 por el matemático británico John Horton Conway, de la Universidad de Cambridge, Inglaterra. Se hizo muy popular desde que Martin Gardner, en su columna de octubre de ese año en la revista Scientific American hablara de las ideas de Conway. Y a partir de ese momento miles de programadores lo codificaron y jugaron con las ideas del británico en sus respectivos tiempos libres.

El juego de la vida ocurre en un tablero cuadriculado, en donde cada cuadro puede haber una célula o estar vacío. La idea es acomodar una serie de células en la malla cuadriculada y observando las vecindades de cada célula, cada cuadro pues -utilizando las reglas de Conway- ir calculando las nuevas configuraciones de células que aparecerán en la siguiente generación. Puede verse que el juego de la vida de Conway no es estrictamente un juego de video, pues el “jugador” no hace nada más que ver la evolución que en cada tiempo, en cada generación, aparece en la pantalla.

Cabe decir que las reglas que se definan para el juego de la vida deben ser tales que la conducta de la población resulte a un tiempo interesante e impredecible. Las reglas de evolución, dadas por el propio matemático, llamadas también reglas genéticas, son de una sencillez deliciosa y pensamos que Conway las fue descubriendo (¿inventando?) poco a poco.



Tomemos un plano cuadriculado entonces de dimensiones infinitas. Cada sitio, cuadro o casilla, tiene 8 casillas vecinas: cuatro ortogonalmente adyacentes (2 en vertical y 2 en horizontal). En cada sitio es posible poner un valor binario (hay célula o no hay en esa casilla). Las reglas son:

  • Supervivencia: cada célula (digámosle ficha), que tenga dos o tres fichas vecinas sobrevive y pasa a la generación siguiente.
  • Fallecimiento: cada ficha que tenga cuatro o más vecinas muere y es retirada del tablero, por sobrepoblación. Las fichas con una vecina o solas fallecen por aislamiento.
  • Nacimientos: cada casilla vacía, adyacente a exactamente tres cifras vecinas -tres, ni más ni menos- es casilla generatriz. Es decir, en la siguiente generación habrá de colocarse una ficha en esa casilla.

Es importante hacer notar que todos los natalicios y fallecimientos ocurren simultáneamente, y constituyen en su conjunto una generación en particular, al paso del tiempo t, también llamado tic del reloj.

Con el mismísimo Conway, en su plática que dio en junio del 2010 en la Facultad de Ciencias de la UNAM.

En un principio el inventor de este singular “juego” conjeturó que ningún patrón inicial podría crecer ilimitadamente. Dicho en otras palabras, ninguna configuración compuesta por un número finito de fichas puede crecer hasta rebasar un límite superior finito, que limita el número de fichas que puede contener el campo del juego. Seguramente esta sea la cuestión más difícil y profunda que planteé el juego.

Conway ofreció un premio de 50 dólares a la primera persona capaz de probar o de refutar la conjetura antes de finalizar el año 1970. Una forma de refutarla sería dar con configuraciones que, generación tras generación, añadiesen más piezas al terreno de juego: un cañón (es decir, una configuración qaue repetidamente dispara objetos en movimiento), o bien el tren puf-puf (configuración que al paso del tiempo t avanza dejando tras de sí una estela de “humo”).

La conjetura de Conway se refutó en noviembre de 1970. Un grupo integrado en el proyecto de inteligencia artificial del MIT, comandado por William Gosper, halló un cañón lanza-deslizadores, el cual genera un deslizador cada 30 pulsos de reloj (o generaciones). La existencia de tal cañón suscita una interesante posibilidad de que el juego de Conway pueda simular una máquina de Turing, la cual es capaz de hacer, en principio, cualquier computación, cualquier cálculo. Si el juego permite esta alternativa, entonces la siguiente pregunta a resolver es si sería capaz de poderse crear un constructor universal. De lo cual se encontraría una máquina con capacidad de autorreproducción no trivial. Desafortunadamente, a la fecha, no ha podido construírse.

El carácter universal del juego de la vida significa que, en principio, es posible usar deslizadores para llevar a cabo cualquier cómputo que pueda efectuarse con la más potente de las computadoras digitales. Mediante la disposición de cañones lanza-deslizadores y otras formas de “vida”, es posible calcular π, e, la raíz cuadrada de 2, o de cualquier otro número, con cualquier número de cifras decimales.

 Hay muchísimos programas de código abierto y gratuito para jugar con el juego inventado por Conway. Vale la pena probar alguno de ellos e intentar configuraciones diferentes. Hay mucha información sobre el juego de la vida del matemático británico y podría asegurarles que es francamente apasionante. El único inconveniente es que esto comienza a hacerse obsesivo.

Algunas fuentes de interés:

Juego de la vida en HTML5
Juego de la vida de Conway
Juego de la vida con fuentes (Delphi)
LifeWiki
________

(*) En la foto inicial del artículo están, de izquierda a derecha: Erik Demaine, Martin Demaine, Bill Spight y John Conway

5 comments:

Meithan West said...

¡Me encanta Conway's Game of Life! Ver tu foto con el mismísimo genio me causó envidia "de la buena" jaja. Qué honor. En fin, me encantó ver este tema en tu blog. Sólo quería aportar un par de comentarios.

Se sabe ya que Conway's Game of Life (CGoL) es Turing-completo, pues es posible implementar las compuertas lógicas NOT y AND, así como un sistema de memoria. Con estos elementos se vuelve posible construir una máquina de Turing universal. Claro, esto sólo demuestra que es posible, no dice cómo construirla en CGoL.

Pero en 2002, Paul Chapman logró construir una máquina de Turing universal:

http://www.igblan.free-online.co.uk/igblan/ca/

Similarmente, también es posible crear un constructor universal. Parece que Conway mismo demostró que es posible, y en 2004 Paul Chapman y Dave Green presentaron un constructor universal programable:

http://groups.google.com/group/comp.theory.cell-automata/browse_thread/thread/c62c88b336a917ca/d26a604b1081e460?pli=1

En lo personal me parece súmamente impresionante que un sistema con reglas tan simples pueda ser Turing-completo. Si todas las leyes de la física resultan ser Turing-computables (conjetura conocida como la Strong Church-Turing Thesis), eso querría decir que CGoL tiene suficiente poder como para simular un universo como el nuestro.

Para terminar, los dejo un videíto (disculpas por la baja calidad) que hice recientemente con un patrón de CGoL que me pareció interesante:

http://www.youtube.com/watch?v=A2Hh9NF-pt0

El patrón evoluciona por sí solo a partir de 0:28.

¡Saludos!

Morsa said...

Así es, Claudio, trivial en sus reglas pero fascinante.

Lo que te puedo decir es que si yo estaba emocionado de estar con Conway, pienso que él estaría fascinando de tomarse una foto conmigo ;)

Mau said...

Alguna implementacion en PROLOG conocida? Un abrazo.

Morsa said...

Mau, en mi opinión no es la mejor idea intentar escribir el juego de la vida en Prolog, porque este lenguaje no tiene estructuras como los arreglos, los cuales -desde luego- pueden emularse con listas, pero el manejo puede ser mucho más incómodo.

Como sea, no falta quien aborda esta ingrata tarea (un programa escrito en un lenguaje poco apropiado me parece siempre una tarea ingrata y fea). He aquí una liga al respecto: http://rosettacode.org/wiki/Conway%27s_Game_of_Life#Prolog

saludos
Manuel

Miguel "Skatox" Useche said...

Buen artículo, al fin pude entender el juego de la vida. Y que bien que tengas una foto con su creador!!