07 febrero, 2009

Brainfuck y Core War

Gracias a Trivium (un excelente blog de enlaces, hoy he descubierto ES, un proyecto para crear un sistema operativo creado totalmente sobre JavaScript y también Brainfuck (Wikipedia/Español, un lenguaje de programación esotérico con tan sólo 8 instrucciones:

Código Significado Equivalente en C
> incrementa el puntero de datos para que apunte a la siguiente casilla (a la derecha).++ptr
< decrementa el puntero de datos para que apunte a la anterior casilla (a la izquierda).--ptr
+ incrementa (+1) el byte señalado por el puntero de datos.++*ptr
- decrementa (-1) el byte señalado por el puntero de datos.--*ptr
. muestra el valor del byte señalado por el puntero de datos.putchar(*ptr)
, acepta un byte de entrada y almacena su valor en el byte señalado por el puntero de datos.*ptr=getchar()
[ si el byte señalado por el puntero es cero, en lugar de mover el puntero de instrucciones adelante al siguiente comando, salta hasta el comando detrás del ] correspondiente.while (*ptr) {
] si el byte señalado por el puntero no es cero, en lugar de continuar la ejecución con el siguiente comando, salta de vuelta al [ correspondiente.}


Me recuerda exageradamente a Core Wars (aunque hay otros: Ook!, Tink). Constaba de un conjunto reducido de instrucciones con el que se confeccionaba un programa que combatía contra otro en una memoria circular con el objetivo de hacer que el otro programa ejecutase una instrucción DAT prohibida. Algunos lo vinculan con el primer gusano de la historia y el precedente de los virus. En cualquier caso, se trata de una forma excelente de despertar el gusanillo de la programación.

En este artículo se relata la experiencia que va adquiriendo un nuevo usuario conforme va experimentando con las posibilidades del entorno. El lenguaje especificado anteriormente permite crear un simple programa que tiene como objetivo capturar la bandera (poner un byte en una posición específica a cero) del oponente dificultando que haga lo mismo con la propia.

El tamaño de la memoria de juego es aleatorio (entre 135 y 167 bytes) y está inicializada a cero. Ambas banderas se marcan con un 128. La bandera propia está en la casilla de más a la izquierda y la del oponente en cualquier posición hacia la derecha. Se gana cuando se consigue marcar la bandera del oponente con un cero, y se pierde cuando el oponente hace lo mismo o el puntero de programa se sale de la memoria en alguno de los extremos.

Una estrategia simple sería moverse hacia la derecha poniendo a 0 cualquier byte que no lo sea:

[>[-]-]

Pero este consigue muy poca puntuación. Probando con un señuelo se puede frenar al adversario:

>+>->+>->+>->+>->+>-[>[-]-]

Este programa marca las primeras casillas (junto a la bandera) con una secuencia de 1 y -1 (que equivale a 255 por ser un byte). Eso hace que no importa si el adversario utiliza incrementos o decrementos para conseguir poner a cero un byte. En cualquier caso se retrasará centenares de ciclos.

Para evitar que el adversario nos haga lo mismo a nosotros, podemos incrementar una posición la casilla antes de entrar en un bucle que decremente hasta cero el valor. Con esto conseguimos que si la casilla contiene un -1, conseguiremos ponerla a cero enseguida sin entrar en un costoso bucle (254 iteraciones).

>+>->+>->+>->+>->+>-[>+[-]-]

También podemos prevenir que el adversario se beneficie de esta técnica usando +3 y -3 como valores de guarda cerca de la bandera:

>+++>--->+++>--->+++>--->+++>--->+++>---[>+[-]-]

Por último, sabiendo que la bandera enemiga está en el rango 135-167, podemos saltar rápidamente hasta la posición 135:

>+++>--->+++>--->+++>--->+++>--->+++>---
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>
+[>+[-]-]


Con cada versión hemos mejorado la puntuación obtenida al hacer combatir el programa con los mejores 15 adversarios de esta página.

Publicar un comentario en la entrada

Últimos links en indiza.com