Proyecto para Labo de Micros

Acá está todo el software del proyecto que hicimos (junto con Mariano Beiró) para la materia Laboratorio de Microcomputadoras: un juego de Ta-Te-Ti capaz de conectarse a cualquier televisor (con audio incluido!). Una de las cosas más particulares que tenía el software era el uso de un tabla comprimida con Huffman para determinar que jugada realizar en base a la posición del tablero. Algunas fotos:



La imagen proyectada sobre una PC cuando hicimos la presentación (como la salida era video compuesto la tomaba sin problemas).



Una vista de la plaqueta principal.

Post de retorno: desarrollo de circuitos

Bueno, pasó bastante tiempo desde la última actualización y no quería llegar a un mes sin posts... Estas últimas semanas estuve ocupado terminando trabajos prácticos finales para varias materias, pero esta pude empezar nuevamente con el trabajo de la tesis. Más específicamente, comenzando a programar el módulo de evaluación.

Este módulo es central para el sistema, ya que debe transformar la descripción del individuo en un circuito con objeto de que pueda obtenerse su transferencia con el SPICE y compararla con la deseada. Esta transformación, que puede verse animada en el sitio de John Koza, consiste en interpretar el cromosoma como una serie de instrucciones que gobiernan el "crecimiento" de un circuito.

Como en el sistema que estoy desarrollando un cromosoma es un array de bytes y debo representar con él un árbol, tenía que decidirme por una codificación. Después de pensar varias opciones, elegí utilizar una codificación prefija por la simplicidad de su "evaluación" recursiva. También evalué la posibilidad de no efectuar la recursión y reemplazarla por iteración, pero decidí seguir el precepto de Knuth respecto a la optimización prematura.

La otra decisión de codificación era respecto al circuito: implementar mi propia representación o utilizar Boost. En base a mis experiencias previas con grafos, elegí utilizar boost::adjacency_list; no por razones de performance, sino para evitar los posibles bugs y tiempo desperdiciado.

Para terminar, un interesante post de Stephen Wolfram (el creador del Mathematica) sobre los diseños de puentes, a la luz de la famosa caída de uno en Estados Unidos.

Descripción del tema de la tesis y otras cosas

Bueno, antes de seguir con los temas del día, voy a hablar un poco de cual es el tema de mi tesis. El tema es la "Utilización de estrategias de selección de población para el diseño de filtro analógicos pasivos utilizando programación genética", pero ¿qué significa?

Bueno empecemos con la programación genética (mucha más información sobre el tema, como siempre, puede encontrarse en Wikipedia o en Google). La programación genética es una técnica para resolver problemas de optimización que se basa en realizar una "evolución artificial" de una población de programas, con el objeto de seleccionar al que dé la solución más conveniente al problema planteado. Se diferencia de los algoritmos genéticos en que el genoma no se interpreta en forma estática, sino que se ejecuta con una máquina virtual (limitada, lógicamente, no es ni HotSpot ni CLR! :-) Voy a hablar más de este tema (uno de los más importantes en un sistema de programación genética) posteriormente, cuando esté implementando la mencionada VM.

Los filtros analógicos pasivos son circuitos electrónicos cuyo objetivo, tal cual lo indica el nombre, es "filtrar" una señal, eliminando ciertos componentes de la misma. Se denominan analógicos porque operan con una representación continua de la señal; esto los diferencia de los filtros digitales que lo hacen con una representación en tiempo discreto. Finalmente son pasivos porque solo utilizan tres clases de componentes: resistores, capacitores e inductores, ninguno de los cuales "entrega energía" a la señal (la definición estricta de pasividad es algo compleja). A pesar de que no figura en el nombre, estos filtros son lineales, lo que implica que la respuesta a la suma de dos señales es al suma de las respuestas que daría a cada señal por separado.

El realizar todas esas generaciones de evolución con poblaciones que pueden llegar a tamaños considerables es computacionalmente costoso. Si bien hoy día es en general ventajoso intercambiar tiempo del programador por tiempo de máquina, como lo muestra la gran popularidad de lenguajes tales como Python, una tarea suficientemente compleja puede vencer incluso al crecimiento exponencial del poder de cálculo. Por ello es importante tener métodos relativamente sofisticados para elegir a los circuitos de la población con mejores perspectivas de acercarnos a la solución. Más adelante hablaré sobre al naturaleza de estas estrategias.

Bueno ahora a los links del día:

Brian Beckman: The Physics in Games - Real-Time Simulation Explained

Photo Tourism: Exploring Photo Collections in 3D (funciona con Firefox)

En el próximo post: GLUT - arcaica o práctica :-D