Skip to content

Costruire una partita di Tetris funzionante nel Gioco della vita di Conway

Questo problema può essere affrontato in vari modi, ma in questo caso condividiamo la risposta per noi più completa.

Soluzione:

Iniziò come una ricerca, ma finì come un'odissea.

Ricerca del processore Tetris, 2.940.928 x 10.295.296

Il file del modello, in tutta la sua gloria, si trova qui, visualizzabile in browser qui.

Questo progetto è il culmine degli sforzi di molti utenti nel corso degli ultimi 1 anno e mezzo. Sebbene la composizione del team sia variata nel tempo, al momento della stesura del presente documento i partecipanti sono i seguenti:

  • PhiNotPi
  • El'endia Starman
  • K Zhang
  • Blu (Pesce Fango)
  • Mucche quack (Kritixi Lithos)
  • Mego
  • Quartata

Vorremmo anche estendere i nostri ringraziamenti a 7H3_H4CK3R, Conor O'Brien e ai molti altri utenti che si sono impegnati per risolvere questa sfida.

A causa della portata senza precedenti di questa collaborazione, questa risposta è suddivisa in più risposte scritte dai membri di questo team. Ciascun membro scriverà su sotto-argomenti specifici, corrispondenti grosso modo alle aree del progetto in cui è stato maggiormente coinvolto.

Si prega di distribuire eventuali upvotes o bounties tra tutti i membri del team.

Indice dei contenuti

  1. Panoramica
  2. Metapixel e VarLife
  3. Hardware
  4. QFTASM e Cogol
  5. Assemblaggio, traduzione e futuro
  6. Nuovo linguaggio e compilatore

Considerate anche la possibilità di consultare la nostra organizzazione GitHub, dove abbiamo inserito tutto il codice che abbiamo scritto come parte della nostra soluzione. Le domande possono essere rivolte alla nostra chat di sviluppo.


Parte 1: Panoramica

L'idea alla base di questo progetto è l'astrazione. Piuttosto che sviluppare direttamente un gioco di Tetris in Life, abbiamo lentamente aumentato l'astrazione in una serie di passaggi. A ogni livello, ci allontaniamo dalle difficoltà di Life e ci avviciniamo alla costruzione di un computer facile da programmare come qualsiasi altro.

Per prima cosa, abbiamo usato i metapixel OTCA come base del nostro computer. Questi metapixel sono in grado di emulare qualsiasi regola "simile alla vita". Wireworld e il computer Wireworld sono stati un'importante fonte di ispirazione per questo progetto, quindi abbiamo cercato di creare una struttura simile con i metapixel. Sebbene non sia possibile emulare Wireworld con i metapixel OTCA, è possibile assegnare a diversi metapixel regole diverse e costruire disposizioni di metapixel che funzionino in modo simile ai fili.

Il passo successivo è stato quello di costruire una serie di porte logiche fondamentali che servissero da base per il computer. Già in questa fase abbiamo a che fare con concetti simili alla progettazione di processori del mondo reale. Ecco un esempio di porta OR; ogni cella di questa immagine è in realtà un intero metapixel OTCA. Si possono vedere gli "elettroni" (ognuno dei quali rappresenta un singolo bit di dati) entrare e uscire dal gate. Si possono anche vedere tutti i diversi tipi di metapixel utilizzati nel nostro computer: B/S come sfondo nero, B1/S in blu, B2/S in verde e B12/S1 in rosso.

Immagine

Da qui abbiamo sviluppato un'architettura per il nostro processore. Ci siamo impegnati a fondo per progettare un'architettura che fosse il più possibile non esoterica e facilmente implementabile. Mentre il computer Wireworld utilizzava un'architettura rudimentale a innesco di trasporto, questo progetto utilizza un'architettura RISC molto più flessibile, completa di opcode e modalità di indirizzamento multiple. Abbiamo creato un linguaggio assembly, noto come QFTASM (Quest for Tetris Assembly), che ha guidato la costruzione del nostro processore.

Il nostro computer è anche asincrono, il che significa che non c'è un orologio globale che controlla il computer. Piuttosto, i dati sono accompagnati da un segnale di clock mentre scorrono all'interno del computer, il che significa che dobbiamo concentrarci solo sulle tempistiche locali e non globali del computer.

Ecco un'illustrazione dell'architettura del nostro processore:

Immagine

Da qui si tratta solo di implementare Tetris sul computer. Per raggiungere questo obiettivo, abbiamo lavorato su diversi metodi di compilazione di linguaggi di livello superiore in QFTASM. Abbiamo un linguaggio di base chiamato Cogol, un secondo linguaggio più avanzato in fase di sviluppo e infine un backend GCC in fase di costruzione. L'attuale programma Tetris è stato scritto e compilato in Cogol.

Una volta generato il codice finale di Tetris QFTASM, i passi finali sono stati l'assemblaggio da questo codice alla ROM corrispondente, e poi dai metapixel al sottostante Gioco della Vita, completando la nostra costruzione.

Esecuzione di Tetris

Per coloro che desiderano giocare a Tetris senza dover smanettare con il computer, è possibile eseguire il codice sorgente di Tetris sull'interprete QFTASM. Impostate gli indirizzi di visualizzazione della RAM su 3-32 per visualizzare l'intero gioco. Ecco un permalink per comodità: Tetris in QFTASM.

Caratteristiche del gioco:

  • Tutti i 7 tetromini
  • Movimento, rotazione, cadute morbide
  • Cancellazione delle linee e marcatura
  • Anteprima del pezzo
  • Gli input del giocatore iniettano casualità

Visualizzazione

Il nostro computer rappresenta la tavola di Tetris come una griglia all'interno della sua memoria. Gli indirizzi 10-31 visualizzano la tavola, gli indirizzi 5-8 visualizzano l'anteprima del pezzo e l'indirizzo 3 contiene il punteggio.

Ingresso

L'input al gioco viene eseguito modificando manualmente il contenuto dell'indirizzo 1 della RAM. Utilizzando l'interprete QFTASM, ciò significa eseguire una scrittura diretta all'indirizzo 1. Cercate "Direct write to RAM" nella pagina dell'interprete. Ogni mossa richiede la modifica di un solo bit della RAM e questo registro di ingresso viene automaticamente cancellato dopo la lettura dell'evento di ingresso.

value     motion
   1      counterclockwise rotation
   2      left
   4      down (soft drop)
   8      right
  16      clockwise rotation

Sistema di punteggio

Si ottiene un bonus se si cancellano più linee in un solo turno.

1 row    =  1 point
2 rows   =  2 points
3 rows   =  4 points
4 rows   =  8 points

Parte 2: OTCA Metapixel e VarLife

OTCA Metapixel

Metapixel OTCA
(Fonte)

Il metapixel OTCA è un costrutto del Gioco della vita di Conway che può essere usato per simulare qualsiasi automa cellulare simile alla vita. Come dice LifeWiki (linkato sopra),

Il metapixel OTCA è una cella unitaria 2048 × 2048 di periodo 35328 costruita da Brice Due... Ha molti vantaggi... tra cui la capacità di emulare qualsiasi automa cellulare simile a Life e il fatto che, se ingrandito, le celle ON e OFF sono facilmente distinguibili...

Il significato di automi cellulari simili a Life è essenzialmente che le cellule nascono e sopravvivono in base a quante delle loro otto cellule vicine sono vive. La sintassi di queste regole è la seguente: una B seguita dal numero di vicini vivi che causeranno una nascita, poi una barra, poi una S seguita dal numero di vicini vivi che manterranno la cellula in vita. È un po' troppo lungo, quindi credo che un esempio possa essere utile. Il gioco della vita canonico può essere rappresentato dalla regola B3/S23, che dice che qualsiasi cellula morta con tre vicini vivi diventerà viva e qualsiasi cellula viva con due o tre vicini vivi rimarrà viva. In caso contrario, la cellula muore.

Nonostante sia una cella di 2048 x 2048, il metapixel OTCA ha in realtà un rettangolo di gioco di 2058 x 2058 celle, poiché si sovrappone di cinque celle in ogni direzione con il suo diagonale vicini. Le celle sovrapposte servono a intercettare i glider - che vengono emessi per segnalare alle metacellule vicine che è in funzione - in modo che non interferiscano con altri metapixel o volino via all'infinito. Le regole di nascita e sopravvivenza sono codificate in una sezione speciale di cellule sul lato sinistro del metapixel, dalla presenza o assenza di mangiatori in posizioni specifiche lungo due colonne (una per la nascita, l'altra per la sopravvivenza). Per quanto riguarda il rilevamento dello stato delle cellule vicine, ecco come avviene:

Un flusso di 9 LWSS gira in senso orario intorno alla cella, perdendo un LWSS per ogni cella adiacente "accesa" che ha innescato una reazione honeybit. Il numero di LWSS mancanti viene contato rilevando la posizione dell'LWSS anteriore e facendolo scontrare con un altro LWSS dalla direzione opposta. Questa collisione libera gli alianti, che innescano un'altra o due reazioni dei meleti se sono assenti i mangiatori che indicano quella condizione di nascita/sopravvivenza.

Un diagramma più dettagliato di ogni aspetto del metapixel OTCA è disponibile sul sito web originale: Come funziona?

VarVita

Ho costruito un simulatore online di regole simili alla vita in cui si poteva far comportare qualsiasi cellula secondo qualsiasi regola simile alla vita e l'ho chiamato "Variations of Life". Questo nome è stato abbreviato in "VarLife" per essere più conciso. Ecco una schermata (il link è qui: http://play.starmaninnovations.com/varlife/BeeHkfCpNR):

Varlife Screenshot

Caratteristiche degne di nota:

  • Alterna le celle tra vive e morte e dipinge il tabellone con regole diverse.
  • Possibilità di avviare e arrestare la simulazione e di eseguire un passo alla volta. È anche possibile eseguire un determinato numero di passi il più velocemente possibile o più lentamente, alla velocità impostata nelle caselle ticks-per-second e millisecondi-per-tick.
  • Cancella tutte le cellule vive o ripristina completamente lo stato di vuoto della scheda.
  • Può modificare le dimensioni delle celle e della tavola, nonché abilitare l'avvolgimento toroidale in orizzontale e/o in verticale.
  • Permalinks (che codificano tutte le informazioni nell'url) e url brevi (perché a volte ci sono troppe informazioni, ma sono comunque carini).
  • Insiemi di regole, con specifiche B/S, colori e casualità opzionale.
  • E infine, ma decisamente non meno importante, il rendering delle gif!

La funzione render-to-gif è la mia preferita, sia perché ha richiesto un sacco di lavoro per essere implementata, quindi è stata una vera soddisfazione quando finalmente l'ho risolta alle 7 del mattino, sia perché rende molto facile condividere i costrutti VarLife con altri.

Circuito VarLife di base

Nel complesso, il computer VarLife ha bisogno solo di quattro tipi di cellule! Otto stati in tutto, contando gli stati di vita e di morte. Essi sono:

  • B/S (bianco/nero), che funge da cuscinetto tra tutti i componenti, poiché le cellule B/S non possono mai essere vive.
  • B1/S (blu/ciano), che è il tipo di cellula principale utilizzata per propagare i segnali.
  • B2/S (verde/giallo), utilizzata principalmente per il controllo del segnale, assicurandosi che non si propaghi all'indietro.
  • B12/S1 (rosso/arancione), utilizzata in alcune situazioni particolari, come l'attraversamento dei segnali e la memorizzazione di un bit di dati.

Utilizzare questo breve url per aprire VarLife con queste regole già codificate: http://play.starmaninnovations.com/varlife/BeeHkfCpNR.

Fili

Esistono diversi modelli di fili con caratteristiche diverse.

È il filo più semplice e basilare di VarLife: una striscia di blu delimitata da strisce di verde.

filo di base
URL breve: http://play.starmaninnovations.com/varlife/WcsGmjLiBF

Questo filo è unidirezionale. Vale a dire, elimina qualsiasi segnale che tenti di viaggiare nella direzione opposta. È anche più stretto di una cella rispetto al filo di base.

filo unidirezionale
URL breve: http://play.starmaninnovations.com/varlife/ARWgUgPTEJ

Esistono anche fili diagonali, ma non sono molto utilizzati.

filo diagonale
URL breve: http://play.starmaninnovations.com/varlife/kJotsdSXIj

Cancelli

Ci sono molti modi per costruire ogni singolo gate, quindi mostrerò solo un esempio di ogni tipo. Questa prima gif mostra rispettivamente le porte AND, XOR e OR. L'idea di base è che una cella verde agisce come un AND, una cella blu come uno XOR e una cella rossa come un OR, mentre tutte le altre celle intorno a loro servono solo a controllare il flusso in modo corretto.

E, xor o porte logiche
URL breve: http://play.starmaninnovations.com/varlife/EGTlKktmeI

Il gate AND-NOT, abbreviato in "gate ANT", si è rivelato un componente fondamentale. È un gate che fa passare un segnale da A se e solo se non c'è alcun segnale da B. Da qui, "A AND NOT B".

E non cancello
URL breve: http://play.starmaninnovations.com/varlife/RsZBiNqIUy

Anche se non è esattamente un cancello, una piastrella di attraversamento dei fili è comunque molto importante e utile da avere.

Attraversamento del filo
URL breve: http://play.starmaninnovations.com/varlife/OXMsPyaNTC

Per inciso, qui non c'è un gate NOT. Questo perché, senza un segnale in ingresso, si deve produrre un'uscita costante, che non funziona bene con la varietà di temporizzazioni richiesta dall'hardware dei computer attuali. In ogni caso, ce la siamo cavata benissimo anche senza.

Inoltre, molti componenti sono stati intenzionalmente progettati per rientrare in un riquadro di 11 per 11 (un piastrella) in cui i segnali impiegano 11 tick dall'entrata nella piastrella all'uscita dalla stessa. Questo rende i componenti più modulari e più facili da assemblare a seconda delle necessità, senza doversi preoccupare di regolare i fili per la spaziatura o la temporizzazione.

Per vedere altri gate che sono stati scoperti/costruiti durante l'esplorazione dei componenti dei circuiti, consultate questo post del blog di PhiNotPi: Blocchi di costruzione: Porte logiche.

Componenti di ritardo

Nel processo di progettazione dell'hardware del computer, KZhang ideò diversi componenti di ritardo, illustrati di seguito.

Ritardo a 4 tick:
4 ritardi di zecca
URL breve: http://play.starmaninnovations.com/varlife/gebOMIXxdh

Ritardo a 5 tacche:
5 ritardi di spunta
URL breve: http://play.starmaninnovations.com/varlife/JItNjJvnUB

Ritardo di 8 tick (tre diversi punti di ingresso):
8 ritardo di zecca
URL breve: http://play.starmaninnovations.com/varlife/nSTRaVEDvA

Ritardo di 11 tick:
11 ritardo del segno di spunta
URL breve: http://play.starmaninnovations.com/varlife/kfoADussXA

Ritardo di 12 tacche:
12 Tick Delay
URL breve: http://play.starmaninnovations.com/varlife/bkamAfUfud

Ritardo a 14 tacche:
14 Tick Delay
URL breve: http://play.starmaninnovations.com/varlife/TkwzYIBWln

Ritardo di 15 tick (verificato confrontandolo con questo):
15 Tick Delay
URL breve: http://play.starmaninnovations.com/varlife/jmgpehYlpT

Bene, questo è tutto per i componenti di base del circuito in VarLife! Si veda il post sull'hardware di KZhang per i circuiti principali del computer!

Parte 3: Hardware

Con la conoscenza delle porte logiche e della struttura generale del processore, possiamo iniziare a progettare tutti i componenti del computer.

Demultiplexer

Il demultiplexer, o demux, è un componente fondamentale per la ROM, la RAM e l'ALU.
Indirizza un segnale di ingresso a uno dei tanti segnali di uscita in base ad alcuni dati del selettore.
È composto da tre parti principali: un convertitore da seriale a parallelo, un controllore di segnale e uno splitter di segnale di clock.

Si inizia convertendo i dati del selettore seriale in "parallelo".
Ciò avviene dividendo e ritardando strategicamente i dati in modo che il bit di dati più a sinistra intersechi il segnale di clock nel quadrato 11x11 più a sinistra, il bit di dati successivo intersechi il segnale di clock nel quadrato 11x11 successivo e così via.
Sebbene ogni bit di dati venga emesso in ogni riquadro 11x11, ogni bit di dati si interseca con il segnale di clock solo una volta.

Convertitore da serial a parallelo

Successivamente, controlleremo se i dati paralleli corrispondono a un indirizzo preimpostato.
Per farlo, utilizziamo porte AND e ANT sul clock e sui dati paralleli.
Tuttavia, dobbiamo assicurarci che anche i dati paralleli vengano emessi in modo da poterli confrontare nuovamente.
Questi sono i gate che ho realizzato:

Cancelle di controllo del segnale

Infine, basta dividere il segnale di clock, impilare una serie di controllori di segnale (uno per ogni indirizzo/uscita) e abbiamo un multiplexer!

Multiplexer

ROM

La ROM deve prendere un indirizzo come ingresso e inviare l'istruzione a quell'indirizzo come uscita.
Iniziamo utilizzando un multiplexer per indirizzare il segnale di clock a una delle istruzioni.
Successivamente, dobbiamo generare un segnale utilizzando alcuni incroci di fili e porte OR.
Gli incroci di fili consentono al segnale di clock di scendere lungo tutti i 58 bit dell'istruzione e permettono anche a un segnale generato (attualmente in parallelo) di scendere attraverso la ROM per essere emesso.

Pezzi di rom

Ora dobbiamo solo convertire il segnale parallelo in dati seriali e la ROM è completa.

Parallelo al convertitore seriale

rom

La ROM viene attualmente generata eseguendo uno script in Golly che traduce il codice assembly dagli appunti in ROM.

SRL, SL, SRA

Queste tre porte logiche sono utilizzate per lo spostamento dei bit e sono più complicate dei tipici AND, OR, XOR, ecc.
Per far funzionare queste porte, occorre innanzitutto ritardare il segnale di clock di un tempo adeguato per provocare uno "spostamento" dei dati.
Il secondo argomento dato a queste porte determina il numero di bit da spostare.

Per lo SL e l'SRL, abbiamo bisogno di

  1. Assicurarsi che i 12 bit più significativi non siano attivi (altrimenti l'uscita è semplicemente 0) e
  2. Ritardare i dati della quantità corretta in base ai 4 bit meno significativi.

Questo è fattibile con un gruppo di porte AND/ANT e un multiplexer.

Srl

L'SRA è leggermente diverso, perché dobbiamo copiare il bit di segno durante lo shift.
Per fare ciò, si fa l'AND del segnale di clock con il bit di segno, e poi si copia l'uscita un po' di volte con splitter e porte OR.

SRA

Latch Set-Reset (SR)

Molte parti della funzionalità del processore si basano sulla capacità di memorizzare i dati.
Utilizzando 2 celle B12/S1 rosse, possiamo fare proprio questo.
Le due celle possono tenersi accese e possono anche rimanere spente insieme.
Utilizzando alcuni circuiti aggiuntivi di impostazione, reset e lettura, possiamo realizzare un semplice SR latch.

SR LATCH

Sincronizzatore

Convertendo i dati seriali in dati paralleli e impostando un gruppo di latch SR, è possibile memorizzare un'intera parola di dati.
Poi, per recuperare i dati, è sufficiente leggere e resettare tutti i latch e ritardare i dati di conseguenza.
Questo ci permette di memorizzare una (o più) parola di dati in attesa di un'altra, consentendo la sincronizzazione di due parole di dati che arrivano in tempi diversi.

Sincronizzatore

Contatore di lettura

Questo dispositivo tiene traccia del numero di volte in cui è necessario effettuare l'indirizzamento dalla RAM.
A tale scopo utilizza un dispositivo simile al latch SR: un T flip flop.
Ogni volta che il flip flop T riceve un ingresso, cambia stato: se era acceso, si spegne e viceversa.
Quando il flip flop T passa da on a off, invia un impulso in uscita che può essere inserito in un altro flip flop T per formare un contatore a 2 bit.

Contatore a due bit

Per realizzare il contatore di lettura, è necessario impostare il contatore sulla modalità di indirizzamento appropriata con due porte ANT e utilizzare il segnale di uscita del contatore per decidere dove indirizzare il segnale di clock: all'ALU o alla RAM.

Leggi il contatore

Coda di lettura

La coda di lettura deve tenere traccia di quale contatore di lettura ha inviato un ingresso alla RAM, in modo da poter inviare l'uscita della RAM alla posizione corretta.
A tale scopo, utilizziamo alcuni SR latches: un latch per ogni ingresso.
Quando un segnale viene inviato alla RAM da un contatore di lettura, il segnale di clock viene suddiviso e imposta il latch SR del contatore.
L'uscita della RAM viene quindi ANData con il latch SR e il segnale di clock della RAM resetta il latch SR.

Leggi la coda

ALU

L'ALU funziona in modo simile alla coda di lettura, in quanto utilizza un SR latch per tenere traccia di dove inviare un segnale.
Per prima cosa, il latch SR del circuito logico corrispondente all'opcode dell'istruzione viene impostato mediante un multiplexer.
Successivamente, i valori del primo e del secondo argomento vengono ANDati con il latch SR e quindi passati ai circuiti logici.
Il segnale di clock resetta il latch al suo passaggio, in modo che l'ALU possa essere utilizzata di nuovo.
(La maggior parte della circuiteria è ridotta a golf e viene inserita una tonnellata di gestione del ritardo, per cui sembra un po' un pasticcio).

Alu

RAM

La RAM è stata la parte più complicata di questo progetto.
Richiedeva un controllo molto specifico su ogni latch SR che memorizzava i dati.
Per la lettura, l'indirizzo viene inviato a un multiplexer e poi alle unità RAM.
Le unità RAM emettono i dati memorizzati in parallelo, che vengono convertiti in seriale e inviati in uscita.
Per la scrittura, l'indirizzo viene inviato a un altro multiplexer, i dati da scrivere vengono convertiti da seriali a paralleli e le unità RAM propagano il segnale in tutta la RAM.

Ogni unità RAM a 22x22 metapixel ha questa struttura di base:

Unità di RAM

Mettendo insieme l'intera RAM, si ottiene qualcosa di simile a questo:

RAM

Mettendo tutto insieme

Utilizzando tutti questi componenti e l'architettura generale del computer descritta nella Panoramica, possiamo costruire un computer funzionante!

Download:
- Computer Tetris finito
- script per la creazione di ROM, computer vuoto e computer per la ricerca di primi

Il computer

Commenti e valutazioni dell'articolo



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.