Solución:
Esto comenzó como una búsqueda pero terminó como una odisea.
Quest for Tetris Processor, 2,940,928 x 10,295,296
El archivo de patrón, en todo su esplendor, se puede encontrar aquí, visible en el navegador aquí.
Este proyecto es la culminación de los esfuerzos de muchos usuarios en el transcurso de los últimos 1 y 1/2 años. Aunque la composición del equipo ha variado con el tiempo, los participantes al momento de escribir son los siguientes:
- PhiNotPi
- El’endia Starman
- K Zhang
- Azul (pez fangoso)
- Las vacas cuac (Kritixi Lithos)
- Mego
- Quartata
También nos gustaría extender nuestro agradecimiento a 7H3_H4CK3R, Conor O’Brien y los muchos otros usuarios que se han esforzado para resolver este desafío.
Debido al alcance sin precedentes de esta colaboración, esta respuesta se divide en partes a través de múltiples respuestas escritas por los miembros de este equipo. Cada miembro escribirá sobre subtemas específicos, que corresponden aproximadamente a las áreas del proyecto en las que estuvieron más involucrados.
Distribuya los votos a favor o las recompensas entre todos los miembros del equipo.
Tabla de contenido
- Visión general
- Metapixeles y VarLife
- Hardware
- QFTASM y Cogol
- Montaje, traducción y futuro
- Nuevo lenguaje y compilador
También considere revisar nuestra organización GitHub donde hemos puesto todo el código que hemos escrito como parte de nuestra solución. Las preguntas se pueden dirigir a nuestra sala de chat de desarrollo.
Parte 1: descripción general
La idea subyacente de este proyecto es abstracción. En lugar de desarrollar un juego de Tetris en Life directamente, aumentamos lentamente la abstracción en una serie de pasos. En cada capa, nos alejamos más de las dificultades de la vida y nos acercamos a la construcción de una computadora tan fácil de programar como cualquier otra.
Primero, usamos metapíxeles OTCA como base de nuestra computadora. Estos metapíxeles son capaces de emular cualquier regla “realista”. Wireworld y la computadora Wireworld sirvieron como importantes fuentes de inspiración para este proyecto, por lo que buscamos crear una construcción similar con metapíxeles. Aunque no es posible emular Wireworld con metapíxeles OTCA, es posible asignar diferentes reglas a metapíxeles diferentes y construir arreglos de metapíxeles que funcionen de manera similar a los cables.
El siguiente paso fue construir una variedad de puertas lógicas fundamentales que sirvieran como base para la computadora. Ya en esta etapa estamos tratando con conceptos similares al diseño de procesadores del mundo real. Aquí hay un ejemplo de una puerta OR, cada celda en esta imagen es en realidad un metapíxel OTCA completo. Puede ver “electrones” (cada uno representa un solo bit de datos) entrar y salir de la puerta. También puede ver todos los diferentes tipos de metapíxeles que usamos en nuestra computadora: B / S como fondo negro, B1 / S en azul, B2 / S en verde y B12 / S1 en rojo.
A partir de aquí desarrollamos una arquitectura para nuestro procesador. Hicimos un esfuerzo significativo en diseñar una arquitectura que fuera lo más no esotérica y tan fácil de implementar como fuera posible. Mientras que la computadora Wireworld usó una arquitectura rudimentaria activada por transporte, este proyecto usa una arquitectura RISC mucho más flexible completa con múltiples códigos de operación y modos de direccionamiento. Creamos un lenguaje ensamblador, conocido como QFTASM (Quest for Tetris Assembly), que guió la construcción de nuestro procesador.
Nuestra computadora también es asincrónica, lo que significa que no hay un reloj global que la controle. Más bien, los datos van acompañados de una señal de reloj a medida que fluye alrededor de la computadora, lo que significa que solo necesitamos enfocarnos en los tiempos locales pero no globales de la computadora.
Aquí hay una ilustración de la arquitectura de nuestro procesador:
A partir de aquí solo es cuestión de implementar Tetris en la computadora. Para ayudar a lograr esto, hemos trabajado en múltiples métodos para compilar lenguaje de nivel superior en QFTASM. Tenemos un lenguaje básico llamado Cogol, un segundo lenguaje más avanzado en desarrollo, y finalmente tenemos un backend GCC en construcción. El programa actual de Tetris fue escrito / compilado a partir de Cogol.
Una vez que se generó el código final de Tetris QFTASM, los pasos finales fueron ensamblar desde este código a la ROM correspondiente, y luego desde los metapíxeles hasta el Juego de la vida subyacente, completando nuestra construcción.
Corriendo Tetris
Para aquellos que deseen jugar Tetris sin jugar con la computadora, pueden ejecutar el código fuente de Tetris en el intérprete QFTASM. Configure las direcciones de visualización de RAM en 3-32 para ver el juego completo. Aquí hay un enlace permanente para mayor comodidad: Tetris en QFTASM.
Características del juego:
- Los 7 tetrominós
- Movimiento, rotación, gotas suaves.
- Línea limpia y puntuación
- Pieza de vista previa
- Las entradas del jugador inyectan aleatoriedad
Monitor
Nuestra computadora representa el tablero de Tetris como una cuadrícula dentro de su memoria. Las direcciones 10-31 muestran el tablero, las direcciones 5-8 muestran la pieza de vista previa y la dirección 3 contiene la partitura.
Aporte
La entrada al juego se realiza editando manualmente el contenido de la dirección RAM 1. Usando el intérprete QFTASM, esto significa realizar escrituras directas en la dirección 1. Busque “Escritura directa en RAM” en la página del intérprete. Cada movimiento solo requiere editar un solo bit de RAM, y este registro de entrada se borra automáticamente después de que se haya leído el evento de entrada.
value motion
1 counterclockwise rotation
2 left
4 down (soft drop)
8 right
16 clockwise rotation
Sistema de puntuación
Obtienes una bonificación por despejar varias líneas en un solo turno.
1 row = 1 point
2 rows = 2 points
3 rows = 4 points
4 rows = 8 points
Parte 2: OTCA Metapixel y VarLife
OTCA Metapixel
(Fuente)
El OTCA Metapixel es una construcción del Juego de la vida de Conway que se puede utilizar para simular cualquier autómata celular similar a la vida. Como dice LifeWiki (vinculado arriba),
El metapíxel OTCA es una celda unitaria de 35328 con un período de 2048 × 2048 que fue construida por Brice Due … Tiene muchas ventajas … incluida la capacidad de emular cualquier autómata celular real y el hecho de que, cuando se aleja, el ON y las celdas OFF son fáciles de distinguir …
Lo que significan los autómatas celulares Life-like aquí es esencialmente que las células nacen y las células sobreviven según cuántas de sus ocho células vecinas estén vivas. La sintaxis de estas reglas es la siguiente: una B seguida de la cantidad de vecinos vivos que provocarán un nacimiento, luego una barra, luego una S seguida de la cantidad de vecinos vivos que mantendrán viva la celda. Un poco prolijo, así que creo que un ejemplo ayudará. El juego canónico de la vida se puede representar mediante la regla B3 / S23, que dice que cualquier celda muerta con tres vecinos vivos cobrará vida y cualquier celda viva con dos o tres vecinos vivos permanecerá viva. De lo contrario, la celda muere.
A pesar de ser una celda de 2048 x 2048, el metapíxel OTCA en realidad tiene un cuadro delimitador de 2058 x 2058 celdas, la razón es que se superpone por cinco celdas en todas las direcciones con su diagonal vecinos. Las celdas superpuestas sirven para interceptar planeadores, que se emiten para indicar a los vecinos de las metacélulas que está encendido, para que no interfieran con otros metapíxeles o vuelen indefinidamente. Las reglas de nacimiento y supervivencia están codificadas en una sección especial de células en el lado izquierdo del metapíxel, por la presencia o ausencia de comedores en posiciones específicas a lo largo de dos columnas (una para el nacimiento y la otra para la supervivencia). En cuanto a la detección del estado de las celdas vecinas, así es como sucede:
Un flujo de 9-LWSS luego gira en el sentido de las agujas del reloj alrededor de la celda, perdiendo un LWSS por cada celda adyacente ‘activada’ que desencadenó una reacción de Honeybit. El número de LWSS que faltan se cuenta detectando la posición del LWSS delantero chocando con otro LWSS desde la dirección opuesta. Esta colisión libera planeadores, lo que desencadena otra o dos reacciones de miel si los comedores que indican que la condición de nacimiento / supervivencia están ausentes.
Se puede encontrar un diagrama más detallado de cada aspecto del metapíxel OTCA en su sitio web original: ¿Cómo funciona ?.
VarLife
Construí un simulador en línea de reglas realistas en el que se podía hacer que cualquier célula se comportara de acuerdo con cualquier regla real y lo llamé “Variaciones de la vida”. Este nombre se ha reducido a “VarLife” para ser más conciso. Aquí hay una captura de pantalla (enlace a ella aquí: http://play.starmaninnovations.com/varlife/BeeHkfCpNR):
Características notables:
- Cambia las celdas entre vivo / muerto y pinta el tablero con diferentes reglas.
- La capacidad de iniciar y detener la simulación y de realizar un paso a la vez. También es posible realizar una determinada cantidad de pasos lo más rápido o más lento posible, a la velocidad establecida en las casillas de ticks por segundo y milisegundos por tick.
- Borre todas las celdas vivas o para restablecer completamente la placa a un estado en blanco.
- Puede cambiar el tamaño de la celda y el tablero, y también para permitir el envoltorio toroidal horizontal y / o verticalmente.
- Enlaces permanentes (que codifican toda la información en la URL) y URL cortas (porque a veces hay demasiada información, pero de todos modos son agradables).
- Conjuntos de reglas, con especificación B / S, colores y aleatoriedad opcional.
- Y por último, pero definitivamente no menos importante, ¡renderizar gifs!
La función render-to-gif es mi favorita, tanto porque tomó un montón de trabajo implementarla, por lo que fue realmente satisfactorio cuando finalmente la resolví a las 7 de la mañana, y porque hace que sea muy fácil compartir construcciones de VarLife con otros. .
Circuito básico VarLife
Con todo, ¡la computadora VarLife solo necesita cuatro tipos de células! Ocho estados en total contando los estados vivo / muerto. Son:
- B / S (negro / blanco), que sirve como un búfer entre todos los componentes, ya que las células B / S nunca pueden estar vivas.
- B1 / S (azul / cian), que es el tipo de celda principal que se utiliza para propagar señales.
- B2 / S (verde / amarillo), que se utiliza principalmente para el control de señales, lo que garantiza que no se propague hacia atrás.
- B12 / S1 (rojo / naranja), que se utiliza en algunas situaciones especializadas, como el cruce de señales y el almacenamiento de algunos datos.
Utilice esta URL corta para abrir VarLife con estas reglas ya codificadas: http://play.starmaninnovations.com/varlife/BeeHkfCpNR.
Alambres
Hay algunos diseños de cables diferentes con diferentes características.
Este es el cable más sencillo y básico de VarLife, una franja de azul bordeada por franjas de verde.
URL corta: http://play.starmaninnovations.com/varlife/WcsGmjLiBF
Este cable es unidireccional. Es decir, eliminará cualquier señal que intente viajar en la dirección opuesta. También es una celda más estrecha que el cable básico.
URL corta: http://play.starmaninnovations.com/varlife/ARWgUgPTEJ
También existen alambres diagonales, pero no se usan mucho.
URL corta: http://play.starmaninnovations.com/varlife/kJotsdSXIj
Puertas
En realidad, hay muchas formas de construir cada puerta individual, por lo que solo mostraré un ejemplo de cada tipo. Este primer gif muestra las puertas AND, XOR y OR, respectivamente. La idea básica aquí es que una celda verde actúa como un Y, una celda azul actúa como un XOR y un glóbulo rojo actúa como un OR, y todas las demás celdas a su alrededor están ahí para controlar el flujo correctamente.
URL corta: http://play.starmaninnovations.com/varlife/EGTlKktmeI
La puerta AND-NOT, abreviada como “puerta ANT”, resultó ser un componente vital. Es una puerta que pasa una señal de A si y solo si no hay señal de B. Por lo tanto, “A AND NOT B”.
URL corta: http://play.starmaninnovations.com/varlife/RsZBiNqIUy
Aunque no es exactamente un portón, una loseta de cruce de cables sigue siendo muy importante y útil de tener.
URL corta: http://play.starmaninnovations.com/varlife/OXMsPyaNTC
Por cierto, no hay ninguna puerta aquí. Eso es porque sin una señal entrante, se debe producir una salida constante, que no funciona bien con la variedad de tiempos que requiere el hardware de computadora actual. Nos llevábamos bien sin él de todos modos.
Además, muchos componentes fueron diseñados intencionalmente para caber dentro de un cuadro delimitador de 11 por 11 (un loseta) donde se necesitan señales de 11 tics para entrar en el mosaico y salir del mosaico. Esto hace que los componentes sean más modulares y más fáciles de unir según sea necesario sin tener que preocuparse por ajustar los cables para el espaciado o el tiempo.
Para ver más puertas que se descubrieron / construyeron en el proceso de exploración de componentes de circuitos, consulte esta publicación de blog de PhiNotPi: Building Blocks: Logic Gates.
Componentes de retardo
En el proceso de diseño del hardware de la computadora, KZhang ideó varios componentes de retardo, que se muestran a continuación.
Retraso de 4 ticks:
URL corta: http://play.starmaninnovations.com/varlife/gebOMIXxdh
Retraso de 5 ticks:
URL corta: http://play.starmaninnovations.com/varlife/JItNjJvnUB
Retraso de 8 ticks (tres puntos de entrada diferentes):
URL corta: http://play.starmaninnovations.com/varlife/nSTRaVEDvA
Retraso de 11 ticks:
URL corta: http://play.starmaninnovations.com/varlife/kfoADussXA
Retraso de 12 tics:
URL corta: http://play.starmaninnovations.com/varlife/bkamAfUfud
Retraso de 14 ticks:
URL corta: http://play.starmaninnovations.com/varlife/TkwzYIBWln
Retraso de 15 ticks (verificado comparando con esto):
URL corta: http://play.starmaninnovations.com/varlife/jmgpehYlpT
Bueno, eso es todo para los componentes de circuitos básicos en VarLife. ¡Consulte la publicación de hardware de KZhang para conocer los principales circuitos de la computadora!
Parte 3: Hardware
Con nuestro conocimiento de las puertas lógicas y la estructura general del procesador, podemos comenzar a diseñar todos los componentes de la computadora.
Demultiplexor
Un demultiplexor, o demux, es un componente crucial para la ROM, RAM y ALU. Enruta una señal de entrada a una de las muchas señales de salida basándose en algunos datos de selector dados. Se compone de 3 partes principales: un convertidor de serie a paralelo, un verificador de señal y un divisor de señal de reloj.
Comenzamos por convertir los datos del selector de serie a “paralelo”. Esto se hace dividiendo estratégicamente y retrasando los datos de modo que el bit de datos más a la izquierda se cruce con la señal del reloj en el cuadrado 11×11 más a la izquierda, el siguiente bit de datos se cruce con la señal del reloj en el siguiente cuadrado 11×11, y así sucesivamente. Aunque cada bit de datos se emitirá en cada cuadrado de 11×11, cada bit de datos se cruzará con la señal de reloj solo una vez.
A continuación, comprobaremos si los datos paralelos coinciden con una dirección preestablecida. Hacemos esto usando compuertas AND y ANT en el reloj y datos paralelos. Sin embargo, debemos asegurarnos de que los datos paralelos también se generen para poder compararlos nuevamente. Estas son las puertas que se me ocurrieron:
Finalmente, simplemente dividimos la señal del reloj, apilamos un montón de verificadores de señal (uno para cada dirección / salida) y ¡tenemos un multiplexor!
ROM
Se supone que la ROM toma una dirección como entrada y envía la instrucción a esa dirección como salida. Comenzamos usando un multiplexor para dirigir la señal del reloj a una de las instrucciones. A continuación, necesitamos generar una señal utilizando algunos cruces de cables y puertas OR. Los cruces de cables permiten que la señal de reloj recorra los 58 bits de la instrucción y también permiten que una señal generada (actualmente en paralelo) se mueva hacia abajo a través de la ROM para su salida.
A continuación, solo necesitamos convertir la señal paralela a datos en serie, y la ROM está completa.
La ROM se genera actualmente ejecutando un script en Golly que traducirá el código ensamblador de su portapapeles a la ROM.
SRL, SL, SRA
Estas tres puertas lógicas se utilizan para cambios de bits y son más complicadas que las típicas AND, OR, XOR, etc. Para hacer que estas puertas funcionen, primero retrasaremos la señal del reloj una cantidad de tiempo adecuada para provocar un “cambio”. en los datos. El segundo argumento dado a estas puertas dicta cuántos bits cambiar.
Para SL y SRL, necesitamos
- Asegúrese de que los 12 bits más significativos no estén activados (de lo contrario, la salida es simplemente 0) y
- Retrase los datos la cantidad correcta en función de los 4 bits menos significativos.
Esto es posible con un montón de puertas AND / ANT y un multiplexor.
El SRA es ligeramente diferente, porque necesitamos copiar el bit de signo durante el turno. Hacemos esto haciendo un AND de la señal de reloj con el bit de signo, y luego copiamos esa salida un montón de veces con divisores de cable y puertas OR.
Pestillo Set-Reset (SR)
Muchas partes de la funcionalidad del procesador dependen de la capacidad de almacenar datos. Usando 2 celdas rojas B12 / S1, podemos hacer precisamente eso. Las dos celdas pueden mantenerse encendidas entre sí y también pueden permanecer apagadas juntas. Usando algunos circuitos adicionales de configuración, reinicio y lectura, podemos hacer un simple pestillo SR.
Sincronizador
Al convertir datos seriales en datos paralelos y luego configurar un grupo de pestillos SR, podemos almacenar una palabra completa de datos. Luego, para volver a sacar los datos, podemos simplemente leer y restablecer todos los pestillos y retrasar los datos en consecuencia. Esto nos permite almacenar una (o más) palabras de datos mientras esperamos otra, lo que permite sincronizar dos palabras de datos que llegan en diferentes momentos.
Leer contador
Este dispositivo realiza un seguimiento de cuántas veces más necesita dirigirse desde la RAM. Lo hace usando un dispositivo similar al pestillo SR: un flip flop T. Cada vez que el flip flop T recibe una entrada, cambia de estado: si estaba encendido, se apaga y viceversa. Cuando el flip flop T cambia de encendido a apagado, envía un pulso de salida, que se puede alimentar a otro flip flop T para formar un contador de 2 bits.
Para hacer la lectura del contador, necesitamos configurar el contador en el modo de direccionamiento apropiado con dos puertas ANT, y usar la señal de salida del contador para decidir hacia dónde dirigir la señal del reloj: a la ALU oa la RAM.
Leer cola
La cola de lectura necesita realizar un seguimiento de qué contador de lectura envió una entrada a la RAM, de modo que pueda enviar la salida de la RAM a la ubicación correcta. Para hacer eso, usamos algunos pestillos SR: un pestillo para cada entrada. Cuando se envía una señal a la RAM desde un contador de lectura, la señal del reloj se divide y establece el pestillo SR del contador. A continuación, la salida de la RAM se conecta mediante AND con el pestillo SR, y la señal de reloj de la RAM restablece el pestillo SR.
ALU
La ALU funciona de manera similar a la cola de lectura, ya que utiliza un pestillo SR para realizar un seguimiento de dónde enviar una señal. Primero, el pestillo SR del circuito lógico correspondiente al código de operación de la instrucción se establece usando un multiplexor. A continuación, los valores del primer y segundo argumento se aplican mediante AND con el pestillo SR, y luego se pasan a los circuitos lógicos. La señal del reloj restablece el pestillo a medida que pasa para que la ALU se pueda usar nuevamente. (La mayoría de los circuitos están reducidos y se ha introducido un montón de gestión de retardos, por lo que parece un poco desordenado)
RAM
La RAM fue la parte más complicada de este proyecto. Se requería un control muy específico sobre cada pestillo SR que almacenaba datos. Para la lectura, la dirección se envía a un multiplexor y se envía a las unidades RAM. Las unidades de RAM emiten los datos que almacenan en paralelo, que se convierten en serie y se envían. Para la escritura, la dirección se envía a un multiplexor diferente, los datos a escribir se convierten de serie a paralelo y las unidades de RAM propagan la señal por toda la RAM.
Cada unidad RAM de 22×22 metapíxeles tiene esta estructura básica:
Al juntar toda la RAM, obtenemos algo que se parece a esto:
Poniendo todo junto
Utilizando todos estos componentes y la arquitectura general de la computadora descrita en la Descripción general, ¡podemos construir una computadora que funcione!
Descargas: – Computadora Tetris terminada – Script de creación de ROM, computadora vacía y computadora de búsqueda principal
