Tetris
Colin Fahey
1. Software
StandardTetris_2007June4.zip
Tetris codice sorgente (C# e C++ versioni) e programma (“exe„);
4068277 bytes
MD5: 4e957e0ead66064183e9f7e04e618ec0
2. Introduzione
In questo articolo viene descritto come un computer può svolgere il classico Tetris videogioco di ricevere informazioni sul consiglio di amministrazione, determinare le azioni buone, e l'esecuzione di tali azioni.
Questo articolo include il software in grado di riprodurre Tetris in tempo reale.
Il software include il miglior tempo reale Tetris-giocare algoritmo di pubblico dominio.
Questo articolo definisce le norme “standard„ per “Tetris,„ un disciplinare sulla base di originale 1986 pre-commerciale di Tetris versione per Personal Computer (PC).
In 2003, il software incluso in questo articolo è stato utilizzato per consentire un computer per giocare Tetris in esecuzione su un computer separato.
USB una normale videocamera è stato utilizzato per consentire al computer per “vedere„ la schermata del computer.
A bordo del relè è stato controllato tramite un RS-232 interfaccia per consentire al computer di “premere i tasti„ sulla tastiera del computer.
Così, il primo computer ha un rapporto con il secondo computer che è simile a un tipico giocatore umano rapporto a un computer durante la riproduzione di Tetris, il gioco è stato conosciuto solo guardando lo schermo, e le azioni giocatore può solo essere avviato tramite una tastiera .
La configurazione in questa dimostrazione stabilito che un computer può svolgere Tetris meglio di un umano, in normali in tempo reale Tetris giocare condizioni.
3. Storia di Tetris
In 1985, Alexey Pajitnov e computer sono stati Dmitry Pavlovsky ingegneri a Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre dei Russian Academy of Sciences
Alexey e Dmitry sono stati interessati allo sviluppo di dipendenza e di vendita di giochi per computer.
Essi testato su diversi giochi.
Alexey è stato ispirato dal greco antico gioco di puzzle, Pentaminos, che ha coinvolto l'organizzazione di puzzle fatto di cinque piazze.
Alexey di pensiero l'idea di organizzare Pentamino pezzi come sono diminuiti in una tazza di forma rettangolare, ma ha capito che i dodici diverse quadrato di cinque forme erano troppo complessi per un videogioco.
Alexey passato a sette utilizzando “tetramino„ pezzi, ciascuno composto di quattro piazze.
In 1985.6, Alexey Pajitnov programmato la prima versione di Tetris su un Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov, e Tetris.
In 1985-1986, Vadim Gerasimov, a 16 anni di alta scuola di computer prodigio che ha lavorato presso l'accademia, attuato per il Tetris IBM PC in esecuzione il sistema operativo MS-DOS.
(Vadim Gerasimov più tardi ha fatto la ricerca al MIT Media Laboratory, tra il 1994 e il 2003, ricevendo un Ph.D. dopo aver completato molti progetti interessanti:
http://vadim.www.media.mit.edu)
L'introduzione schermata del 1987-1988 pre-commerciale di rilascio di Tetris per la PC
Il gioco schermata del 1987-1988 pre-commerciale di rilascio di Tetris per la PC
Dopo 1987, Tetris diffusione in tutto il mondo.
The Tetris Company, LLC, possiede il marchio Tetris.
4. Progetti ispirati da Tetris
4.1 0-dimensionali Tetris
Non ancora sviluppato.
4.2 1-dimensionale Tetris
Ziga Hajdukovic ha sviluppato 1-dimensionale Tetris software che può essere giocato in un browser Internet.
Ziga Hajdukovic ha anche messo a 1-dimensionale Tetris software per i telefoni cellulari utilizzando il Java J2ME piattaforma.
4.3 2-dimensionale Tetris
Tutti i convenzionali Tetris varianti sono in questa categoria.
Questa sezione comprende interessanti varianti.
4.3.1 Tetris gioco più grande mai: Delft University of Technology (1995)
Tetris svolto su un edificio; 2000 m^2 superficie; Delft University of Technology (1995)
Tetris svolto su un edificio; 2000 m^2 superficie; Delft University of Technology (1995)
4.3.2 Un altro gioco Tetris svolto su un edificio: Brown University (2000)
Tetris gioco visualizzata utilizzando luci nelle finestre di un edificio a Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
“Credo che sia stato solo il più incredibile di un giorno cosa che sono riuscito a immaginare nella mia vita. Steve Jobs, come sempre detto, il viaggio è la ricompensa.„
“Mi ha fatto pensare a progetti abbiamo fatto ritorno a scuola. Cose che sono state quasi annullata che altre persone non pensano di fare.„
Steve Wozniak (2000)
4.3.3 Browser internet gioco con MIT “bioedilizia„ immagine
Vadim Gerisimov's browser Internet Tetris
Questo browser Internet Tetris variante è stato creato da Vadim Gerasimov.
Questo browser Internet Tetris caratteristiche “Green„ la costruzione presso il campus della MIT.
Tetris questa variante ha solo nove colonne invece dello standard dieci colonne.
Tetris questa variante presenta nuovi pezzi con orientamenti casuali.
Vadim Gerasimov è la persona che ha scritto il codice per computer per il PC versione di Tetris in 1986.
Vadim Gerasimov ha fatto Ph.D. la ricerca al MIT Media Laboratory durante 1994-2003, lavorando su molti progetti interessanti.
4.3.4 PIC16F84 12 MHz microcontrollore a base di NTSC / PAL video gioco Tetris
PIC16F84 12 MHz microcontrollore a base di NTSC / PAL video gioco Tetris
L'immagine sopra mostra il NTSC / PAL uscita video prodotto da un microcontrollore PIC16F84 12 MHz in esecuzione il software scritto da Rickard Gunee in 1998.
Il segnale video è generato da software di controllo delle uscite digitali.
4.3.5 “Scopetris„ oscilloscopio di Tetris Lars Pontoppidan (2007.8)
“Scopetris„ oscilloscopio di Tetris Lars Pontoppidan (2007.8)
Lars Pontoppidan codice scritto per il microcontrollore AtMega32, e ha aggiunto semplici circuiti analogici, per creare una versione Tetris che possono essere riprodotti su un oscilloscopio.
Alcuni registri degli AtMega32 controllo microcontrollori a 8-bit, segnali di uscita, e, quando passò attraverso una resistenza elettrica “R-2R„ circuito per il digitale-analogico (D/A) conversione, la conseguente segnali analogici in grado di controllare la (x,y) coordinate di un oscilloscopio fascio (quando l'oscilloscopio è impostato su “modalità X-Y).„
YouTube video:
FLV video:
4.3.6 Obfuscated codice Tetris: C / Unix
Il seguente è stato assegnato “1989 IOCCC Best Game„.
long h[4];t(){h[3]-=h[3]/3000;setitimer(0,h,0);}c,d,l,v[]={(int)t,0,2},w,s,I,K
=0,i=276,j,k,q[276],Q[276],*n=q,*m,x=17,f[]={7,-13,-12,1,8,-11,-12,-1,9,-1,1,
12,3,-13,-12,-1,12,-1,11,1,15,-1,13,1,18,-1,1,2,0,-12,-1,11,1,-12,1,13,10,-12,
1,12,11,-12,-1,1,2,-12,-1,12,13,-12,12,13,14,-11,-1,1,4,-13,-12,12,16,-11,-12,
12,17,-13,1,-1,5,-12,12,11,6,-12,12,24};u(){for(i=11;++i<264;)if((k=q[i])-Q[i]
){Q[i]=k;if(i-++I||i%12<1)printf("\033[%d;%dH",(I=i)/12,i%12*2+28);printf(
"\033[%dm "+(K-k?0:5),k);K=k;}Q[263]=c=getchar();}G(b){for(i=4;i--;)if(q[i?b+
n[i]:b])return 0;return 1;}g(b){for(i=4;i--;q[i?x+n[i]:x]=b);}main(C,V,a)char*
*V,*a;{h[3]=1000000/(l=C>1?atoi(V[1]):2);for(a=C>2?V[2]:"jkl pq";i;i--)*n++=i<
25||i%12<2?7:0;srand(getpid());system("stty cbreak -echo stop u");sigvec(14,v,
0);t();puts("\033[H\033[J");for(n=f+rand()%7*4;;g(7),u(),g(0)){if(c<0){if(G(x+
12))x+=12;else{g(7);++w;for(j=0;j<252;j=12*(j/12+1))for(;q[++j];)if(j%12==10){
for(;j%12;q[j--]=0);u();for(;--j;q[j+12]=q[j]);u();}n=f+rand()%7*4;G(x=17)||(c
=a[5]);}}if(c==*a)G(--x)||++x;if(c==a[1])n=f+4**(m=n),G(x)||(n=m);if(c==a[2])G
(++x)||--x;if(c==a[3])for(;G(x+12);++w)x+=12;if(c==a[4]||c==a[5]){s=sigblock(
8192);printf("\033[H\033[J\033[0m%d\n",w);if(c==a[5])break;for(j=264;j--;Q[j]=
0);while(getchar()-a[4]);puts("\033[H\033[J\033[7m");sigsetmask(s);}}d=popen(
"stty -cbreak echo stop \023;sort -mnr -o HI - HI;cat HI","w");fprintf(d,
"%4d from level %1d by %s\n",w,l,getlogin());pclose(d);}
4.3.7 Obfuscated codice Tetris: Perl codice
Il testo seguente è Tetris Perl per l'interprete: Perltris (versione 20050717) di Sean Adams.
#!/usr/bin/perl
$_='A=15; B=30; select(stdin); $|=1; select(stdout);$|=1; system
"stty -echo -icanon eol \001"; for C(split(/\s/,"010.010.010.010
77.77 022.020.020 330.030.030 440.044.000 055.550.000 666.060.".
"000")){D=0;for E(split(/\./,C)){F=0;for G(split("",E)){C[P][F++
][D]=G} D++}J[P]=F; I[P++] =D}%L=split(/ /,"m _".chr(72)." c 2".
chr(74)." a _m");sub a{for K(split(/ /,shift)){(K,L)=split(/=/,K
);K=L{K};K=~s/_/L/; printf "%c[K",27}}sub u{a("a=40");for D(0..B
-1){for F(0..A-1){M=G[F][D];if(R[F][D]!=M) {R[F][D]=M;a("m"."=".
(5+D).";".(F*2+5)); a("a=".(40+M).";" .(30+M));print " "x2}}}a(
"m=0;0 a=37;40")}sub r{(N)=@_;while(N--) {Q=W;W=O=H;H=Q;for F( 0
..Q-1){for D(0..O-1) {Q[F][D]=K[F][D]}}for F(0..O-1){for D(0..Q-
1){K[F][D]= Q[Q-D-1][F]}}}}sub l{for F(0..W-1){for D(0..H-1){(K[
F][D]&& ((G[X+F][Y+D])|| (X+F<0)||(X+F>=A)|| (Y+D>=B)))&& return
0}}1}sub p{for F(0..W-1){for D(0..H-1){(K[F][D]>0)&&(G[X+F][Y+D]
=K[F][D]) }}1}sub o{for F(0..W-1){for D(0..H-1){(K[F][D]>0)&&(G[
X+F][ Y+D]=0)}}}sub n{C=int(rand(P)) ;W=J[C];H=I[C];X=int(A/2)-1
;Y=0;for F(0..W-1){for D(0..H-1){K[F][D]= C[C][F][D]}}r(int(rand
(4)));l&&p}sub c{d:for(D=B;D>=0;D--){for F(0..A-1){G[F][D]||next
d}for(D2=D;D2>=0; D2--){for F(0..A-1){G[F][D2]= (D2>1)?G[F][D2-1
]:0; }}u;}}a ("m=0;0 a=0;37;40 c");print "\n\n".4x" "." "x(A-4).
"perltris\n".(" "x4)."--"xA."\n".((" "x3)."|"." "x(A*2)."|\n")xB
.(" "x4). "--"xA."\n";n;for(;;) {u;R=chr(1); (S,T)=select(R,U,V,
0.01);if(S) {Z=getc;}else {if($e++>20){Z=" ";$e=0;}else{next;} }
if(Z eq "k"){o;r(1);l||r(3);p}; if(Z eq "j"){o;X--;l||X++;p}; if
(Z eq "l"){o;X++;l||X--;p};if(Z eq " "){o;Y++;(E=l)||Y--;p;E|| c
|c|c|c|c|n||goto g;};if(Z eq "q"){last;}}g: a("a=0 m=".(B+8).";0
" ); system "stty sane"; '; s/([A-Z])/\$$1/g; s/\%\$/\%/g; eval;
4.3.8 Mozilla SVG Tetris
Scalable Vector Graphics (SVG) è uno standard per la descrizione di oggetti grafici utilizzando XML.
Mozilla SVG Tetris: Tetris implementato usando un Scalable Vector Graphics (SVG) descrizione
4.3.9 Google “widget„ Tetris
Google, Yahoo!, e Microsoft, e altre società, hanno promosso in miniatura basati su Internet software denominato “widgets„ che sono generalmente caratterizzati da un uso dinamico di dati disponibili su Internet.
Uno di questi widget disponibili attraverso Google è un gioco Tetris.
Il seguente esempio è simpatico, ma le forme ruotare in fastidiosi modi:
Google “widget„ Tetris
Altri Google widgets:
4.3.10 MIT ricerca carta: “Tetris is Hard, Even to Approximate„ (2002)
I seguenti attività di ricerca del documento contiene una prova del fatto che un certo tipo di Tetris variante è “NP-completo.„
Erik D. Demaine, Susan Hohenberger, e David Liben-Nowell, “Tetris is Hard, Even to Approximate„, Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
“NP-è„ una “completa„ classificazione di costo il tempo e lo spazio costo di un algoritmo.
Altre classificazioni comprendono “P„ e “NP„.
Una classificazione di “NP-completo„ implica che, per problemi più grandi di alcune piccole dimensioni, l'algoritmo non è in grado di trovare una soluzione desiderata in un pratico importo di tempo o di spazio.
4.3.11 Ricerca documento: “Applying reinforcement learning to Tetris„
Il seguente documento, pubblicato 2005.5.30, di Donald Carr presso il dipartimento di Informatica presso Rhodes University, Sud Africa, presenta la domanda di “rafforzamento imparare„ a Tetris.
4.3.12 Tetris gonna (2007.11)
Tetris gonna (2007.11)
Tetris la gonna è stato creato da “Lucy„ (“hissyfitoly„ a etsy.com) prima 2007.11.
Da parte del creatore della descrizione dei gonna (in vendita sul etsy.com):
"Okay, so I was a secret, closet Tetris fanatic from about, oh, 1993 to 1996. It was a bitter-sweet obsession. My life wasn't so great, but I could control the stacking of a few measly blocks, [damn it]! Or could I? Video games have been coming back to haunt my dreams as of late, and I find myself stacking blocks, jumping away from a frighteningly-large Q*Bert, and slipping off of logs next to a pixellated frog. This skirt is the result of those nightmares."
Forum commenti su questo gonna:
“L'uomo che succhia gonna a Tetris„
“Ahahahaha, ho pensato la stessa cosa.„
“C'è una linea completa giù in fondo ... completato linee di scomparire.„ “FARE PIÙ DI„ “.„
“Ci dovrebbe essere un posto nella parte posteriore o anteriore lungo pezzo in cui si inseriscono perfettamente ...„
“Che è davvero un brutto se gonna. Il mio fidanzato non ha potuto acquistare me abbastanza cioccolato e fiori di convincere me che cosa indossare.„
4.3.13 Tetris fase atto (2007.4)
Tetris fase atto (2007.4)
“Da quelli che hanno portato la Triforce in 2006 ... Proviene la prossima generazione di oggetto inanimato scenetta ... Tetris.„
Localmente-cache Flash video in formato video (FLV) (VLC uso per giocare):
4.3.14 Hilarious Tetris variazioni su una televisione giapponese mostra
Tetris variazioni sul mostrano la televisione giapponese
Il video da un segmento della televisione giapponese mostra comprende hilarious varianti di Tetris, tra cui:
pezzi che svaniscono allo sbarco, un pezzo che riempie un'intera riga (in modo da completare una riga su di sbarco), di cui più pezzi contemporaneamente, dalla forma irregolare pezzi, un lungo pezzo che è un po 'troppo grande per andare bene in un divario (prevenzione di un 4-riga completamento!), Mario colpire un fungo e di diventare enorme e morire!, piccolo pezzo detriti che rimane dopo le righe sono distrutti, verso l'alto la gravità pezzi galleggiante verso l'alto, ecc
Localmente-cache Flash video in formato video (FLV) (VLC uso per giocare):
4.3.15 “The Original Human TETRIS Performance by Guillaume Reymond„ (2007.11)
“The Original Human TETRIS Performance by Guillaume Reymond„ (2007.11)
Dalla descrizione YouTube a:
“TETRIS svolto dalla reale esseri umani-in seduta un auditorium:„
TETRIS è il 4 ° prestazioni video del GAME OVER Project, diretto da artista svizzero Guillaume REYMOND (NOTsoNOISY agenzia creativa).
Questo stop-motion video è stato girato e ha svolto per “LES URBAINES„ festival
http://www.urbaines.ch presso il Palais de Rumine (Losanna, Svizzera) a November 24th 2007.
Localmente-cache Flash video in formato video (FLV) (VLC uso per giocare):
4.3.16 2.5-dimensionale Tetris
Il termine “2.5-dimensionale„ è qui utilizzato per indicare un non-ortogonale vista di un bidimensionale versione di Tetris, con un certo spessore nella terza dimensione.
(Trovi il link “tetris3d„ in “F7: GAMES„.)
4.4 3-dimensionale Tetris
Linux / GTK versione
Tridimensionale di Tetris in forma di un Java applet per Internet browser:
Tridimensionale Tetris Windows per il sistema operativo:
4.5 4-dimensionale Tetris
Greg Kaiser's “HyperTetris„ (1996): un 4-dimensionale Tetris
In [1996], [...], Greg Kaiser mettere insieme un quattro-dimensionali variante per il gioco classico.
Utilizzando IrisGL (a.k.a. igl) egli ha creato un gruppo di lavoro, se difficile da svolgere, gioco con quattro sotto-schermi di rappresentare diversi tridimensionale aspetti di tutto il gioco-spazio.
[Perché] non vi è un facilmente [comprensibili] modo di trarre quattro oggetti-D su una due-D schermo, le quattro sotto-opinioni sono un metodo pratico per manipolare e visualizzare la traduzione e la rotazione dei pezzi attraverso le quattro dimensioni ( nel gioco chiamato x,y,z,w).
Piuttosto che il completamento delle linee di blocchi come in originale, l'obiettivo in questo caso è di riempire un cubo in x,y,z subview (di solito 4 di 4 da 4).
Subviews gli altri che contengono la dimensione “w„ sono disposti in un default di 4 in 4 blocchi da 10 a disposizione “w„ essere lungo, “vertical„ dimensione in tutti e tre i casi, con diverse basi di (x,y), (x,z), (y,z).
Gravità agisce in “-w„ direzione, in modo pezzi “cadere„ nei tre lunghi subviews che includono “w„, e non muoverti a meno di controllo lettore negli ultimi (x,y,z) subview.
Ci vuole un po 'per abituarmi, per non dire altro.
Se per qualche miracolo di pazienza o modificare i parametri di gioco, si fa compilare un cubo, scompariranno come completato linee fare in originale Tetris, anche se non cliente è tenuto in HyperTetris.
Benjamin Bernard (2000)
4.6 N-dimensionale Tetris
Polytope Tetris (2003): un N-dimensionale gioco Tetris variante
Polytope Tetris è n-dimensionalmente Tetris.
Ispirato al programma HyperTetris, Polytope Tetris consente di tonnellate giocare in qualsiasi Tetris NUMERO DI dimensione.
Gioca Tetris in 3D, 4D, 5D, o più.
HyperTetris è molto catchier nome di Polytope (DEF) Tetris, ma non posso rubare il nome.
5. “Tetris„ specifiche “standard„
5.1 Introduzione
La definizione di “standard di Tetris„ è un modello idealizzato dei più importanti caratteristiche e comportamenti dei primi IBM-PC attuazione del gioco Tetris (circa 1986-1988).
Idealizzato il modello si basa su di dedurre l'apparente intenzioni degli sviluppatori del primo IBM-PC attuazione del gioco Tetris.
Per esempio, sembra ragionevole dedurre che gli sviluppatori del primo IBM-PC attuazione del gioco Tetris destinato a selezionare la forma di ogni nuovo pezzo che rientrano “in maniera casuale,„ e che l'uso del Borland C attuazione del rand() funzione è stata solo una pratica di ravvicinamento l'intenzione.
La definizione di “standard di Tetris„ precisa che la forma di ogni nuovo pezzo di cui deve essere selezionato “in modo casuale.„
Questo ideale comportamento non può essere realizzato con qualsiasi applicazione, ma le implementazioni in grado di ravvicinare le comportamento ideale.
Anche se non perfettamente l'attuazione può applicare la definizione di “standard di Tetris,„ gli ideali di “Tetris Standard„ coinvolgere caratteristiche oggettive, e implementazioni può essere paragonata a seconda della loro relativa vicinanza agli ideali di “Standard Tetris.„
Questa sezione descrive una serie di elementi, comportamenti, e delle norme che, collettivamente, definire “standard di Tetris.„
5.2 Tetris standard di bordo
Il consiglio di amministrazione è una griglia di cellule, che hanno 10 colonne e 20 righe, per un totale di 10 * 20 = 200 cellule.
Tetris standard di bordo (10 colonne, 20 righe)
Ogni cella può essere vuoto (vuoto) o occupato (full).
5.3 Tetris standard pezzi
Ci sono sette (7) standard Tetris pezzi, con la seguente lettera nomi:
{ O, I, S, Z, L, J, T }
La lettera nomi si ispirano le forme dei pezzi.
I sette pezzi standard di Tetris e la loro “orientamenti„
Il punto alla (0,0) coincide con bordo posizione (6,20) quando il primo pezzo appare.
La prima colonna mostra l'iniziale “orientamenti.„
Nei seguenti, la parola “orientamento„ è utilizzato per descrivere ogni stato di un pezzo, all'interno di un insieme di stati ammessi, che possono derivare da una rotazione antiorario.
Cambiare “l'orientamento„ da un determinato “orientamento„ di un “I, S,„ o “Z„ pezzo, richiede la combinazione di una rotazione e una traduzione.
Pertanto, la parola “orientamento„ è qui utilizzato per indicare qualcosa di più di rotazione solo.
Tuttavia, “l'orientamento„ può cambiare solo in seguito a un evento di rotazione antiorario, e il ciclo di distinti “orientamenti„ per ogni pezzo ravvicina, o partite, il ciclo derivanti da puro rotazioni.
La particolare uso della parola “orientamento„ in questo contesto è quasi equivalente al significato della parola o “angolo di rotazione,„ ma la parola “orientamento„ è usato al posto di “rotazione„ per tentare di portare l'attenzione sul fatto che alcuni pezzi richiedono più di rotazione per produrre il serie di permesso membri derivanti da eventi “di rotazione„ antiorario.
Pezzi non può che passare orientamenti (o sottoposti a una specifica orizzontale o verticale traduzione) se il conseguente stato di pezza non avrebbe occupato (full) le cellule al di là della zona del consiglio di amministrazione e non avrebbe occupato le cellule che si sovrappongono qualsiasi attualmente occupati cellule del consiglio di amministrazione.
(In questa regola, occupati (completo) delle cellule di pezza, non sono considerati come parte della “attualmente occupati cellule del consiglio di amministrazione„
Nei seguenti osservazioni, qualsiasi riferimento ad un risultato di una rotazione antiorario evento è realizzato con il presupposto che un tale rotazione può essere effettivamente eseguite, date le attuali condizioni del pezzo e il bordo.
La “O„ (box) solo pezzo ha un unico orientamento, e non cambia l'ubicazione di uno dei suoi occupati (completo) di cellule in risposta a qualsiasi evento di rotazione antiorario.
La “I„ (linea) pezzo ha due possibili orientamenti, inizialmente appare in un orientamento orizzontale.
“I„ il pezzo alterna tra i due orientamenti in risposta a successivi eventi di rotazione antiorario.
La “S„ e “Z„ pezzi ogni possibile avere due orientamenti.
Questi pezzi si alternano ogni tra due orientamenti in risposta a successivi eventi di rotazione antiorario.
La “L„, “J„, e ogni “T„ pezzi sono quattro possibili orientamenti, e questi orientamenti sono il risultato di semplici rotazioni sul centro punti sulla forma.
Quando un pezzo prima che compare sul bordo, il pezzo ha il suo “asse maggiore„ in un orientamento orizzontale, e il pezzo è nella parte superiore del consiglio di amministrazione.
Pertanto, non pezzi sono inizialmente in grado di avere cambiato i loro orientamenti. Il pezzo deve discendere da una fila di avere la possibilità di aver cambiato il suo orientamento.
Una volta che un pezzo è diminuito di una riga sul bordo, tutti gli orientamenti pezzo può essere raggiunto (supponendo che il pezzo non è troppo vicino alle pareti laterali o per l'attuale pila di pezzi).
5.4 Tetris diagramma di flusso standard
Il seguente è un approssimativo del diagramma di flusso per un semplice gioco Tetris.
Approssimativa del diagramma di flusso per un semplice gioco Tetris
Approssimativa del diagramma di flusso per un semplice gioco Tetris
5.5 Standard Tetris pezzo creazione
Il diagramma seguente mostra l'(4 cella cella * 2) la regione a bordo di tutti i pezzi in cui vengono visualizzati quando creato.
Regione in cui vengono visualizzati quando pezzi creati in standard Tetris
Quando un nuovo pezzo prima che compare sul bordo, la sua origine coincide con il punto su questo diagramma, e il pezzo sarà completamente contenuta dalla zona ombreggiata a questo schema.
Quando un nuovo gioco è iniziato, una piena caduta libera trascorre ritardo, e il primo a caduta libera da un pezzo di iterazione è generato nella parte superiore del consiglio di amministrazione.
Durante il normale gioco, quando un determinato la caduta libera iterazione “terre„ un pezzo, una piena caduta libera ritardo trascorre e sulla prossima caduta libera iterazione un pezzo è generato nella parte superiore del consiglio di amministrazione.
Quando un pezzo è generato, il tipo di pezzo è scelto in base al seguente algoritmo:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Perché c'è un costante p (= 1/7) possibilità di selezionare uno specifico tipo di pezzo, e tutti i pezzi dello stesso tipo sono indistinguibili, la probabilità di avere esattamente k pezzi di un tipo specifico dopo n prove segue una distribuzione binomiale:
P(k) = (1-p)^(n-k) * p^k * ( n! / ( (n-k)! k! ) );
p = 0.0 ... 1.0;
k = 0, 1, 2, ..., n;
mean = ( n * p )
variance = ( n * p *(1-p) )
standard deviation = sqrt( variance )
Quando abbiamo scelto tra i 7 (sette) pezzi a caso, la probabilità di ottenere un determinato pezzo è p=(1/7).
Se faremo questo n=70 volte, ad esempio, la probabilità di ottenere esattamente k pezzi (con k nella gamma 0 a n) è dato dalla distribuzione binomiale, come illustrato nella seguente immagine.
Distribuzione binomiale per n=70, p=(1/7)
In tal modo, si può prevedere il totale medio di pezzi di un unico tipo di dato un numero totale di pezzi casuali, e si può anche calcolare l'atteso varianza e deviazione standard (radice quadrata della varianza):
p = (1/7):
total random standard
pieces (n) mean variance deviation
============ ======= ======== =========
70 10 8 3
700 100 85 9
7000 1000 857 29
70000 10000 8571 93
Quando abbiamo convertire un valore casuale a un pezzo indice, noi interpretarlo come segue:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[Il pre-commerciale MS-DOS versione di Tetris utilizzato il numero casuale funzione offerti dal Borland Pascal compilatore.
Che utilizzava una funzione a 32 bit stato variabile.
Pertanto, la sequenza di numeri casuali è stato limitato a 2^32 valori distinti.
Pertanto, in linea di principio, un giocatore potrebbe scoprire, dopo l'abbandono forse 10 pezzi, il luogo esatto in 2^32 serie di numeri corrispondenti allo stato attuale del gioco.
Se Tetris simulazioni sono effettuate con la sequenza fissa di 2^32 pezzi, poi ottimale decisioni possono essere trovati per ogni posto nella sequenza.
(Non vi sembrano essere sufficienti opportunità di essere a bordo di uno completamente vuoto bordo di Stato, permettendoci di avere sincronizzato con il precalcolate soluzione ottimale percorso.)
Il rischio di usare un semplice generatore di numeri casuali in una simulazione destinato a trovare una soluzione ottimale a un problema è che la soluzione sarà ottimale solo per il particolare percorso attraverso il problema di spazio selezionati dalla semplice generatore di numeri casuali. ]
5.6 Tetris controlli standard
Durante il gioco, i seguenti fattori produttivi sono disponibili:
left : request to translate left by one column
right : request to translate right by one column
rotate : request to do a counterclockwise rotation
drop : request to instantly drop the piece
Tutti gli ingressi in vigore il crescente di punta del positivo ingresso (premere il pulsante, al contrario di pulsante di rilascio).
Quando un tasto si verifica, questo conta come una richiesta.
In possesso di un pulsante al di là di un certo periodo di tempo potrebbe comportare la “ripetizione automatica„ caratteristica di una tastiera, un pulsante di generare nuove presse - ma questa funzionalità è esterno al motore di gioco.
Gli ingressi di cui sopra sono conformi all'originale gioco Tetris.
Ruota di richieste può essere eseguito se non vi è alcuna sovrapposizione tra l'orientamento desiderato e impostare le cellule a bordo di corrente (esclusa la caduta pezzo), e se l'orientamento desiderato non ha fissato le cellule al di fuori della zona di bordo.
Tradurre le richieste può essere eseguito se non vi è alcuna sovrapposizione tra la configurazione desiderata tradotti e impostare le cellule a bordo di corrente (esclusa la caduta pezzo), e se la configurazione desiderata tradotto non ha fissato le cellule al di fuori della zona di bordo.
Le richieste di ingresso sono trattati con una latenza che dipende il frame rate del gioco (esempio: 75 Hz), e le richieste in vigore (se valido) immediatamente.
Un pezzo può essere eliminato senza alcuna linea di cui si verificano i passaggi.
Un pezzo può essere tradotto più volte a sinistra oa destra, e successivamente abbandonato, senza verifica un funzionario linea che rientrano passo.
Perché generato un nuovo pezzo non può essere ruotato (perché si è bloccata contro il bordo superiore del consiglio di amministrazione), il giocatore deve accettare almeno un pezzo di cui rotazioni passaggio se si desidera o richiesto.
L'effetto sul cliente è insignificante.
5.7 Tetris standard pezzo “di atterraggio„
Se un pezzo è semplicemente che rientrano, spetta di una sola riga nel corso di ogni pezzo che rientrano iterazione.
Ci sarà una iterazione che muove da un luogo senza alcun contatto con superfici orizzontali in un luogo che ha contatto con superfici orizzontali. Una volta che questo si verifica iterazioni, i pezzi sono in contatto di riposo.
Se un iterazione inizia con un pezzo di riposo in contatto con una superficie orizzontale, il pezzo “terre,„ e diventa parte della statica palo.
5.8 Tetris “linee„ standard “completato„
Una fila è completata una fila di palo in cui tutte le cellule sono occupati. Quando una riga completato viene eliminato dal palo, e le righe di sopra della riga eliminati sono spostati verso il basso di una riga per eliminare il divario, questo conta come una “linea„ completata.
Quando un pezzo terre diventa parte del palo.
Immediatamente dopo il pezzo terre, il palo è completato a controllo per verificare le righe, e completato tutti i file vengono eliminati.
Fino a quattro righe può essere completato contemporaneamente.
La tabella seguente fornisce il limite superiore a linee compiuta contemporaneamente da un unico pezzo:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Tetris “livelli„ standard
Tetris standard dispone di 10 livelli di difficoltà, numerate 1 (uno) attraverso 10 (dieci), a livello 1 essere “meno difficile.„
Il livello è l'indice massimo di due valori:
actualLevel = max( initialLevel, earnedLevel );
initialLevel il valore è il livello che il giocatore sceglie quando si inizia un nuovo gioco.
Il modello di livello in funzione di linee a termine è facilmente osservabile nel pre-commerciale MS-DOS versione di Tetris:
{ 0, 1, 2, ..., 10 } --> earned level 1
{ 11, 12, ..., 20 } --> earned level 2
{ 21, 22, ..., 30 } --> earned level 3
{ 31, 32, ..., 40 } --> earned level 4
{ 41, 42, ..., 50 } --> earned level 5
{ 51, 52, ..., 60 } --> earned level 6
{ 61, 62, ..., 70 } --> earned level 7
{ 71, 72, ..., 80 } --> earned level 8
{ 81, 82, ..., 90 } --> earned level 9
{ 91, ... } --> earned level 10
Di conseguenza, il earnedLevel valore è calcolato secondo la seguente algoritmo:
if (linesCompleted <= 0)
{
earnedLevel = 1;
}
else if ((linesCompleted >= 1) && (linesCompleted <= 90))
{
earnedLevel = 1 + ((linesCompleted - 1) / 10);
}
else if (linesCompleted >= 91)
{
earnedLevel = 10;
}
5.10 Tetris standard di cui iterazione ritardo
Tetris standard ha un tempo reale ritardo tra successive linea caduta libera iterazioni che è una funzione dell 'attuale livello di difficoltà.
La seguente relazione tra indice del livello di iterazione e che rientrano ritardo è basato su misurazioni ripetute cronometro a tutti i livelli della pre-commerciale MS-DOS versione di Tetris.
actualLevel iterationDelay [seconds]
(rounded to nearest 0.05)
============ =========================
1 0.50
2 0.45
3 0.40
4 0.35
5 0.30
6 0.25
7 0.20
8 0.15
9 0.10
10 0.05
Quindi, stabilire la seguente formula per il valore di iterazione ritardo in funzione del livello effettivo indice:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Se il bordo è vuota, e non vi è alcun input, un pezzo generato a livello effettivo 1 terre in circa 10 secondi, e un pezzo generato a livello effettivo 10 terre in circa 1 secondo.
5.11 Tetris standard “cliente„
Tetris standard premi punti solo per l'atto di sbarco di un pezzo.
Non ci sono punti assegnati per l'atto di completare una sola riga, o il completamento di due, tre, o quattro linee contemporaneamente.
[Nota: Alcune varianti di Tetris assegnare punti per l'atto di completare le linee, con un aumento esponenziale di bonus per un numero sempre maggiore di linee contemporaneamente completato.
Quindi, la strategia per massimizzare il cliente in tali varianti di Tetris tratta di creare opportunità di “ottenere un Tetris,„ slang per l'utilizzo del “I„ forma per ottenere quattro linee di traduzione simultanea e ottenere un sacco di punti. ]
Se si dispone di un vuoto bordo, e si lascia un non-“I„ fare un pezzo caduta libera e la terra, o immediatamente goccia non “I„ pezzo, è possibile stabilire il punto seguente grafico utilizzando il pre-commerciale MS-DOS versione di Tetris:
actualLevel free-fall instant-drop
points points
=========== ========= ============
1 6 24
2 9 27
3 12 30
4 15 33
5 18 36
6 21 39
7 24 42
8 27 45
9 30 48
10 33 51
Unrotated, non “I„ pezzi caduta di un totale di 18 righe.
Questo rappresenta il punto di differenza tra la caduta libera e immediata-drop casi.
Di sperimentazione di casi intermedi è facile dedurre il punto seguente formula:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Si noti che questa formula non ha nulla a che fare con la distanza cade un pezzo!
E 'severamente una funzione del livello effettivo, e una sanzione per il numero di iterazioni un pezzo è consentito a scendere liberamente.
Questo punisce per un utente che necessitano di tempo per riflettere.
Si noti inoltre che, perché un pezzo non può essere ruotato inizialmente quando depone le uova in un primo, un giocatore è punito con almeno una caduta libera iterazione se rotazioni sono tenuti a mettere un pezzo di palo.
Questo probabilmente non colpisce i giocatori umani, a meno che in qualche modo: riconoscere il pezzo, premere i tasti di traduzione (a “sinistra„ oa “destra),„ premere il tasto “ruotare„ una o più volte, e premere il tasto “goccia,„ tutte in meno di 0.5 secondi a livello 1, o meno di 0.05 secondi a livello 10.
6. Tetris strategia standard
6.1 Introduzione
Una strategia per giocare a un gioco dipende dalle regole del gioco.
Una strategia dipende da quale parametro deve essere ottimizzato.
Standard in Tetris, uno sopravvive completando le righe, si punti di sbarco pezzi, e punteggi più punti possibili per ogni pezzo di una goccia di esecuzione prima che uno o più caduta libera iterazioni traspirare.
A.I. un possibile ottimizzare i punti assegnati per ogni pezzo semplicemente di decidere in merito a una mossa rapidamente e “premendo i tasti„ per eseguire la mossa.
Più importante è uno A.I. sopravvivenza, perché indeterminato sopravvivenza arbitrariamente, un punteggio elevato può essere raggiunto. Tetris perché la caduta di pezzi in un determinato tasso, la A.I. deve prendere delle decisioni in almeno questa veloce - e la A.I. deve compiere passi che completano le righe con un ritmo tale che in media almeno 1 riga per 2,5 pezzi. (Ogni pezzo ha 4 cellule, e ogni riga ha 10 celle.)
Naturalmente si può rinviare il completamento righe di accumulazione di pezzi e la costruzione di un grande palo, ma ci sono solo 200 cellule su tutto il bordo, che in linea di principio può tenere solo 50 pezzi, per cui ogni giocatore (ad esempio un A.I.) devono aver completato come linee una priorità fondamentale.
Standard in Tetris, il gioco membro comprende tra l'attuale bordo di professione e di cui l'attuale pezzo (tipo, posizione e orientamento). Il gioco di Stato possono facoltativamente includere il "Avanti Piece".
6.2 Una sequenza alternata di "S" e "Z" pezzi
Heidi Burgiel, Ph.D., del Department of Mathematics, Statistics and Computer Science a University of Illinois at Chicago, ha dimostrato che una sequenza alternata di "S" e "Z" pezzi si vigore una norma (10-colonna, riga 20) Tetris gioco a fine entro un prevedibile numero di mosse.
Citare l'articolo: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Associati stampata articolo: Mathematical Gazette, luglio 1997, "How to Lose at Tetris"
Heidi Burgiel offre una Java applet che viene eseguito in un browser Internet che dispone di un clone di Tetris alterati che depone le uova in alternanza "S" e "Z" pezzi.
[Il "Standard Tetris" software associato con il documento che state leggendo ha anche una modalità che depone le uova in alternanza "S" e "Z" pezzi. ]
Heidi Burgiel sostenuto che un gioco che coinvolgono l'alternanza "S" e "Z" pezzi (per un tipo Tetris consiglio di amministrazione di 10 colonne e 20 righe) deve terminare prima di meno di 70000 pezzi sono diminuiti.
Standard Tetris software incluso con il presente documento consente ad una persona di giocare con l'alternanza "S" e "Z" pezzi, e cambiare il bordo di larghezza.
E 'facile vedere che le cui schede sono larghezze intero multipli di quattro colonne (esempi: 4 colonne, 8 colonne, 12 colonne, ecc) può essere giocato sempre quando si alternano tra pezzi "S" e "Z", con il palo in aumento non superiori a 4 righe. Lo dico per chiarire che la limitata sopravvivenza descritte nel documento di ricerca di cui sopra è specificamente per il caso di un modello di Tetris pensione (con 10 colonne e 20 righe).
6.3 Irrisolvibili pezzo sequenze in generale
Ci sono intere categorie di sequenze patologiche che non possono essere sopravvissuto.
Sarebbe interessante per calcolare la probabilità totale di incontrare un gioco-che chiude la sequenza, perché questo avrebbe messo un limite superiore sulle prestazioni di qualsiasi strategia, anche in piena conoscenza di tutti i futuri pezzi in un dato punto in un gioco.
6.4 Totale possibili configurazioni di bordo
Dato che l'organo di amministrazione ha 10 * 20 = 200 cellule, e dato che ogni cella può essere solo in uno dei due Stati (vuoti o occupati), il numero totale di configurazioni di bordo deve essere inferiore o pari a: (2 ^ 200).
Dato che ogni pezzo aggiunge 4 cellule ad una pensione, e ogni riga 10 completamento elimina le cellule del bordo, il numero di occupati cellule del consiglio d'amministrazione sarà sempre anche. Per esempio, (3*4 - 1*10) = 2, (1*4 - 0*10) = 4, (4*4 - 1*10) = 6, (2*4 - 0*10) = 8, (5*4 - 1*10) = 10, ecc Così, solo la metà delle (2 ^ 200) bordo configurazioni possono essere raggiunti tramite la riproduzione del gioco.
Quindi, il numero totale di bordo è di circa configurazioni: (2 ^ 199) = 8.03469... * 10^59.
Tuttavia, dobbiamo escludere dal nostro totale qualsiasi configurazione che include riempito le righe, perché riempito le righe vengono eliminati prima della fine di ogni mossa. Qualsiasi configurazione con uno o più righe riempito crollerà a un altro di configurazione che non contiene alcuna riempito righe.
Inoltre, dovremmo escludere qualsiasi configurazione che include un non-riga vuota sopra una o più righe vuote, perché non riga vuota sopra di un riga vuota sempre caduta, e tutte le fermate che rientrano entro la fine di ogni mossa.
Ogni riga può essere in 2^10 = 1024 Stati, uno dei quali è "vuoto", uno dei quali è "piena", e (1024 - 2) = 1022 di cui sono parzialmente occupati. Si esclude la "piena" caso da considerare.
Se la riga in basso è vuota, quindi tutte le righe di sopra della riga in basso deve anche essere vuoto.
Se la riga in basso è parzialmente occupati, poi la seconda fila può essere vuoto o parzialmente occupati.
Continuando questa analisi, si può calcolare un certo numero di configurazioni di bordo che tenga in conto per l'esclusione della piena righe e le restrizioni a vuoto righe: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), che è di circa ((1022 ^ 19) * (1023)).
Quindi, troviamo una più precisa stima del numero totale di bordo stabile configurazioni: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199); vale a dire, circa il 3,74% in meno rispetto alla stima (2 ^ 199).
Tuttavia, il numero effettivo di stabile, accessibile Stati bordo sarà probabilmente inferiore, in particolare a causa del fatto che la maggior parte dei top-righe può essere riempito solo in pochi modi. Come la maggior parte dei top-riempire le righe, un nuovo pezzo generato non può essere spostato o ruotato molto. Questo limita il numero di modi in alto a più righe possono essere riempiti.
6.5 In linea di principio, la migliore mossa può essere trovato per ogni pezzo bordo e configurazione
Perché siamo in grado di ottenere ogni possibile di sette pezzi per un dato bordo di Stato, il numero totale di Stati gioco è di circa 7 * (2 ^ 199) = 5.624... * 10^60.
Perché noi possiamo, in linea di principio, fare una profonda ricerca di tutti i possibili strategie per il futuro in tutte le possibili mosse per un dato gioco Stato, siamo in grado di disporre di un unico "migliori" spostare associata a ciascun gioco.
Si assume che non abbiamo accesso a tutte le informazioni diverso da quello attuale bordo e attuale pezzo, in modo "migliori" significa "la mossa che offre le maggiori possibilità di soddisfare il nostro obiettivo a lungo termine di sopravvivenza".
Una mossa è solo una traduzione (fino a 10 opzioni) e una rotazione (fino a 4 opzioni), si può codificare i migliori muoversi in un singolo byte.
Quindi, in linea di principio, si potrebbe formare un tavolo con 10^61 voci (byte) che ci ha detto il miglior dato spostare qualsiasi bordo di Stato e di corrente pezzo.
Questo, naturalmente, è pratico, così come l'enumerazione di tutti "Go" assi o "Chess" forum non è pratico. Ma il punto è che non vi è una vera soluzione, e vi è una mossa migliore per una determinata configurazione. Ci potrebbe essere altrettanto bene si muove per una determinata configurazione, ma possiamo scegliere arbitrariamente una sola mossa in questo caso.
Molti gioco-giocare algoritmi hanno tabelle che enumerare in modo esaustivo tutti i gioco possibilità stato limitato ai contesti, come ad esempio "l'apertura (iniziale) si muove" o "fine-gioco (finale) si muove" in scacchi. Forse elenco esaustivo di Tetris palo di superfici (circa (20 ^ 10) Stati) è fattibile. E 'un'idea interessante.
Elenco esaustivo di tutti gli Stati di fondo due righe, moltiplicato per sette pezzi possibile, la conservazione e la migliore muoversi in un singolo byte, sarebbe abbastanza facile, che richiede solo il 7 MB di memoria. Forse l'ottimizzazione delle prestazioni per i sette milioni di casi avrebbe fornito i dati grezzi sia per l'analisi e lo sviluppo di semplici modelli di dati; tali modelli potrebbe essere considerato come parte del generale ideale Tetris-giocare strategia.
Si noti che l'esecuzione si sposta ancora più non protegge contro possibili gioco patologico-pezzo che chiude sequenze. E 'solo che ci sarà sempre eseguire mosse che ci offre il massimo potenziale di sopravvivenza futura, dato che tutti i futuri pezzi sono del tutto casuale (e sconosciuti al momento stiamo per decidere come spostare un unico pezzo conosciuto attuale).
6.6 Prestazioni in tempo reale
Un vincolo di fronte alcuni algoritmi strategia è la necessità di prestazioni in tempo reale - il che significa che l'algoritmo deve prendere una decisione entro un determinato periodo di tempo.
Quando un umano svolge Tetris, i pezzi non si fermano che rientrano a dare al giocatore la possibilità di pensare. Che fa parte della sfida di Tetris. Pertanto, un sistema di A.I. che è destinata a simulare il ruolo di un giocatore umano deve anche prendere decisioni a un ritmo dettato dal gioco Tetris.
6.7 Riga e pezzo totali
Nota che, nel lungo termine, il numero di pezzi è sceso molto vicino a 2.5 volte il numero di righe completato - perché ogni riga ha 10 celle, e ogni pezzo è di 4 cellule, e noi dobbiamo completare una riga, in media, una volta ogni (10/4) = 2.5 pezzi diminuito.
In modo da poter utilizzare "completato le righe" e "lasciato cadere pezzi" quasi intercambiabile con l'opportuna costante di proporzionalità. Il più grande errore è quando il bordo è completamente riempito fatta eccezione per un unico divario in ciascuna riga (((10*20)-20)/4) = 45 pezzi abbandonato, ma un deficit del previsto (45/2.5) = 18 completato righe.
6.8 Current-pezzo (e pensione) strategia
Se vogliamo permettere solo il A.I. a conoscenza degli attuali bordo e l'attuale pezzo, e noi consideriamo solo il risultato di spostare l'attuale pezzo in particolare le modalità, allora questo può essere chiamato un "pezzo unico" analisi.
Qui è un grezzi schizzo di come un pezzo di analisi in grado di decidere su una mossa in Tetris:
Current-pezzo di analisi di un gioco Tetris stato
In sostanza cerchiamo tutte le possibili mosse e scegliere la mossa che rese il miglior risultato.
La parte difficile è rating ciascun risultato.
Dobbiamo votare un ipotetico gioco di Stato in base al modo in cui tale Stato sostiene la nostra breve termine e obiettivi a lungo termine.
Il nostro obiettivo a lungo termine è la sopravvivenza. La sopravvivenza dipende da prevenire il palo da traboccante il bordo. Siamo in grado di ridurre il palo di altezza completa formazione di righe che vengono poi eliminati dal palo.
Per formare una riga completa, si deve inserirsi parti di pezzi per ogni colonna di quella riga. Così, abbiamo bisogno di tutte le parti di una riga di essere esposti a cadere pezzi se vogliamo infine compilare l'intera riga.
Se per qualche motivo abbiamo coprire fino vuota parti di una fila di pezzi superiore a qualsiasi riga, quindi siamo ora in grado di riempire vuoti in quelle parti della riga. L'unico modo (supponendo che non scorrevole) per accedere a quei "sepolti buchi" è quello di eliminare le righe sopra che sono parti in qualità di ostacoli.
I seguenti fattori sono tra quelli che possiamo usare per un dato tasso di bordo Stato:
Overall pile height
Il più alto il palo, la nostra situazione peggiore sembra essere, perché siamo più vicini ai traboccante il bordo.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
La rougher il palo, tanto più è probabile che sarà difficile riempire tutti i embedded complessi contorni non appena saranno esposti alla superficie.
Number of buried empty cells
Il più buchi che abbiamo sepolto, il peggio è la nostra situazione, perché dobbiamo scoprire sepolto buche prima di poter completare le corrispondenti righe.
Potete immaginare altri fattori che in genere un ipotetico tasso di bordo su come pure il suo palo in grado di ospitare tutti i possibili futuri pezzi, e come buona la situazione per tutti i pezzi possibile.
Il prossimo numero è come determinare l'importanza relativa di questi fattori.
Un approccio generale è la seguente. Assegnare una serie di "pesi" (importanza relativa) a questi fattori, e quindi simulare numerosi giochi e registrare i risultati di questi giochi (punteggio finale, ecc.) Quindi, assegnare una nuova serie di pesi e simulare una nuova serie di giochi. Basato sulla necessità o meno che la nuova serie di giochi ha avuto risultati migliori rispetto alla precedente serie di giochi, sappiamo se la nuova serie di pesi è stata migliore di quella del precedente serie di pesi.
Nel mio esperimenti ho cercato di ricerca sistematica e casuale alla ricerca di buone combinazioni di peso, ma non ho alcun preavviso su larga scala delle tendenze che ho potuto proseguire. Tuttavia, ho visto molti dossi sorprendentemente armonioso. Ho pensato che fosse interessante il fatto che il rendimento medio potrebbe costituire un buon curva quando è stato un parametro varia lentamente con gli altri parametri terrà presso alcuni valore combinazione.
Il miglior tempo reale, un pezzo Tetris algoritmo nel mondo, creato da Pierre Dellacherie (Francia) nel 2003, deve molto del suo successo alla sua serie di misurazioni (o parametri). Trovare pesi è necessario quando l'ottimizzazione di una strategia, ma è anche fondamentale per iniziare con il tipo di misure che rivelano le caratteristiche dello Stato.
Pierre Dellacherie's invenzione di nuovi modi per caratterizzare ogni bordo rende il suo algoritmo davvero eccellente; le caratterizzazioni bordo di catturare l'importante dimensione strategica del consiglio di amministrazione.
Si potrebbe sviluppare un insieme di diverse dimensioni che caratterizzazione lavorato altrettanto bene; Ho fiducia che sia possibile span pertinenti bordo stato spazio in molti modi diversi che possono essere utilizzati per specificare una strategia funzione. La chiave è trovare caratteristiche che lo stato del progetto di spazio fino a un piccolo numero di dimensioni che possono essere utilizzati per sviluppare una semplice funzione di rating (esempio: il ponderata combinazioni lineari delle caratteristiche utilizzate da Pierre's algoritmo).
Un pezzo algoritmo utilizzato dal "bot" nel "xtris" software (1996) scritto da Roger Espel Llima utilizza pesi determinata da una larga scala di esplorazione di possibili combinazioni di peso "algoritmi genetici". Ricottura simulata è un altro possibile metodo di esplorazione di spazio pluridimensionale combinazioni di peso.
Sembra che, sulla base di varie osservazioni, la funzione di multidimensionale media Tetris prestazioni in funzione dei pesi, esempio: F(w1,w2,w3,...), è "grezzi" (lotti minimi degli enti locali e maxima), il che significa che un semplice multidimensionale "collina di arrampicata" potrebbero non funzionare.
6.9 Quando attuale strategia pezzo, prossimo pezzo, e sono noti bordo
Se una strategia algoritmo è data l'attuale pezzo, il prossimo pezzo, e cartone, allora può prendere decisioni che trarre vantaggio dalla combinazione di pezzi.
La conoscenza del prossimo pezzo in grado di migliorare il successo di un algoritmo di Tetris che giocano da diversi ordini di grandezza. È facile comprendere come conoscere il prossimo pezzo fa una grande differenza nella strategia.
Si può fare "Crazy" si muove, come ad esempio coprire enormi buche, ecc, perché sanno già che il prossimo pezzo può essere usato per "fissare" la situazione. Se non si dispone di conoscenze del prossimo pezzo, si sono costantemente cercando di riprodurre il contrasto, cercando di mantenere le opzioni aperte nel caso in cui il prossimo pezzo non è ideale.
Il disegno seguente mostra come tutte le possibili mosse del pezzo attuale sono considerate, e per ciascuno di tali spostare consideriamo tutte le possibili mosse che coinvolgono il prossimo pezzo.
Strategia che preveda pezzo attuale e il prossimo pezzo
Standard Tetris software utilizza questa strategia quando il "Avanti pezzo" è attivato per l'utente ed è visibile sullo schermo, e quando un due pezzi A.I. è abilitata (come quello scritto da me, Colin Fahey). Se il "Avanti Piece" non è visibile sullo schermo, i miei due pezzi rientra in un unico pezzo A.I..
Il mio unico pezzo A.I. è terribile rispetto agli altri AIs nel Tetris software standard; quindi questa mostra benefici maggiori informazioni (ad esempio: il prossimo pezzo) può essere a un sistema A.I.; è sufficiente per migliorare le prestazioni del mio mediocri in due pezzi, A.I. di diversi ordini di grandezza - facilmente superare le prestazioni dei migliori d'un pezzo A.I. nel mondo.
(Tuttavia, convertendo i migliori d'un pezzo A.I. nel mondo a prendere in considerazione due pezzi sarebbe facilmente migliorarlo di diversi ordini di grandezza, troppo! Conoscere il prossimo pezzo è enorme!)
Il mio primo test con il mio gioco in due pezzi, A.I. durato circa 182 ore (7,6 giorni) su un 800 MHz PC, completando 7216290 righe. Non ho ancora testato l'algoritmo su un computer più veloce.
Quando si salva lo stato di un gioco Tetris (Shift-W) in un file di testo, è possibile quindi copia e incolla l'elenco dei numeri, dalla sezione "heightHistogram", a un foglio di calcolo Excel.
Ogni bin nel istogramma indica il numero di mosse a termine che si è concluso con una particolare palo di altezza (dopo aver completato le righe vengono eliminati). Come potete immaginare, facendo una mossa che elimina totalmente una pila è rara, pertanto il numero totale di mosse che termina con un palo di altezza pari a zero è relativamente basso.
Nel frattempo, si potrebbe prevedere che il palo di altezza generalmente oscilla attorno ad alcuni media, in modo bidoni corrispondenti a queste righe domineranno l'istogramma. Infine, bidoni per la maggior parte dei top-righe (dove siamo in pericolo di straripamento consiglio di amministrazione) sono molto bassi totali.
Nel corso di molte ore, con la A.I. la riproduzione di un unico gioco utilizzando la strategia che preveda la conoscenza dell ' "Avanti Piece", ho preso campioni casuali del gioco di Stato, copiando il palo altezza istogrammi a un foglio di lavoro, come indicato qui di seguito:
Palo di altezza istogrammi registrati in diversi punti in un tipico gioco (con le attuali e di nuova strategia pezzo)
Si può scalare in ogni istogramma per il numero totale di pezzi (numero totale di mosse a termine) per ottenere i seguenti dati:
Istogrammi in scala, e una teoria
La cosa sorprendente è che questi istogrammi in scala guardare identica nonostante i diversi ordini di grandezza del numero di pezzi (completato muove).
Solo guardando i numeri che ho fatto l'ipotesi che la coda della curva è un decadimento esponenziale. Di tentativi ed errori sono arrivato fino a grezzo teoria che la coda è stata descritta da:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Il grafico seguente mostra la scala istogramma su tutta la gamma di righe.
Grafico in scala di istogrammi
Si noti che la curva di 50000 pezzi, e la curva di 2000000 pezzi, e la curva della coda teoria sono quasi indistinguibili in questa scala.
Il seguente è un esame più attento a capo della curva.
Parte inferiore di altezza istogramma
Il seguente è un grande-vista ingrandita dell 'estrema coda fine del misurati e teorici istogramma curve.
Vista ingrandita di estrema coda fine di scala istogrammi
Come potrete immaginare, è molto raro che per il palo di raggiungere tali altezze anche nel caso in esperimenti a lungo - ma anche con i nostri limitati elementi di prova in questa regione estrema, la teoria sembra ancora accettabile.
Nel pieno grafico la teoria sembra sovrapporsi la coda della distribuzione "esattamente", mentre nel grafico ingrandito della coda della coda, vediamo apparente errore. Tuttavia, affermare che questo è insufficiente a causa di dati a queste altezze estreme palo. Se ho aumentato il gioco, per dire, un'altezza di 25 righe invece di 20 righe, in modo che i giochi non chiudere bruscamente, credo che la teoria che ho presentato in precedenza dovrà coincidere perfettamente con la tendenza.
La mia sensazione è che questo istogramma è un diretto risultato combinato del Tetris A.I. e le norme di Tetris. Così, questa stessa distribuzione verrà osservato per qualsiasi casuale lungo termine gioco di Tetris usando il mio particolare A.I. strategia per giocare con "Next Piece" conoscenza.
Inoltre, credo che questo tipo di istogramma può essere utilizzato per confrontare AIs che utilizzano le stesse informazioni durante il gioco. Pertanto, non devi giocare giochi completo (che potrebbe durare per giorni o anni) per confrontare il lungo termine le prestazioni di diversi algoritmi di strategia.
Ad esempio, nonostante la semplicità del mio modello, credo che può essere utilizzato per prevedere la durata media di gioco! Abbiamo semplicemente capire come molti pezzi rende la "linea 21" palo di altezza di un numero significativo, come ad esempio un count di uno.
La frequenza relativa per riga 21, secondo il mio semplice teoria, è:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
È necessario moltiplicare questo numero di (5.3 * 10^(7)), circa 50 milioni di euro, per ottenere un valore di uno.
Così, ho circa prevedere che il mio attuale "Avanti Piece" strategia è solo un bene per l'ordine di circa 10 milioni di righe completato. Una ragione faccio questa stima conservativa è il fatto che anche 18 righe può essere mortale per il mio A.I. perché non permettere la mia A.I. pezzi di prendere in considerazione fino a quando non abbiamo diminuito di almeno una riga! (Questo è in modo che non debba preoccupare di non essere in grado di ruotare pezzi.)
Sono colpito dal fatto che giocare solo 50000 pezzi (e forse molto di un minor numero di pezzi) può darvi una buona stima di lungo termine altezza istogramma, e quindi, una buona stima di ordine di grandezza dei file completato prima della partita estremità. Questo approccio è estremamente utile per valutare rapidamente sottili cambiamenti in un A.I. che sta già facendo molto bene.
6.10 Bordo di metriche di valutazione imitare speculativi look-ahead
Se un algoritmo, come ad esempio quello che ho presentato a questo progetto, cerca semplicemente tutti gli orientamenti pezzo e traduzioni per cadere, e le tariffe risultanti bordo di ogni configurazione secondo alcuni misura di merito, l'algoritmo è essenzialmente imitando "look-ahead".
Quando si impiega i parametri, quali il "palo di altezza", "sepolto buchi", "rugosità superficiale" o "e profondità", uno è veramente utilizzando una forma semplificata di "guardare avanti". Queste caratterizzazioni generale del consiglio di amministrazione fornisce qualche indicazione per la redditività a lungo termine del consiglio di amministrazione.
L'approccio ideale, dato un'infinita quantità di potenza di calcolo, sarebbe quello di valutare un consiglio di amministrazione di configurazione di tutti i possibili sequenze pezzo che possono seguire.
Anche se è necessario prendere in considerazione tutti i 7 pezzi come facenti ugualmente probabile a ciascun livello di look-ahead, è necessario ottimizzare l'effettiva traduzioni (fino a 10) e orientamenti (fino a 4) per ogni pezzo in ogni possibile sequenza! Che sta a (7*10*4) = 280 rami ad ogni livello del consiglio di amministrazione di valutazione! Così, che sta a bordo ((280)^(LookAheadLevels)) configurazioni a prendere in considerazione.
Perché dobbiamo terminare l'analisi dopo un numero finito di livelli, abbiamo bisogno di alcuni non-look-ahead metodo di valutazione del bordo di stato - un modo di dare valori a foglia nodi del nostro sistema di ricerca albero. Quindi, per questi nodi foglia, noi siamo tornati a utilizzare una formula che racchiude l'idea di previsione generale della futura redditività del consiglio di amministrazione!
Questo tipo di speculazione può essere provato con l'd'un pezzo e in due pezzi, algoritmi, in sostituzione del semplicistico bordo metriche di valutazione. Assumere tutti i successivi pezzi sono ugualmente probabili e riassumere le capacità di una commissione per ospitare pezzi di tutti i generi nel migliore dei modi. Questo può essere effettuato con uno, due, o un numero qualsiasi di spostare profondità speculativa - con tutti i pezzi facenti ugualmente probabile (p=1/7),.
Il terminale nodi di questo albero potrebbe richiedere ancora ponderata parametri per valutare, ma la speculazione strati più precisamente catturare l'essenza di ciò che vogliamo fare: determinare come pure un dato bordo in grado di accettare tutti i possibili pezzi, tra cui fattori positivi come ad esempio il completamento delle linee e fattori negativi quali l'aumento globale palo di altezza, ecc
7. Tetris A.I. sistema di dimostrazione
7.1 Panoramica sistema
Questo diagramma seguente mostra il mio sperimentale di set-up.
Il sistema globale di dimostrazione
7.2 Attrezzature
Ecco un breve elenco delle attrezzature utilizzate in questa dimostrazione:
[1] Ontrak Control Systems ADR2200 RS-232 8-Relay Board: $149.00 (USD 2003)
[2] Ontrak Control Systems ADRPWR Power Supply : $ 12.95 (USD 2003)
[3] Creative WebCam Pro (640x480 USB video camera) : $ 39.95 (USD 2003)
Chiaramente è possibile utilizzare simili attrezzature per realizzare gli stessi risultati. Ulteriori informazioni riguardanti l'attrezzatura, sono descritti nelle sezioni corrispondenti del presente articolo.
Qui sono brevi descrizioni dei personal computer utilizzati in questo dimostrazione:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Questa dimostrazione potrebbe facilmente essere riprodotti con altri sistemi operativi, come ad esempio Linux. E 'più importante avere un CPU velocità dell'ordine di 800 MHz o più veloce per il computer che per eseguire il software A.I., perché questo computer farà in tempo reale trasformazione di video.
7.3 Hardware di cattura video
Io ho usato un comune USB videocamera come un dispositivo di acquisizione video per il mio A.I. sistema. In particolare, ho usato la Creative "WebCam Pro", un USB videocamera con 640 * 480 risoluzione.
Creative(TM) USB videocamera descrizione
USB videocamera (in angolo)
USB videocamera (anteriore)
USB videocamera (a bordo CCD)
USB videocamera (principali chip)
OV511 blocchi principali (nota: USB videocamera è OV511+)
7.4 OV511 scheda di dati
ov511ds.pdf
OV511 schede di dati
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "plus") funzionalità di differenze
ov511plus_101.pdf
OV511+ funzione differenze
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Il software di cattura video
Microsoft ha un API molto vecchio di nome "Video for Windows" (VFW) che ho usato con successo per questo progetto. (Clicca link "vfw32.lib" C++ nel vostro progetto, o fare un DllImport di "vfw32.dll" C# nel vostro codice.) Esempi di utilizzo dei VFW API sono ampiamente disponibili.
Un'alternativa è di utilizzare Microsoft's "DirectShow" API a fare di cattura video.
VFW perché ha preso solo una dozzina di linee di codice da usare, ed eseguito accettabile per il mio 800 MHz macchina, non ho preoccuparsi di esplorare il APIs alternativa. DirectShow ma è più contemporaneo API per Windows di cattura video, le rese e potenzialmente molto più elevato il tasso della struttura per lo stesso hardware.
Vedi le "CPF.StandardTetris.STVideoCapture" codice sorgente nel file standard Tetris software per vedere come sia facile ottenere cattura video in base alle proprie progetti.
7.7 Computer interfaccia a relè (via RS232)
Per avere un computer "premere i tasti" sulla tastiera di un altro computer, io ho usato un "relay bordo" controllata di testo comandi inviati da una porta di comunicazione seriale (esempio: "COM1") tramite un cavo RS-232. Ho usato ogni relè per collegare le due fili di una specifica chiave di tastiera per simulare una pressione di un tasto.
Ciò ha richiesto l'apertura della tastiera e le coincidenze. Ci sono molti metodi più facile per la simulazione premendo chiave a un computer, ma ho voluto fare qualcosa che sembrava il più vicino possibile ad una persona veramente digitando su una tastiera.
Uno molto versatile e ben fatto relè bordo ADR2200 è il fatto di Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
È possibile osservare il "CPF.StandardTetris.STRS232" file di codice sorgente per vedere come sia facile inviare bytes attraverso una porta seriale, che può quindi essere utilizzato per controllare dispositivi come ad esempio il bordo ADR2200 mostrato sopra.
8. Tetris software standard
8.1 Scaricare il software
Vai alla fine di questo articolo a trovare un link per scaricare il codice sorgente (C# e C++ versioni) ed è stato costruito il software (*.exe).
8.2 Riassunto delle caratteristiche
Caratteristiche del software:
Istruzione schermi e crediti
La modalità in bianco e nero
Ombra modalità
Suggerimento modalità
Junk righe
Tasso di controllo
Prossimo pezzo
Le dimensioni del Consiglio
S/Z pezzi
Metodo di taratura
Di acquisizione video e il riconoscimento
Console di debug
Salva gioco
Caricare gioco
8.3 A partire aspetto
Aspetto quando il software viene avviato:
Aspetto quando il software è iniziato
8.4 La modalità in bianco e nero
Per impostazione predefinita, il bordo viene visualizzato in colore:
Per impostazione predefinita, il bordo appare nel colore.
La modalità colore può essere cambiato in bianco e nero (Shift + K):
La modalità colore può essere cambiato in bianco e nero.
8.5 Ombra modalità
Ombra indica la modalità in cui un pezzo di terra. Questo è molto utile per pannelli di grandi dimensioni, perché è difficile giudicare se un pezzo di terra.
Ombra indica la modalità in cui un pezzo di terra.
8.6 Suggerimento modalità
Metodo di suggerimento vi mostra dove attualmente selezionato AI-si sposterebbe data la situazione attuale. (Shift + H)
Suggerimento modo in cui la mostra attualmente selezionato AI-sarebbe mossa.
8.7 Junk righe
Inserire "junk" righe nella parte inferiore del palo, uno per uno, manualmente. (Shift + J)
Inserire "junk" righe nella parte inferiore del palo.
8.8 Tasso di controllo
La '+' (più) e '-' (meno) chiavi di controllare la velocità del gioco.
Per impostazione predefinita, il gioco gira ad una velocità standard, secondo le regole e standard di Tetris (velocità basata su livello).
Ecco una tabella dei significati di distorsione di velocità:
-3,-4,...: lentezza proporzionale alla parzialità
-2: più lento di quello di livello 1
-1: normale, ma limitata a livello 6 (0,2 sec) della velocità;
0: normale; Tetris standard di controllo della velocità;
+1: leggermente più veloce di livello 9 (0.05 sec ritardi);
+2: delimitate da tasso di rendering (esempio: 75 Hz);
+3,+4,...: più iterazioni per resi telaio;
Mi piace correre il A.I. a una definizione di "+2" (colpo '+' due volte il tasto se distorsione inizia a zero).
Velocità di distorsione altera la velocità del gioco.
8.9 Visualizza il prossimo pezzo
Hit 'N' per attivare / disattivare il "Avanti Piece". La A.I. di utilizzare il "Avanti Piece" informazioni solo se il "Avanti Piece" appare sullo schermo.
Si può essere certi che l'influenza aviaria non sta utilizzando "Avanti Piece" informazioni quando non è possibile visualizzare il "Avanti Piece" sullo schermo.
Mostra il prossimo pezzo
8.10 Le dimensioni del Consiglio
Premendo Ctrl + (sinistra, destra, giù, fino), si può regolare la dimensione a bordo di dimensioni arbitrarie da 4 * 4 fino a 200 * 400.
Le dimensioni del Consiglio: 4 * 8
Bordo size: 20 * 40
Bordo size: 40 * 80
Bordo size: 20 * 5
Le dimensioni del Consiglio: 4 * 100
8.11 S/Z solo pezzi
L'interessante studio alternata S/Z pattern.
Questo modello non può essere risolto per un 10 * 20 bordo (larghezza * altezza).
Tuttavia, le commissioni che hanno larghezze che sono multipli di 4 sono banale dimostrato per consentire la sopravvivenza infinita.
La AIs sopravvivere indefinitamente in questi casi, anche se essi non sono stati specificamente ottimizzato per gestire questa situazione patologica.
S/Z solo pezzi
8.12 Metodo di taratura video
Hit 'C' per passare alla "modalità di calibrazione". Quando in modalità di taratura, è possibile premere i tasti numerici: {1,2,3,4,5,6,7} per selezionare un pezzo {O,I,S,Z,L,J,T} in cima alla riproduzione di bordo.
Questo è utile come riferimento per l'immagine di acquisizione video a un secondo Standard Tetris software.
Se premete il 0 (zero) chiave, questo renderebbe il bordo bianco.
Si può fingere di uova di pezzi di selezione di un pezzo (1..7), quindi la selezione di un vuoto (0), mentre un secondo computer facendo di acquisizione video per orologi pezzi.
È possibile eseguire il A.I. sul secondo computer e vedere come si tratta con il tuo immesso manualmente patologica scenari Tetris!
Modalità di calibrazione è l'unica volta che si può manipolare la cattura video modello di elaborazione delle immagini (4 * 2 griglia). È possibile utilizzare il mouse per disegnare il rettangolo, ma poi è possibile utilizzare i tasti cursore ( "up", "down", "sinistra", "destra") hanno per fine il controllo delle frontiere - Shift utilizzando il tasto per selezionare di fronte frontiere del rettangolo (esempio: "Shift-sinistra" combo è diverso da "sinistra").
Metodo di taratura video
8.13 Di acquisizione video e il riconoscimento
Premendo 'V' alterna le modalità di acquisizione video. Se opportunamente tarato (vedi "video di taratura" in una sezione precedente), i pezzi di un telecomando schermo video verrà catturato dalla videocamera e classificati - i pezzi e verrà generato nel locale per il gioco a prendere in considerazione A.I. e reagire .
A.I. la produzione deve poi essere trasmessa (tramite l'interfaccia RS-232 alla manifestazione descritto in questo articolo) per il telecomando gioco di input (esempio: tastiera) per la A.I. a svolgere con successo il gioco a distanza.
Se in qualsiasi momento questo circuito chiuso è disturbato (esempio: acquisizione video malfunzionamenti o il segnale di uscita del malfunzionamento), allora la A.I. svilupperà una falsa impressione dello status di telecomando gioco, e la A.I. farà inopportuno decisioni che perdere rapidamente il gioco .
(Nota: Questo problema può essere superato con una modesta quantità di sforzo: Il sistema A.I. bisogno soltanto di esaminare l'intero schermo remoto Tetris in corso per una "realtà" di tutto il bordo, e la A.I. sistema dovrebbe essere preparato per alcuni comandi di uscita non in qualche modo.)
Di acquisizione video e il riconoscimento
9. Tetris originale esperimento AI (2003)
Il seguente mostra la prima versione del Tetris A.I. sistema nel 2003.
Videocamera di fronte a computer # 1 in esecuzione qualsiasi pianura gioco Tetris
# 2 computer in esecuzione standard Tetris software in modalità A.I.
A sinistra: Disegno griglia per calibrare immagine video riconoscimento;
Destra: Tetris pezzo riconoscimento casi.
Frame dal video di Tetris A.I. esperimento nel 2003
10. Migliori d'un pezzo da gioco Tetris-algoritmo nel mondo
10.1 Pierre Dellacherie (2003; Francia)
Pierre Dellacherie (2003; Francia), sviluppatore dei migliori d'un pezzo da gioco Tetris-algoritmo nel mondo
La migliore d'un pezzo, in tempo reale Tetris algoritmo, a mia conoscenza, è stato creato da Pierre Dellacherie di Francia.
La sua incredibile algoritmo a volte riempie più di 2 milioni di righe!
La performance media è l'ordine di 650000 righe.
L'algoritmo prende una piccola quantità di memoria, e viene eseguito ad alta velocità (circa 160 righe al secondo a 800 MHz mio computer).
Prestazioni di Pierre Dellacherie's algoritmo:
Il mio attuale modello per le prestazioni di Tetris AIs è che per un dato pezzo vi è una costante di probabilità che il gioco terminerà, p.
Pertanto, la probabilità che un pezzo non porrà un gioco è q=(1-p).
La probabilità di gioco che chiude dopo k muove è semplicemente il prodotto delle probabilità di sopravvivere (k-1) muove, vale a q^(k-1), e la probabilità che la chiude a la prossima mossa, cioè p.
Questo uno corrisponde al "Geometric Distribution":
Geometric Distribution:
P(k) = p * [(1-p)^(k-1)] = p * [q^(k-1)] = p * exp[ln(q) * (k-1)]
MEAN: [1/p]
VARIANCE: [q/(p*p)]
STANDARD DEVIATION: sqrt( VARIANCE )
Per le piccole p, ln(q) è di circa (-p), e noi abbiamo il seguente:
Exponential Distribution:
P(k) = p * exp[-p * (k-1)]
= p * exp[-p * k ] approximately
MEAN: [1/p]
VARIANCE: [1/(p*p)]
STANDARD DEVIATION: sqrt( VARIANCE )
Ci aspettiamo che la frazione del numero totale di giochi svolto per terminare con un numero di righe nella completato l'intervallo [k1, k2] da:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Dopo aver completato 36 giochi sul mio computer, per un periodo di due giorni, ho trovato un una media di 674827 completato righe.
Secondo la teoria generale di cui sopra, mi attendo il seguente relativa frazione di giochi per finire nelle seguenti gamme completato riga:
p = (1/674827) = 0.000001482 = 1.482*10^(-6)
Completed Row Range Relative Fraction of Total Games
======================= =================================
0 ... 400 000 [exp( 0 )-exp(-0.59)] = 0.447
400 000 ... 800 000 [exp(-0.59)-exp(-1.19)] = 0.250
800 000 ... 1 200 000 [exp(-1.19)-exp(-1.78)] = 0.135
1 200 000 ... 1 600 000 [exp(-1.78)-exp(-2.37)] = 0.075
1 600 000 ... 2 000 000 [exp(-2.37)-exp(-2.96)] = 0.042
2 000 000 ... 2 400 000 [exp(-2.96)-exp(-3.55)] = 0.023
Ecco un grafico che confronta la teoria Exponential Distribution osservati con la distribuzione di giochi.
Prestazioni di Pierre's algoritmo di più di 36 giochi completato
Anche se ci sono pochissimi i giochi in questo insieme di dati, risulta che il modello è abbastanza buona corrispondenza con la distribuzione osservata.
Pierre's introduzione al suo algoritmo:
Pierre iniziato a lavorare su questo pezzo di un algoritmo in 2003,1.
Pierre mi ha inviato una e-mail a proposito del suo algoritmo a 2003.4.9, la notifica dei seguenti prestazioni più di 20 giochi consecutivi:
Game 1 : 1 213 220 rows
Game 2 : 876 618 rows
Game 3 : 37 327 rows
Game 4 : 260 337 rows
Game 5 : 165 349 rows
Game 6 : 2 288 991 rows
Game 7 : 1 112 094 rows
Game 8 : 138 648 rows
Game 9 : 107 089 rows
Game 10 : 1 284 387 rows
Game 11 : 935 011 rows
Game 12 : 80 766 rows
Game 13 : 253 158 rows
Game 14 : 1 877 331 rows
Game 15 : 145 034 rows
Game 16 : 888 081 rows
Game 17 : 433 694 rows
Game 18 : 15 446 rows
Game 19 : 494 498 rows
Game 20 : 16 273 rows
Average is 631167 completed rows.
"L'algoritmo è implementato in Turbo Pascal e completa 7000 righe / min. Con un Athlon 1600+".
I convertiti Pierre's algoritmo a C++ a 2003,6, dopo diversi scambi di e-mail con Pierre. Abbiamo verificato che il A.I. nella versione C++ fatto la stessa decisioni dei Pascal versione.
Ho osservato prestazioni simili alla sua relazione originale; media di circa 650000 completato righe, e alcuni giochi completamento 2 milioni di righe.
Incredibile!
10.2 Conversazione con Pierre Dellacherie
[1] Quando ti crei per la prima volta questo codice?
Ho lavorato sul algoritmo da fine gennaio 2003 fino ad oggi.
[2] Quanto tempo hai lavorato?
Ho lavorato su di esso quasi ogni settimana ... ma non tutti i giorni a lungo perché ho altre attività: purtroppo devo guadagnare soldi come chiunque altro!
[3] Che cosa ha ispirato la progettazione del codice?
Tetris ho giocato 10 o 15 anni fa, ma non avevo giocato ancora per un lungo periodo di tempo. Io direi che sono un "medio" del giocatore che conosce le regole e alcuni trucchi.
Tuttavia, quando ho iniziato a lavorare per l'algoritmo non ho giocare così tanto, perché ho trovato è stato un po 'più efficace per guardare il computer giocare e analizzare le sue debolezze.
[4] Ti è utilizzare qualsiasi “treno„ automazione per il tuo codice per l'esecuzione di meglio? Lo hai commenti per migliorare l'algoritmo?
O avete semplicemente guardare i risultati e decidere di apportare modifiche?
Sono da “vecchia scuola:„ ho semplicemente guardato i risultati e ha deciso di apportare modifiche.
"Automatico di apprendimento" è un tipo di meta-algoritmo in modo non sono sicuro che facendo in questo modo sarebbe più facile in quanto meta-algoritmo dovrebbe essere costruito troppo e che non è così facile!
Che cosa c'è di più, io concordo con Roger Penrose quando afferma (nel suo libro "Shadows of the mind") che la comprensione umana e intuizione non può essere algoritmico (esempio: computo).
[5] Quando si inizia a giocare Tetris, e quando hai avuto l'idea di risolvere con un Tetris A.I.?
Io insegno algoritmica e programmazione di computer (Turbo Pascal e Scilab) per gli studenti che treno per esame di laurea presso le scuole di ingegnere.
A prima, "Computer svolge Tetris" è stata un 'idea che volevo sviluppare per il mio prossimo anno gli studenti.
Non ero a conoscenza della tua pagina web quando ho iniziato a lavorare per l'algoritmo.
In effetti ho avuto la fortuna di essere a conoscenza della tua pagina web solo poche settimane fa, perché credo sarebbe stato scoraggiato dal vostro risultati (come potete indovinare, le prime versioni del mio algoritmo non hanno giocato così bene!).
[6] Qual è il suo stato attuale?
Sono quasi 30 [prima del 2003 aprile 27]. Ho diverse attività: Sono un violoncellista, comporre musica e insegno programmazione di computer.
Ho un laureato in musicologia (1994) e un "Artificial Intelligence and Algorithmic" diploma (1998).
In Francia questo diploma corrisponde al 5 ° anno di studio presso l'Università (4 ° anno è il master e 6 anni è la tesi).
Pierre's composizioni:
[7], dove abiti?
Sono francese e vivo a Rouen (Normandia).
[8] Altre osservazioni:
Alla fine non ho alcuna nuova idea per migliorarla.
Ho cercato così tanto inutile (e sciocco) le cose che dubito che potrebbe essere migliorata.
D'altra parte, credo che potrebbero esistere completamente diversi algoritmi che potrebbe avere una migliore performance.
A proposito, un più veloce di prova consiste nel lanciare i pezzi in un mezzo-box (10 righe X 10 colonne): in un mezzo-box, il mio algoritmo fa una media di 280 righe completato.
Una cosa: l'algoritmo può essere facilmente modificato in un doppio strati algoritmo ([farò] presto le prove).
Amo la musica di film: diventare un film compositore fa parte della mia principale sogni (ma è solo sogno!).
11. Miglior giocatore umani nel mondo
11.1 Tetris Master giapponese (2001 gennaio 27) video
Tetris maestro (2001; Giappone) video
Arika presenta il giapponese Tetris Finals maestro (2001 gennaio 27). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Feedback
12.1 Slashdot thread (2003)
Nel 2003, il mio Tetris A.I. progetto è stato discusso sul forum Slashdot Internet (
http://slashdot.org).
Slashdot (http://slashdot.org) Internet intestazione forum per una discussione del mio progetto Tetris A.I.
Benefactor of mankind--thank you! (Score:4, Funny)
by EnlightenmentFan (617608) on Tuesday January 28, @02:29PM
(#5176294)
(http://betsydevine.weblogger.com/ | Last Journal: Tuesday
January 21, @01:55PM)
Now I can set up computer #1 to play an infinite, obsessive
game of Tetris on computer #2, leaving me free at last to sit
down at computer #3 and get some work done. The $200 for
webcam and other hardware is cheap for an invention like this,
with the revolutionary potential of the wheel, or fire, or
even pizza delivery.
Thank you! Thank you! Thank you!
[ Reply to This ]
The New 4th law... (Score:5, Funny)
by gokubi (413425) on Tuesday January 28, @02:09PM (#5176135)
(http://www.gokubi.com/kinggeorge)
1. A robot may not injure a human being, or, through inaction,
allow a human being to come to harm.
2. A robot must obey the orders given it by human beings
except where such orders would conflict with the First Law.
3. A robot must protect its own existence as long as such
protection does not conflict with the First or Second Law.
4. A robot must never place the long skinny ones horizontally,
unless it leads to a long skinny vertical hole so 4 rows can
be cleared at once the next time a long skinny one comes
around.
[ Reply to This ]
Re:The New 4th law... (Score:5, Funny)
by GuyMannDude (574364) on Tuesday January 28,
@02:14PM (#5176179)
I thought Directive 4 was that any attempt to arrest a
senior officer of OCP Corporation would result in
immediate shutdown!
GMD
[ Reply to This | Parent ]
Comico ispirato dal mio Tetris A.I. progetto (2003) (la prima volta che ho sempre ispirato un fumetto!)
Comico ispirato dal mio Tetris A.I. progetto (2003) (la seconda volta che ho sempre ispirato un fumetto!)
13. La storia di Tetris A.I. progetto
Nella primavera del 1989 mi è stato occupato il salto (e non) di secondo semestre freshman classi a University of Pennsylvania.
Uno dei miei stanza, Bill Matthews, ha avuto il Mac Classic e, talvolta, svolto videogiochi.
Persone che ottenere l'ammissione alla Ivy League scuole sono in genere inclini a competere con le altre persone a tutti i tempi - quando Bill ottenuto il gioco Tetris per la sua Mac, abbiamo immediatamente avviato una prospettiva a lungo termine battaglia per il punteggio elevato.
Come la valutazione salita, il tempo investimenti necessari a fare un piccolo guadagno drammaticamente aumentato.
A fare una lunga storia breve, presumibilmente Bill detiene il punteggio elevato tra di noi, ma ho il sospetto di lui ResEdit utilizzando l'hacking e il punteggio di file!
Bill aveva classi in Wharton School of Business, il alma mater di Michael Milken e Donald Trump, pertanto non è inconcepibile che qualcuno brogli uno impossibile punteggio elevato ...
Nell'estate del 1990 ho preso in prestito da uno 30 MHz Intel 80386 IBM PC mia stanza, Alex Haidas.
Ho comprato un Mac tastiera in un mercato delle pulci di $ 1.
Ho costruito circuiteria porta parallela per consentire l'PC per il controllo della Mac tastiera.
(Io ho usato un CMOS 4040 chip di agire come un tipo di stato solido relè di aderire tastiera contatti all'interno del Mac tastiera.)
Ho scritto un programma per computer che ha utilizzato un albero decisionale come la sua strategia per giocare il gioco Tetris. Nel giro di poche settimane ho avuto un PC la riproduzione del gioco Tetris in esecuzione su un Mac.
Tuttavia, mi è stato richiesto di utilizzare la tastiera PC a dire il A.I. su ogni pezzo che rientrano sullo schermo.
Ho iniziato a lavorare su un circuito utilizzando CdS (Cadmium Sulfide) luce rivelatori che magra contro la Mac schermo e "vedere" la caduta di pezzi, ma CdS sensori reagito troppo lentamente ai cambiamenti di luminosità e il contrasto tra Tetris pezzi e lo sfondo sul Mac Classic schermo è stato troppo basso per discriminare affidabile.
In quei giorni non avevo molto denaro, così è stato troppo rischioso per l'acquisto di un $ 2 Radio Shack phototransistor che potrebbe non fare quello che volevo.
Inoltre, dato il contrasto problema, ero pessimista riguardo l'intero approccio.
Quando ho comprato il mio primo personal computer nel 1996, non sono riuscito a far software sotto Windows 95 su un 100 MHz CPU di fare elaborazione video abbastanza veloce per fare un semplice sistema di visione lavoro.
Ho scritto il codice di elaborazione delle immagini in linguaggio assembly, ma ci è stato così tanto generali prima del mio codice effettivamente percepito dati video che sembrava impossibile fare qualcosa di utile.
Nel 2003, la tecnologia, in particolare CPU velocità, aveva raggiunto un livello di finitura che hanno reso il progetto quasi banale.
Ho scavato il mio vecchio progetto personale e, infine, è finito, ottenendo un certo senso di chiusura.
E 'stato molto emozionante vedere un computer che giocano un altro computer attraverso il USB videocamera e il relè.
Il suono del relè clic, e guardando i pezzi di spin-and-drop in ridicolo, sovrumana velocità, fatta l'esperienza molto gratificante in un modo multisensoriale.
Nel 2003, il mio lavoro è stato riconosciuto dalla Slashdot (
http://slashdot.org), e ho ricevuto un sacco di grandi commenti.
Sono stato invitato a comparire su "Screen Savers" televisione mostra sulla televisione digitale TechTV rete.
Sono andato a San Francisco e apparso su lo spettacolo, e l'esperienza è stata grande.
Più avanti in 2003, ho ricevuto un messaggio da Henk Rogers, invitato alle Hawaii per incontrare lui e Alexey Pajitnov a parlare di creare una specie di standard per Tetris, ai fini di disporre di Tetris tornei.
Un particolare interesse è stata permettendo ai giocatori di utilizzare i telefoni cellulari di “competere gli uni con gli altri,„ indirettamente, attraverso A.I. che imita i giocatori (di una preventiva analisi di ogni giocatore azioni), evitando in tal modo gli effetti della telefonia mobile di latenza di accesso a Internet, e consente ai giocatori di “competere contro„ * I migliori giocatori umani nel mondo (*... o, piuttosto, A.I. imitando i migliori giocatori umani nel mondo).
Sono stato entusiasta della prospettiva di incontrare il creatore di Tetris. Purtroppo, battenti mi rende ansiosi, e ho declinato l'invito.
Nel 2006, ho convertito la mia "Standard Tetris" software da C++ a C# per rendere il software più accessibili e utili ai programmatori contemporanea.
