Tetris
Colin Fahey
1. Software
StandardTetris_2007June4.zip
Tetris codul sursă (C# şi C++ versiuni) si programul ("exe");
4068277 bytes
MD5: 4e957e0ead66064183e9f7e04e618ec0
2. Introducere
Acest articol descrie cum un computer poate juca clasic joc video Tetris de obtinerea de informatii cu privire la bord, determinarea bună de actiuni, iar efectuarea acestor acţiuni.
Acest articol include software capabile de a juca Tetris în timp real.
Produsul software include cele mai bune în timp real, Tetris-playing algoritm în domeniul public.
Acest articol defineşte regulile "standard" de "Tetris," pe baza unui caiet de sarcini, originale 1986 de pre-comerciale versiune de Tetris pentru calculator personal (PC).
În 2003, software-ul inclus în acest articol a fost folosit pentru a permite unui computer să joace Tetris execută pe un computer separat.
Un ordinare USB camera video a fost folosit pentru a permite computerului pentru a "vedea" ecranul de pe celălalt computer.
Un Releu de bord a fost controlată printr-o interfaţă RS-232 pentru a permite computerului să "apăsaţi tastele" de pe tastatură de celălalt computer.
Astfel, primul computer are o relaţie de la cel de-al doilea computer care este similar cu un jucător tipic umane relaţia cu un computer atunci când redaţi Tetris; jocul de stat este cunoscut doar de privirea de la ecran, precum şi acţiuni de jucator poate fi iniţiat numai printr-o tastatură .
De configurare în această demonstraţie a stabilit că un calculator poate juca Tetris mai bine decât un om, în condiţii normale în timp real Tetris joaca condiţii.
3. Istoria Tetris
În 1985, Alexey Pajitnov şi Dmitry Pavlovsky computerul au fost ingineri de la Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre a Russian Academy of Sciences
Alexey şi Dmitry au fost interesate în dependenţă de vânzare în curs de dezvoltare şi de jocurile pe calculator.
Au testat mai multe jocuri diferite.
Alexey a fost inspirat de puzzle antice greco joc, Pentaminos, care a implicat amenajarea puzzle piesele făcute de cinci patrate.
Alexey crezut de ideea de a aranja piesele Pentamino în care acestea au scăzut în plan dreptunghiular la o cupă, dar dat seama ca cele douăsprezece diferite forme de cinci pătrate au fost prea complexe pentru un joc video.
Alexey trecut la utilizarea "tetramino" şapte piese, fiecare făcută de patru patrate.
În 1985.6, Alexey Pajitnov programată prima versiune de pe un Electronica 60 Tetris.
Dmitry Pavlovsky, Alexey Pajitnov, şi Tetris.
În 1985-1986, Vadim Gerasimov, un 16 an vechi liceu computerul prodigy care a lucrat in cadrul Academiei, pentru punerea în aplicare Tetris IBM PC de MS-DOS rulează sistemul de operare.
(Vadim Gerasimov nu mai târziu de cercetare la MIT Media Laboratory, începând cu 1994, prin 2003, primesc un doctorat după finalizarea multe proiecte interesante:
http://vadim.www.media.mit.edu)
Introducerea ecran de 1987-1988 comerciale de pre-lansare de Tetris pentru PC
Jocul juca ecran de 1987-1988 comerciale de pre-lansare de Tetris pentru PC
După 1987, Tetris răspândite pe tot globul.
The Tetris Company, LLC, deţine Tetris de patente.
4. Proiecte inspirat de Tetris
4.1 0-dimensionale Tetris
Nu a fost încă dezvoltat.
4.2 1-dimensional Tetris
Ziga Hajdukovic a dezvoltat 1-dimensional Tetris software care poate fi jucat într-un browser de Internet.
Ziga Hajdukovic-a dezvoltat de asemenea si 1-dimensional Tetris de software pentru telefoanele mobile folosind Java J2ME platforma.
4.3 2-dimensional Tetris
Toate variantele sunt Tetris convenţionale în această categorie.
Această secţiune cuprinde variante interesante.
4.3.1 Cel mai mare joc Tetris vreodată: Delft University of Technology (1995)
Tetris jucat pe un imobil; 2000 m^2 suprafaţa; Delft University of Technology (1995)
Tetris jucat pe un imobil; 2000 m^2 suprafaţa; Delft University of Technology (1995)
4.3.2 Un alt Tetris joc jucat pe o cladire: Brown University (2000)
Tetris joc afişat folosind lumini în ferestre de la o clădire Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
"Cred că a fost doar cele mai incredibile, de o zi am putut imagina în viaţa mea. Ca întotdeauna a spus Steve Jobs, călătoria este recompensa."
"Ea a făcut-mă credeţi că am de proiecte inapoi la colegiu. Lucruri care au fost aproape undoable ca alte persoane să nu credeţi că de a face."
Steve Wozniak (2000)
4.3.3 Joc cu browser de Internet MIT "Green Building" imagine
Vadim Gerisimov's browser de Internet Tetris
Acest browser de Internet Tetris variantă a fost creat de către Vadim Gerasimov.
Acest browser de Internet Tetris "Green" caracteristici de construire, la campusul din MIT.
Tetris Această variantă are doar nouă coloane în loc de standard de zece coloane.
Aceasta varianta de Tetris a prezentat noi piese cu orientări aleatoare.
Vadim Gerasimov este persoana care a scris de cod de computer pentru PC versiune de Tetris în 1986.
Vadim Gerasimov făcut doctoratul de cercetare la MIT Media Laboratory în timpul 1994-2003, de lucru cu privire la multe proiecte interesante.
4.3.4 PIC16F84 12 MHz microcontroler bazate pe NTSC / PAL joc video Tetris
PIC16F84 12 MHz microcontroler bazate pe NTSC / PAL joc video Tetris
Imaginea de mai sus arată NTSC / PAL ieşire video produse de o PIC16F84 12 MHz microcontroler care rulează software-ul scris de Rickard Gunee în 1998.
De semnal video este generat de un software de control de iesiri digitale.
4.3.5 "Scopetris" osciloscop Tetris de Lars Pontoppidan (2007.8)
"Scopetris" osciloscop Tetris de Lars Pontoppidan (2007.8)
Lars Pontoppidan a scris codul pentru microcontroler AtMega32, adaugă şi simplu analogic circuitry, pentru a crea o versiune Tetris, care ar putea fi redat pe un osciloscop.
Anumite registre ale AtMega32 microcontroler de control cu 8 biţi de ieşire semnale, şi, atunci când a trecut printr-o rezistenţă electrică de circuit "R-2R" pentru digital-analogic (D/A) conversie, semnale analogice, rezultă posibilitatea de a controla (x,y) coordonate de un osciloscop grinda (atunci când este osciloscop pentru a stabili "modul de X-Y)."
YouTube video:
FLV video:
4.3.6 Tetris Obfuscated cod: C / Unix
Următoarele au fost acordate "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 Tetris Obfuscated cod: Perl cod
Următoarele este Tetris pentru Perl interpret: Perltris (versiunea 20050717) de către 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) este un standard de descriere a obiectelor grafice, folosind XML.
Mozilla SVG Tetris: Tetris implementat folosind o descriere Scalable Vector Graphics (SVG)
4.3.9 Google "widget" Tetris
Google, Yahoo!, şi Microsoft, şi alte companii, au promovat in miniatura de software bazate pe Internet numit "widgets" care sunt caracterizate de obicei de unele utilizarea dinamică a datelor disponibile pe Internet.
Un astfel de widget disponibile prin intermediul Google este un joc Tetris.
Următorul exemplu este dragut, dar cu forme roti în enervante moduri:
Google "widget" Tetris
Alte Google widgets:
4.3.10 MIT de cercetare hârtie: "Tetris is Hard, Even to Approximate" (2002)
Următoarele cercetare documentul conţine o dovadă că un anumit fel de Tetris varianta este "NP-completă."
Erik D. Demaine, Susan Hohenberger, şi David Liben-Nowell, "Tetris is Hard, Even to Approximate", Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
"NP-completă" este o clasificare a costurilor în timp şi spaţiu de cost al unui algoritm.
Alte clasificări includ "P" şi "NP".
O clasificare a "NP-completă" implică faptul că, pentru probleme mai mari decât unele de dimensiuni mici, algoritm este puţin probabil să găsească o soluţie dorită de practică într-o perioadă de timp sau spatiu.
4.3.11 Cercetare document: "Applying reinforcement learning to Tetris"
Următoarele hârtie, publicat 2005.5.30, Donald Carr de la Departamentul de Informatică, la Rhodes University, Africa de Sud, prezinta cererea de "armare de învăţare" pentru a Tetris.
4.3.12 Tetris Fusta (2007.11)
Tetris Fusta (2007.11)
Tetris de fusta a fost creat de către "Lucy" ("hissyfitoly" pe etsy.com) înainte de 2007.11.
De la creatorul's descriere a diafragmei (oferite spre vânzare pe 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 comentarii referitoare la acest fusta:
"Omul care sucks la fusta Tetris"
"Ahahahaha, m-am gândit la acelaşi lucru."
"Există o linie completa jos în partea de jos, completat de linii ... dispar." "FACE PESTE" "."
"Nu ar trebui să fie un loc in spatele sau fata de lungă în cazul în care piesa ar potrivi perfect ..."
"E chiar urât fusta, totuşi. Prietenul meu nu a putut-mi cumpar destul de ciocolată şi flori pentru a ma convinge sa poarte un lucru."
4.3.13 Tetris etapa actul (2007.4)
Tetris etapa actul (2007.4)
"De la cele care au adus vă Triforce în 2006 ... Comes următoarea generaţie de obiect inanimate Skit ... Tetris."
Local-cache Flash video în format video (FLV) (utilizaţi pentru a juca VLC):
4.3.14 Hilar Tetris variaţii pe un show de televiziune japonez
Tetris variaţii pe show de televiziune japonez
Acest video de la un segment de show de televiziune japonez include hilar variaţii de Tetris, inclusiv:
piese care vanish la debarcare, o piesa care umple o întreagă rând (astfel finalizarea, la un rând de destinaţie), mai multe piese care se încadrează în acelaşi timp, ocazional în formă de bucăţi, o bucată lungă că este puţin prea largă pentru a se potrivi într-un GAP (prevenire a 4-rând finalizarea!), Mario apăsarea de ciuperci şi de a deveni un enorm şi pe moarte!, mici piese rămăşiţe rămase după rânduri sunt distruse, piese de luare in sus gravitatea float la început, etc
Local-cache Flash video în format video (FLV) (utilizaţi pentru a juca VLC):
4.3.15 "The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
"The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
Din descrierea pe YouTube:
"TETRIS jucat de-fiinţe umane reale de zi într-un auditorium:"
TETRIS este a 4-video de executare a GAME OVER Project, regizat de Guillaume REYMOND artist elveţian (NOTsoNOISY agentie de creatie).
Acest stop-motion video a fost împuşcat şi a jucat pentru "LES URBAINES" festivalului
http://www.urbaines.ch la Palais de Rumine (Lausanne, Elvetia), pe November 24th 2007.
Local-cache Flash video în format video (FLV) (utilizaţi pentru a juca VLC):
4.3.16 2.5-dimensional Tetris
Termenul de "2.5-dimensional" este folosit aici pentru a înţelege un non-orthogonal vederea unei bidimensional versiune de Tetris, cu unele grosime în cea de-a treia dimensiune.
(Găsiţi pe link-ul de "tetris3d" în "F7: GAMES".)
4.4 3-dimensional Tetris
Versiune Linux / GTK
Tri-dimensional Tetris, sub forma unui aplet pentru Internet Java browsere:
Tri-dimensional Tetris pentru Windows sistem de operare:
4.5 4-dimensional Tetris
Greg Kaiser's "HyperTetris" (1996): un 4-dimensional Tetris
În [1996], [...], Greg Kaiser pus impreuna o perioada de patru-dimensionale pe varianta clasica de joc.
Utilizarea IrisGL (a.k.a. igl) el a creat un grup de lucru, dacă este greu să joace, joc, utilizând patru ecrane pentru a depict tri-dimensională de diferite aspecte ale intregului joc-spatiu.
[Pentru că] nu există un uşor [inteligibile] modalitate de a atrage obiecte de patru-D pe o perioada de doi-D ecran, cele patru sub-punctele de vedere sunt o metodă practică de a manipula si vizualiza rotaţie şi de traduceri de piese prin cele patru dimensiuni ( în jocul numit x,y,z,w).
Decât completarea linii de blocuri ca în original, în acest caz, obiectivul este de a umple un cub în x,y,z subview (de obicei 4 de 4 de 4).
Celelalte subviews care conţin "w" dimensiune sunt aranjate în mod implicit 4 de 4 până la 10 bloc aranjament cu "w" fiind lung, "vertical" dimensiune în toate cele trei cazuri, cu diferite baze de (x,y), (x,z), (y,z).
Gravity acţionează în direcţia "-w", astfel de piese se încadrează "în" cele trei lung subviews care includ "w", şi nu se muta cu excepţia cazului în care controlul de către jucător în ultimele (x,y,z) subview.
Este nevoie de awhile folosit pentru a ajunge la, să zicem cel mai puţin.
Dacă unele miracol de răbdare sau de schimbare a parametrilor de joc, o face complet, un cub, va dispărea ca şi completat cote, în original Tetris, deşi nu Scorul este păstrat în HyperTetris.
Benjamin Bernard (2000)
4.6 N-dimensional Tetris
Polytope Tetris (2003): o N-dimensional Tetris joc varianta
Polytope Tetris este n-dimensionally Tetris.
Inspirat de HyperTetris program, Polytope Tetris va permite sa joace Tetris de tone, în orice NUMĂRUL DE dimensiune.
Joaca Tetris în 3D, 4D, 5D, sau mai mult.
HyperTetris este un nume de catchier mult decât Polytope (def) Tetris, dar eu nu pot fura numele.
5. "Standard Tetris" caiet de sarcini
5.1 Introducere
Definiţia din "Standardul Tetris" idealizate este un model din cele mai importante caracteristici şi comportamente de prima punere în aplicare a IBM-PC Tetris joc (circa 1986-1988).
Idealizate de model se bazează pe inferring aparentă a intenţiilor de dezvoltatorii de la primul IBM-PC punerea în aplicare a jocului Tetris.
De exemplu, se pare că este rezonabil să se Inferred că dezvoltatorii de prima punere în aplicare a IBM-PC Tetris Joc destinate pentru a selecta forma de fiecare nouă piesă care se încadrează "la întâmplare," şi că utilizarea de Borland C punerea în aplicare a rand() funcţie a fost doar o practică de apropiere intenţia.
Definiţia din "Standardul Tetris" specifică faptul că forma nouă care se încadrează fiecare bucată este de a fi selectate "aleator."
Acest ideal de comportament nu poate fi atins prin orice punere în aplicare, dar implementările poate aproximative ideal comportament.
Deşi nu poate aplicare perfect punerea în aplicare a definiţiei "standard Tetris," idealurile "Standard Tetris" obiectiv implică caracteristici, aplicaţii şi pot fi comparate în funcţie de apropierea de relativă idealurile "Standard Tetris."
Această secţiune descrie un set de elemente, comportamente şi reguli, care, colectiv, să definească "Standard Tetris."
5.2 Standard Tetris bord
Consiliul este o grilă de celule, avand 10 de coloane, şi 20 de rânduri, pentru un total de 10 * 20 = 200 celule.
Standard Tetris bord (10 coloane, 20 rânduri)
Fiecare celulă poate fi unoccupied (gol) sau ocupat (plin).
5.3 Standard piese Tetris
Există şapte (7) standard Tetris de bucăţi, literă cu următorul nume:
{ O, I, S, Z, L, J, T }
Scrisoarea nume sunt inspirate de forme de piese.
Cele şapte Standard Tetris de piese şi "orientările" lor
De la dot (0,0) coincide cu poziţia (6,20) bord în momentul în care piesa apare pentru prima dată.
Prima coloană arată iniţial "orientări."
În cele ce urmează, "orientare" cuvânt este folosit pentru a descrie orice stat dintr-o bucată, în termen de un set de permise de state, care pot rezulta dintr-o rotaţie counterclockwise eveniment.
Schimbarea "orientarii" de la o anumită "orientare" a unei "I, S," sau "Z" bucata, necesită o combinaţie de rotaţie şi de o traducere.
De aceea, cuvântul "orientare" este folosit aici pentru a însemna ceva mai mult de rotatie in pace.
Cu toate acestea, "orientarea" poate schimba doar ca răspuns la un eveniment counterclockwise de rotaţie, şi ciclul de "orientări" distincte pentru fiecare piesa apropie, sau meciuri, rezultate din ciclul de rotaţii pure.
Specială de utilizare a cuvântul "orientare," în acest context, este aproape echivalentă cu sensul de "rotaţie" cuvântul sau "cu unghi," dar cuvântul "orientare" este folosit în loc de "rotatie" la încercarea de a aduce atenţia asupra faptului că unele piese necesită mai mult de rotatie pentru a produce set de permise membre care decurg din counterclockwise "de rotaţie a" evenimentelor.
Piesele pot trece doar orientări (sau supuse unui anumit orizontale sau verticale de traducere) în cazul în care rezultă din bucata de stat nu vor avea nici o ocupate (full) dincolo de zona de celule de la bord şi nici nu ar fi ocupat de celule care se suprapun peste nici în prezent ocupate de celule de la bord.
(În această regulă, ocupat (complet) bucată de celule nu sunt considerate ca parte "în prezent" din "celulele ocupate de bord"
În următoarele comentarii, orice referire la o urmare a unui eveniment counterclockwise de rotaţie se face cu presupunerea că o astfel de rotaţie poate fi efectiv realizate, având în vedere condiţiile existente de piese si tabla.
De "O" (caseta) piesa are doar o singură orientare, si nu se schimba locaţiile de orice de la ocupate (full) de celule ca răspuns la orice eveniment counterclockwise de rotaţie.
De "I" (linie) piesa are două orientări posibile, apare într-o orientare orizontala.
"I" bucata de supleanţi între cele două orientări, ca răspuns la evenimente succesive counterclockwise de rotaţie.
De "S" şi "Z" piese au fiecare două posibile orientări.
Aceste piese de fiecare membru supleant între două orientări în răspuns la counterclockwise succesive de rotaţie a evenimentelor.
De "L", "J", şi "T" piese au fiecare patru orientări posibile, iar aceste orientări sunt rezultatele simplu rotaţii despre centrul de puncte de pe forme.
Atunci când apare pentru prima dată o bucată de pe bord, piesa a "axei" sale "importante" într-o orientare orizontală, iar piesa este în partea de sus a tablei de joc.
Prin urmare, nu sunt piese de iniţial, capabile de a avea orientari lor a fost schimbat. De piese trebuie să coborâm de către un rând de a avea posibilitatea de a avea sale de orientare a fost schimbat.
Odată ce o bucata a scăzut cu un rând de pe tablã, toate orientările piesa poate fi atins (asumându-şi piesa nu este prea aproape de ziduri sau reacţii la curent gramada de piese).
5.4 Standard Tetris flowchart
Următorul este un flowchart aproximative pentru un standard Tetris joc.
Aproximativ flowchart pentru un joc standard Tetris
Aproximativ flowchart pentru un joc standard Tetris
5.5 Standard Tetris bucata crearea
Următoarea diagramă arată (4 celule * 2 celule) regiune cu privire la bord în cazul în care toate piesele apărea atunci când a creat.
Regiunea unde apar piese atunci când a creat în standardul Tetris
Atunci când o nouă piesă apare pentru prima dată pe bord, originea acestuia coincide cu punctul de pe această diagramă, iar piesa va fi complet cuprinse de zona umbrită de pe acest diagrama.
Când este un joc nou inceput, un complet de free-toamna întârziere elapses, şi pe primul-gratuit toamna iteration spawned este o bucata din partea de sus a tablei de joc.
În timpul normal de joc joaca, atunci când un anumit liber-toamna iteration "terenuri-o" bucată, un complet de free-toamna întârziere elapses şi pe lângă liber-toamna iteration spawned este o bucata din partea de sus a tablei de joc.
Când o bucată este spawned, tipul de piesă este selectat utilizând următorul algoritm:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Pentru că există o constantă p (= 1/7) şansa de a selecta un anumit tip de piesa, si toate piesele de acelasi tip sunt indistinguishable, probabilitatea de a avea exact k piese de un anumit tip de teste de n după ce urmează un Binomial de distribuţie:
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 )
Când vom alege din rândul 7 (şapte) piese, la întâmplare, probabilitatea de a avea o anumită piesă este p=(1/7).
Dacă vom face acest lucru n=70 ori, de exemplu, probabilitatea de a avea exact k piese (cu k în intervalul 0 la n) este dat de binomial de distribuţie, aşa cum se arată în următoarea imagine.
Binomial de distribuţie pentru n=70, p=(1/7)
Astfel, se poate anticipa o medie totală de piese de un singur tip de dat un număr total de piese aleatoare, şi se poate calcula de asemenea, varianta de aşteptat şi deviaţii standard (rădăcina pătrată de variabilitate):
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
Când vom converti o valoare aleatoare la o bucata index, va interpreta aceasta, după cum urmează:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[De pre-comerciale MS-DOS versiune de Tetris folosit aleatoare număr funcţia oferite de Borland Pascal compilator.
Asta a utilizat o funcţie pe 32 de biţi variabilă de stat.
Prin urmare, secvenţă de numere aleatoare, a fost limitat la 2^32 distincte de valori.
De aceea, în principiu, un jucator ar putea descoperi, după ce îţi poate 10 de bucăţi, în loc exact în 2^32 set de numere corespunzătoare pentru starea actuală a jocului.
Dacă Tetris simulări sunt executate cu fix 2^32 succesiune de piese, apoi optime de decizii pot fi găsite pentru fiecare loc, în secvenţa.
(Nu par a fi suficiente oportunitati de a fi de bord la un bord complet gol de stat, permitandu-ne pentru a primi sincronizate cu precomputed soluţie optimă cale.)
Riscul de a folosi un număr aleatoriu simplu într-un generator de simulare destinate pentru a găsi o soluţie optimă pentru o problemă este că soluţia optimă va fi doar pentru o anumită problemă cale prin spatiu selectate de simplu aleatoare, generator de număr. ]
5.6 Standard Tetris de control
În timpul jocului juca, sunt disponibile următoarele intrări:
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
Toate intrările în vigoare la marginea de creştere-pozitive de intrare (pe butonul de presa, ca spre deosebire de butonul de eliberare).
Când apare un buton de presa, acest lucru contează ca o cerere.
Deţine un buton jos dincolo de un anumit timp ar putea duce la "auto-repeat" facilitate de o tastatură, a apăsat butonul de generare de noi - dar această facilitate este externe ale motorului de joc.
Factorilor de producţie specificate mai sus, conforme cu originalul Tetris joc.
Rotire cererile pot fi executate dacă nu există nici o suprapunere între dorit de orientare şi de celule stabilite cu privire la bord (cu exceptia celor care se încadrează la bucată), şi în cazul în care nu a dorit de orientare a celulelor stabilite în afara zonei de bord.
Traduceţi cererile pot fi executate dacă nu există nici o suprapunere între dorit tradus şi setaţi configuraţia curentă a celulelor de pe bord (cu exceptia celor care se încadrează la bucată), şi în cazul în care doriţi tradus de configurare nu are nici un set de celule din afara zonei de bord.
Cererile de intrare sunt procesate cu o latenţă care depinde de rata de cadre ale jocului (de exemplu: 75 Hz), cererile şi să aibă efect (dacă este valabilă) instantaneu.
O piesă poate fi abandonat fără nici o linie care se încadrează paşi care au loc.
O piesă poate fi tradus de mai multe ori la stânga sau la dreapta, şi a scăzut ulterior, toate fără întâmpină o linie care se încadrează pas.
Pentru ca un nou spawned piesa nu poate fi rotit, eventual, (pentru că este blocat împotriva început marginea tablei de joc), jucatorul trebuie să accepte cel puţin o piesă care se încadrează pas rotaţii, dacă sunt necesare sau de dorit.
Efectul pe de scor este nesemnificativă.
5.7 Standard Tetris bucata "de destinaţie"
Dacă o piesă este pur şi simplu care se încadrează, care aparţine de un singur rând fiecare bucată care se încadrează în timpul iteration.
Nu va fi o iteration că ea se mută de la un loc cu nici un contact cu suprafete orizontale la un loc care are contact cu suprafete orizontale. După ce se produce acest iterations, piesele sunt în repaus de contact.
Dacă o iteration incepe cu o bucata de repaus în contact cu o suprafata orizontala, piese de "terenuri," şi devine o parte din gramada statice.
5.8 Standard Tetris "linii de completat"
Un rând este completat de un rând de ansamblu în care toate celulele sunt ocupate. Atunci când un rând este completat eliminate de la gramada, şi rândurile de mai sus sunt eliminate rând mutat de pe un rând pentru a elimina decalajul, acest lucru contează ca o "linie de" completat.
Când o bucată a terenurilor el devine o parte din gramada.
Imediat după ce piesa a terenurilor, de ansamblu este verificat pentru completat rânduri, şi completat toate rândurile sunt eliminate.
Până la patru rânduri să poată fi încheiat în acelaşi timp.
Următorul tabel oferă limita superioară pe linii încheiat în acelaşi timp de către o singură bucată:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Tetris "nivelurile" standard
Standard 10 Tetris are nivele de dificultate, numerotate de 1 (o) prin 10 (zece), cu nivel de 1 fiind "cel mai puţin dificilă."
Nivelul indicelui este de maxim două valori:
actualLevel = max( initialLevel, earnedLevel );
initialLevel de valoare este nivelul care jucatorul selecteaza atunci când porniţi un joc nou.
Modelul de nivel, în funcţie de liniile de completat este uşor de observat în pre-comerciale MS-DOS versiune de 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
Astfel, earnedLevel valoare este calculat în conformitate cu următorul algoritm:
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 care se încadrează iteration întârziere
Tetris standard are o întârziere în timp real între succesive de toamna-line gratuit iterations că este o funcţie de actualul nivel de dificultate.
Următoarele relaţie între nivelul indicelui şi care se încadrează iteration întârziere se bazează pe măsurători repetate Cronometru, la toate nivelurile de pre-comerciale MS-DOS versiune de 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
Astfel, vom stabili următoarea formulă pentru iteration întârziere valoare, în funcţie de nivelul real Index:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
În cazul în care consiliul este gol, şi nu există nici un utilizator de intrare, o bucată spawned la nivelul real 1 terenurilor în aproximativ 10 secunde, si o bucata spawned la nivelul real 10 terenurilor în aproximativ două 1.
5.11 Standard "Scorul" Tetris
Standard Tetris doar premii de puncte pentru a actului de debarcare o bucată.
Nu sunt acordate puncte pentru completarea act de o singură linie, completarea sau două, trei sau patru linii simultan.
[Notă: Unele variante de atribuire Tetris puncte pentru completarea act de linii, cu o creştere exponenţial bun pentru un număr tot mai mare de simultan, completat de linii.
Astfel, strategia pentru maximizarea scorul în astfel de variante de Tetris implică înfiinţarea de şanse pentru a "obţine o Tetris," argou pentru utilizarea "I" forma de a obtine patru linii simultane şi o mulţime de puncte de achiziţie. ]
Dacă aveţi un gol bord, şi veţi permite un nu-"I" face o bucată de liber se încadrează şi teren, sau dacă o picătură imediat ne-"I" bucata, aveţi posibilitatea să stabilească următoarele punct folosind diagrama de pre-comerciale MS-DOS versiune de 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" piese de toamna-un total de 18 rânduri.
Acest punct de conturi pentru diferenţa între libera-toamna si instant-drop cazuri.
Prin experimente intermediare cazuri, este usor de Inferred următorul punct formulă:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Notaţi faptul că această formulă nu are nimic de a face cu o bucata de distanta cade!
Este strict o funcţie de nivelul real, şi o penalizare pentru numărul de iterations o bucată este permis să se încadreze liber.
Acest punish un utilizator pentru a avea nevoie de timp să se gândească.
De asemenea, reţineţi că în cazul în care o piesă iniţial nu poate fi rotit atunci când este primul spawns, un jucator este pedepsit de către cel puţin unul gratuit-toamna iteration rotaţii, dacă sunt necesare pentru a plasa o piesă în ansamblu.
Aceasta, probabil, niciodată nu afectează umane jucători, cu excepţia cazului în care cumva: recunosc piesa, apăsaţi tastele de traducere "(la stânga" sau la "dreapta)," apăsaţi tasta "roti" una sau mai multe ori, şi apăsaţi "drop-cheie," toate în mai puţin de 0.5 secundă la nivel 1, sau 0.05 secunde mai puţin decât la nivel 10.
6. Standard Tetris strategie
6.1 Introducere
O strategie pentru redarea unui joc depinde de regulile jocului.
O strategie care depinde de un parametru este de a fi perfectă.
În Standard Tetris, unul supravietuieste prin completarea rânduri, devine puncte pentru piese de destinaţie, şi înscrie cele mai multe puncte posibil pentru fiecare bucata cu o cădere, înainte de executarea uneia sau a mai multor liber-toamna iterations transpire.
Un A.I. pot optimiza de puncte acordate pentru fiecare piesa pur şi simplu de a decide pe un deplaseze rapid şi "apăsând tastele" pentru a executa muta.
Mai important pentru un A.I. este de supravieţuire, deoarece supravieţuirea nedeterminată reprezintă un mod arbitrar de mare scor poate fi atins. Deoarece Tetris piese de toamna, la o rată specifică, A.I. trebuie să ia decizii cu cel puţin acest rapid - şi trebuie să facă A.I. completă rânduri că se mută la o rată care medii de cel puţin 1 rând pe 2,5 piese. (Fiecare piesa are 4 celule, fiecare rând şi are 10 de celule.)
Desigur, se poate să amâne finalizarea rânduri de către acumularea de piese şi construirea unui ansamblu de mare, dar exista doar 200 de celule de pe întregul bord, care, în principiu, nu poate decât să deţină 50 de bucăţi, astfel încât orice player (cum ar fi o A.I.) trebuie să aibă ca liniile de finalizarea o prioritate fundamentală.
În Standard Tetris, jocul de stat include bord, ocupaţia actuală şi cea curentă, care se încadrează bucata (tip, poziţie, şi orientare). Jocul de stat include mai opţional "Next piesa".
6.2 O succesiune de alternative "S" şi "Z" bucăţi
Heidi Burgiel, doctorat, pe de Department of Mathematics, Statistics and Computer Science la University of Illinois at Chicago, s-a dovedit că o succesiune de alternative "S" şi "Z" bucăţi va forţa un standard (10-coloana, 20-RL) Tetris joc pentru a se termina într-un număr de previzibil de mutãri.
Citat din articol: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Asociat tipărite articol: Mathematical Gazette, iulie 1997, "How to Lose at Tetris"
Heidi Burgiel ofera o Java applet care se execută într-un browser de Internet caracteristici care o clona modificat Tetris că spawns alternativ "S" şi "Z" piese.
[The "standard Tetris" software asociate cu documentul pe care o citiţi de asemenea, are un modul care spawns alternativ "S" şi "Z" piese. ]
Heidi Burgiel a susţinut că un joc care implică alternative "S" şi "Z" bucati (pentru un standard de bord Tetris de 10 coloane si 20 randuri) trebuie să se termine înainte de mai puţin de 70000 de piese au scăzut.
Tetris de software standard incluse în acest document permite o persoană pentru a juca jocuri cu alternative "S" şi "Z" bucăţi, precum şi schimbarea consiliului latime.
Este uşor să vedem că panouri a căror număr întreg lăţimile sunt multipli de patru coloane (exemple: 4 coloane, 8 coloane, 12 coloane, etc), poate fi jucat la infinit, atunci când piesele supleant între "S" şi "Z", în creştere cu gramada nu mai mare de 4 rânduri. Mentionez aceasta să se precizeze clar că supravieţuire limitate de cercetare descrise în documentul menţionat mai sus este specific pentru cazul unui standard de Tetris bord (cu 10 de coloane şi 20 de rânduri).
6.3 Unsolvable bucata de secvenţe, în general,
Există întregi categorii de secvenţe patologice care nu pot fi supravietuit.
Ar fi interesant pentru a calcula totalul probabilitatea de a întâlni un joc-secvenţă de încheiere, pentru că acest lucru ar pune sus un legat cu privire la îndeplinirea oricărei strategii, chiar şi în deplină cunoştinţă de toate viitoarele piese de la orice punct dat într-un joc.
6.4 Total posibile configuraţii de bord
Având în vedere faptul că Consiliul a 10 * 20 = 200 celule, şi având în vedere faptul că fiecare celulă poate fi în una din cele două state (goale sau ocupate), numărul total de configuraţii de bord trebuie să fie mai mică sau egală cu: (2 ^ 200).
Având în vedere că fiecare piesă adaugă 4 celule de la un bord, fiecare rând şi completarea elimină 10 celule de la bord, a numărului de celule ocupate de pe bord vor fi întotdeauna, chiar. De exemplu, (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, etc Astfel, doar jumătate din (2 ^ 200) bord configuraţii poate fi atins prin jocul.
Astfel, numărul total de configuraţii de bord este de aproximativ: (2 ^ 199) = 8.03469... * 10^59.
Cu toate acestea, ar trebui să excludă de la orice nostru total de configurare care include completat rânduri, rânduri pline, deoarece sunt eliminate înainte de sfârşitul fiecărui completat muta. Orice configuraţie cu una sau mai multe rânduri va restrângere completat la alta configurare, care nu conţine nici un fel de completat rânduri.
De asemenea, ar trebui să excludă orice configuraţie care include un rând gol ne-o mai sus sau mai multe rânduri goale, pentru că un nu-i nimic în Coş de mai sus un rând gol rând întotdeauna va scădea, precum şi toate staţiile de care se încadrează înainte de sfârşitul celui de fiecare mutare.
Fiecare rând poate să fie în 2^10 = 1024 state, dintre care una este "gol", dintre care una este "completa", si (1024 - 2) = 1022 de care sunt parţial ocupate. Ne exclude "completa" de la caz considerare.
Dacă în partea de jos, rând este gol, atunci toate rândurile de mai sus în partea de jos, rând trebuie de asemenea să fie gol.
Dacă în partea de jos, rând este parţial-au ocupat, cel de-al doilea rând, atunci poate fi gol sau parţial-au ocupat.
Continuarea acestei analize, putem calcula un număr de configuraţii de bord care să ia în considerare a excluderii din plin de rânduri şi de restricţii de gol pe rânduri: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), care este de aproximativ ((1022 ^ 19) * (1023)).
Astfel, vom găsi o estimare mai precisă din numărul total de configuraţii stabile bord: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199); adică, circa 3,74% mai puţin decât (2 ^ 199) estimare.
Cu toate acestea, numărul efectiv de stabil, accesibil bord state este probabil să fie mai mici în special datorită faptului că cele mai multe rânduri de sus pot fi completate numai în câteva moduri. Ca de cele mai multe rânduri de sus-completa, un nou generat piesa nu poate fi mutat sau rotit foarte mult. Aceasta limitează numărul de moduri de Top-cele mai multe rânduri pot fi completate.
6.5 În principiu, cea mai bună mutare poate fi găsit pentru orice bord si piesa de configurare
Pentru ca noi a putea a lua orice posibil de şapte piese pentru orice consiliului de stat, numărul total de joc de state este de aproximativ 7 * (2 ^ 199) = 5.624... * 10^60.
Pentru că noi putem, în principiu, să faceţi şi o adâncime de căutare din toate posibilele futures, pentru toate mutãri posibile pentru un anumit joc de stat, putem avea un singur "cel mai bun" muta asociate cu fiecare joc de stat.
Presupunem că nu avem acces la toate informaţiile, altele decât actualul bord şi piesa actuală, aşa încât "cel mai bun" înseamnă "a muta, care oferă cea mai mare şansă de a satisface nostru obiectiv pe termen lung de supravieţuire".
O mutare este doar o traducere (de până la 10 opţiuni) şi o rotaţie (de până la 4 optiuni), putem cu uşurinţă în cele mai bune codifică muta într-un singur octet.
Deci, în principiu, am putea forma un tabel cu 10^61 intrări (octeţi) ne-a spus că cea mai bună mutare dat nici un consiliu de stat şi actuale bucata.
Bineînţeles, acest lucru este imposibil, doar ca enumerating all "Go" panouri sau "Chess" placi este imposibilă. Dar este că există o adevărată soluţie, şi există o mutare cele mai bune pentru o anumită configuraţie. Nu ar putea fi la fel de bună se mută pentru o anumită configuraţie, dar putem alege în mod arbitrar o singură mutare, în acest caz.
Multe Joc-joaca algoritmi de tabele care au exhaustively enumera toate posibilităţile jocului de stat în termen de contexte limitate, cum ar fi "deschiderea (iniţiale) se mută" sau "la sfârşitul jocului (finală) se mută" în şah. Poate exhaustivă enumerarea Tetris gramada de suprafete (aproximativ (20 ^ 10) state) este fezabil. Este o idee interesanta.
Enumerare exhaustivă a tuturor statelor în partea de jos, din două rânduri, înmulţită cu cele şapte posibile de piese şi stocarea în cele mai bune mutaţi într-un singur octet, ar fi destul de uşor; necesită doar 7 MB de memorie. Poate optimizarea performanţei pentru aceste şapte milioane de cazuri ar furniza date brute pentru ambele analiza si dezvoltarea de modele simple pentru a datelor; astfel de modele ar putea fi considerate ca parte din totalul ideal de joaca Tetris-strategie.
Reţineţi că, executând cele mai bune mutãri încă nu ne proteja împotriva unor posibile patologice Joc-terminală bucata de secvenţe. E doar faptul că întotdeauna vom efectua mutãri care ne ofera maxim de potenţial de supravieţuire pentru viitor având în vedere faptul că toate viitoarele piese sunt complet aleatoare (şi necunoscut în momentul suntem de a decide modul de a muta un singur curent cunoscut bucata).
6.6 Real-time performance
O constrângere confruntă cu unele strategii de algoritmi este nevoia de performanţă în timp real - în sensul că algoritmul trebuie să ia o decizie în termen de o anumită perioadă de timp.
Atunci când un om joacă Tetris, piese care se încadrează nu opri pentru a da o sansa jucător de a gândi. Asta este o parte a provocării de Tetris. Astfel, un sistem de A.I. că este menit să simuleze rolul unui jucător uman trebuie, de asemenea, să ia decizii la o rată de dictat de joc Tetris.
6.7 Rând si piese Totale
Reţineţi că, în termen lung, numărul scăzut de piese este foarte aproape de 2.5 ori numărul de rânduri completate - pentru că fiecare rând are 10 de celule, şi fiecare bucată este de 4 celule, iar noi trebuie să completeze un rând, în medie, o dată la fiecare (10/4) = 2.5 piese renunţat.
Deci, putem folosi "completat rândurile" şi "a scăzut de piese" aproape interchangeably cu constanta de proporţionalitate este cazul. Cea mai mare eroare este atunci când consiliul este acoperita complet cu excepţia unui singur lacune în fiecare rând (((10*20)-20)/4) = 45 piese renunţat însă o deficienţă a anticipat (45/2.5) = 18 completat rânduri.
6.8 - Piese de curent (şi a consiliului de administraţie) strategie
Dacă vom permite doar A.I. să aibă cunoştinţe de bord curentă şi cea curentă, piesa, si ne ia în considerare rezultatul doar de a muta piesa curente, în special, puncte de vedere, atunci acest lucru poate fi numita "o piesă-o" analiză.
Aici este o stare brută schita de modul în care o singură bucată de analiză poate decide cu privire la o mutare în Tetris:
- Piese de curent de analiză a unui joc Tetris de stat
Practic vom încerca toate posibilele mută şi alege muta că randamentele cel mai bun rezultat.
De o parte este dificil de rating fiecare rezultat.
Noi trebuie să notez o ipotetică joc de stat în funcţie de cât de bine un astfel de stat suportă noastre pe termen scurt şi pe termen lung, obiective.
Nostru obiectiv pe termen lung este de supravieţuire. Supravieţuirea depinde de prevenirea gramada de la overflowing de bord. Putem reduce gramada de înălţime fac complet rânduri care apoi sunt eliminate din ansamblu.
Pentru a completa un formular rând, trebuie să se potrivească în părţi de piese, pentru fiecare coloană din acel rând. Astfel, am nevoie de toate piesele dintr-un rând pentru a fi expuse la care se încadrează piese, dacă noi ne pentru a completa întregul rând.
Dacă, din anumite motive am acoperi până gol părţi dintr-un sir de piese mai mare cu privire la orice rând, atunci noi suntem acum în imposibilitatea de a completa în acele părţi ale gol rând. Singura modalitate (presupunând că nu glisante) de a accesa aceste "ingropat" gauri "este de a elimina rândurile de mai sus, care au părţi care acţionează ca obstacole.
Următorii factori sunt printre cei pe care îi puteţi folosi pentru a rata un anumit stat bord:
Overall pile height
Cu cât este mai mare de ansamblu, mai rău ne pare a fi situaţia, pentru că suntem mai aproape de overflowing de bord.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
La gramada de rougher, cu atât mai probabil este că va fi dificil să completaţi toate embedded complexe de conturul pe măsură ce acestea sunt expuse la suprafata.
Number of buried empty cells
De mai multe gauri pe care le-am ingropat, situaţia noastră este mai rău, pentru că trebuie să ne dezvălui ingropat găuri înainte de a vă putea completa rândurile corespunzătoare.
Vă puteţi imagina că alţi factori, în general, rata de bord pe o ipotetică cât de bine îşi poate găzdui toate gramada de piese posibile pentru viitor, şi cum arată situaţia de bună pentru toate cele posibil de piese.
A doua problemă este modul de a determina importanţa relativă a acestor factori.
O abordare generală este urmatoarea. Alocaţi un set de "greutăţi" (importanţa relativă) pentru a acestor factori, şi apoi simulează numeroase jocuri şi să înregistreze rezultatele acestor jocuri (scor final, etc.) Apoi, alocaţi un nou set de greutăţi şi simulează un nou set de jocuri. Pe baza sau nu noul set de jocuri au avut rezultate mai bune decât cele anterioare set de jocuri, ştim dacă nou set de greutăţi a fost mai bun decât cel precedent set de greutăţi.
În propria mea de experimente am încercat şi căutarea sistematică aleatoare caută bune combinaţii de greutate, dar nu am observaţi orice scară largă a tendinţelor pe care le-am putut urmări. Cu toate acestea, am vazut surprinzator buna bumps. M-am gândit că aceasta a fost interesant faptul că performanţa de mediu ar putea forma o buna curba de un parametru, atunci când a fost lent, variat cu alţi parametri valoare deţinute la unele combinaţie.
Cel mai bun timp real, o piesa-Tetris algoritm din lume, creat de Pierre Dellacherie (Franţa) în 2003, datorează mult din succesul său set de măsurători (sau măsurători). Găsirea greutăţi atunci când este necesară o optimizare a strategiei, dar, de asemenea, este critică pentru a porni cu tipuri de masuratori care dezvăluie caracteristicile relevante ale statului.
Pierre Dellacherie's inventarea unor noi modalităţi de a caracteriza fiecare bordul său algoritm face chiar bine; consiliului characterizations capteze strategice importante dimensiuni ale consiliului de stat.
Unul ar putea dezvolta un set diferit de caracterizare dimensiuni care a funcţionat la fel de bine; am încredere că este posibil să se span relevante bord, spaţiu de stat în diferite moduri, care pot fi folosite pentru a specifica o strategie de funcţie. Cheia este de a găsi caracteristici că proiectul de spaţiu de stat, faţă de un număr mic de dimensiuni care pot fi folosite pentru a dezvolta un simplu Opinia funcţie (de exemplu: liniare determinate de combinaţii de caracteristici utilizate de către Pierre's algoritm).
Piese de un algoritm utilizat de către "bot" în "xtris" de software (1996) scrise de Roger Espel Llima foloseşte greutăţi determinate de o scară largă de explorare de greutate de combinaţii posibile de "algoritmi genetici". Simulated recoacere este un alt posibil metoda de analiza multidimensionala spaţiu de greutate combinaţii.
Se pare că, pe baza diferitelor observaţii, multidimensionale, în funcţie de medie Tetris de performanţă, în funcţie de greutatea, de exemplu: F(w1,w2,w3,...), este "stare brută" (loturi de minim local şi maxima), ceea ce înseamnă că un simplu multidimensionale "urca dealul" ar putea să nu funcţioneze.
6.9 Strategia de curent, atunci când piesa, de lângă bucată, şi a consiliului de administraţie sunt cunoscute
Dacă un algoritm este prezentat strategia curentă bucata, de lângă bucată, şi a consiliului de administraţie, atunci el poate lua decizii care să profite de combinaţie de piese.
Cunoştinţe de următoarea bucată poate îmbunătăţi succesul unei Tetris joaca algoritm de mai multe comenzi de magnitudine. Este uşor de înţeles cum a cunoaşte următoarea bucată face o mare diferenţă de strategie.
Se poate face "nebun" misca, cum ar fi uriase, care acoperă goluri, etc, pentru că deja ştii că următoarea bucată poate fi folosit pentru a "stabili" a situaţiei. Dacă nu aveţi cunoştinţe de lângă bucată, sunteţi constant, încercând să joace cote, încercaţi să vă menţineţi deschis opţiunile următoare, în cazul în care piesa nu este ideală.
Urmatoarea schita cum arată toate mutãrile posibile de piese curente sunt considerate, şi pentru fiecare astfel de mutare vom considera toate mutãri posibile care implică următoarea bucată.
Strategia actuală care implică şi piese de lângă bucata
Tetris de software standard utilizează în momentul în care această strategie "Next piesa" este activată de către utilizator şi este vizibilă de pe ecran, şi în momentul în care o bucată de două A.I. este activat (cum ar fi de-o scrise de mine, Colin Fahey). În cazul în care "Next piesa" nu este vizibil pe ecran, mi se încadrează în două bucata înapoi la o bucata A.I..
My-o bucata A.I. este teribilă în comparaţie cu celelalte AIs în Tetris de software standard; astfel încât această benefice vă arată mai multe informaţii (de exemplu: în următorii bucata) poate fi la un sistem A.I.; este suficient pentru a îmbunătăţi performanţa mea mediocre două piese A.I. de mai multe ordine de magnitudine de - uşor surpassing performanţa cea mai bună piesă A.I.-o în lume.
(Cu toate acestea, convertind-o în cele mai bune piese A.I. din lume să aibă în vedere două bucăţi ar îmbunătăţi cu uşurinţă de către mai multe comenzi de magnitudine, prea! Cunoasterea de lângă piesa este imens!)
Primul meu test de joc cu meu de doua piesa A.I. a durat aproximativ 182 oră (7,6 zile) pe un 800 MHz PC, completand 7216290 rânduri. Nu am testat pe un algoritm mai rapid computer.
Când salvaţi o stare de joc Tetris (Shift-W) la un fişier text, puteţi apoi copiaţi şi lipiţi lista de numere, de la secţiunea "heightHistogram", la o foaie de lucru Excel.
Fiecare cutie în histogramă indică numărul de completat mutãri care sa încheiat cu o gramada special înaltime (după rânduri sunt complet eliminate). După cum vă puteţi imagina, a face o mutare pe care elimină complet o gramada este rară, astfel încât numărul total de mutãri care se sfârşeşte cu o gramada de înălţime de zero este relativ scăzut.
În acelaşi timp, aţi putea aştepta ca gramada înălţime variază în general în jur de unele medii, fasole, corespunzătoare astfel încât aceste rânduri va domina histogramei. În cele din urmă, fasole de cele mai multe rânduri de sus (unde suntem în pericol de a overflowing de bord) au un nivel foarte scăzut Totale.
Pe parcursul a multor ore, cu A.I. juca un singur joc de strategie care implică utilizarea de cunoştinţe "Next piesa", am luat probe de aleatoare, jocul de stat, copierea gramada de înălţime histograms la o foaie de calcul, aşa cum este arătat mai jos:
Teanc înălţime histograms înregistrate la diferite puncte într-un joc tipic (cu curent-şi-next-strategie bucata)
Puteţi fiecare scară histogramă la numărul total de piese (numărul total de completat mutãri) de a obtine urmatoarele date:
Scalate histograms, precum şi o teorie
De lucru este de remarcat că aceste scalate histograms arate identic în ciuda diferite de ordine de magnitudine de numarul de piese (completat mutãri) implicate.
Doar cu privirea de la numerele-am făcut ipoteza că coada de curba este o exponenţială de degradare. Prin probe de eroare şi am venit cu teoria stare brută care coada a fost descrisă de către:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Următorul grafic arată scalate histogramei pentru întreaga gamă de rânduri.
Grafic de scalate histograms
Reţineţi că, curba de 50000 bucăţi, şi curba de 2000000 de bucăţi, şi curba de coada teorie sunt aproape indistinguishable la această scară.
Următoarele este mai atent la conducerea curba.
Lower parte din înălţimea histogramă
Aceasta este o foarte mult-magnified de vedere extreme coada sfârşitul celei de-a măsurat şi histogramă curbele teoretice.
Magnified de vedere extreme, coada sfârşitul scalate histograms
Aşa cum s-ar putea să aşteptaţi, este foarte rare de ansamblu pentru a ajunge la aceste înălţimi, chiar în timp de experimente - dar chiar si cu dovezi noastră limitată în această regiune extremă, tot teoria pare acceptabil.
În diagramă completă teoria pare să se suprapun peste coada de distribuţie "exact", întrucât, în cadrul planului de magnified coada de coada, vedem aparenta eroare. Cu toate acestea, aş afirma că aceasta este din cauza insuficienţei datelor la aceste extreme, gramada inaltime. Dacă I a crescut de la tabla de joc, să zicem, o înălţime de 25 de rânduri în loc de 20 de rânduri, astfel încât să nu pună capăt jocuri brusc, cred in teoria am prezentat mai sus ar coincid perfect cu tendinţa.
Impresia mea este că această histogramă este un rezultat direct al combinate Tetris A.I. şi regulile de Tetris. Deci, această distribuţie va fi aceeaşi pentru orice aleatoare observate pe termen lung joc de Tetris, folosind meu special A.I. strategie de joc cu "Next piesa" cunoştinţe.
Mai mult decât atât, cred că acest tip de histogramă pot fi folosite pentru a compara AIs angajeze că aceleaşi informaţii în timp ce redaţi. Astfel, nu trebuie să joace jocuri complete (care ar putea dura zile sau ani) de a compara performanta pe termen lung a diferitelor strategii de algoritmi.
De exemplu, în ciuda simplitatea modelul meu, cred ca pot fi folosite pentru a estima durata medie de joc! Suntem pur şi simplu seama cum face de multe piese "rândul 21" gramada înălţimea de un număr semnificativ, cum ar fi un contor de unul.
Frecvenţă relativă pentru rândul 21, în conformitate cu teoria mea simplă, este:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Trebuie să înmulţim acest număr de (5.3 * 10^(7)), circa 50 milioane de euro, pentru a obţine o valoare de unu.
Astfel, am aproximativ mele actuale prevăd că "Next piesa" Strategia este de numai bune pentru de pe ordinea de aproximativ 10 de milioane de completat rânduri. Un motiv am face această estimare conservatoare este faptul că, chiar şi 18 rânduri poate fi mortala pentru A.I. mea pentru că eu nu-mi permite A.I. să ia în considerare până la piese pe care le-aţi scăzut cu cel puţin un rând! (Aceasta este deci nu am să vă faceţi griji pentru a nu fi capabil la spre rotate piese.)
Sunt impresionat de faptul că joacă doar 50000 de piese (şi, eventual, mult mai puţine piese) poate da o estimare a extrem de buna pe termen lung înălţimea histogramă şi, prin urmare, o bună estimare a privire la ritmul de rânduri completate înainte de joc capete. Această abordare este extrem de valoros pentru evaluarea rapid subtile de modificări din A.I. care o faci este deja extrem de bine.
6.10 Consiliul de evaluare măsurătorile imite look-speculative mai departe
Dacă un algoritm, cum ar fi o am prezentat cu acest proiect, pur şi simplu încearcă toate orientările bucata si traduceri pentru eliminarea, şi ratele de fiecare consiliu de configurare care rezultă potrivit unor măsuri de merit, algoritm este în esenţă imitării "uite-inainte".
Când unul se ocupă de măsurare, cum ar fi "gramada înălţime", "ingropat" gauri "," locuibilă rugozitate "sau" adâncimi de bine ", este un adevăr, folosind o formă simplificată de" fata de urmat în viitor ". Aceste generale characterizations de bord oferă anumite indicii privind viabilitatea pe termen lung din partea consiliului.
Ideală de abordare, dat fiind infinit o suma de putere de calcul, ar fi de a evalua un consiliu de configurare dat toate posibilele bucata de secvenţe care pot urma.
Deşi trebuie să ia în considerare toate piesele 7 ca fiind la fel de probabile la fiecare nivel de look-ahead, aveţi nevoie pentru a optimiza reale de traduceri (de până la 10) şi orientări (de până la 4) pentru fiecare bucată în fiecare secvenţă posibil! Asta-i până la (7*10*4) = 280 ramuri la fiecare nivel al comisiei de evaluare! Deci, asta-i până la bord ((280)^(LookAheadLevels)) configuraţii să ia în considerare.
Pentru că trebuie să ne pună capăt analiza după ce un numar finit de nivele, avem nevoie de a avea unele non-uite-ahead metoda de evaluare a consiliului de stat - un mod de a-şi da valori de frunze de noduri de arbore noastră de căutare. Deci, pentru aceste frunze de noduri, suntem înapoi la utilizând o formulă care include generale predictors de viitor viabilitatea de bord!
Acest tip de speculă, poate fi încercat cu cel piese şi două piese în loc de algoritmi de evaluare simplistă bord de măsurare. Presupune ulterioare, toate piesele sunt la fel de probabile şi suma de un consiliu de abilitati pentru a se potrivi cu piese de toate tipurile, în cele mai bune moduri. Aceasta poate fi efectuată cu una, două, sau orice număr de speculativ muta adâncimi - cu toate piesele fiind la fel de probabile (p=1/7).
În nodurile terminale de acest copac ar putea cere în continuare determinate de măsurare pentru a evalua, dar mai multe straturi speculative surprinde exact esenta a ceea ce vrem să facem: Determinaţi cât de bine o anumită bord poate accepta toate piesele, inclusiv pozitiv factori, cum ar fi finalizarea linii şi negative factori, cum ar fi creşterea globală gramada inaltime, etc
7. Tetris A.I. sistem de demonstraţie
7.1 Sistemul de ansamblu
Acest Următoarea diagramă arată-mi experimental set-up.
Sistem global pentru demonstratii
7.2 Echipament
Iată o scurtă listă a echipamentelor folosite în acest demonstrative:
[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)
În mod evident, puteţi utiliza echipamente similare pentru a realiza aceleaşi rezultate. Mai multe detalii cu privire la echipamentele sunt descrise în secţiunile corespunzătoare ale prezentului articol.
Aici sunt scurte descrieri ale calculatoarelor personale utilizate în această demonstraţie:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Această demonstraţie ar putea fi reprodus cu usurinta cu alte sisteme de operare, cum ar fi Linux. Este mai important să aibă o viteză CPU pe ordinea de 800 sau mai rapid MHz pentru computer pe care se A.I. pentru a rula software-ului, deoarece acest computer se va face în timp real, prelucrarea video.
7.3 Hardware de captură video
Am folosit o camera video comune USB ca un dispozitiv de captură video pentru a mea A.I. sistem. Mai exact, am folosit Creative "WebCam Pro", USB o cameră video cu rezoluţie 640 * 480.
Creative(TM) USB camera video descriere
USB camera video (la unghi)
USB camera video (front)
USB camera video (bord cu CCD)
USB camera video (principale chips-uri)
OV511 mari blocuri (notă: USB camera video este OV511+)
7.4 OV511 foaie de date
ov511ds.pdf
OV511 Data sheets
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "plus") facilitate diferenţele
ov511plus_101.pdf
Diferenţele de caracteristici OV511+
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Inregistrare video software
Microsoft are o foarte veche API numit "Video for Windows" (VFW) pe care l-am utilizat cu succes pentru acest proiect. (Vă link-ul de la "vfw32.lib" în C++ proiectului, sau de a face o DllImport "vfw32.dll" în C# dvs. de cod.) Exemple de utilizare a VFW API sunt disponibile pe scară largă.
O alternativă este să folosiţi Microsoft's "DirectShow" API de a face cu captura video.
Pentru ca VFW a avut doar o duzina de linii de cod pentru a utiliza, şi acceptably efectuat pe 800 MHz masina mea, nu am deranja explorarea APIs alternativă. Dar este o DirectShow mai multe contemporane API pentru Windows de captură video şi, posibil randamentele un cadru mult mai mare rată de acelaşi hardware.
Uita-te la "CPF.StandardTetris.STVideoCapture" codul sursă în fişiere standard Tetris de software pentru a vedea cât de uşor este de a obtine de captură video pentru a-ţi propriul proiect.
7.7 Calculator de interfaţă cu relee (prin RS232)
Pentru a avea un calculator "apăsaţi tastele" de pe tastatură dintr-un alt calculator, am folosit un "Releu de bord" controlate de comenzi de text trimise de la un port serial de comunicaţie (de exemplu: "COM1") prin intermediul unui cablu RS-232. Am folosit fiecare releu pentru a conecta cele două fire de o anumită tastatură cheie pentru a simula o cheie de presa.
Acest necesare deschiderii de tastatură şi de a face conexiuni. Există multe metode pentru simularea mai uşor apăsând tasta la un computer, dar am vrut să fac ceva care parea cât mai aproape posibil de o persoană cu adevărat tastarea pe o tastatură.
Unul versatil şi foarte bine puse la Releu de bord este ADR2200 făcute de Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Puteţi să aruncaţi o privire şi asupra "CPF.StandardTetris.STRS232" fişierele cod sursă pentru a vedea cât de uşor este să trimiteţi octeţi printr-un port serial, care pot fi apoi folosite pentru a controla, cum ar fi dispozitivele de bord ADR2200 arătat mai sus.
8. Standard Tetris de software
8.1 Download software
Du-te la începutul acestui articol, pentru a găsi un link pentru a descărca codul sursă (C# şi C++ versiuni) şi software-ul construit (*.exe).
8.2 Sumar de caracteristici
Produse de plastic caracteristici:
Instrucţiuni de ecrane şi credite
Mod monocrom
Mod de Shadow
Sugestie modul
Nedorită rânduri
Rata de control
Next bucata
Consiliul de dimensiune
S/Z piese
Mod de etalonare
Inregistrare video şi recunoaşterea
Debugging consola
Salvaţi Joc
Joc de încărcare
8.3 Incepand de aparitie
Aspect atunci când software-ul este pornit:
Aspect atunci când software-ul este pornit
8.4 Mod monocrom
În mod implicit de bord apare în culoarea:
În mod implicit de bord apare în culoare.
Mod de culoare poate fi modificat pentru a monocrom (Shift + K):
Mod de culoare poate fi modificat pentru a monocrom.
8.5 Mod de Shadow
Shadow indică modul în cazul în care o piesa va teren. Acest lucru este foarte util pentru placi foarte mari, deoarece este dificil de a judeca în cazul în care o piesa va teren.
Shadow indică modul în cazul în care o piesa va teren.
8.6 Sugestie modul
Sugestie vă arată modul în cazul în care în mod curent selectată AI-ar muta, având în vedere situaţia actuală. (Shift + H)
Sugestie modul în care arată în mod curent selectată AI-ar muta.
8.7 Nedorită rânduri
Inserare "junk" rânduri în partea de jos a gramada, una cate una, manual. (Shift + J)
Inserare "junk" rânduri în partea de jos a gramada.
8.8 Rata de control
De '+' (plus) şi '-' (minus) chei de control viteza de joc.
În mod implicit, jocul rulează la un standard de viteză, în conformitate cu normele standard de Tetris (viteza bazate pe nivel).
Iată un tabel de sensuri de viteză prejudecată:
-3,-4,...: lentoarea proporţională cu prejudecăţile
-2: mai lent decât nivelul 1
-1: normale, dar limitat la nivelul 6 (0,2 sec) viteza;
0: normal; Standard Tetris viteză de control;
+1: uşor mai rapid decât nivelul 9 (0.05 sec întârzieri);
+2: delimitate prin rata de redare (de exemplu: 75 Hz);
+3,+4,...: iterations de mai multe cadre pe prestate;
Îmi place să rula A.I. la o setare de "+2" (apăsaţi de două ori '+' cheie, dacă o prejudecată începe de la zero).
Viteza de prejudecată modifică viteza de joc.
8.9 Arată următoarea bucată
Apăsaţi "N 'pentru a comuta la" Next piesa "de afişare. De A.I. va utiliza "Next piesa" informaţii numai în cazul în care "Next piesa" apare pe ecran.
Puteţi fi sigur că AI nu este folosind "Next piesa" de informaţii atunci când nu pot vedea "Next piesa" de pe ecran.
Arată următoarea bucată
8.10 Consiliul de dimensiune
Presare Ctrl + (stânga, dreapta, jos, până), se poate regla dimensiunea bord în mod arbitrar de la 4 * 4 dimensiuni de până la 200 * 400.
Mărimea camerei: 4 * 8
Board size: 20 * 40
Board size: 40 * 80
Board size: 20 * 5
Mărimea camerei: 4 * 100
8.11 S/Z piese doar
Studiu de interesant S/Z alternative de model.
Acest model nu poate fi rezolvata pentru un 10 * 20 bord (latime * inaltime).
Cu toate acestea, comisii care au latimi care sunt multipli de 4 sunt afişate pentru a permite trivially infinit de supravieţuire.
AIs nelimitat de supravieţuire în aceste cazuri, chiar dacă acestea nu au fost reglate în special pentru a gestiona această situaţie patologică.
S/Z piese doar
8.12 Video modul de etalonare
Apăsaţi "C" pentru a introduce "Modul de calibrare". Când în modul de etalonare, aveţi posibilitatea să apăsaţi tastele numerice: {1,2,3,4,5,6,7} pentru a selecta o bucată {O,I,S,Z,L,J,T} din partea de sus a juca bord.
Aceasta este utilă şi ca o referinţă pentru imagine video cu captura de pe un al doilea standard Tetris software.
Dacă apăsaţi tasta 0 (zero) cheie, se va face de bord gol.
Aveţi posibilitatea de a pretinde spawn piese prin selectarea unei piese (1..7), apoi selectarea unui gol (0), în timp ce un al doilea computer face ceasuri de captură video pentru piese.
Puteţi rula A.I. pe al doilea computer şi a vedea cum se ocupa de dvs. a intrat manual patologice Tetris scenarii!
Modul de etalonare este singura dată când pot manipula video cu captura de imagine de prelucrare şablon (4 * 2 grilă). Aveţi posibilitatea să utilizaţi mouse-ul pentru a trage de dreptunghi, dar apoi puteţi folosi tastele cursor ( "up", "jos", "stânga", "dreapta") pentru a avea amenda de control al frontierelor - folosind Shift cheie pentru a selecta opusă frontierelor de dreptunghi (de exemplu: "Shift-stânga" pieptene este diferită de "stânga").
Video modul de etalonare
8.13 Inregistrare video şi recunoaşterea
Presare 'V "Comută în modul de captură video. Dacă sunt corect calibrate (a se vedea "video calibrare" într-o secţiune anterioară), piesele de la distanţă video ecran va fi capturat de camera video şi clasificate - şi piesele vor fi în spawned locale de joc pentru A.I. să ia în considerare şi reacţionează .
A.I. de ieşire trebuie să fie transmise (prin intermediul interfeţei RS-232 în demonstrative, descrise în acest articol) la distanta de joc de intrare (de exemplu: tastatură) pentru a A.I. de a juca cu succes la distanţă de joc.
Dacă în orice moment această buclă închisă este perturbată (de exemplu: Inregistrare video defectare, semnalul de ieşire sau funcţionarea incorectă), atunci A.I. va dezvolta o falsa impresie de la distanta, stare de joc, şi va face A.I. nepotrivit că deciziile de repede pierde jocul .
(Notă: Această problemă poate fi depăşită cu o modesta suma de efort: A.I. sistem trebuie doar să examineze întreaga distanţă Tetris ecran pentru un curs de "realitate verifica" din tabla, şi A.I. sistem ar trebui să fie pregătită pentru unele comenzi de ieşire pentru a nu într-o anumită măsură.)
Inregistrare video şi recunoaşterea
9. Original Tetris de experiment AI (2003)
Următoarele spectacole de lucru prima versiune a sistemului de Tetris A.I. în 2003.
Camera video confruntă cu computerul # 1 rulaţi nici un simplu joc Tetris
Calculator # 2 rulează software-ul standard Tetris A.I. în mod
Stânga: Desen videoclip grilă se calibreze imaginea de recunoaştere;
Dreapta: Tetris bucata de recunoaştere de cazuri.
Cadru de la video de Tetris A.I. experiment în 2003
10. Cel mai bun-o bucata Tetris-playing algoritm în lume
10.1 Pierre Dellacherie (2003; Franţa)
Pierre Dellacherie (2003; Franţa), dezvoltator de cea mai bună piesă-o joaca Tetris-algoritm în lume
Cea mai bună-o bucată, în timp real Tetris algoritm pentru a-mi cunoaştere a fost creat de către Pierre Dellacherie din Franţa.
Lui uimitoare algoritm uneori umple mai mult de 2 milioane de rânduri!
În medie, performanţa este pe ordinea de 650000 rânduri.
Algoritm are foarte puţină memorie, şi rulează la viteză ridicată (aproximativ 160 de rânduri pe secundă la mine pe 800 MHz calculator).
Performanţă de Pierre Dellacherie's algoritm:
Modelul meu de curent pentru îndeplinirea Tetris AIS este că, pentru o anumită piesă există o probabilitate constantă că jocul se va termina, p.
Astfel, probabilitatea ca o piesa nu va termina un joc este q=(1-p).
Probabilitatea de joc, după ce se termină k mutãri este pur şi simplu produsul dintre probabilitatea de supravietuire (k-1) mută, şi anume q^(k-1), si probabilitatea de a se termină pe lângă mişcare, şi anume p.
Aceasta corespunde unei "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 )
Pentru p mici, ln(q) este de aproximativ (-p), şi avem următorul text:
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 )
Ne aşteptăm de fracţiunea din numărul total de jucat jocuri la capăt cu un număr de rânduri completate în intervalul [k1, k2] să fie:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
După completarea 36 de jocuri pe computer, pe o perioadă de două zile, am gasit un o medie de 674827 completat rânduri.
Conform teoriei generale de mai sus, mi-ar aştepta următoarele relativă fracţiune de jocuri pentru a se termina in urmatoarele completat variază de rând:
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
Aici este un grafic care compară Exponential Distribution teoria cu observate de distribuţie de jocuri.
Performanţă de Pierre's algoritm de peste 36 de jocuri terminate
Deşi există un număr foarte mic de jocuri în acest set de date, este evident că modelul este destul de bun, la care se potrivesc cu observate de distribuţie.
Pierre's introducerea lui la algoritm:
Pierre a inceput lucrul la acest algoritm de o bucata din 2003,1.
Pierre mi-a trimis un e-mail despre sale pe 2003.4.9 algoritm, de raportare a performanţei în urma peste 20 de jocuri consecutive:
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.
"Algoritm este pus în aplicare în Turbo Pascal si completeaza 7000 rânduri / min. Cu un Athlon 1600+."
Am convertit Pierre's algoritm pentru a C++ în 2003,6, după mai multe schimburi de e-mail cu Pierre. Am verificat că A.I. în C++ făcut aceeaşi versiune a deciziilor Pascal versiune.
Am observat similare de performanţă pentru a raportului său în original; medie în jur de 650000 completat rânduri, şi unele jocuri de finalizarea 2 milioane de rânduri.
Incredibil!
10.2 Conversaţie cu Pierre Dellacherie
[1] Când v-au fost creaţi iniţial acest cod?
Am fost pe algoritmul de lucru de la sfârşitul lunii ianuarie 2003 până acum.
[2] Cât de mult ati lucrat la ea?
Am lucrat pe ea aproape în fiecare săptămână ... de zi cu zi, dar nu mult timp, deoarece am alte activitati: din păcate, am să câştigaţi bani ca oricine altcineva!
[3] Ce a inspirat design-i codul?
Tetris am jucat 10 sau 15 de ani în urmă, dar nu am jucat din nou pentru o lungă perioadă de timp. Aş spune că eu sunt un "mediu" jucator care stie regulile şi unele trucuri.
Cu toate acestea, atunci când am început să lucreze, pe algoritm nu am jucat atat de mult deoarece am gasit aceasta a fost destul de eficiente pentru a viziona mai multe computer sa jucam si analiza a punctelor slabe.
[4] Ati utiliza orice automatizare a "instrui" codul dvs. să funcţioneze mai bine? Ai orice feedback de îmbunătăţire a algoritmului?
Sau v-au fost pur şi simplu urmăriţi rezultatele şi să decidă de a face modificări?
Sunt din "vechea scoala:" Am pur şi simplu urmăreşti rezultatele şi a decis de a face modificări.
"Automat de învăţare" este un tip de meta-algoritm, deci sunt sigur ca nu-l faci acest fel, ar obţine mai uşor ca această meta-algoritm ar trebui să fie construit prea şi că nu este aşa de uşor!
Ce e mai mult, fac de acord cu Roger Penrose atunci când spune el (în cartea lui "Shadows of the mind") că înţelegerea omului şi intuiţiei nu poate fi algoritmi (de exemplu: computable).
[5] Când v-au începe joaca Tetris, şi atunci când nu aveţi idee de rezolvare Tetris cu o A.I.?
Tin algoritmică şi de computer, programare (Turbo Pascal şi Scilab) pentru studenţii care trenul pentru examenul de intrare la inginer absolvent al scoli.
La primul, "Calculator joacă Tetris" a fost o idee I vrut la spre a dezvolta mea de anul viitor pentru studenţi.
Eu nu am fost conştient de pagina dumneavoastră de web, atunci când am început să lucreze, pe algoritm.
Într-adevăr am fost norocos să fie conştienţi de pagina dumneavoastră de web doar câteva săptămâni în urmă, deoarece cred că ar fi fost descurajaţi de rezultatele dvs. (aşa cum s-ar putea să ghicesc, mai devreme versiuni de algoritmul meu nu a jucat atât de bine!).
[6] Care este starea actuală?
Sunt aproape 30 [aprilie 2003, înainte de 27]. Am mai multe activităţi: Sunt un cellist, am compus muzica si am preda programare.
Eu am un masterat în muzicologie (1994) şi un "Artificial Intelligence and Algorithmic" diplomă (1998).
În Franţa această diplomă corespunde a 5 ani de studiu, la Universitatea (4th an este de masterat şi 6a an este teza).
Pierre's compozitii:
[7] Când vrei sa vii?
Sunt în franceză şi eu sunt în Rouen (Normandia).
[8] Alte comentarii:
În cele din urmă nu am nici o idee nouă pentru îmbunătăţirea acesteia.
Am încercat atât de mult inutil (si stupide) lucruri pe care le-am îndoieli ar putea fi ea îmbunătăţită.
Pe de altă parte, cred că ar putea exista algoritmi complet diferite, care ar putea avea performanţe mai bune.
Apropo, un test de mai rapidă constă în lansarea de piese într-o jumătate de caseta (10 rânduri X 10 coloane): într-o jumătate de cutie, algoritmul meu face o medie de 280 completat rânduri.
Încã ceva: algoritm poate fi uşor modificat într-un dublu-ply algoritm ([Voi face] testelor în curând).
Imi place muzica de film: a deveni un compozitor de film face parte din visele mele principale (dar este doar vis!).
11. Cel mai bun jucator omului în lume în
11.1 Tetris Japonez Master (2001 ianuarie 27) video
Tetris de masterat (2001; Japonia) video
Arika prezinta Tetris Japonez Finals master (2001 27 ianuarie). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Feedback
12.1 Slashdot thread (2003)
În 2003, mi Tetris A.I. proiect a fost discutat pe forum Slashdot Internet (
http://slashdot.org).
Slashdot (http://slashdot.org) Internet titlu pentru un forum de discutii al meu Tetris A.I. proiect
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 ]
Usurare inspirat de mi Tetris A.I. proiectul (2003) (pentru prima dată când am inspirat un comic!)
Usurare inspirat de mi Tetris A.I. proiectul (2003) (a doua oară, am inspirat un comic!)
13. Istoric al Tetris A.I. proiect
In primavara anului 1989 am fost ocupat sar (şi în lipsa) al doilea semestru boboc clase la University of Pennsylvania.
Unul de meu de cameră, Bill Matthews, au avut Mac Classic, şi, uneori, a jucat jocuri video.
Persoanele admise la care ajunge Ivy League şcoli sunt, de obicei, înclinate pentru a concura cu alte persoane în orice moment - aşa încât, atunci când Bill luat jocul Tetris pentru Mac, am inceput imediat o batalie pe termen lung, pentru a ridicat scorul.
Ca punctajele urcat, timp de investiţii necesară pentru a face un mic câştig a crescut dramatic.
Pentru a face o scurta lunga poveste, se presupune Bill deţine scorul de mare între noi, dar mi-l suspectaţi de a folosi ResEdit hacking şi de Scorul de fişiere!
Bill avut clase în Wharton scoala de afaceri, alma mater de Michael Milken şi Donald Trump, deci nu este de neconceput ca cineva o rigged imposibil de mare scor ...
În vara anului 1990 am împrumutat de la un 30 MHz Intel 80386 IBM PC mea de camera, Alex Haidas.
Am cumparat un Mac tastatură la un flea piaţă pentru $ 1.
Am construit port paralel circuitry pentru a permite PC pentru a controla Mac tastatură.
(Am folosit un CMOS 4040 chip pentru a acţiona ca un tip de Releu solid-state să adere la tastatură contacte in interiorul Mac tastatură.)
Am scris un program de computer care utilizează un arbore de decizie ca strategia pentru jocul Tetris. În doar câteva săptămâni, am avut o PC joaca Tetris de joc care rulează pe un Mac.
Cu toate acestea, am fost obligat să utilizeze tastatura pentru a PC spun A.I. care se încadrează despre fiecare piesă de pe ecran.
Am inceput lucrul la un circuit, folosind CdS (Cadmium Sulfide) detectoare de lumină slabă care ar împotriva Mac ecran si "vedea" în care se încadrează piese, dar CdS senzori reactionat prea lent la schimbările din luminozitate, contrast şi între Tetris piese si fundal pe ecran Mac Classic a fost prea mic pentru a discrimina fiabil.
În acele zile, n-am făcut nu au bani de mult, asa ca a fost prea riscant pentru a cumpara un $ 2 Radio Shack phototransistor că ar putea să nu facă ceea ce am vrut.
De asemenea, având în vedere problema de contrast, am fost pessimistic despre întreaga abordare.
Când am cumpărat primul meu calculator personal, în 1996, nu am putut obţine în cadrul software-ului Windows 95 pe un 100 MHz CPU de a face procesarea video suficient de rapid pentru a face un simplu sistem de viziune muncă.
Am scris imaginea de prelucrare a codului în limbajul de asamblare, dar nu a fost atât de mult inainte sa-mi globale codul primit efectiv video date pe care acesta parea imposibil de a face ceva util.
În 2003, a tehnologiei, în special CPU viteza, au ajuns la un nivel care a făcut de finisare a proiectului de aproape trivial.
I dug up vechiul meu personal şi, în final, proiectul terminat-o, obtinerea unor sentiment de închidere.
A fost foarte incitant pentru a vedea un calculator joacă un alt computer prin intermediul USB camera video şi relee.
Sunetul de relee clic, şi este atent la piesele de spin şi de cădere de la ridicol, superhuman viteze, a făcut experienţa foarte multisensory satisfacerea într-un fel.
În 2003, munca mea a fost recunoscut de către Slashdot (
http://slashdot.org), si am primit o mulţime de mare de feedback.
Am fost invitat să apară pe "Screen Savers" show de televiziune pe TechTV reţeaua de televiziune digitală.
Am fost la San Francisco şi a apărut în spectacol, şi experienţa a fost minunat.
Mai târziu, în 2003, am primit un mesaj de la Henk Rogers, invitându-mă la Hawaii pentru a satisface Alexey Pajitnov el şi să vorbească despre un fel de stabilire a standardului de Tetris, în sensul de a avea Tetris turnee.
Un interes deosebit a fost jucători care să permită de a utiliza telefoanele mobile pentru a "concura cu altele," indirect, prin intermediul A.I. care imită jucatori (de analiză înainte de fiecare jucator al acţiunilor), evitându-se astfel efectele de telefon mobil, acces la Internet latenţă, şi jucători care să permită să "concureze împotriva" * Cele mai bune playere omului în lume în (*..., sau, mai degrabă, A.I. imitării cele mai bune umane jucători din lume).
I was thrilled de perspectiva de a reuniune creatorul Tetris. Din pacate, zborul face anxious mine, si am refuzat invitaţia.
În 2006, am convertit meu "Standard Tetris" software-ul de la C++ la C# software-ul pentru a face mai accesibile şi utile pentru programatori contemporane.
