Tetris
Colin Fahey
1. Mjukvara
2. Inledning
Denna artikel beskriver hur en dator kan spela det klassiska spelet Tetris genom att få information om styrelsen, fastställa goda insatser, och utför dessa åtgärder.
Denna artikel innehåller program som kan spela Tetris i realtid.
Programvaran innehåller de bästa realtid Tetris-playing algoritm i det offentliga rummet.
I denna artikel definieras reglerna för ”Standard Tetris,” en specifikation baserad på den ursprungliga 1986 pre-kommersiell version av Tetris för Personal Computer (PC).
I 2003, den programvara som ingår i denna artikel har använts för att göra det möjligt för en dator att spela Tetris körs på en separat dator.
En vanlig USB videokamera användes för att göra det möjligt för datorn att ”se” skärmen i den andra datorn.
Ett relä ombord kontrollerades via en RS-232 gränssnitt som gör det möjligt för datorn att ”trycka på tangenterna” på tangentbordet på den andra datorn.
Det första dator har en relation till den andra datorn som liknar en typisk mänskliga spelarens relation till en dator när man spelar Tetris; turneringsstatus är endast känd genom att titta på skärmen, och spelare åtgärder endast kan inledas genom ett tangentbord .
Konfigurationen i denna demonstration fastställas att en dator kan spela Tetris bättre än en människa under normala realtid Tetris spelas villkor.
3. History of Tetris
I 1985, Alexey Pajitnov och Dmitry Pavlovsky var datorn ingenjörer vid Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre av Russian Academy of Sciences
Alexey och Dmitry var intresserade av att utveckla och sälja beroendeframkallande datorspel.
De provade flera olika spel.
Alexey var inspirerad av den antika grekiska pusselspel, Pentaminos, som innebar att arrangera pussel bitar som gjorts av fem rutor.
Alexey trodde på idén att arrangera Pentamino bitar som de hamnat i en rektangulär skål, men insåg att de tolv olika fem kvadratiska former var för komplicerad för ett videospel.
Alexey bytt till använt sju ”tetramino” bitar, varje består av fyra rutor.
I 1985.6, Alexey Pajitnov programmerade den första versionen av Tetris på en Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov och Tetris.
I 1985-1986, Vadim Gerasimov, en 16-årig gymnasiet dator vidunder som arbetat vid akademin, genomföras Tetris för IBM PC köra MS-DOS operativsystemet.
(Vadim Gerasimov senare gjorde forskning vid MIT Media Laboratory, från 1994 tom 2003, tar emot en doktorsexamen efter att ha avslutat många intressanta projekt:
http://vadim.www.media.mit.edu)
Införandet skärmen i 1987-1988 pre-kommersiell utsättning av Tetris för PC
Spelet spela skärmen i 1987-1988 pre-kommersiell utsättning av Tetris för PC
Efter 1987, Tetris spridda runt om i världen.
The Tetris Company, LLC, äger Tetris varumärke.
4. Projekt inspirerat av Tetris
4.1 0-dimensionella Tetris
Ännu inte utvecklat.
4.2 1-dimensionella Tetris
Ziga Hajdukovic har utvecklat 1-dimensionella Tetris mjukvara som kan spelas i en webbläsare.
Ziga Hajdukovic har också utvecklat 1-dimensionella Tetris programvara för mobiltelefoner som använder Java J2ME plattform.
4.3 2-dimensionella Tetris
Alla konventionella Tetris-varianter är i den här kategorin.
Detta avsnitt innehåller intressanta varianter.
4.3.1 Största Tetris spelet någonsin: Delft University of Technology (1995)
Tetris spelas på en fastighet, 2000 m^2 yta; Delft University of Technology (1995)
Tetris spelas på en fastighet, 2000 m^2 yta; Delft University of Technology (1995)
4.3.2 Ett annat Tetris spelet spelas på en byggnad: Brown University (2000)
Tetris spel visas med lampor i fönstren i en byggnad på Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
”Jag tror att det var just det mest otroliga en dag som jag skulle kunna tänka mig i mitt liv. Precis som Steve Jobs alltid sagt, resan är belöningen.”
”Det fick mig att tänka på projekt som vi gjorde redan i college. Saker som var nästan ångras att andra människor skulle inte tro att göra.”
Steve Wozniak (2000)
4.3.3 Webbläsare spel med MIT ”Green Building” bild
Vadim Gerisimov's webbläsare Tetris
Denna webbläsare Tetris-variant skapades av Vadim Gerasimov.
Denna webbläsare Tetris funktioner de ”Green” byggnad på campus i MIT.
Detta Tetris-variant bara har nio kolumner i stället för de vanliga tio kolumner.
Detta Tetris-variant presenterar nya bitar med slumpmässiga riktlinjer.
Vadim Gerasimov är den person som skrev datorn kod för PC version av Tetris i 1986.
Vadim Gerasimov gjorde Ph.D. Forskningen vid MIT Media Laboratory under 1994-2003, arbetar med många intressanta projekt.
4.3.4 PIC16F84 12 MHz mikrokontroller-baserade NTSC / PAL video Tetris spelet
PIC16F84 12 MHz mikrokontroller-baserade NTSC / PAL video Tetris spelet
Bilden ovan visar den NTSC / PAL videoutgång som producerats av en PIC16F84 12 MHz mikrokontroller köra programvara skriven av Rickard Gunee i 1998.
Den videosignal genereras av programvaran kontroll av digitala utgångar.
4.3.5 ”Scopetris” Oscilloskop Tetris till Lars Pontoppidan (2007.8)
”Scopetris” Oscilloskop Tetris till Lars Pontoppidan (2007.8)
Lars Pontoppidan skrev kod för AtMega32 mikrokontroller, och läggas enkla analoga kretsar, för att skapa en Tetris-version som kan spelas på ett oscilloskop.
Vissa register hos AtMega32 mikrokontroller kontroll 8-bitars output signaler, och då passerade en ”R-2R” elektriska motstånd krets för digital-till-analog (D/A) omställning det resulterande analoga signaler kan styra (x,y) koordinaterna för ett oscilloskop beam (när oscilloskopet är inställd på ”X-Y läge).”
YouTube video:
FLV video:
4.3.6 Krypterat kod Tetris: C / Unix
Följande fick ”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 Krypterat kod Tetris: Perl kod
Följande är Tetris för Perl tolk: Perltris (version 20050717) av 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) är en standard för att beskriva grafiska objekt med XML.
Mozilla SVG Tetris: Tetris genomföras med hjälp av en Scalable Vector Graphics (SVG) beskrivning
4.3.9 Google ”widget” Tetris
Google, Yahoo! och Microsoft samt andra bolag, har främjat miniatyr Internet-baserad programvara som heter ”widgets” som brukar kännetecknas av vissa användning av dynamiska data på Internet.
En sådan widget tillgängliga via Google är ett Tetris spel.
Följande exempel är söta, men de former rotera i irriterande sätt:
Google ”widget” Tetris
Andra Google widgets:
4.3.10 MIT forskning papper: ”Tetris is Hard, Even to Approximate” (2002)
Följande forskning dokumentet innehåller ett bevis på att en viss typ av Tetris-variant är ”NP-klar.”
Erik D. Demaine, Susan Hohenberger och David Liben-Nowell, ”Tetris is Hard, Even to Approximate”, Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
”NP-komplett” är en klassificering av tid kostnad och utrymme kostnaden för en algoritm.
Andra klassificeringar omfattar ”P” och ”NP”.
En klassificering av ”NP-komplett” innebär att det för problem större än några små, algoritm är osannolikt att finna en önskvärd lösning på ett praktiskt tid eller rum.
4.3.11 Forskning dokument: ”Applying reinforcement learning to Tetris”
Följande dokument, som offentliggjordes 2005.5.30, genom Donald Carr vid datavetenskap institutionen vid Rhodes University, Sydafrika, presenterar tillämpningen av ”förstärkning lära” att Tetris.
4.3.12 Tetris Jeanskjol (2007.11)
Tetris Jeanskjol (2007.11)
Den Tetris kjol skapades av ”Lucy” (”hissyfitoly” på etsy.com) innan 2007.11.
Från skaparen beskrivning av kjol (som erbjuds till försäljning 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 om den här kjol:
”Mannen som kjol sucks på Tetris”
”Ahahahaha, jag trodde samma sak.”
”Det finns en komplett linje ner på botten ... ifyllda linjer försvinna.” ”GÖRA UNDER” ”.”
”Det borde finnas en plats på baksidan eller framsidan där långa pjäs skulle passa perfekt ...”
”Det är en riktigt ful kjol though. Min pojkvän kunde inte köpa mig nog choklad och blommor för att övertyga mig att bära denna sak.”
4.3.13 Tetris skede agera (2007.4)
Tetris skede agera (2007.4)
”Från dem som förde dig Triforce i 2006 ... Kommer nästa generation av livlös objektet skit ... Tetris.”
Lokalt cachade video i Flash video (FLV) format (använd VLC att spela):
4.3.14 Munter Tetris variationer på en japansk tv visar
Tetris variationer på japanska TV-visa
Denna video segment från en japansk tv visar inkluderar lustiga varianter av Tetris, däribland:
stycken att försvinna efter landning, en pjäs som fyller en hel rad (och därmed slutföra en rad efter landning), flera bitar faller samtidigt, oregelbundet formade bitar, en lång bit det är lite för bred för att passa i en lucka (och förhindra ett 4-raden slutförandet!), Mario trycka en svamp och blir enormt och dö!, liten bit rymdskrot som återstår efter rader skall förstöras, stigande svårighetsgrad gör bitar float till början etc.
Lokalt cachade video i Flash video (FLV) format (använd VLC att spela):
4.3.15 ”The Original Human TETRIS Performance by Guillaume Reymond” (2007.11)
”The Original Human TETRIS Performance by Guillaume Reymond” (2007.11)
Från beskrivningen YouTube:
”TETRIS spelas av verkliga mänskliga varelser som sitter i ett auditorium:”
TETRIS är den 4: e video utförandet av GAME OVER Project, regisserad av den schweiziska konstnären Guillaume REYMOND (NOTsoNOISY kreativa byrå).
Detta stop-motion video sköts och spelade för ”LES URBAINES” festival
http://www.urbaines.ch vid Palais de Rumine (Lausanne, Schweiz) i November 24th 2007.
Lokalt cachade video i Flash video (FLV) format (använd VLC att spela):
4.3.16 2,5-dimensionella Tetris
Begreppet ”2,5-dimensionell” används här för att innebära en icke-rätvinkliga bakgrund av en tvådimensionell version av Tetris, med viss tjocklek i den tredje dimensionen.
(Hitta på länken ”tetris3d” i ”F7: GAMES”.)
4.4 3-dimensionella Tetris
Linux / GTK version
Tredimensionellt Tetris i form av en Java applet för webbläsare:
Tredimensionellt Tetris för Windows operativsystem:
4.5 4-dimensionella Tetris
Greg Kaiser's ”HyperTetris” (1996): en 4-dimensionella Tetris
I [1996], [...], Greg Kaiser sätta ihop en fyrdimensionell variant av det klassiska spelet.
Använda IrisGL (a.k.a. igl) han skapat en fungerande, om svårt att spela spel med fyra sub-skärmar att skildra olika tredimensionella aspekter av hela spel-rymden.
[Eftersom] det är inte en lätt [begriplig] sätt att dra fyra-D objekt på en två-D skärm, de fyra sub-åsikter är en praktisk metod att manipulera och visualisera rotation och översättning av bitar genom fyra dimensioner ( i spelet kallas x,y,z,w).
Snarare än att fylla rader av block som i den ursprungliga, målet i detta fall är att fylla en hel kub i x,y,z subview (vanligtvis 4 till 4 av 4).
De andra subviews som innehåller ”w” dimensionen är uppställda i en standard 4 av 4 till 10 block arrangemang med ”w” är lång, ”vertical” dimension i samtliga tre fall, med olika baser i (x,y), (x,z), (y,z).
Gravity rättsakter i ”-w” riktning, så bitar faller ”ner” i de tre långa subviews att omfatta ”w”, och rör sig inte om inte genom spelarens kontroll under de sista (x,y,z) subview.
Det tar en stund att vänja sig, minst sagt.
Om av några mirakel tålamod eller att ändra parametrarna i spelet, en har slutföra en kub, det kommer att försvinna som det ifyllda rader gör i originalet Tetris, men ingen värdering hålls i HyperTetris.
Benjamin Bernard (2000)
4.6 N-dimensionella Tetris
Polytope Tetris (2003): en N-dimensionella Tetris spelet variant
Polytope Tetris är n-dimensionally Tetris.
Inspirerad av HyperTetris program Polytope Tetris kan du tons spela Tetris på något ANTAL dimension.
Spela Tetris i 3D, 4D, 5D, eller mer.
HyperTetris är en mycket catchier namn än Polytope (def) Tetris, men jag kan inte stjäla namnet.
5. ”Standard Tetris” specifikation
5.1 Inledning
Definitionen av ”Standard Tetris” är ett idealized modell av de viktigaste egenskaper och beteenden i första IBM-PC genomförandet av Tetris spelet (cirka 1986-1988).
The idealized modellen bygger på inferring den uppenbara avsikter av utvecklarna av de första IBM-PC genomförandet av Tetris spelet.
Exempelvis verkar det rimligt att dra slutsatsen att utvecklarna av de första IBM-PC genomförandet av Tetris spel avsedda att välja den form av varje nytt faller bit ”slumpmässigt,” och att användningen av Borland C genomförandet av rand() funktion var bara en praktisk tillnärmning av avsikten.
Definitionen av ”Standard Tetris” anger att formen på varje ny faller pjäs ska väljas ut ”slumpmässigt.”
Detta ideal beteende inte kan uppnås på något genomförande, men implementeringar kan närma ideala beteende.
Även om inga genomförandet kan helt genomföra definitionen av ”Standard Tetris,” ideal ”Standard Tetris” engagera objektiva egenskaper, och implementeringar kan jämföras enligt deras relativa närhet till ideal ”Standard Tetris.”
Detta avsnitt beskriver en rad faktorer, beteenden och regler, vilket sammantaget definiera ”Standard Tetris.”
5.2 Standard Tetris styrelse
Styrelsen är ett rutnät av celler, med 10 kolumner och 20 rader, för totalt 10 * 20 = 200 celler.
Standard Tetris board (10 kolumner, 20 rader)
Varje ruta kan antingen vara obesatt (tom) eller utnyttjas (full).
5.3 Standard Tetris bitar
Det finns sju (7) standard Tetris bitar, med följande skrivelse namn:
{ O, I, S, Z, L, J, T }
I skrivelsen namn är inspirerat av de former av bitar.
De sju Standard Tetris bitar och deras ”inriktningar”
Punktförstoringen vid (0,0) sammanfaller med styrelsens ståndpunkt (6,20) då pjäsen först uppträder.
Den första kolumnen visar den ursprungliga ”riktlinjer.”
I det följande ordet ”läggning” används för att beskriva något av en pjäs, inom en uppsättning tillåtna stater, som kan bli följden av en moturs rotation händelse.
Att ändra ”inriktning” från en bestämd ”inriktning” av en ”I, S” eller ”Z” pjäs, kräver en kombination av en rotation och en översättning.
Därför ordet ”läggning” används här för att betyda något mer än rotation ensam.
Men ”inriktningen” kan förändras bara som svar på en moturs rotation evenemanget och kretslopp distinkta ”riktlinjer” för varje pjäs tillnärmas, eller matcher, cykeln som följer av ren rotationer.
Den särskilda användningen av ordet ”orientering” i detta sammanhang är nästan lika med innebörden av ordet ”rotation” eller ”vinkel,” men ordet ”läggning” används i stället för ”rotation” att försöka väcka uppmärksamhet på det faktum att vissa bitar kräver mer än rotation för att producera uppsättning tillåtna stater som följer av moturs ”rotation” händelser.
Bitar kan bara byta inriktning (eller genomgå en särskild horisontella eller vertikala översättning) om det erhållna tillstånd av pjäsen skulle inte få några ockuperade (full) celler än området för styrelsen och skulle inte få några ockuperade celler som överlappar alla närvarande ockuperade celler i styrelsen.
(I denna regel, de ockuperade (full) celler av pjäsen är inte att betrakta som en del av de ”närvarande ockuperade celler i styrelsen”
I följande kommentarer, någon hänvisning till en träff av en moturs rotation händelse görs med antagandet att ett sådant byte verkligen kan ske, med tanke på de befintliga villkoren i pjäsen och linjen.
Den ”O” (fält) pjäs bara har en enda inriktning, och inte ändra plats på någon av dess ockuperade (full) celler som svar på en moturs rotation händelse.
Den ”I” (linje) pjäs har två möjliga inriktningar, som ursprungligen förekommer i en övergripande orientering.
Den ”I” pjäs växlar mellan de två inriktningar som svar på varandra följande moturs rotation händelser.
Den ”S” och ”Z” bitar har vardera två möjliga inriktningar.
Dessa bitar varje växlar mellan två inriktningar som svar på varandra följande moturs rotation händelser.
Den ”L”, ”J” och ”T” bitar har vardera fyra möjliga inriktningar, och dessa riktlinjer är resultaten av enkla rotationer om center poäng på de former.
När en pjäs först förekommer i styrelsen, pjäsen har sin ”stora axeln” i en horisontell riktning, och pjäsen är på toppen av brädet.
Därför kommer inga bitar är ursprungligen kan ha sin inriktning ändrats. Verket måste härstamma från en rad som ska ha möjlighet att låta sin inriktning ändrats.
När en pjäs har minskat med en rad på bordet, alla pjäs riktlinjer kan uppnås (om man antar att pjäsen inte är för nära sidoväggarna eller till den aktuella högen av bitar).
5.4 Standard Tetris flödesschemat
Följande är ett ungefärligt flödesschemat för en Standard Tetris spelet.
Ungefärliga flödesschemat för en Standard Tetris spel
Ungefärliga flödesschemat för en Standard Tetris spel
5.5 Standard Tetris pjäs skapande
Följande diagram visar (4 cell * 2 cell) region i styrelsen där alla bitar visas när skapats.
Region där bitar visas när skapats i Standard Tetris
När en ny pjäs först förekommer i styrelsen, dess ursprung sammanfaller med prick på den här bilden, och pjäsen kommer att vara helt innesluten av den skuggade ytan på den här figuren.
När ett nytt spel är startat, en fullständig fritt fall dröjsmål förflyter, och den första fritt fall iteration en bit är skapat i början av linjen.
Under normala spelet, när en särskild fritt fall iteration ”landar” en pjäs, en fullständig fritt fall dröjsmål förflyter och om nästa fritt fall iteration en bit är skapat i början av linjen.
När en pjäs är skapat, vilken typ av pjäs är vald med hjälp av följande algoritm:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Eftersom det är en ständig p (= 1/7) chans att välja en specifik typ av pjäs, och alla pjäser av samma typ är omöjlig att skilja, sannolikheten för att ha exakt k bitar av en viss typ efter n prövningar följer 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äljer bland de 7 (sju) stycken slumpvis, sannolikheten att få en viss pjäs är p=(1/7).
Om vi gör detta n=70 gånger, till exempel, sannolikheten att få exakt k bitar (med k i intervallet 0 att n) fås genom binomial distribution, som i följande bild.
Binomial distribution för n=70, p=(1/7)
Således kan man förutsäga de genomsnittliga totala bitar av en enda typ gett ett totalt antal slumpmässiga bitar, och man kan också beräkna den förväntade varians och standardavvikelse (kvadratroten av 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 omvandlar ett slumpmässigt värde till en bit index, vi tolka det på följande sätt:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[The pre-kommersiella MS-DOS version av Tetris använt slumpmässigt antal funktioner som erbjuds genom Borland Pascal kompilator.
Denna funktion används ett 32-bitars statliga variabel.
Därför är den sekvens av slumptal var begränsad till 2^32 skilda värderingar.
Därför, i princip, en spelare kan upptäcka, efter att släppa kanske 10 stycken, den exakta plats i den uppsättning 2^32 numren motsvarar det aktuella läget i spelet.
Om Tetris simuleringar är utförda med fast sekvens av 2^32 bitar, då optimala beslut finns för varje plats i sekvens.
(Det tycks finnas tillräckliga möjligheter att vara styrelsen att en helt tom kartong stat, möjliggör för oss att få synkroniseras med förhand optimala lösningen väg.)
Risken med att använda ett slumpmässigt antal generator i en simulering som syftar till att hitta en optimal lösning på ett problem är att lösningen blir optimal bara för särskilt väg genom problemet rymden väljs av slumpmässigt nummer generator. ]
5.6 Standard Tetris kontroller
Under spelet, följande ingångar finns tillgängliga:
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
Alla ingångar verkan den stigande-kanten av positiv input (på knapptryckning, i motsats till knapp release).
När en knapp tryck uppstår, detta räknas som en begäran.
Håll en knapp ned efter en viss tid kan resultera i att ”auto-repeat” funktionen av ett tangentbord, genererar ny knapp pressar - men denna funktion är extern till spelets motor.
De insatsvaror som anges ovan överensstämmer med den ursprungliga Tetris spelet.
Rotera begäran kan verkställas om det inte finns någon överlappning mellan önskad inriktning och uppsättning celler i den nuvarande styrelsen (exklusive de fallande bit), och om den önskade inriktningen har ingen uppsättning celler utanför styrelsen.
Översätt begäran kan verkställas om det inte finns någon överlappning mellan de önskade översatt konfigurering och uppsättning celler i den nuvarande styrelsen (exklusive de fallande bit), och om den önskade översatt konfiguration har ingen uppsättning celler utanför styrelsen.
Ingång ansökningar behandlas med en latency som beror på bildfrekvensen av spelet (exempel: 75 Hz), och begär verkan (om giltig) direkt.
En pjäs kan avlägsnas utan att linjen faller steg inträffar.
En pjäs kan översättas flera gånger till vänster eller höger, och minskade därefter, alla utan upplever en officiell linje som omfattas steg.
Eftersom en nyligen givit pjäsen omöjligen kan roteras (eftersom det är stickat mot den övre änden av linjen), spelaren måste ta minst en bit som faller steget om rotationer är önskvärd eller nödvändig.
Effekten av värdering är obetydlig.
5.7 Standard Tetris pjäs ”landning”
Om en pjäs är helt enkelt faller, faller genom en enda rad under varje bit som faller iteration.
Det kommer att finnas en iteration som flyttar den från en plats utan kontakt med horisontella ytor till en plats som har kontakt med horisontella ytor. När detta upprepningar förekommer, pjäserna är i vila kontakt.
Om en iteration börjar med en bit i vila kontakt med en horisontell yta, pjäsen ”landar,” och blir en del av statisk lugg.
5.8 Standard Tetris ”linjer ifyllda”
En färdig raden är en rad med luggen där alla celler är ockuperat. När en färdig raden utsöndras ur högen, och raderna ovanför bort raden flyttas ner till en rad för att eliminera klyftan, detta räknas som en färdig ”linje.”
När en pjäs landar det blir en del av högen.
Omedelbart efter pjäs landar, luggen är markerad för färdig rader och alla ifyllda rader skall elimineras.
Upp till fyra rader kan slutföras samtidigt.
Nedanstående tabell visar den övre gränsen på linjer slutföras samtidigt genom ett enda stycke:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Standard Tetris ”nivåer”
Standard Tetris har 10 svårighetsgrader, numrerade 1 (en) genom 10 (tio), med nivån 1 är det ”minst svåra.”
Nivån index är högst två värden:
actualLevel = max( initialLevel, earnedLevel );
Den initialLevel värde är den nivå som spelaren väljer när de startar ett nytt spel.
Mönstret av nivå som en funktion av färdig linjer är lätt iakttas i pre-kommersiella MS-DOS version av 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
Det earnedLevel värde beräknas enligt följande 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 Standard Tetris faller iteration dröjsmål
Standard Tetris har en realtid fördröjning mellan kronologisk linje fritt fall iterationer som är en funktion av den aktuella svårighetsgrad.
Följande förhållande mellan nivå index och fallande iteration dröjsmål bygger på upprepade stoppur mätningar på alla nivåer i den pre-kommersiella MS-DOS version av 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
Alltså, vi fastställa följande formel för iteration dröjsmål värde som en funktion av den faktiska nivån index:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Om verket är tom och det finns inga användarens input, ett givit pjäsen på faktiska nivån 1 landar på cirka 10 sekunder och en givit pjäsen på faktiska nivån 10 landar på cirka 1 andra.
5.11 Standard Tetris ”värdering”
Standard Tetris bara poäng för själva landningen en bit.
Det finns inga poäng för handlingen att fylla en rad, eller fylla två, tre eller fyra linjer samtidigt.
[Notera: Vissa varianter av Tetris tilldelning poäng för handlingen att fylla raderna med en exponentiell ökning bonus för allt fler samtidigt fyllas linjer.
De strategi för att maximera värdering i sådana varianter av Tetris innebär att inrätta möjligheter att ”få en Tetris,” slang för att använda ”I” form för att få fyra parallella linjer och få massor av poäng. ]
Om du har en tom kartong, och du låter en icke-”I” pjäs göra ett fritt fall och mark, eller du omedelbart släpper ett icke-”I” bit kan du skapa följande diagram med hjälp av pre-kommersiella MS-DOS version av 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, icke-”I” bitar faller totalt 18 rader.
Detta står för den punkt skillnaden mellan fritt fall och instant-släpp fall.
Genom att experimentera med mellanliggande fall är det lätt att dra slutsatsen följande punkt formel:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Observera att denna formel har ingenting att göra med avståndet en bit faller!
Det är absolut en funktion av den faktiska nivån, och en straffavgift för antalet iterationer en bit får falla fritt.
Detta straffar en användare för att behöva tid att tänka.
Observera också att eftersom en del inte kan inledningsvis vara roteras när den första äggläggningar, en spelare straffas med minst ett fritt fall iteration om rotationer är skyldiga att placera en pjäs i högen.
Detta förmodligen aldrig påverkar människors spelare, såvida de inte på något sätt: erkänna pjäsen trycker översättning nycklar ”(vänster” eller ”höger),” tryck på ”rotera” nyckeln en eller flera gånger, och tryck på ”släpp” nyckeln, alla inom mindre än 0.5 sekunder på nivå 1, eller mindre än 0.05 sekunder på nivå 10.
6. Standard Tetris strategi
6.1 Inledning
En strategi för att spela ett spel beror på spelets regler.
En strategi beror på vilken parameter som skall optimeras.
I Standard Tetris, ett överlever genom att fylla rader, får poäng för landning bitar, och gör flest poäng möjligt för varje bit genom en droppe innan ett eller flera fritt fall iterationer avdunsta.
En A.I. kan optimera poäng för varje pjäs helt enkelt genom att besluta om ett snabbt och ”trycka på tangenterna” att verkställa flytten.
Fler viktigt att en A.I. är överlevnad, eftersom obestämd överlevnad innebär ett godtyckligt hög värdering kan uppnås. Eftersom Tetris bitar falla på en viss kurs, A.I. måste fatta beslut åtminstone denna snabbt
