Archivos en el mes de Agosto del 2004

Todo está inventado

Durante la carrera estuve becado en un departamento de mi universidad, y pude tener una visión desde dentro de cómo funciona el mundo universitario, y más en concreto, de cómo funciona todo lo relacionado con la docencia y la investigación.

Recuerdo una anécdota de aquella época: yo estaba en el despacho del profesor con el que estaba becado mientras él discutía sobre temas académicos con otro colega. Estaban hablando de próximos proyectos y se decían:

-Mira, ¿has visto lo que han hecho estos ingleses?

-Vaya, sí… pues está muy bien.

-¿Y recuerdas aquello que dijimos que sería interesante desarrollar?

-Sí, claro.

-Pues estos Alemanes ya han hecho algo parecido también.

-Sí, pero no sigas mirando… En realidad TODO ESTÁ INVENTADO YA. Lo único que se puede hacer es repetir lo mismo de distinta forma.

Hoy he recordado esa conversación porque llevo unos días pensando en comenzar un nuevo proyecto relacionado con mi Doctorado y acabo de descubrir que ya está hecho, y no una vez, sino varias.

Había pensado en desarrollar un sistema de programación genética distribuida, que pudiera ser utilizado para superar los problemas de escalabilidad de la programación genética tradicional, repartiendo la carga de trabajo entre varios procesadores. Ya había mencionado la librería de programación genética Groovy Java Genetic Programming en un post anterior, pero había intentado ir un poco más allá imaginando un sistema parecido a SetiAtHome en el que, mediante un salvapantallas pudieran emplearse los ciclos de CPU ociosos de ordenadores conectados a internet para resolver problemas de programación genética de gran complejidad.

El Sistema Distribuido que se conseguiria de esta manera permitiría que pudieran abordarse problemas que hasta ahora eran inviables por la escasez de recursos de cómputo.

Yo sabía que había algun proyecto similar en el ámbito académico. De hecho, el proyecto Tierra de Tom Ray utiliza una aproximación parecida a la que yo menciono, aunque no está orientado a la resolución de problemas: su objetivo es conseguir una diversificación e incremento de la complejidad de los programas evolutivos análogo al sufrido por los organismos biológicos durante la explosión cámbrica. Como objetivo, esto es bastante distinto de lo que yo pretendo, de modo que aunque las técnicas sean similares no hay casi solapamiento.

Sin embargo, antes de decidirme a comenzar el desarrollo he pasado unos días investigando por Internet qué hay desarrollado que pudiera servirme de base, y me he encontrado con esto:

- La programación genética distribuida es una disciplina relativamente explorada en la actualidad y hay unas cuantas decenas de artículos académicos al respecto.

Esto lo intuía. La idea de la paralelización de la programación genética es algo que se te ocurre de manera casi obvia cuando llevas un tiempo pensando en estos temas.

- Hay una implementación de un sistema de programacíón genética distribuida basado en Java que data del año 1998. Esto no me inquieta demasiado, porque se ve que dicha implementación se desarrolló como proyecto académico y que no ha tenido demasiada continuidad.

- Hay un sistema de computación distribuida bastante bueno (aparentemente) llamado Distributed Beagle. Este sistema ha sido desarrollado en C++ y está basado en Open Beagle (un sistema secuencial bastante serio).

Esto es lo que más me ha hecho pensar… Este sistema es algo muy parecido a lo que yo pretendo desarrollar y ahora me pregunto: si esto ya está hecho, ¿vale la pena que me ponga yo a reescribir lo mismo?

Seguro que si lo hago aprenderé mucho sobre el tema, pero ¿no sería mejor emplear este sistema como base y desarrollar por encima de él?

O, siendo algo más radical: ¿no debería plantearme comenzar un proyecto distinto?

Cualquiera de las tres posibilidades me plantea bastantes dudas.

Tengo que pensar un poco más sobre todo esto….

Sokoban

Por fin voy a dar por terminada mi versión del juego japonés “Sokoban”. Por mi tendencia a dejar las cosas a medias, llevaba casi un par de años con el jueguecito estancado, programando un día cada cuatro o cinco meses. Ayer decidí que ya estaba bien. Sé que debe de haber todavía algún bug por ahí escondido, pero se puede decir que ha quedado relativamente estable.

Lo he colgado en la web. A partir de ahora, cualquiera que esté interesado puede echarse una partidita. Como la página todavía está en blanco y no hay nada más que el applet del juego, que no lleva ayuda, voy a comentar aquí cómo jugar (más adelante ya pondré una página de instrucciones).

El jugador controla al “sokoban”, que en japonés creo que quiere decir “mozo de almacén” o algo así. Cada nivel es una especie de laberinto y en él hay unas cajas y unas marcas en el suelo. Tenemos que usar al sokoban para empujar las cajas hasta las marcas. Hay que tener cuidado porque el sokoban sólo puede empujar las cajas, no puede tirar de ellas, con lo que si no nos fijamos bien, podemos dejar alguna caja bloqueada y será imposible lograr el objetivo.

Los controles son: cursores para mover al sokoban, y tecla de borrado para deshacer movimientos (así, si nos hemos equivocado podemos volver atrás e intentar de nuevo)

Esta versión de Sokoban tiene además una funcionalidad bastante interesante: podemos mover al sokoban con el ratón: Si pulsamos en cualquier lugar accesible de la pantalla, el sokoban se moverá hasta allí. Además de esto, si pulsamos en una caja y luego pulsamos en el punto en el que la queremos colocar, el sokoban la empujará hasta allí, si es que eso es posible.

Para incluir estas funcionalidades tuve que desarrollar una implementación del algoritmo A* para la búsqueda de rutas (un algoritmo clásico en Inteligencia Artificial). No es una implementación muy rápida que digamos, pero tampoco ha quedado mal.

El diseño gráfico es bastante conceptual. El sokoban no se parece en nada a un mozo de almacén, y las cajas y marcas tampoco son muy tradicionales. Los sprites los tomé prestados de uno de los skins de una versión de Sokoban para Windows (No recuerdo cómo se llama. La buscaré y pondré el link aquí)

También he tomado prestados los niveles. En la próxima versión que desarrolle, pondré un espacio en la pantalla en el que aparecerá el nombre del nivel y el autor. Qué menos que eso, teniendo en cuenta el esfuerzo que pone esta gente en la creación de los niveles…

Bueno, espero que lo disfrutéis.