Tetris
Colin Fahey
1. Software
2. Indledning
Denne artikel beskriver, hvordan en computer kan spille det klassiske spil Tetris ved at få oplysninger om bord, bestemme gode aktioner, og at udføre disse handlinger.
Denne artikel indeholder software i stand til at spille Tetris i realtid.
Softwaren indeholder de bedste real-time Tetris-spiller algoritme i det offentlige rum.
Denne artikel definerer regler for "Standard Tetris," en specifikation, baseret på den oprindelige 1986 præ-kommercielle version af Tetris for Personal Computer (PC).
I 2003, software, der er inkluderet i denne artikel blev brugt til at aktivere en computer til at spille Tetris kører på en separat computer.
En almindelig USB video kamera blev brugt til at gøre det muligt for computeren at "se" skærmen på den anden computer.
Et relæ bord blev kontrolleret via en RS-232 interface til, at computeren til at "trykke på tasterne" på tastaturet på den anden computer.
Således er den første computer har et forhold til den anden computer, der ligner en typisk menneskelig spillerens forhold til en computer, når du spiller Tetris; spillets tilstand kun er kendt ved at se på skærmen, og afspilleren aktioner kan kun iværksættes via et tastatur .
Konfigurationen i denne demonstration fastslået, at en computer kan spille Tetris bedre end et menneske under normale real-time Tetris leger betingelser.
3. History of Tetris
I 1985, Alexey Pajitnov og Dmitry Pavlovsky var computer ingeniører på Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre af Russian Academy of Sciences
Alexey og Dmitry var interesserede i at udvikle og sælge vanedannende computerspil.
De afprøvet flere forskellige spil.
Alexey var inspireret af den antikke græske puslespil, Pentaminos, der er involveret arrangere puslespil brikker lavet af fem kvadrater.
Alexey tænkte på idéen om at arrangere Pentamino stykker, da de faldt i et rektangulært kop, men indså, at de tolv forskellige fem-kantede figurer var for kompliceret til et videospil.
Alexey skiftes til at bruge syv "tetramino" stykker, hver bestående af fire firkanter.
I 1985.6, Alexey Pajitnov programmeret den første version af Tetris på en Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov, og Tetris.
I 1985-1986, Vadim Gerasimov, en 16-årig high-skolen computer vidunder der arbejdede på akademiet, gennemført Tetris for IBM PC kører MS-DOS operativsystemet.
(Vadim Gerasimov senere gjorde forskning på MIT Media Laboratory, fra 1994 gennem 2003, modtager en ph.d. efter at have gennemført mange interessante projekter:
http://vadim.www.media.mit.edu)
Indførelsen skærmbillede i 1987-1988 præ-kommercielle frigivelse af Tetris for PC
Spillet spille skærmbillede i 1987-1988 præ-kommercielle frigivelse af Tetris for PC
Efter 1987, Tetris spredt rundt om i verden.
The Tetris Company, LLC, ejer Tetris varemærke.
4. Projekter inspireret af Tetris
4.1 0-dimensional Tetris
Endnu ikke udviklet.
4.2 1-dimensional Tetris
Ziga Hajdukovic har udviklet 1-dimensional Tetris software, der kan afspilles i en Internet browser.
Ziga Hajdukovic har også udviklet 1-dimensional Tetris software til mobiltelefoner ved hjælp af Java J2ME platform.
4.3 2-dimensional Tetris
Alle konventionelle Tetris-varianter er i denne kategori.
Dette afsnit omfatter interessante varianter.
4.3.1 Største Tetris spil nogensinde: Delft University of Technology (1995)
Tetris spilles på en bygning; 2000 m^2 areal; Delft University of Technology (1995)
Tetris spilles på en bygning; 2000 m^2 areal; Delft University of Technology (1995)
4.3.2 Et andet Tetris spil spilles på en bygning: Brown University (2000)
Tetris spil vises ved hjælp af lys i vinduerne i en bygning på Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
"Jeg synes, det var blot den mest utrolige én dag, jeg kunne forestille mig i mit liv. Ligesom Steve Jobs altid sagt, turen er den belønning."
"Det fik mig til at tænke på projekter, vi har tilbage i kollegium. Ting, der var næsten undoable at andre mennesker ikke ville synes om at gøre."
Steve Wozniak (2000)
4.3.3 Internet browser spil med MIT "Green Building" image
Vadim Gerisimov's Internet browser Tetris
Denne Internet browser Tetris variant blev oprettet ved Vadim Gerasimov.
Denne Internet browser Tetris træk den "Green" bygning på campus i MIT.
Denne Tetris variant kun har ni kolonner i stedet for de normale ti kolonner.
Denne Tetris variant præsenterer nye stykker med tilfældige retningslinjer.
Vadim Gerasimov er den person, der skrev computeren kode for PC version af Tetris i 1986.
Vadim Gerasimov gjorde Ph.D. forskning på MIT Media Laboratory under 1994-2003, arbejder på mange interessante projekter.
4.3.4 PIC16F84 12 MHz mikrokontroller-baserede NTSC / PAL video Tetris spil
PIC16F84 12 MHz mikrokontroller-baserede NTSC / PAL video Tetris spil
Billedet ovenfor viser den NTSC / PAL videoudgang fremstillet af en PIC16F84 12 MHz mikrokontroller kører software skrevet af Rickard Gunee i 1998.
Videoen signalet er genereret af software kontrol af digitale udgange.
4.3.5 "Scopetris" Oscilloscope Tetris ved Lars Pontoppidan (2007.8)
"Scopetris" Oscilloscope Tetris ved Lars Pontoppidan (2007.8)
Lars Pontoppidan skrev kode for AtMega32 mikrokontroller og tilføjede enkle analoge kredsløb, til at skabe et Tetris version, der kan afspilles på et oscilloskop.
Visse registre over AtMega32 mikrokontroller kontrol 8-bit output signaler, og når passeret gennem en "R-2R" elektrisk modstand kredsløb til digital-til-analog (D/A) konvertering, det resulterende analoge signaler kan styre (x,y) koordinater for et oscilloskop bom (når oscilloskop er sat til "X-Y tilstand)."
YouTube video:
FLV video:
4.3.6 Uklar kode Tetris: C / Unix
Følgende blev uddelt "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 Uklar kode Tetris: Perl kode
Det følgende er Tetris for Perl tolk: Perltris (version 20050717) ved 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) er en standard til at beskrive grafiske objekter ved hjælp XML.
Mozilla SVG Tetris: Tetris gennemføres ved hjælp af en Scalable Vector Graphics (SVG) beskrivelse
4.3.9 Google "widget" Tetris
Google, Yahoo!, og Microsoft og andre selskaber, har fremmet miniature Internet-baserede software navngivne "widgets", der normalt er kendetegnet ved en vis brug af dynamiske data tilgængelige på Internettet.
En sådan widget tilgængelige via Google er et Tetris spil.
Følgende eksempel er nuttet, men figurer rotere i irriterende måder:
Google "widget" Tetris
Andre Google widgets:
4.3.10 MIT forskning papir: "Tetris is Hard, Even to Approximate" (2002)
Til følgende forskningsaktiviteter dokument indeholder et bevis for, at en vis form for Tetris variant er "NP-komplet."
Erik D. Demaine, Susan Hohenberger, og David Liben-Nowell, "Tetris is Hard, Even to Approximate", Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
"NP udfyldning" er en klassificering af den tid, omkostninger og rumfart omkostningerne ved en algoritme.
Andre klassifikationer omfatte "P" og "NP".
En klassificering af "NP udfyldning" indebærer, at problemerne er større end nogle mindre størrelse, algoritme er usandsynligt at finde en ønsket løsning i et konkret beløb på tid eller rum.
4.3.11 Forskning dokument: "Applying reinforcement learning to Tetris"
Følgende papir, der blev offentliggjort 2005.5.30 ved Donald Carr på Computer Science afdeling på Rhodes University, Sydafrika, præsenterer anvendelsen af "forstærkning lære" at Tetris.
4.3.12 Tetris Nederdel (2007.11)
Tetris Nederdel (2007.11)
De Tetris nederdel blev oprettet ved "Lucy" ("hissyfitoly" om etsy.com) før 2007.11.
Fra skaberen's beskrivelse af nederdel (der udbydes til salg på 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 kommentarer til denne nederdel:
"Mennesket at nederdel sutter på Tetris"
"Ahahahaha, jeg troede det samme."
"Der er en komplet linje ned i bunden ... afsluttet linjer forsvinder." "DO OVER" "."
"Der bør være en plet i ryggen eller foran hvor lang stykke ville passe perfekt ..."
"Det er en virkelig grim nederdel selv om. Min kæreste kunne ikke købe mig nok chokolade og blomster til at overbevise mig om at bære denne ting."
4.3.13 Tetris fase handle (2007.4)
Tetris fase handle (2007.4)
"Fra dem, der bragte dig Triforce i 2006 ... Leveres den næste generation af livløs genstand skit ... Tetris."
Lokalt cached video i Flash video (FLV) format (brug VLC at spille):
4.3.14 Lattervækkende Tetris varianter af en japansk tv viser
Tetris varianter af japansk tv viser
Denne video segment fra et japansk tv viser omfatter lattervækkende variationer af Tetris, herunder:
brikker at forsvinde ved landingen, et stykke, som fylder en hel række (dermed afslutte rækken efter landing), flere brikker falder på samme tid, uregelmaessigt formede stykker, et langt stykke at der er lidt for bred til at passe i et hul (for at undgå en 4-rækken færdiggørelse!), Mario rammer en svamp og blive enorm og dø! lille stykke vragrester tilbage efter rækker er ødelagt, opadgående alvor gør stykker flyde til toppen osv.
Lokalt cached video i Flash video (FLV) format (brug VLC at spille):
4.3.15 "The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
"The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
Fra beskrivelsen YouTube:
"TETRIS spilles af virkelige menneskelige væsener sidder i et auditorium:"
TETRIS er 4th video udførelsen af GAME OVER Project, instrueret af den schweiziske kunstner Guillaume REYMOND (NOTsoNOISY kreative bureau).
Dette stop-motion video blev skudt og spillede for "LES URBAINES" festival
http://www.urbaines.ch på Palais de Rumine (Lausanne, Schweiz) om November 24th 2007.
Lokalt cached video i Flash video (FLV) format (brug VLC at spille):
4.3.16 2.5-dimensional Tetris
Udtrykket "2.5-dimensional" bruges her forstås som en ikke-retvinklede baggrund af en to-dimensional udgave af Tetris, med en vis tykkelse i den tredje dimension.
(Find linket "tetris3d" i "F7: GAMES".)
4.4 3-dimensional Tetris
Linux / GTK version
Tre-dimensionel Tetris i form af en Java applet til Internet browsere:
Tre-dimensionel Tetris for Windows operativsystem:
4.5 4-dimensional Tetris
Greg Kaiser's "HyperTetris" (1996): en 4-dimensional Tetris
I [1996], [...], Greg Kaiser at sammensætte en fire-dimensional variant af det klassiske spil.
Brug IrisGL (a.k.a. igl) han oprettede en arbejdsgruppe, hvis det svært at spille spil med fire sub-skærmene til at vise forskellige tredimensionelle aspekter af hele vildt-rummet.
[Fordi] er der ikke en let [forståelig] måde at trække fire-D objekter på en to-D skærm, de fire sub-synspunkter er en praktisk metode til at bearbejde og visualisere rotation og oversættelse af stykker gennem de fire dimensioner ( i spillet kaldet x,y,z,w).
Snarere end at udfylde linjer i blokke som i originalen, at målet i dette tilfælde er at udfylde et komplet terning i x,y,z subview (normalt 4 af 4 af 4).
De øvrige subviews der indeholder "w" dimension er arrangeret i et standard 4 af 4 af 10 blokere arrangement med "w" er lang, "vertical" dimension i alle tre tilfælde med forskellige baser i (x,y), (x,z), (y,z).
Gravity retsakter i "-w" retning, så brikker falder "ned" i de tre lange subviews at omfatte "w", og ikke bevæger medmindre ved spilleren kontrol i sidste (x,y,z) subview.
Det tager et stykke tid at vænne sig til, at sige det mildt.
Hvis af nogle mirakel tålmodighed eller ændre parametrene for spillet, en ikke fuldføre en terning, vil forsvinde som de udfyldte linjer gøre i den originale Tetris, selvom ingen score er holdt i HyperTetris.
Benjamin Bernard (2000)
4.6 N-dimensional Tetris
Polytope Tetris (2003): en N-dimensional Tetris spil variant
Polytope Tetris er n-dimensionsstabil Tetris.
Inspireret af HyperTetris program, Polytope Tetris giver dig mulighed tons spille Tetris i enhver ANTALLET AF dimension.
Spil Tetris i 3D, 4D, 5D, eller mere.
HyperTetris er en langt catchier navn end Polytope (def) Tetris, men jeg kan ikke stjæle navnet.
5. "Standard Tetris" specifikation
5.1 Indledning
Definitionen af "Standard Tetris" er en idealized model af de vigtigste egenskaber og opførsel af de første IBM-PC gennemførelsen af Tetris spil (ca. 1986-1988).
De idealized model er baseret på betyde den formodede hensigter for udviklere af den første IBM-PC gennemførelsen af Tetris spil.
For eksempel, forekommer det rimeligt at antage, at udviklerne af den første IBM-PC gennemførelsen af Tetris vildt bestemt til at vælge den form for hver ny henhørende stykke "tilfældigt," og at brugen af Borland C gennemførelsen af rand() funktion blot var en praktisk tilnærmelse af hensigten.
Definitionen af "Standard Tetris" specificerer, at formen af hver ny henhørende stykke er at blive udvalgt "tilfældigt."
Dette ideal problem kan ikke nås ved enhver gennemførelse, men implementeringer kan tilnærmelsesvis den ideelle opførsel.
Selv om der ikke gennemførelsen kan udmærket gennemføre definitionen af "Standard Tetris," idealerne om "Standard Tetris" inddrage objektive kendetegn, og implementeringer kan sammenlignes i henhold til deres relative nærhed til idealerne om "Standard Tetris."
Dette afsnit beskriver en række elementer, adfærd og regler, som kollektivt, definere "Standard Tetris."
5.2 Standard Tetris bord
Tavlen er et gitter af celler, der har 10 kolonner og 20 rækker, for i alt 10 * 20 = 200 celler.
Standard Tetris bord (10 kolonner, 20 rækker)
Hver celle kan enten være ubesatte (tomme) eller besatte (fulde).
5.3 Standard Tetris stykker
Der er syv (7) standard Tetris stykker, med følgende brev navne:
{ O, I, S, Z, L, J, T }
Brevet navne er inspireret af figurer i stykker.
De syv Standard Tetris stykker og deres "retningslinjer"
Den prik på (0,0) sammenfaldende med bord holdning (6,20) når stykke synes ved første øjekast.
Den første kolonne viser de oprindelige "retningslinjer."
I det følgende ordet "orientering" bruges til at beskrive en tilstand af et stykke, inden for en række tilladt stater, der kan skyldes en rotation mod uret begivenhed.
Ændre "orientering" fra et bestemt "orientering" af en "I, S," eller "Z" stykke, kræver en kombination af en rotation og en oversættelse.
Derfor er ordet "orientering" er brugt her for at betyde noget mere end rotation alene.
Men "orientering" kan ændre kun som svar på en rotation mod uret hændelsen, og den onde cirkel af særskilte "retningslinjer" for hvert stykke foretages der, eller kampe, er cyklus som følge af ren rotationer.
Den særlige brug af ordet "orientering" i denne sammenhæng, er næsten lig med den betydning af ordet "rotation" eller "vinkel," men ordet "orientering" bruges i stedet for "tur" til at forsøge at bringe opmærksomhed på, at nogle stykker kræve mere end en rotation til at producere sæt tilladt stater som følge af "rotation" mod uret begivenheder.
Stykker kan kun skifte retningslinjer (eller underkaste en specifik horisontal eller vertikal oversættelse) hvis den deraf følgende status for det stykke ikke ville have nogen besatte (fulde) celler uden for det område af bestyrelsen og ville ikke have nogen besatte celler, der overlapper nogen på nuværende tidspunkt besat celler af bestyrelsen.
(I denne regel, de besatte (fulde) celler af den brik, betragtes ikke som en del af det "i øjeblikket er besat celler af bestyrelsen"
I de følgende bemærkninger, og enhver henvisning til et resultat af en rotation mod uret begivenhed er lavet med den forudsætning at en sådan rotation faktisk kan udføres i betragtning af de eksisterende vilkår for det stykke og bord.
De "O" (rubrik) stykke kun har et enkelt orientering, og ikke ændrer placeringen af nogen af sine besatte (fulde) celler som svar på eventuelle mod uret rotation begivenhed.
De "I" (linje) brik har to mulige retningslinjer, der oprindeligt blev vist i en horisontal orientering.
De "I" stykke suppleanter mellem de to retningslinjer, som svar på hinanden følgende mod uret rotation begivenheder.
De "S" og "Z" stykker har hver to mulige retningslinjer.
Disse stykker hver suppleant mellem to retningslinjer, som svar på hinanden følgende mod uret rotation begivenheder.
De "L", "J", og "T" stykker har hver fire mulige retningslinjer, og disse retningslinjer er resultatet af enkle rotationer omkring midten punkter på figurer.
Når en brik først optræder om bord, brik har sin "store akse" i en horisontal orientering, og den brik står øverst på brættet.
Der er derfor ingen brikker er i første omgang kan have deres retningslinjer ændres. Det stykke skal stige ned ved en række, der har mulighed for at have sin orientering ændret.
Når en brik er faldet med en række på bordet, alle brik retningslinjer kan nås (hvis det stykke er ikke for tæt på sidevæggene eller til den aktuelle bunke stykker).
5.4 Standard Tetris diagram
Det følgende er en tilnærmelsesvis diagram for et standard Tetris spillet.
Omtrentlig diagram for et standard Tetris vildt
Omtrentlig diagram for et standard Tetris vildt
5.5 Standard Tetris stykke skabelse
Følgende diagram viser de (4 celle * 2 celler) regionen om bord, hvor alle brikker vises, når oprettet.
Region, hvor stykker vises, når skabt i Standard Tetris
Når en ny brik først optræder om bord, dets oprindelse er sammenfaldende med prik på dette diagram, og emnet vil være helt indesluttet af det skraverede område på dette diagram.
Når et nyt spil er startet, en fuldstændig frit fald straks går, og den første frit fald iteration et stykke er opfostrede øverst på brættet.
Under normale spil, når en specifik frit fald iteration "lander" et stykke, en fuldstændig frit fald straks går, og på den næste frit fald iteration et stykke er opfostrede øverst på brættet.
Når en brik er udklækkede, hvilken type brik er markeret ved hjælp af følgende algoritme:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Fordi der er en konstant p (= 1/7) chance for at vælge en bestemt slags smykke, og alle stykker af samme type er ikke skelnes, sandsynligheden for at have nøjagtigt k stykker af en bestemt type efter n forsøg følger en binomial distribution:
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 )
Når vi vælger blandt de 7 (syv) stykker tilfældigt, sandsynligheden for at få et bestemt stykke er p=(1/7).
Hvis vi gør dette n=70 gange, for eksempel, sandsynligheden for at få præcis k stykker (med k i intervallet 0 til n) er givet ved binomial distribution, som vist i nedenstående billede.
Binomial distribution til n=70, p=(1/7)
Således kan man forudsige den gennemsnitlige samlede stykker af samme type tildeles et samlet antal tilfældige stykker, og man kan også beregne den forventede varians og standardafvigelse (kvadratroden af variansen):
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
Når vi konverterer en tilfældig værdi til et stykke indeks, vi tolker det som følger:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[Den præ-kommercielle MS-DOS version af Tetris anvendt de tilfældige tal-funktionen tilbydes af Borland Pascal compiler.
Denne funktion benyttes en 32-bit tilstand variabel.
Derfor er den sekvens af tilfældige tal var begrænset til 2^32 forskellige værdier.
Derfor, i princippet, at en spiller kan finde, efter at slippe måske 10 stykker, det nøjagtige sted i sæt 2^32 tal svarer til den aktuelle situation i spillet.
Hvis Tetris simuleringer er udført med det faste sekvens af 2^32 stykker, så optimale beslutninger kan findes for hvert sted i den rækkefølge.
(Der synes at være tilstrækkelige muligheder for at blive bordet til et helt tomt bord stat, der gør det muligt for os at få synkroniseret med precomputed optimale løsning sti.)
Risikoen ved at bruge en simpel tilfældig tal generator i en simulering beregnet til at finde en optimal løsning på et problem er, at den løsning vil være optimal kun for de særlige sti gennem problem rummet er udvalgt af den simple tilfældige tal generator. ]
5.6 Standard Tetris kontrol
Under spillet, således indgange er tilgængelige:
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
Alle input får virkning på den stigende kant af den positive input (på knap pressen, i modsætning til knap udgivelse).
Når en knap Tryk opstår, dette tæller som en anmodning.
Holding en knap nede ud over en vis tid kan resultere i "auto-repeat" funktionen af et tastatur, genererer nye knappen presser - men denne funktion er eksterne i forhold til spillets motor.
Indgangene er angivet ovenfor i overensstemmelse med den oprindelige Tetris spil.
Roter anmodninger kan blive henrettet, hvis der er nogen overlapning mellem den ønskede orientering og sætte væv på den nuværende bestyrelse (med undtagelse af den faldende brik), og hvis den ønskede orientering har ingen sæt celler uden for bord-området.
Oversæt anmodninger kan blive henrettet, hvis der er nogen overlapning mellem den ønskede oversat konfiguration og sæt celler om den nuværende bestyrelse (bortset fra den faldende brik), og hvis den ønskede oversat konfiguration har ingen sæt celler uden for bord-området.
Input anmodninger er behandlet med en latenstid, der afhænger af frame rate af spillet (eksempel: 75 Hz), og anmodninger får virkning (hvis gyldig) øjeblikkeligt.
Et stykke kan være faldet uden line faldende trin indtræder.
Et stykke kan oversættes flere gange til venstre eller højre, derefter faldt, alle uden oplever en officiel linje faldende skridt.
Fordi en nyligt udklækkede stykke ikke kan drejes (fordi den har viklet sig ind mod den øverste kant af bestyrelsen), så må spilleren acceptere mindst ét stykke henhørende skridt, hvis rotationer er ønsket eller påkrævet.
Virkningen på den score, er ubetydeligt.
5.7 Standard Tetris stykke "landing"
Hvis en brik er simpelthen faldende, det falder med en enkelt række i løbet af hvert stykke henhørende iteration.
Der vil være en iteration, der flytter det fra et sted uden nogen kontakt med horisontale overflader til et sted, der har kontakt med horisontale overflader. Når denne gentagelser opstår, brikkerne er i hvile kontakt.
Hvis en iteration begynder med en brik i hvile kontakt med en vandret flade, brik "lander," og bliver en del af den statiske bunke.
5.8 Standard Tetris "linjer afsluttet"
En afsluttet rækken er en række i bunken, hvor alle celler er besat. Når en afsluttet rækken er elimineret fra bunken, og den rækker over elimineret Rækken er flyttet ned ved en række at fjerne den kløft, dette tæller som et udfyldt "linje."
Når en brik lander det bliver en del af bunken.
Umiddelbart efter brik lander, bunken er kontrolleret for afsluttet rækker, og alle afsluttede rækker er fjernet.
Op til fire rækker kan afsluttes samtidigt.
Nedenstående tabel giver den øvre grænse på strækninger afsluttes samtidigt med et enkelt stykke:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Standard Tetris "niveauer"
Standard Tetris har 10 sværhedsgrader, nummereret 1 (en) gennem 10 (ti), med plan 1 er de "mindst vanskelige."
Niveauet indeks er det højst to værdier:
actualLevel = max( initialLevel, earnedLevel );
De initialLevel værdi er det niveau, spilleren vælger, når der begynder et nyt spil.
Mønsteret af niveau som en funktion af afsluttede linjer er let observeret i før-kommercielle MS-DOS version af 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
Således er earnedLevel værdi er beregnet efter følgende algoritme:
if (linesCompleted <= 0)
{
earnedLevel = 1;
}
else if ((linesCompleted >= 1) && (linesCompleted <= 90))
{
earnedLevel = 1 + ((linesCompleted - 1) / 10);
}
else if (linesCompleted >= 91)
{
earnedLevel = 10;
}
5.10 Standard Tetris faldende iteration forsinkelse
Standard Tetris har en real-time forsinkelse mellem successive linje frit fald gentagelser, som er en funktion af de aktuelle vanskeligheder plan.
Følgende forhold mellem plan-indekset og falder iteration forsinkelse er baseret på gentagne stopuret målinger på alle niveauer af den præ-kommercielle MS-DOS version af 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
Således har vi fastslå følgende formel for iteration forsinkelse værdi som en funktion af den konkrete plan indeks:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Hvis nævnet er tom, og der er ingen bruger input, en opfostrede brik i den faktiske niveau 1 lander på ca 10 sekunder, og en opfostrede brik i den faktiske niveau 10 lander på ca 1 sekund.
5.11 Standard Tetris "score"
Standard Tetris kun tildeles point for den retsakt landings et stykke.
Der er ingen point for den retsakt af at fuldføre en enkelt linje, eller at færdiggøre to, tre eller fire linjer samtidigt.
[Bemærk: Nogle varianter af Tetris tildele point for den handling at afslutte linjer, med en eksponentielt voksende bonus for et stigende antal samtidigt afsluttet linjer.
Således strategien for maksimering score i sådanne varianter af Tetris indebærer oprettelse af muligheder for at "få en Tetris," slang for at bruge "I" forme at få fire samtidige linjer og få masser af point. ]
Hvis du har et tomt bord, og du lader en ikke-"I" stykke gøre en frit fald og jord, eller du straks drop en ikke-"I" stykke, kan du oprette følgende punkt diagram ved hjælp af den præ-kommercielle MS-DOS version af 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, ikke-"I" brikker falder på i alt 18 rækker.
Dette er baggrunden for de point forskel mellem de frit fald og instant-slip tilfælde.
Ved at eksperimentere med mellemliggende tilfælde er det let at udlede følgende punkt formel:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Bemærk at denne formel har intet at gøre med den afstand et stykke falder!
Det er strengt en funktion af den konkrete plan, og en straf for det antal gentagelser et stykke er tilladt at falde frit.
Dette straffer en bruger har behov for tid til at tænke.
Bemærk også, at fordi en brik kan ikke i første omgang blive roteret, når den første gydninger, at en spiller straffes med mindst et frit fald iteration hvis rotationer er forpligtet til at placere en brik i bunken.
Dette er sandsynligvis aldrig påvirker menneskers spillere, medmindre de på en eller anden måde: anerkende den brik, tryk oversættelse nøgler "(venstre" eller "højre)," tryk på "dreje" nøglen en eller flere gange, og tryk på "drop" nøgle, alt sammen inden for mindre end 0.5 sekunder på niveau 1, eller mindre end 0.05 sekunder på niveau 10.
6. Standard Tetris strategi
6.1 Indledning
En strategi for at spille et spil, afhænger af spillets regler.
En strategi, afhænger af hvilken parameter der skal optimeres.
I standardversionen Tetris, en overlever ved at udfylde skemaet, får point for landing stykker, og point for de fleste punkter er muligt for hver brik ved at udføre en dråbe, før en eller flere frit fald gentagelser svede.
En A.I. kan optimere point for hver brik blot ved at beslutte, om et hurtigt og "trykke på tasterne" til at fuldbyrde farten.
Mere vigtigt at en A.I. er overlevelse, fordi ubestemt overlevelse betyder en vilkårligt høj score kan nås. Fordi Tetris brikker falder på en bestemt kurs, A.I. skal træffe beslutninger i det mindste dette hurtige - og de A.I. skal gøre bevæger sig at fuldføre rækker til en sats, gennemsnit mindst 1 række pr 2,5 stykker. (Hver brik har 4 celler, og hver række har 10 celler.)
Selvfølgelig kan man udsætte færdiggørelsen rækker ved at akkumulere stykker og opbygge en stor bunke, men der er kun 200 celler på hele bord, som i princippet kun kan holde 50 stykker, så enhver aktør (såsom en A.I.) skal have udfyldelse linjer som en grundlæggende prioritet.
I standardversionen Tetris, spillet stat består af den nuværende bestyrelse besættelse og den nuværende faldende brik (type, placering og orientering). Spillet stat kan eventuelt omfatte "Næste Piece".
6.2 En skiftevis sekvens af "S" og "Z" stykker
Heidi Burgiel, ph.d., af Department of Mathematics, Statistics and Computer Science på University of Illinois at Chicago, har vist, at en skiftevis sekvens af "S" og "Z" stykker vil tvinge en standard (10-kolonnen, 20-rækken) Tetris spillet til ende inden for en forudsigelig række af bevægelser.
Citat fra artiklen: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Tilknyttet trykt artiklen: Mathematical Gazette, juli 1997, "How to Lose at Tetris"
Heidi Burgiel tilbyder en Java applet, der kører i en Internet browser, er udstyret med en ændret Tetris-klon, at gydninger skiftevis "S" og "Z" stykker.
[ "Standard Tetris" software associeret med det dokument du læser også har en tilstand som gydninger skiftevis "S" og "Z" stykker. ]
Heidi Burgiel hævdede, at et spil der involverer skiftevis "S" og "Z" stykker (for en standard Tetris bord på 10 kolonner og 20 rækker) skal slutte før færre end 70000 brikker er faldet.
Standarden Tetris software inkluderet med dette dokument gør det muligt for en person at spille spil med skiftevis "S" og "Z" stykker, og ændre bord bredde.
Det er let at se, at bestyrelser, hvis bredder er heltal multipla af fire kolonner (eksempler: 4 kolonner, 8 kolonner, 12 kolonner osv.) kan spilles for evigt, når stykker suppleant mellem "S" og "Z", med luv stigende ingen højere end 4 rækker. Jeg nævner dette for at gøre det klart, at den begrænsede overlevelsesevne beskrevet i forskning dokument nævnt ovenfor er specifikt for det drejer sig om en standard Tetris bord (med 10 kolonner og 20 rækker).
6.3 Uløselige stykke sekvenser i almindelighed
Der er hele kategorier af patologiske sekvenser, der ikke kan overlevede.
Det ville være interessant at beregne den samlede sandsynlighed for at støde på et spil-afslutning sekvens, fordi det ville sætte en øvre grænse for udførelsen af enhver strategi, selv med fuld viden om alle fremtidige brikker på ethvert givent tidspunkt i et spil.
6.4 I alt muligt bord konfigurationer
I betragtning af, at bestyrelsen har 10 * 20 = 200 celler, og da hver celle kan kun være i én af to stater (tomme eller besat), det samlede antal bord konfigurationer skal være mindre end eller lig med: (2 ^ 200).
I betragtning af, at hvert stykke tilføjer 4 celler til et bord, og hver række afslutningen eliminerer 10 celler fra bestyrelsen, er antallet af besatte celler om bord vil altid være endnu. F.eks (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 osv. Således er det kun halvdelen af (2 ^ 200) bord konfigurationer kan nås ved at spille spillet.
Således er det samlede antal bord konfigurationer er ca: (2 ^ 199) = 8.03469... * 10^59.
Men vi bør udelukke fra vores samlede nogen konfiguration, som omfatter fyldte rækker, fordi fyldt rækker er fjernet inden udgangen af hvert afsluttet flytte. Enhver konfiguration med en eller flere fyldte rækker vil kollapse til en anden konfiguration, som ikke indeholder nogen fyldt rækkerne.
Ligeledes bør vi udelukke enhver konfiguration, der omfatter en ikke-tom række over en eller flere tomme rækker, fordi en ikke-tom række over en tom række, altid vil falde, og alle falder stopper inden udgangen af hvert træk.
Hver række kan være i 2^10 = 1024 stater, hvoraf den ene er "tom", hvoraf den ene er "fuld", og (1024 - 2) = 1022 som er delvist besat. Vi udelukker "fuld"-sagen fra sine overvejelser.
Hvis den nederste række er tom, vil alle rækker over den nederste række skal også være tom.
Hvis den nederste række er delvist besat, så anden række kan være tom eller delvist besat.
Videreførelse af denne analyse kan vi beregne en række bord konfigurationer, der tager ind på kontoen udelukkelse af fuld rækker og de begrænsninger i den tomme rækker: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), der er ca ((1022 ^ 19) * (1023)).
Således har vi finde et mere præcist skøn over det samlede antal af stabile bord konfigurationer: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199); dvs. omtrent 3,74% mindre end den (2 ^ 199) skøn.
Men det faktiske antal af stabile, tilgængelige bord stater må forventes at blive betydeligt lavere skyldes, at den øverste mest rækker kun kan fyldes på et par måder. Som øverste mest rækker udfylde et nyligt genereret brik ikke kan flyttes eller drejes meget. Dette begrænser antallet af måder øverste mest rækker kan besættes.
6.5 I princippet kan de bedste flytte kan findes for ethvert bord og brik konfiguration
Fordi vi kan få en af syv mulige stykker for enhver given bord stat, det samlede antal spil stater er ca 7 * (2 ^ 199) = 5.624... * 10^60.
Fordi vi kan i princippet gøre en dyb søgning af alle mulige fremtider for alle mulige skridt for et givet spil tilstand, vi kan få en enkelt "bedste" flytte forbundet med hvert spil.
Vi antager, at vi ikke har adgang til andre oplysninger end den nuværende bestyrelse og aktuelle stykke, så "bedste" betyder "i bevægelse, der tilbyder den største chance for at opfylde vores langsigtede mål om overlevelse".
En overgang er blot en oversættelse (op til 10 optioner) og en rotation (op til 4 optioner), kan vi let indkode den bedste bevæge sig i en enkelt byte.
Så i princippet, kunne vi danne en tabel med 10^61 poster (byte), der fortalte os det bedste flytte givet nogen bord tilstand og aktuelle stykke.
Det er naturligvis upraktisk, ligesom opremse alle "Go" boards eller "Chess" boards er upraktisk. Men pointen er, at der er en ægte løsning, og der er en god bevægelse for en given konfiguration. Der kan være lige så god bevæger sig for en given konfiguration, men vi kan vilkårligt vælge en enkelt bevæge sig i denne sag.
Mange spil-spiller algoritmer har tabeller, der udtømmende opregner alle spillets tilstand muligheder inden for begrænsede sammenhænge, såsom "åbning (oprindelige) bevæger sig" eller "end-game (endelig) bevæger sig" i skak. Måske udtømmende opregning af Tetris bunke overflader (ca. (20 ^ 10) stater) er mulig. Det er en interessant idé.
Udtømmende opregning af alle stater i det nederste to rækker, multipliceret med de syv mulige stykker, og lagring af de bedste bevæge sig i en enkelt byte, ville være helt let; kræver kun 7 MB hukommelse. Måske optimere ydeevnen for disse syv millioner tilfælde ville give rå data for både analyse og udvikling af simple modeller for data; sådanne modeller kunne betragtes som en del af den overordnede ideal Tetris-spiller strategi.
Bemærk, at fuldbyrdelsesstaten bedste bevæger sig stadig ikke beskytte os mod mulige patologiske vildt-afslutning stykke sekvenser. Det er bare at vi altid vil udføre bevægelser, der tilbyder os det maksimale potentiale for fremtidig overlevelse i betragtning af, at alle fremtidige stykker er fuldstændig tilfældigt (og ukendte på det tidspunkt, vi skal beslutte, hvordan du kan flytte en enkelt nuværende kendte stykke).
6.6 Real-time ydeevne
En begrænsning står nogle strategi algoritmer er behovet for realtids performance - hvilket betyder, at den algoritme skal træffe en afgørelse inden for en bestemt tid.
Når en menneskelig spiller Tetris, brikkerne ikke stopper henhørende at give spilleren en chance for at tænke. Det er en del af udfordringen i Tetris. Således er en A.I. system, der er beregnet til at simulere en rolle som menneskelige Spilleren skal også træffe beslutninger med en hastighed dikteres af Tetris spil.
6.7 Row og brik totalerne
Bemærk, at på lang sigt, er antallet af faldet stykker er meget tæt på 2.5 gange antallet af afsluttede rækker - fordi hver række har 10 celler, og hver brik er 4 celler, og vi skal udfylde en række, i gennemsnit en gang hver (10/4) = 2.5 stykker droppes.
Så vi kan bruge "afsluttet rækker" og "faldt stykker" næsten ombyttelig med passende proportionalitet konstant. Den største fejl er, når bestyrelsen er helt fyldt med undtagelse af et enkelt hul i hver række (((10*20)-20)/4) = 45 brikker faldt, men en mangel på den forventede (45/2.5) = 18 afsluttet rækker.
6.8 Current-stykke (og bestyrelsen) strategi
Hvis vi kun tillade A.I. har viden om den nuværende bestyrelse og den nuværende stykke, og vi kun betragte resultatet af at flytte den nuværende brik i særdeleshed måder, så det kan være opkaldt en "one-stykke" analyse.
Her er et groft omrids af, hvordan et stykke analyse kan afgøre om et skridt i Tetris:
Nuværende stykker analyse af et Tetris spil tilstand
Dybest vi forsøger alle mulige figurer og vælge de færdes, der giver det bedste resultat.
Den vanskelige del er rating hvert resultat.
Vi skal sats et hypotetisk spil stat i henhold til hvor godt sådan en stat støtter vores kortsigtede og langsigtede mål.
Vores langsigtede mål er overlevelse. Overlevelse afhænger af at forebygge bunken fra overfyldte linjen. Vi kan reducere den bunke højde ved at danne komplette rækker som derefter fjernes fra bunken.
For at danne en komplet række, skal vi passe dele af stykker på hver kolonne i samme række. Derfor kræver vi, at alle dele af en række at blive udsat for de faldende brikker, hvis vi i sidste ende at udfylde hele rækken.
Hvis der af en eller anden grund vi dække op tomme dele af en række af brikker på nogen højere række, så vi nu er ude af stand til at udfylde de tomme dele af rækken. Den eneste måde (forudsat ingen glidende) at få adgang til disse "begravet huller" er at fjerne de rækker over at have dele fungerer som hindringer.
Følgende faktorer er blandt dem, vi kan bruge til at vurdere en given bord tilstand:
Overall pile height
Jo højere bunken, jo dårligere vores situation synes at være, fordi vi er tættere på overfyldte linjen.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
De rougher bunken, jo mere sandsynligt er det, at det vil være vanskeligt at udfylde alle de indlagte komplekse konturer som de bliver udsat for overfladen.
Number of buried empty cells
Jo flere huller, vi har begravet, jo dårligere vores situation er, fordi vi skal afdække begravet huller, før vi kan udfylde de tilsvarende rækker.
Du kan forestille sig andre faktorer, der generelt sats et hypotetisk bord på hvor godt sin bunke kan tage højde for alle de mulige fremtidige stykker, og hvor god situationen ser ud for alle de mulige enheder.
Det næste spørgsmål er, hvordan man kan bestemme den relative betydning af disse faktorer.
En generel fremgangsmåde er følgende. Tildel et sæt "synk" (relative betydning) til disse faktorer, og så simulere en lang række spil og optage resultatet af disse spil (slutbedømmelse, etc). Derefter skal tildele et nyt sæt vægte og simulere en række nye spil. Baseret om, hvorvidt det nye sæt af spil haft bedre resultater end de foregående sæt spil, vi ved, hvis det nye sæt af vægte var bedre end det foregående sæt lodder.
I mit eget forsøg Jeg forsøgte systematisk søgning og tilfældig søgning for god vægt kombinationer, men jeg har ikke bemærker nogen store tendenser, jeg kunne fortsætte. Men jeg har set mange overraskende glat bumps. Jeg troede, det var interessant, at den gennemsnitlige effektivitet kunne danne en jævn kurve, når en parameter blev langsomt varieret med de andre parametre holdes på en vis værdi kombination.
Den bedste real-time, en brik Tetris algoritme i verden, skabt af Pierre Dellacherie (Frankrig) i 2003, skylder meget af sin succes til sine sæt målinger (eller målinger). Finde vægtene er nødvendigt, når optimering af en strategi, men det er også afgørende at begynde med den slags målinger, der afslører de relevante karakteristika for staten.
Pierre Dellacherie's opfindelsen af nye metoder til at karakterisere hvert bord gør hans algoritme virkelig fremragende; bestyrelsen karakterisering indfange de vigtige strategiske dimensioner af bestyrelsen stat.
Man kunne udvikle en meget anderledes sæt karakterisering dimensioner, der fungerede lige så godt, jeg er overbevist om, at det er muligt at spænde de relevante bord stat rummet på mange forskellige måder, der kan bruges til at angive en strategi funktion. Nøglen er at finde karakteristika, som projektet staten rummet ned til et lille antal dimensioner, der kan bruges til at udvikle en enkel rating funktion (eksempel: den lineære vejede kombinationer af egenskaber, som anvendes af Pierre's algoritme).
Den ene-Piece algoritme bruges af "bot" i "xtris" software (1996) skrevet af Roger Espel Llima bruger vægte bestemmes ved en storstilet efterforskning af mulige vægt kombinationer af "genetiske algoritmer". Simulerede udgloedning er en anden mulig metode til udforskning af det flerdimensionale rum med vægt kombinationer.
Det lader til, at baseret på forskellige bemærkninger, multidimensional funktion af den gennemsnitlige Tetris ydeevne som funktion af vægtene, eksempel: F(w1,w2,w3,...), er "groft" (masser af lokale minima og maksima), hvilket betyder, at en enkel multidimensional "Hill klatring" kan ikke fungere.
6.9 Strategi, når de nuværende brik til næste stykke, og pap er kendt
Hvis en strategi algoritme er givet den nuværende brik til næste stykke, og pap, så det kan træffe beslutninger, at udnytte en kombination af brikker.
Kendskab til det næste stykke kan forbedre gennemførelsen af en Tetris spiller algoritme af flere ordrer størrelsesorden. Det er nemt at forstå, hvordan vide det næste stykke gør en stor forskel i strategien.
Man kan gøre "vanvittigt" moves, såsom dækkende enorme huller, etc, fordi de allerede kender, at det næste stykke kan bruges til "fix" situationen. Hvis du ikke har kendskab til det næste stykke, bliver du konstant forsøger at spille odds, forsøger at holde dine muligheder åbne i sagen de næste stykke er ikke ideel.
Nedenstående tegning viser, hvordan alle de forskellige mulige tiltag af den aktuelle brik er overvejet, og for hver sådan færdes vi tage alle mulige skridt involverer det næste stykke.
Strategi, der omfatter aktuelle stykke og næste brik
Standarden Tetris software bruger denne strategi, når "Næste Piece" er aktiveret af brugeren og er synlige på skærmen, og når en to-brik A.I. er aktiveret (såsom den ene skrevet af mig, Colin Fahey). Hvis "Næste Piece" er ikke synlige på skærmen, mine to stykker falder tilbage til et stykke A.I..
Min ét stykke A.I. er forfærdeligt i forhold til andre AIs i Standard Tetris software, så det viser dig gavnlig mere information (eksempel: det næste stykke) kan være at en A.I. system, det er nok til at forbedre effektiviteten af min egen middelmådig to stykker A.I. af flere ordrer størrelsesorden - let overgår udførelsen af de bedste one-brik A.I. i verden.
(Men konvertere de bedste one-brik A.I. i verden til at overveje to stykker uden problemer vil kunne forbedre den ved flere ordrer størrelsesorden også! Knowing det næste stykke er enormt!)
Min første test spil med mine to stykker A.I. varede cirka 182 timer (7,6 dage) på en 800 MHz PC, udfyldelse 7216290 rækker. Jeg har ikke testet den algoritme på en hurtigere computer.
Når du gemmer tilstand af et Tetris spil (Shift-W) til en tekstfil, kan du derefter kopiere og indsætte en liste over de numre, fra afsnittet "heightHistogram", til et Excel-regneark.
Hver bin i histogrammet viser antallet af gennemførte tiltag, der sluttede med en særlig bunke højde (efter fuldstændig rækker er fjernet). Som du kan forestille dig, hvilket gør en bevægelse, der fuldstændigt fjerner en bunke er sjælden, så det samlede antal tiltag, der ender med en bunke højde på nul er forholdsvis lav.
I mellemtiden, kan du forvente, at bunken højden generelt svinger omkring nogle gennemsnit, så bins svarer til disse rækker vil dominere histogrammet. Endelig bins for top-mest rækker (hvor vi er i fare for overfyldte bestyrelsen) har meget lave sammentællinger.
I løbet af mange timer, med A.I. spiller et enkelt spil ved hjælp af den strategi, der omfatter kendskab til "Next Piece", jeg tog stikprøver af spillet stat, kopiering bunken højden histogrammer til et regneark som vist nedenfor:
Pile højden histogrammer registreres på forskellige punkter i en typisk vildt (med den nuværende-og næste stykke strategi)
Du kan skala hvert histogram med det samlede antal stykker (det samlede antal afsluttede flytter) for at få følgende oplysninger:
Skaleret histogrammer, og en teori
Det bemærkelsesværdige er, at disse skaleret histogrammer ser ens på trods af de forskellige kendelser af størrelsen af det antal stykker (fuldført bevæger sig) er involveret.
Blot ved at se på de tal, jeg fremsatte hypotese, at halen af kurven er en eksponentiel henfald. Ved trial and error "Jeg kom op med de uslebne teorien om, at hale blev beskrevet ved:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Nedenstående graf viser de skaleres histogram over hele spektret af rækkerne.
Diagram af skaleret histogrammer
Bemærk, at kurven for 50000 stykker, og kurven for 2000000 stykker, og kurven af halen teori er næsten ikke skelnes på denne skala.
Følgende er et nærmere blik på hovedet af kurven.
Nederste del af højden histogram
Følgende er en stor-forstørret billede af den ekstreme hale udgangen af den målte og teoretiske histogram kurver.
Forstørret visning af ekstreme hale udgangen af skaleret histogrammer
Som man kunne forvente, er det meget sjældent, at bunken for at nå disse højder i endnu lang eksperimenter - men selv med vores begrænsede beviser i denne ekstreme regionen, teorien stadig synes acceptabel.
I den fulde chart teorien synes at overlappe hale af fordelingen "præcis", mens den i den forstørrede chart af halen af den hale, ser vi åbenbare fejl. Men jeg hævde, at det er på grund af utilstrækkelige data på disse ekstreme bunke højder. Hvis jeg steg spillet bord, siger en højde på 25 rækker i stedet for 20 rækker, så spil ikke opsige brat, tror jeg, at den teori jeg fremlagde ovenfor, vil falde sammen perfekt med den tendens.
Min fornemmelse er, at dette histogram er en direkte kombineret resultat af Tetris A.I. og reglerne for Tetris. Så denne samme fordeling vil blive observeret for enhver tilfældig langsigtede spil Tetris bruger min særlig A.I. strategi for at lege med "Næste Piece" viden.
Jeg mener i øvrigt, denne type histogram kan bruges til at sammenligne AIs at ansætte de samme oplysninger, når de spiller. Således behøver du ikke at spille komplet spil (som kan vare i dage eller år) at sammenligne de langsigtede resultater af forskellige strategi algoritmer.
For eksempel, på trods af enkelheden i min model, tror jeg, at det kan bruges til at forudsige den gennemsnitlige varighed vildt! Vi har simpelthen regne ud hvor mange stykker gør det "rækken 21" bunke højden et betydeligt antal, såsom en optælling af én.
Den relative hyppighed for rækken 21, ifølge mine simpel teori, er:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Du skal formere dette nummer af (5.3 * 10^(7)), omtrent 50 millioner, for at få en værdi af én.
Således er jeg nogenlunde forudsige, at min nuværende "Næste Piece" strategi er kun godt for efter ordre fra cirka 10 mio afsluttet rækker. En af grundene jeg gøre denne konservativt skøn er den kendsgerning, at selv 18 rækker kan være dødelig for mit A.I. fordi jeg ikke tillade mig A.I. at overveje stykker, indtil de har faldet med mindst én række! (Dette er så jeg ikke behøver at bekymre dig om ikke at kunne rotere stykker.)
Jeg er imponeret over den kendsgerning, at spiller kun 50000 stykker (og muligvis langt færre enheder) kan give dig et ekstremt godt skøn over den langsigtede højden histogram, og dermed et godt skøn over i størrelsesordenen af afsluttede rækker før spillet ender. Denne fremgangsmåde er særdeles værdifuld for hurtigt at vurdere, subtile ændringer i en A.I., der allerede gør meget godt.
6.10 Board evaluering målinger efterligne spekulative look-forude
Hvis en algoritme, som det, jeg præsenteret for dette projekt, blot forsøger alle brik retningslinjer og oversættelser til at opgive, og rater hver følge board configuration ifølge nogle foranstaltning af fortjeneste, algoritme er primært at efterligne "look-forude".
Når man beskæftiger parametre såsom "bunke højden", "begravet huller", "overfladeruhed" eller "godt dybder", en der virkelig er ved hjælp af en forenklet form af "se fremad". Disse generelle karakterisering af bestyrelsen give nogle fingerpeg om den langsigtede levedygtighed af bestyrelsen.
Den ideelle tilgang, da en uendelig mængde af computerkraft, ville være at vurdere et board configuration givet alle mulige stykke sekvenser, der kan følge efter.
Selvom du skal overveje alle 7 stykker som værende lige så sandsynligt på hvert niveau af look-forude, er du nødt til at optimere de faktiske oversættelser (op til 10) og retningslinjer (op til 4) for hver brik i alle mulige sekvens! Det er op til (7*10*4) = 280 afdelinger på alle niveauer af bestyrelsen evaluering! Så det er op til ((280)^(LookAheadLevels)) bord konfigurationer til at overveje.
Fordi vi skal bringe den analyse efter en række niveauer, vi skal have nogle ikke-look-forude metode til at evaluere bord stat - en måde at give værdier til bladet knudepunkter i vores søgning træet. Så for disse blade noder, er vi tilbage til ved hjælp af en formel, der udtrykker generelle indikatorer for fremtidige rentabilitet af bestyrelsen!
Denne form for spekulation kan forsøgt med et stykke og i to stykker algoritmer i stedet for den forenklede bord evaluering målinger. Påtage sig alle efterfølgende stykker er lige sandsynlige og opsummere evner af en bestyrelse for at tilgodese stykker af alle slags i den bedst mulige måder. Dette kan udføres med en, to eller et hvilket som helst antal spekulative flytte dybder - med alle brikker er lige sandsynlige (p=1/7).
Den terminale noder af dette træ kan muligvis stadig kræve den vejede målinger for at vurdere, men den spekulative lag mere præcist indfange essensen af, hvad vi ønsker at gøre: Undersøg, hvor godt en given bord kan acceptere alle mulige stykker, herunder positive faktorer, såsom at udfylde linjer og negative faktorer såsom at øge de samlede bunke højde osv.
7. Tetris A.I. system demonstration
7.1 System overblik
Det følgende diagram viser min eksperimentelle set-up.
Samlet system til demonstration
7.2 Udstyr
Her er en kort liste over det udstyr, der benyttes i denne demonstration:
[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)
Det står klart, du kan bruge lignende udstyr til at udføre de samme resultater. Flere oplysninger om det udstyr, der beskrives i de tilsvarende afsnit i denne artikel.
Her er korte beskrivelser af personlige computere anvendes i denne demonstration:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Denne demonstration kan let blive gengivet med andre operativsystemer, såsom Linux. Det er mere vigtigt at have en CPU hastighed på rækkefølgen af 800 MHz eller hurtigere for den computer, er at køre A.I. software, fordi denne computer vil gøre real-time behandling af video.
7.3 Videooptagelse hardware
Jeg brugte en fælles USB videokamera som en video capture enhed for mit A.I. system. Helt konkret har jeg brugt Creative "WebCam Pro", en USB videokamera med 640 * 480 beslutning.
Creative(TM) USB videokamera beskrivelse
USB videokamera (i vinkel)
USB videokamera (forside)
USB videokamera (pap med CCD)
USB videokamera (vigtigste chips)
OV511 vigtigste blokke (note: USB videokamera er OV511+)
7.4 OV511 datablad
ov511ds.pdf
OV511 Data Sheets
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "plus") funktionen forskelle
ov511plus_101.pdf
OV511+ Feature Forskelle
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Videooptagelse software
Microsoft har en meget gammel API navnet "Video for Windows" (VFW) at jeg med held anvendes til dette projekt. (Du linket til "vfw32.lib" i din C++ projektet, eller gøre en DllImport af "vfw32.dll" i din C# kode.) Eksempler på anvendelse af de VFW API er bredt tilgængelig.
Et alternativ er at bruge Microsoft's "DirectShow" API at gøre video-capture.
Fordi VFW tog kun en halv snes linjer kode til brug, og der udføres et acceptabelt på min 800 MHz maskine, jeg ikke gider at undersøge alternative APIs. Men DirectShow er en mere nutidige API for Windows video capture og potentielt giver en langt højere billedhastighed for den samme hardware.
Kig på "CPF.StandardTetris.STVideoCapture" kildekode filer i Standard Tetris software til at se, hvor nemt det er at få video-capture ind på dine egne projekter.
7.7 Computer grænseflade til relæ (via RS232)
At have en computer "tryk på tasterne" på tastaturet fra en anden computer, jeg brugte en "relay bord" kontrolleret af tekst-kommandoer sendt fra en seriel kommunikationsport (eksempel: "COM1") via en RS-232 kabel. Jeg brugte hver relay til at forbinde de to ledninger af et særligt tastatur nøglen til at simulere en central pressen.
Dette krævede en åbning af tastatur og foretager tilslutninger. Der er mange lettere metoder til at simulere centrale trykke på en computer, men jeg ønskede at gøre noget, der syntes så tæt som muligt på en person virkelig at skrive på et tastatur.
Et meget alsidigt og godt-gjort relay bord er ADR2200 foretaget af Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Du kan se på "CPF.StandardTetris.STRS232" kildekode filer for at se, hvor nemt det er at sende bytes via en seriel port, som derefter kan bruges til at styre anordninger såsom ADR2200 bord vist ovenfor.
8. Standard Tetris software
8.1 Hent software
Gå til begyndelsen af denne artikel for at finde et link til at downloade kildekoden (C# og C++ versioner) og indbyggede software (*.exe).
8.2 Oversigt over funktioner
Software funktioner:
Instruktion skærme og kreditter
Monokrom mode
Shadow mode
Tip mode
Uønsket rækker
Bedøm kontrol
Næste stykke
Bestyrelsens størrelse
S/Z stykker
Kalibrering mode
Videooptagelse og anerkendelse
Fejlretning konsol
Gem spil
Load vildt
8.3 Starting udseende
Udseende Når softwaren er startet:
Udseende Når softwaren er startet
8.4 Monokrom mode
Som standard linjen vises i farve:
Som standard linjen vises i farver.
Den farve tilstand kan ændres til monokrom (Shift + K):
Den farve tilstand kan ændres til sort / hvid.
8.5 Shadow mode
Skygge-tilstand angiver, hvor en brik lander. Dette er meget nyttige for meget store boards, fordi det er vanskeligt at bedømme, hvor en brik lander.
Skygge-tilstand angiver, hvor en brik lander.
8.6 Tip mode
Tip tilstand viser dig, hvor de aktuelt udvalgte AI ville bevæge sig i lyset af den nuværende situation. (Shift + H)
Tip tilstand viser, hvor de i øjeblikket udvalgte AI ville flytte.
8.7 Uønsket rækker
Insert "junk" rækker i bunden af stakken, én efter én, manuelt. (Shift + J)
Insert "junk" rækker i bunden af bunken.
8.8 Bedøm kontrol
De '+' (plus) og '-' (minus) nøgler kontrollere hastigheden af spillet.
Som standard er spillet kører på en standard hastighed, i henhold til reglerne i Standard Tetris (hastighed baseret på niveau).
Her er en tabel over de betydninger af hastighed skævhed:
-3,-4,...: langsomhed proportional med partiskhed
-2: langsommere end niveau 1
-1: normal, men begrænset til niveau 6 (0,2 sek) hastighed;
0: normal; Standard Tetris hastighedsbestemmelser;
+1: en anelse hurtigere end niveauet 9 (0.05 sec forsinkelser);
+2: afgrænset af præstationen sats (eksempel: 75 Hz);
+3,+4,...: flere gentagelser pr afsmeltede ramme;
Jeg kan godt lide at køre A.I. på en indstilling af "+2" (hit '+' tasten to gange, hvis partiskhed starter ved nul).
Fart partiskhed ændrer hastigheden af spillet.
8.9 Vis næste stykke
Hit 'N' for at slå "Næste Piece" skærm. De A.I. vil bruge "Næste Piece" oplysninger kun, hvis "Næste Piece" vises på skærmen.
Du kan være forvisset om, at AI ikke bruger "Næste Piece" oplysninger, når du ikke kan se den "Næste Piece" på skærmen.
Vis det næste stykke
8.10 Bestyrelsens størrelse
Trykker Ctrl + (venstre, højre, ned, op), kan man justere bord størrelse til vilkårlige størrelser fra 4 * 4 op til 200 * 400.
Board størrelse: 4 * 8
Board størrelse: 20 * 40
Board størrelse: 40 * 80
Board størrelse: 20 * 5
Board størrelse: 4 * 100
8.11 S/Z stykker kun
Undersøgelse de interessante skiftevis S/Z mønster.
Dette mønster kan ikke løses i en 10 * 20 bord (bredde * højde).
Men, nævn, der har bredder, der er mangefold af 4 er trivially vist sig at tillade uendelig overlevelse.
De AIs overleve på ubestemt tid i disse sager, selv om de ikke var specielt tunet til at håndtere dette patologiske situation.
S/Z stykker kun
8.12 Video kalibrering mode
Hit 'C' for at indtaste "Kalibrering Mode". Når kalibrering mode, kan du trykke på taltasterne: {1,2,3,4,5,6,7} at vælge et stykke {O,I,S,Z,L,J,T} øverst på at spille bord.
Dette er nyttigt som en henvisning image for video-capture på en anden Standard Tetris software.
Hvis du trykker på 0 (nul) tasten, vil det gøre bord tomt.
Du kan foregive at gyde brikker ved at vælge et stykke (1..7), og derefter vælge en tom (0), mens en anden computer laver video capture ure for brikker.
Du kan køre A.I. på den anden computer og se, hvordan det behandler din manuelt trådte patologiske Tetris scenarier!
Kalibrering Mode er den eneste gang, du kan manipulere video capture billedbehandling skabelon (4 * 2 gitter). Du kan bruge musen til at trække rektanglet, men så kan du bruge cursor-tasterne ( "op", "ned", "Venstre", "ret") for at få bøde kontrol af grænserne - at bruge Shift nede for at vælge modsatte grænser af rektanglet (eksempel: "Shift-venstre" combo er anderledes end "til venstre").
Video kalibrering mode
8.13 Videooptagelse og anerkendelse
Trykke på 'V' Skifter video capture mode. Hvis ordentligt kalibreret (se "video kalibrering" i et foregående afsnit), stykker af en fjernbetjening video-skærmen vil blive taget til fange af videokameraet og klassificeret - og de stykker vil blive skabt i den lokale vildt for A.I. til at overveje og reagere .
De A.I. output skal derefter sendes (via RS-232 grænseflade i demonstrationen beskrevet i denne artikel) til fjerntliggende vildt input (eksempel: keyboard) for A.I. at kunne spille fjernbetjeningen spillet.
Hvis der på noget tidspunkt denne lukkede kredsløb forstyrres (eksempel: video capture svigt, eller output signal svigt), derefter A.I. vil udvikle et falsk indtryk af status for de fjerntliggende spil, og A.I. vil gøre uhensigtsmæssige beslutninger, som hurtigt taber spillet .
(Bemærk: Dette problem kan overvindes med et beskedent beløb af indsatsen: A.I. system behøver kun at undersøge hele fjernbetjening Tetris skærmen for en igangværende "reality check" af hele bord, og A.I. system bør være forberedt på nogle output-kommandoer til at mislykkes på nogle måde.)
Videooptagelse og anerkendelse
9. Oprindelig Tetris AI eksperiment (2003)
Følgende viser den første udgave af Tetris A.I. system i 2003.
Videokamera står computer # 1 kører nogen almindelig Tetris spil
Computer # 2 kører Standard Tetris software i A.I. mode
Venstre: Tegning nettet til kalibrere videobilledet anerkendelse;
Højre: Tetris stykke anerkendelse tilfælde.
Ramme fra videooptagelse af Tetris A.I. eksperiment i 2003
10. Bedste one-brik Tetris-spiller algoritme i verden
10.1 Pierre Dellacherie (2003; Frankrig)
Pierre Dellacherie (2003; Frankrig), udvikleren af de bedste one-brik Tetris-spiller algoritme i verden
The best one-brik, tidstro Tetris algoritme til min viden blev oprettet ved Pierre Dellacherie af Frankrig.
Hans fantastiske algoritme til tider fylder mere end 2 millioner rækker!
Den gennemsnitlige resultater er på rækkefølgen af 650000 rækker.
Den algoritme tager meget lidt hukommelse, og kører med høj hastighed (ca. 160 rækker i sekundet på mit 800 MHz computer).
Opfyldelse af Pierre Dellacherie's algoritme:
Min nuværende model for udførelsen af Tetris AIS er, at for et givet stykke er der en konstant sandsynlighed for, at spillet vil opsige, p.
Således er sandsynligheden for, at et stykke ikke vil opsige en Spillet er q=(1-p).
Sandsynligheden for spillets afslutning efter k flytter er simpelthen produktet af sandsynligheden for at overleve (k-1) bevæger sig, nemlig q^(k-1), og sandsynligheden for, at der slutter den næste træk, nemlig p.
Dette svarer til en "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 )
For små p, ln(q) er omtrent (-p), og vi har således:
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 )
Vi forventer, at brøkdel af det samlede antal spillede spil til at opsige med et antal udfyldte rækker i intervallet [k1, k2] være:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Efter at have afsluttet 36 spil på min computer, der over en periode på to dage, jeg fandt en et gennemsnit på 674827 afsluttet rækker.
Ifølge den generelle teori ovenfor, ville jeg forvente følgende relative fraktion af spil til slut i følgende afsluttet rækken værdiskalaer:
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
Her er en graf, der sammenligner Exponential Distribution teori med den observerede fordeling af spil.
Opfyldelse af Pierre's algoritme over 36 afsluttede spil
Selvom der er meget få spil i dette datasæt, er det tydeligt, at modellen er temmelig god til at matche den observerede distribution.
Pierre's introduktion til hans algoritme:
Pierre begyndt at arbejde på dette one-brik algoritme i 2003,1.
Pierre sendt mig en e-mail om hans algoritme på 2003.4.9, rapportering følgende resultater over 20 på hinanden følgende spil:
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.
"Den algoritme er implementeret i Turbo Pascal og fuldender 7000 rækker / min. Med en Athlon 1600+."
Jeg konverterede Pierre's algoritme til C++ i 2003,6, efter flere e-mail-udveksling med Pierre. Vi har kontrolleret, at A.I. i C++ version fremsat samme afgørelser truffet af Pascal version.
Jeg observeret lignende resultater til hans oprindelige rapport; gennemsnit omkring 650000 afsluttet rækker, og nogle spil udfyldelse 2 mio rækker.
Utroligt!
10.2 Samtale med Pierre Dellacherie
[1] Hvornår har du først oprette denne kode?
Jeg har arbejdet med den algoritme fra slutningen af januar 2003 indtil nu.
[2] Hvor længe har du arbejdet på det?
Jeg har arbejdet på det næsten hver uge ... men ikke dagligdags længe, fordi jeg har andre aktiviteter: desværre er jeg nødt til at tjene penge ligesom alle andre!
[3] Hvad inspirerede design af koden?
Jeg spillede Tetris 10 eller 15 år siden, men jeg havde ikke spilles igen i lang tid. Jeg vil sige, at jeg er en "gennemsnitlige" afspiller der kender reglerne og nogle tricks.
Men da jeg begyndte at arbejde på algoritme jeg ikke spille så meget fordi jeg fandt det var lidt mere effektivt at se computeren spille og analysere sine svagheder.
[4] Har du bruge enhver automatisering til at "uddanne" din kode til at udføre bedre? Gjorde du har feedback til at forbedre den algoritme?
Eller har du bare se på resultaterne og beslutte at foretage ændringer?
Jeg er fra "gamle skole:" Jeg har simpelthen set resultaterne og besluttede at foretage ændringer.
"Automatisk læring" er en form for meta-algoritme, så jeg er ikke sikker på, at gøre det på denne måde vil få lettere, da denne meta-algoritme skulle bygges også, og det er ikke så nemt!
Hvad mere er, jeg er enig med Roger Penrose når han siger (i sin bog "Shadows of the mind"), at menneskelig forståelse og intuition ikke kan algoritmisk (eksempel: beregnelige).
[5] Hvornår har du først begynde at spille Tetris, og hvornår gjorde du har tanken om at løse Tetris med en A.I.?
Jeg underviser algoritmisk og edb-programmering (Turbo Pascal og Scilab) for studerende, der tog til indgangen undersøgelse på graduate ingeniør's skoler.
Ved første, "Computer spiller Tetris" var en idé, jeg ønskede at udvikle til mit næste år studerende.
Jeg var ikke klar over din web side, da jeg begyndte at arbejde på algoritme.
Faktisk var jeg heldig at være opmærksom på din webside kun et par uger siden, fordi jeg tror, jeg ville være blevet afskrækket af dine resultater (som du kan gætte, de tidlige versioner af min algoritme ikke spillede så godt!).
[6] Hvad er din nuværende status?
Jeg er næsten 30 [før 2003 april 27]. Jeg har flere aktiviteter: Jeg er en cellist, jeg komponere musik, og jeg underviser i edb-programmering.
Jeg har en master degree i musikvidenskab (1994) og en "Artificial Intelligence and Algorithmic" eksamensbevis (1998).
I Frankrig dette eksamensbevis svarer til det 5 år at studere på universitetet (4th år er skibsføreren graden og 6 år er den tese).
Pierre's kompositioner:
[7] Hvor Bor du?
Jeg er fransk og jeg bor i Rouen (Normandiet).
[8] Andre kommentarer:
Til sidst har jeg ikke nogen ny idé at forbedre det.
Jeg har prøvet så meget ubrugelig (og dum) ting, som jeg tvivler på det kunne forbedres.
På den anden side, jeg tror, at der måtte findes helt andre algoritmer, som kunne have bedre resultater.
For resten, en hurtigere test består i lanceringen af brikker i et halvt-box (10 rækker X 10 kolonner): I et halvt-box, min algoritme gør et gennemsnit på 280 afsluttede rækker.
En ting mere: algoritme kan let ændret på en dobbelt-lag algoritme ([vil jeg gøre] testene snart).
Jeg elsker film, musik: at blive en film komponist er en del af mine største drømme (men det er bare drømme!).
11. Bedste menneskelige aktør i verden
11.1 Japansk Tetris Master (2001 januar 27) video
Tetris master (2001, Japan) video
Arika præsenterer japansk Tetris finaler master (2001 den 27 januar). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Tilbagemelding
12.1 Slashdot tråden (2003)
I 2003, min Tetris A.I. projektet blev drøftet på Slashdot Internet forum (
http://slashdot.org).
Slashdot (http://slashdot.org) Internet forum overskrift til en diskussion af min Tetris A.I. projekt
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 ]
Comic inspireret af min Tetris A.I. projekt (2003) (den første gang jeg nogensinde har inspireret en tegneserie!)
Comic inspireret af min Tetris A.I. projekt (2003) (den anden gang, jeg har nogensinde inspireret en tegneserie!)
13. Historie af Tetris A.I. projekt
I foråret 1989 var jeg travlt skipping (og modsat) anden halvdel Russer klasser på University of Pennsylvania.
En af mine roommates, Bill Matthews havde Mac Classic, og til tider spillede videospil.
Folk der bliver optaget til Ivy League skoler er typisk tilbøjelig til at konkurrere med andre mennesker på alle tidspunkter - så når Bill fik spillet Tetris for hans Mac vi straks indledte en langvarig kamp for den høje score.
Som scoringer klatrede, tidspunktet investering, der kræves for at gøre en lille gevinst drastisk øget.
For at gøre en lang historie kort, Bill angiveligt besidder den høje score mellem os, men jeg mistænkte ham for at bruge ResEdit og hacking scoren fil!
Bill havde klasser i Wharton School of Business, alma mater af Michael Milken og Donald Trump, så det er ikke utænkeligt, at nogen rigget en impossibly høj score ...
I sommeren 1990 Jeg har lånt en 30 MHz Intel 80386 IBM PC fra min roommate, Alex Haidas.
Jeg købte en Mac tastaturet på et loppemarked for $ 1.
Jeg indbygget parallel port kredsløb at tillade PC at kontrollere Mac tastaturet.
(Jeg brugte en CMOS 4040 chip til at fungere som en slags solid-state relay til at slutte tastaturet kontakter inde i Mac tastatur.)
Jeg skrev et edb-program, der bruges et beslutningstræ som sin strategi for at spille spillet Tetris. På bare et par uger havde jeg en PC spille Tetris Spillet kører på en Mac.
Men jeg var forpligtet til at bruge PC tastaturet til at fortælle A.I. om hver henhørende brik på skærmen.
Jeg begyndte at arbejde på et kredsløb ved hjælp CdS (Cadmium Sulfide) lyset detektorer, der ville magert mod Mac skærmen og "se" de faldende brikker, men CdS sensorer reagerede for langsomt på ændringer i lysstyrken og kontrasten mellem Tetris stykker og baggrunden på Mac Classic skærmen var for lavt til at pålideligt forskelsbehandle.
I disse dage jeg ikke har mange penge, så det var for risikabelt at købe et $ 2 Radio Shack phototransistor, der kunne ikke gøre det, jeg ønskede.
Også i betragtning af kontrasten problem, jeg var pessimistisk hele tilgang.
Da jeg købte min første personlige computer i 1996, kunne jeg ikke få software under Windows 95 på en 100 MHz CPU at gøre video-behandling hurtigt nok til at gøre en enkel vision system arbejde.
Jeg skrev billedbehandling kode i forsamling sprog, men der var så meget overhead før min kode, der rent faktisk modtog videodata, at det syntes umuligt at gøre noget værd.
I 2003, teknologi, især CPU hastighed, havde nået et niveau, der gjorde færdigbehandling af projektet næsten trivielt.
Jeg gravede op min gamle personlige projekt og endelig færdig med det, fik en vis følelse af lukningen.
Det var meget spændende at se en computer at spille en anden computer via USB videokamera og relæer.
Lyden af relæer klikker, og ser brikkerne spin og slip på latterligt, overmenneskelig hastigheder, gjort den erfaring meget tilfredsstillende i en multisensoriske måde.
I 2003, mit arbejde blev anerkendt af Slashdot (
http://slashdot.org), og jeg modtaget et parti af stor feedback.
Jeg var inviteret til at blive vist på "Screen Savers" fjernsyn vises på TechTV digitale tv-net.
Jeg gik til San Francisco og syntes om showet, og den oplevelse var stor.
Senere i 2003, jeg har modtaget en meddelelse fra Henk Rogers, inviterer mig til Hawaii for at mødes med ham og Alexey Pajitnov at tale om at etablere en form for standard for Tetris, med henblik på at have Tetris turneringer.
En særlig interesse blev der gør det muligt for spillere at bruge mobiltelefoner til at "konkurrere med hinanden," indirekte via A.I. at efterligner spillere (ved en forudgående analyse af hver spillers aktioner), for således at undgå virkningerne af mobiltelefon Internet access latenstid, og gøre det muligt for spillere at "konkurrere mod" * De absolut bedste menneskelige spillere i verden (*... eller rettere A.I. efterligne de allerbedste menneskelige spillere i verden).
Jeg var begejstret ved udsigten til at møde skaberen af Tetris. Desværre flyvende gør mig magtpåliggende, og jeg afviste invitationen.
I 2006 er jeg konverteret min "Standard Tetris" software fra C++ til C# at gøre software mere tilgængeligt og nyttigt at nutidens programmører.
