Investigación aceptores - norman-ipn/Evolutivo GitHub Wiki

Antes de comenzar el show de hoy, quiero comentarles sobre esta imagen que había estado buscando desde hace ya algunos años. Esta es una escena de la primera película de “Terminator” de 1984. Mas o menos en la escena en donde el malvado T-800 se aproxima al hotel donde Kyle Reese y Sarah Connor se esconden. En esta escena la toma es una vista en primera persona del robot, donde se puede leer con toda claridad unas lineas de lenguaje ensamblador para procesadores Motorola compatibles con el 6502. La controversia sobre a que tipo de computadora pertenece este código es una discusión muy amplia en el mundo Geek, pues esta familia de CPU’s perteneció a sistemas tan famosos como la Apple II, el Nintendo Entertainment System, algunos modelos de Commodore, etc. De hecho, poco antes de esta toma, aparece una secuencia de numeros hexadecimales o como dirían los nerds, un volcado de memoria. De hecho, considero que esta escena es la mas realista de toda la película, pues programar un robot en ensamblador es tarea que solo puede hacer una inteligencia (no necesariamente humana) muy avanzada. Sobre todo si tomamos en cuenta que aquel era un modesto procesador de 8 bits.

Y de eso es precisamente lo que trata el show de hoy: de autómatas. Primero díganme una cosa. ¿Que es lo primero que les viene a la mente cuando escuchan la palabra “autómata”? La mayoría pensará en un robot casi siempre humanoide hecho de metal, quizas con ojos que prenden y apagan, nariz de tubo de vacío, sombrero de embudo y voz de sintetizador de los años ochenta. Una cruza entre el hombre de hojalata del Mago de Oz y el robot de Perdidos en el espacio. Pues oh sorpresa, para nuestros reputados ingenieros en computación, un autómata no es mas que un simple ciclo con una condición en medio.

No voy a entrar aqui con esas discusiones somníferas de los libros de lógica matemática sobre que son los autómatas. Solo que en esta clase de documentos a estas entidades se les conoce simplemente como aceptores. De hecho este es el término que a mi me gusta usar porque estas cosas se usan para aceptar o rechazar una secuencia de entradas. Veamos un ejemplo mas sencillo de lo que es un aceptor:

Para los que son geeks y han intentado programar un juego de peleas como Street Fighter, KOF, etc. Seguramente se han preguntado como demonios le hace la computadora para detectar las combinaciones de teclas que activan los movimientos especiales. Pues en estos juegos, las secuencias de entrada que componen los ataques especiales son exactamente las mismas que se usan para los movimientos normales. Entonces, conforme el jugador aporrea la palanca y los botones, la máquina va registrando estas entradas y ejecutando órdenes de acuerdo con las reglas del juego. El aceptor comienza en un estado inicial y dependiendo de las entradas va cambiando a otros estados intermedios. Al final de la secuencia se llega a un estado de aceptación o de no-aceptación, así como estados que dan por terminada la secuencia. En el caso del juego de peleas, si la secuencia de entradas llega al estado de aceptación se activa el ataque. Si se cae en un estado de no-aceptación se anula todo el proceso y se vuelve al principio del aceptor.

¿Y como demonios se programa un aceptor? La manera mas directa es hacer corresponder cada estado con un ciclo y la transición de uno a otro con saltos condicionales hacia otros ciclos. Conforme las entradas se leen la condición dentro de cada uno de esos ciclos determina a cual ciclo hay que saltar. Este enfoque es el mas directo. Pero hay otra forma mas interesante de automatizar el aceptor. Si declaramos un array de 2 dimensiones donde cada columna corresponde a un estado y cada renglón a una posible entrada, y dentro de cada elemento de este array guardamos el índice al estado que debe de saltar, tendremos una estructura capaz de manejar cualquier aceptor finito determinista, en este caso la palabra determinista significa que a cada entrada corresponde una y solo una acción. De este modo, podemos hacer un solo programa que cargue una de estas matrices y a pueda procesar una secuencia de entradas. Dependiendo del estado en el que acabemos cuando las entradas se acaben sabremos si esta fue aceptada o no.

Supongo que cualquiera de ustedes que haya leído algun libro de lógica matemática ya sabrá esto. Pero estoy seguro de que pocos saben como se puede hacer para que esta misma estructura ejecute órdenes. Vamos a volver al ejemplo del juego de peleas. En esos juegos la misma secuencia de botones hace cosas diferentes dependiendo de si el personaje está de pie, agachado, corriendo, saltando por los aires o cuando entra en contacto con el oponente. Eso da en un juego típico mas de 30 movimientos básicos diferentes por cada personaje. Y en un típico juego de peleas de hoy con decenas de peleadores diferentes, programar a mano todas las posibles combinaciones sería algo impensable. Sobre todo si tomamos en cuenta programas como MUGEN donde uno puede crear sus propios personajes (aunque la mayoría de los usuarios solo se los lamean de otros juegos).

Un programador que conozca como hacer un programa que reciba como entrada un aceptor que ejecute órdenes es algo muy valioso para desarrollar este tipo de juegos. Bastaría con hacer una aplicación que los artistas/diseñadores usen para crear a los personajes y sus movimientos directamente sin necesidad de saber nada de programación. A grandes rasgos, para lograr esto solo hay que agregar a cada celda del aceptor anterior un índice a una tabla que almacene las funciones a llamar. De este modo, en cada transición de un estado a otro se ejecutaría una función. Al terminar de ejecutar el proceso, el aceptor pasaría al siguiente estado y así indefinidamente hasta que se acabe la secuencia de entradas o hasta que se caiga en un estado de salida. Con esto la estructura del aceptor tendría que incluir una palabra de 32 bits que almacene la posición de la tabla de funciones y si fuera necesario su número. De hecho, existe una estructura lógica similar al aceptor llamada diagrama de estado, que es un grafo donde las acciones ejecutadas en un estado lo hacen cambiar a otro, y en cada estado se pueden ejecutar acciones diferentes. Esta estructura también sirve para este tipo de estructuras.

Pero aún hay mas, como programamos en Ensamblador y no en ninguno de esos lenguajitos de niñas podemos redefinir la estructura para que los cambios de estado sean muy rápidos. Si la cantidad de entradas es una potencia de 2 (1,2,4,8,16,32,…) puede combinarse en un registro índice el valor de la entrada y el estado actual usando operaciones bitwise (AND, OR, XOR), desplazamientos y rotaciones binarias para componer la posición de la entrada. Esto no son mas que 3 o 4 instrucciones de máquina. Para separar el estado actual del índice de función a ejecutar basta usar algunos AND’s y SHR’s. Esto suena demasiado enredado pero pronto podremos ver el código en este mismo blog. La ventaja de este proceso es que la función no tiene ningún salto condicional ni comparaciones. El único salto es el que da el ciclo que lee las entradas y aún ese puede acelerarse.

Bueno, volviendo a lo del programa comentado en la entrada Darwin Digital, ahora debería de ser capaz de leer un texto y cambiar de estado dependiendo del texto que recorra. Como siempre la salida se da en un archivo de texto. Ya veremos que sucede cuando lo acabe. Dato Inutil: Por cierto, en la terminología de los aceptores, el tipo de entrada que detiene el proceso de un aceptor se le conoce con el nombre de “Terminator”