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

No comments:

Post a Comment