Tetris
Colin Fahey
1. Programvare
StandardTetris_2007June4.zip
Tetris kildekoden (C# og C++ versjoner) og program ("exe");
4068277 bytes
MD5: 4e957e0ead66064183e9f7e04e618ec0
2. Innledning
Denne artikkelen beskriver hvordan en datamaskin kan spille klassiske spill Tetris ved å få informasjon om bord, bestemme gode handlinger, og utfører disse handlingene.
Denne artikkelen inneholder programvaren i stand til å spille Tetris i sanntid.
Programvaren omfatter de beste sanntid Tetris-spiller algoritmen i den offentlige sfæren.
Denne artikkelen definerer reglene for "Standard Tetris," en spesifikasjon basert på den opprinnelige 1986 pre-kommersiell versjon av Tetris for Personal Computer (PC).
I 2003, programvare inkludert i denne artikkelen ble brukt til å aktivere en maskin til å spille Tetris kjører på en separat maskin.
En vanlig USB videokamera ble brukt til å aktivere maskinen til å "se" skjermen på den andre datamaskinen.
Et relé bord ble styrt via en RS-232 grensesnitt for å aktivere datamaskinen til å "trykke på tastene" på tastaturet på den andre datamaskinen.
Derfor, den første datamaskinen har et forhold til den andre datamaskinen som ligner på en typisk menneskelig spillerens forhold til en datamaskin når man spiller Tetris; spillet staten er bare kjent ved å se på skjermen, og spilleren handlinger bare kan igangsettes gjennom et tastatur .
Den konfigurasjonen i denne demonstrasjonen ble etablert som en datamaskin kan spille Tetris bedre enn et menneske, under normale sanntid Tetris spille betingelser.
3. Historien om Tetris
I 1985, Alexey Pajitnov og Dmitry Pavlovsky ble datamaskinen ingeniører på Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre av Russian Academy of Sciences
Alexey og Dmitry var interessert i å utvikle og selge vanedannende dataspill.
De testet ut flere forskjellige spill.
Alexey ble inspirert av det gammelgreske puslespill spillet, Pentaminos, som er involvert arrangere puslespill brikker laget av de fem rutene.
Alexey tenkte på ideen om å arrangere Pentamino brikker som de falt i en rektangulær cup, men innså at de tolv forskjellige fem-torget figurer var for komplisert for et spill.
Alexey slått til ved hjelp av syv "tetramino" brikkene, hver laget av fire firkanter.
I 1985.6, Alexey Pajitnov programmert den første versjonen av Tetris på en Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov, og Tetris.
I 1985-1986, Vadim Gerasimov, en 16-år gamle high-school nytt vidunder som jobbet på Norges musikkhøgskole, gjennomført Tetris for IBM PC kjører MS-DOS operativsystemet.
(Vadim Gerasimov senere gjorde forskning på MIT Media Laboratory, fra 1994 til 2003, får en doktorgrad etter fullført mange interessante prosjekter:
http://vadim.www.media.mit.edu)
Innføringen skjermen av 1987-1988 pre-kommersielle versjonen av Tetris for PC
Spillet spille skjermen av 1987-1988 pre-kommersielle versjonen av Tetris for PC
Etter 1987, Tetris spredt rundt om i verden.
The Tetris Company, LLC, eier Tetris varemerke.
4. Prosjekter inspirert av Tetris
4.1 0-dimensjonale Tetris
Ikke ennå utvikles.
4.2 1-dimensjonale Tetris
Ziga Hajdukovic har utviklet 1-dimensjonale Tetris programvare som kan spilles av i en nettleser.
Ziga Hajdukovic har også utviklet 1-dimensjonale Tetris programvare for mobiltelefoner ved hjelp av Java J2ME plattformen.
4.3 2-dimensjonale Tetris
Alle konvensjonelle Tetris-variantene er i denne kategorien.
Denne delen inneholder interessante variantene.
4.3.1 Størst Tetris spill noensinne: 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 Another Tetris spill spilles på en bygning: Brown University (2000)
Tetris spill vises ved hjelp av lys i vinduene i en bygning på Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
"Jeg tror det var bare de mest utrolige én dag jeg kunne forestille seg i livet mitt. I likhet med Steve Jobs alltid sagt, reisen er belønning."
"Det gjorde meg tenke på prosjekter vi gjorde tilbake i høgskolen. Ting som var nesten angrast at andre mennesker ikke ville tenke på å gjøre."
Steve Wozniak (2000)
4.3.3 Internett leseren spillet med MIT "Green Building" bilde
Vadim Gerisimov's nettleser Tetris
Denne nettleseren Tetris-varianten ble opprettet av Vadim Gerasimov.
Denne nettleseren Tetris funksjonene "Green" bygningen på campus av MIT.
Dette Tetris-varianten bare har ni kolonner i stedet for den vanlige ti kolonner.
Dette Tetris-varianten presenterer nye brikker med tilfeldig orientering.
Vadim Gerasimov er den personen som skrev datamaskinen koden for PC versjon av Tetris i 1986.
Vadim Gerasimov gjorde doktorgrad forskning på MIT Media Laboratory under 1994-2003, arbeider med mange interessante prosjekter.
4.3.4 PIC16F84 12 MHz microcontroller-baserte NTSC / PAL video Tetris spill
PIC16F84 12 MHz microcontroller-baserte NTSC / PAL video Tetris spill
Bildet ovenfor viser NTSC / PAL video produsert av en PIC16F84 12 MHz microcontroller kjører programvaren er skrevet av Rickard Gunee i 1998.
Videoen signalet er generert av programvare for kontroll av digitale utganger.
4.3.5 "Scopetris" Oscilloskop Tetris ved Lars Pontoppidan (2007.8)
"Scopetris" Oscilloskop Tetris ved Lars Pontoppidan (2007.8)
Lars Pontoppidan skrev koden for AtMega32 microcontroller, og lagt til enkle analoge kretskoblinger, for å lage en Tetris-versjon som kan spilles på et oscilloskop.
Enkelte registre av AtMega32 microcontroller kontroll 8-bit output-signaler, og da gikk gjennom en "R-2R" elektrisk motstand krets for digital-til-analog (D/A) konvertering, noe som fører analoge signaler kan styre (x,y) koordinater for et oscilloskop beam (når oscilloskop er satt til "X-Y modus)."
YouTube video:
FLV video:
4.3.6 Uklar koden Tetris: C / Unix
Følgende ble tildelt "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 koden Tetris: Perl koden
Følgende er Tetris for Perl tolk: Perltris (versjon 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 for å beskrive grafiske objekter ved hjelp XML.
Mozilla SVG Tetris: Tetris gjennomført ved hjelp av en Scalable Vector Graphics (SVG) beskrivelse
4.3.9 Google "widget" Tetris
Google, Yahoo!, og Microsoft og andre selskaper, har markedsført miniatyr Internett-basert programvare kalt "widgets" som vanligvis er preget av noen bruk av dynamiske data tilgjengelig på Internett.
Et slikt widget tilgjengelig gjennom Google er et Tetris-spill.
Følgende eksempel er søte, men former rotere på irriterende måter:
Google "widget" Tetris
Andre Google widgets:
4.3.10 MIT forskning papir: "Tetris is Hard, Even to Approximate" (2002)
Følgende forsknings-dokumentet inneholder et bevis for at en bestemt slags Tetris-varianten er "NP-fullført."
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-komplett" er en klassifisering av tiden pris og plass pris av en algoritme.
Andre klassifikasjoner inkludere "P" og "NP".
En klassifisering av "NP-komplett" innebærer at for problemer større enn noen av liten størrelse, algoritmen er lite sannsynlig å finne en ønsket løsning på et praktisk mengde tid eller plass.
4.3.11 Forskning dokumentet: "Applying reinforcement learning to Tetris"
Følgende papir, publisert 2005.5.30 ved Donald Carr ved Computer Science-avdelingen ved Rhodes University, Sør-Afrika, presenterer anvendelse av "forsterkning" for "læring" Tetris.
4.3.12 Tetris Skirt (2007.11)
Tetris Skirt (2007.11)
The Tetris skjørt ble opprettet av "Lucy" ("hissyfitoly" på etsy.com) før 2007.11.
Fra skaperen beskrivelse av skjørt (tilbys for 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 om denne skjørt:
"Man at skjørt amme på Tetris"
"Ahahahaha, jeg trodde det samme."
"Det er en komplett linje ned på bunnen ... fullført linjene forsvinner." "GJØRE OVER" "."
"Det bør være et punkt på ryggen eller foran hvor langt stykke ville passe perfekt ..."
"Det er en virkelig stygg skjørt though. Min kjæreste ikke kunne kjøpe meg nok sjokolade og blomster til å overbevise meg om å bære det ting."
4.3.13 Tetris stage handle (2007.4)
Tetris stage handle (2007.4)
"Fra de som brakte deg Triforce i 2006 ... Leveres neste generasjon av inanimate objekt skit ... Tetris."
Lokalt hurtigbufrede video i Flash video (FLV) format (bruk VLC å spille):
4.3.14 Munter Tetris varianter på en japansk TV-program
Tetris varianter på japansk TV-program
Denne videoen segment fra en japansk TV-program inkluderer munter varianter av Tetris, inkludert:
brikkene som forsvinne ved landing, et stykke som fyller en hel rad (og dermed fylle en rad ved landing), flere brikker faller samtidig, irregularly shaped pieces, et langt stykke som er litt for lang til å passe inn i et gap (hindre en 4-rad ferdigstillelse!), Mario treffer en sopp og bli enorme og dø!, liten vrakgodset igjen etter at radene er ødelagt, oppadgående tyngdekraften gjør brikkene flyte til toppen, osv.
Lokalt hurtigbufrede video i Flash video (FLV) format (bruk VLC å 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 på YouTube:
"TETRIS spilt av ekte menneske-vesener sitter i et auditorium:"
TETRIS er den 4de video resultatene av GAME OVER Project, ledet av den sveitsiske kunstneren Guillaume REYMOND (NOTsoNOISY kreative byrå).
Dette stop-motion video ble skutt og spilte for "LES URBAINES" festivalen
http://www.urbaines.ch ved Palais de Rumine (Lausanne, Sveits) på November 24th 2007.
Lokalt hurtigbufrede video i Flash video (FLV) format (bruk VLC å spille):
4.3.16 2,5-dimensjonale Tetris
Begrepet "2,5-dimensjonale" er brukt her for å føre en ikke-ortogonale visning av en todimensjonal versjon av Tetris, med litt tykkelse på den tredje dimensjonen.
(Finn koblingen "tetris3d" i "F7: GAMES".)
4.4 3-dimensjonale Tetris
Linux / GTK versjon
Tre-dimensjonale Tetris i form av en Java applet for Internet nettlesere:
Tre-dimensjonale Tetris for Windows operativsystem:
4.5 4-dimensjonale Tetris
Greg Kaiser's "HyperTetris" (1996): en 4-dimensjonale Tetris
I [1996], [...], Greg Kaiser satt sammen en fire-dimensjonale varianten på den klassiske spillet.
Bruke IrisGL (a.k.a. igl) han opprettet et arbeidsutvalg, hvis vanskelig å spille spillet med fire sub-skjermer for å skildre ulike tre-dimensjonale aspekter av hele spill-plass.
[Fordi] er det ikke en enkelt [forståelig] måte å trekke fire-D-objekter på en to-D skjerm, fire sub-visninger er en praktisk metode for å manipulere og visualisere rotasjon og omsetjing av bitene gjennom de fire dimensjonene ( i spillet kalt x,y,z,w).
Snarere enn å fullføre linjer med blokker som i den opprinnelige, er målet i dette tilfellet er å fylle en fullstendig cube i x,y,z subview (vanligvis 4 av 4 av 4).
Den andre subviews som inneholder "w" dimensjon er ordnet i en standard 4 av 4 av 10 blokker ordningen med "w" være lang, "vertical" dimensjon i alle tre tilfeller, med ulike baser av (x,y), (x,z), (y,z).
Gravity handlinger i "-w" retning, slik at brikkene faller "ned" i de tre lange subviews som inkluderer "w", og ikke flytte med mindre av spilleren kontroll i den siste (x,y,z) subview.
Det tar litt tid å bli vant til, å si minst.
Hvis noen av mirakel av tålmodighet eller endring av parametere i spillet, en ikke fullfører en terning, det vil forsvinne som avsluttet linjer gjør i den opprinnelige Tetris, men ingen poeng er holdt i HyperTetris.
Benjamin Bernard (2000)
4.6 N-dimensjonale Tetris
Polytope Tetris (2003): en N-dimensjonale Tetris spill variant
Polytope Tetris er n-dimensionally Tetris.
Inspirert av HyperTetris programmet, Polytope Tetris lar deg tonn spille Tetris i en hvilken som helst ANTALL dimensjon.
Spill Tetris i 3D, 4D, 5D, eller mer.
HyperTetris er en mye catchier navn enn Polytope (def) Tetris, men jeg kan ikke stjele navnet.
5. "Standard Tetris" spesifikasjon
5.1 Innledning
Definisjonen av "Standard Tetris" er en idealized modell av de viktigste egenskaper og atferd i den første IBM-PC gjennomføring av Tetris spill (circa 1986-1988).
The idealized modellen er basert på inferring den åpenbare intensjoner av utviklerne av de første IBM-PC gjennomføring av Tetris spill.
For eksempel synes det rimelig å antyde at utviklerne av de første IBM-PC gjennomføring av Tetris spill ment for å velge den formen for hver nye fallende stykke "tilfeldig," og at bruk av Borland C gjennomføring av rand() funksjonen var bare en praktisk tilnærming til intensjonen.
Definisjonen av "Standard Tetris" presiserer at formen på hver nye fallende brikker er å bli valgt "tilfeldig."
Denne ideelle situasjonen kan ikke oppnås ved eventuell gjennomføring, men implementeringer kan tilnærmet den ideelle situasjonen.
Selv om ikke perfekt gjennomføring kan implementere definisjonen av "Standard Tetris," idealer "Standard Tetris" innebære objektive kjennetegn, og implementeringer kan sammenlignes i henhold til deres relative nærhet til idealer "Standard Tetris."
Dette avsnittet beskriver et sett av elementer, atferd og regler, som samlet definerer "Standard Tetris."
5.2 Standard Tetris bord
Styret er et rutenett av celler, har 10 kolonner og 20 rader, for hele 10 * 20 = 200 celler.
Standard Tetris bord (10 kolonner, 20 rader)
Hver celle kan enten være ledig (tom) eller opptatt (full).
5.3 Standard Tetris brikker
Det er sju (7) standard Tetris stykker, med følgende brev navn:
{ O, I, S, Z, L, J, T }
Brevet er inspirert av former av bitene.
De sju Standard Tetris stykker og deres "orientering"
Den prikken på (0,0) stemmer med bord stilling (6,20) når stykke vises først.
Den første kolonnen viser den første "orientering."
I det følgende ordet "orientering" er brukt for å beskrive noen av et stykke, innenfor et sett av tillatte stater, som kan resultere fra en mot rotasjon hendelsen.
Endre "orientering" fra en bestemt "retning" av en "I, S" eller "Z" brikke, krever en kombinasjon av en rotasjon og en oversettelse.
Derfor ordet "orientering" er brukt her for å bety noe mer enn rotasjon alene.
Men "legning" kan endres bare i respons til en rotasjon mot hendelsen, og sykler av forskjellige "retninger" for hver brikke approximates eller kamper, syklusen som følge av ren rotasjoner.
Den spesielle bruken av ordet "orientering" i denne sammenheng er nesten lik den betydningen av ordet "rotasjon" eller "vinkel," men ordet "orientering" er brukt i stedet for "rotasjon" for å forsøke å bringe oppmerksomhet til det faktum at noen av brikkene krever mer enn rotasjon til å produsere satt over tillatte land som følge av mot "rotasjon."
Pieces kan bare bytte orientering (eller gjennomgå en bestemt horisontale eller vertikale oversettelse) hvis de resulterende tilstand av brikke ville ikke ha noen okkupert (full) celler utenfor det området av styret og ikke ville ha noen okkupert celler som overlapper noen for øyeblikket okkupert celler av styret.
(I denne regelen, okkupert (full) celler av brikke er ikke å betrakte som en del av den "tiden okkupert celler på brettet"
I det følgende kommentarer, enhver referanse til et resultat av en mot rotasjon hendelse er gjort med antagelsen om at en slik rotasjon kan faktisk bli utført, gitt de eksisterende forhold av brikke og bord.
Den "O" (boks) brikke har bare én retning, og det vil ikke endre plassering av noen av dets okkupert (full) cellene som svar på eventuelle mot rotasjon hendelsen.
Den "I" (linje) brikke har to mulige retninger, først vises i en horisontal orientering.
Den "I" stykke veksler mellom de to retninger som svar på en rekke mot rotasjon.
Den "S" og "Z" brikker hver har to mulige retninger.
Disse brikkene hver veksle mellom to retninger som svar på en rekke mot rotasjon.
Den "L", "J", og "T" brikker hver har fire mulige retninger, og disse retninger er resultatene av enkle rotasjoner om sentrum peker på figurene.
Når en brikke vises først på bordet, den brikke har sin "store aksen" i en horisontal orientering, og brikke er på toppen av brettet.
Derfor ingen brikker er i utgangspunktet i stand til å ha sine retninger endret. Den brikken må stige ned av en rad for å ha muligheten til å ha sin legning endret.
Når et stykke har falt med en rad på bordet, alle stykke orientering kan oppnås (forutsatt at innlegget er ikke så nær side vegger eller til den gjeldende hoper brikkene).
5.4 Standard Tetris flytdiagram
Følgende er en omtrentlig flytdiagram for en standard Tetris spillet.
Omtrentlige flytdiagram for en standard Tetris Kamp
Omtrentlige flytdiagram for en standard Tetris Kamp
5.5 Standard Tetris stykke etablering
Følgende diagram viser (4 * celle 2 celle) regionen på bordet hvor alle brikkene vises når opprettet.
Region hvor brikkene vises når opprettet i Standard Tetris
Når en ny brikke som vises først på bordet, sin opprinnelse faller sammen med prikken på denne diagram, og brikken vil være fullstendig inneholdt i skyggelagt område på denne diagram.
Når et nytt spill er startet, en fullstendig fritt fall forsinkelse går, og på den første fritt-fall-iteration et stykke er spawned øverst på brettet.
Under normale spillet, når en bestemt fritt fall iteration "lander" et stykke, en fullstendig fritt fall forsinkelse går og på de neste fritt fall iteration et stykke er spawned øverst på brettet.
Når en brikke er spawned, type brikke som er valgt ved hjelp av følgende algoritme:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Siden det er en konstant p (= 1/7) mulighet til å velge en bestemt type brikke, og alle brikker av samme type er indistinguishable, sannsynlighet for å ha nøyaktig k stykker av en bestemt type etter n prøvelsene følger en Binomial fordeling:
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 velger blant de 7 (sju) brikkene tilfeldig, sannsynligheten for å få et bestemt stykke er p=(1/7).
Hvis vi gjør dette n=70 ganger, for eksempel sannsynligheten for å få nøyaktig k brikker (med k i området 0 til n) er gitt av binomial fordeling, som vist i følgende bilde.
Binomial fordeling av n=70, p=(1/7)
Dermed kan man forutse den gjennomsnittlige totale stykker av en enkelt type gitt et totalt antall tilfeldige brikker, og man kan også beregne forventet varians og standardavvik (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 konverterer en tilfeldig verdi til et stykke indeksen, kan vi tolke det som følger:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[Pre-kommersiell MS-DOS versjon av Tetris brukte tilfeldige tall funksjon som tilbys av Borland Pascal kompilatoren.
Denne funksjonen brukes en 32-biters staten variabel.
Derfor er sekvens av tilfeldige tall var begrenset til 2^32 distinkte verdier.
Derfor, i prinsippet, en spiller kan oppdage, etter slippe kanskje 10 stykker, nøyaktig sted i settet av 2^32 tall som tilsvarer den nåværende tilstand av spillet.
Hvis Tetris simuleringer er utført med fast sekvens av 2^32 stykker, deretter optimale beslutninger kan bli funnet på hvert sted i sekvensen.
(Det synes å være tilstrekkelige muligheter til å bli brettet til et helt tomt brett tilstand, som tillater oss å få synkronisert med precomputed optimal løsning banen.)
Risikoen for å bruke en enkel tilfeldig tall-generator i en simulering ment å finne en optimal løsning på et problem er at løsningen vil være optimal bare for den bestemte banen gjennom problemet plass valgt av den enkle tilfeldige nummer generator. ]
5.6 Standard Tetris kontroller
I løpet av spillet, er følgende innganger er tilgjengelige:
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 innganger trer i kraft på den økende-kanten av den positive innspill (på tastetrykk, i motsetning til for utgivelsen).
Når et tastetrykk oppstår, dette regnes som en forespørsel.
Holde en knapp nede utover en viss tid kan resultere i "auto-repeat" funksjon av et tastatur, genererer nye knappen presser - men denne funksjonen er ekstern i forhold til spillets motor.
Den innganger angitt ovenfor, i samsvar med den opprinnelige Tetris spill.
Roter forespørsler kan kjøres hvis det ikke er noen overlapping mellom ønsket orientering og sette cellene på det nåværende styret (med unntak av den fallende brikker), og hvis ønsket orientering har ingen fastsatt celler utenfor brettet.
Oversett forespørsler kan kjøres hvis det ikke er noen overlapping mellom ønsket oversatt konfigurasjonen og sette cellene på det nåværende styret (med unntak av den fallende brikker), og hvis den ønskede oversatt konfigurasjonen har ingen fastsatt celler utenfor brettet.
Inngang forespørsler blir behandlet med en ventetid som avhenger av bildefrekvens av spillet (eksempel: 75 Hz), og forespørsler trer i kraft (hvis gyldig) umiddelbart.
En brikke kan utelates uten linje fallende trinn forekommende.
En brikke kan bli oversatt flere ganger til venstre eller høyre, og senere droppet, uten å oppleve en offisiell linje fallende trinn.
Fordi en nylig spawned stykke ikke kan muligens bli rotert (fordi det er stakk mot den øvre kanten av brettet), spilleren må godta minst en brikke faller trinnet hvis rotasjoner er ønskelig eller nødvendig.
Effekten på resultat er ubetydelig.
5.7 Standard Tetris stykke "landing"
Hvis en brikke er bare fallende, det faller av en enkelt rad i hver brikke fallende gjennomkøyring.
Det vil være en gjennomkøyring som beveger seg fra et sted uten kontakt med horisontale flater til et sted som har kontakt med horisontale flater. Når denne gjentakelser skjer, bitene er i hvile kontakt.
Hvis en iteration begynner med en brikke i hviler kontakt med en horisontal overflate, brikke "lander," og blir en del av den statiske hoper.
5.8 Standard Tetris "linjer avsluttet"
En avsluttet rad er en rad av hoper der alle cellene er okkupert. Når en fullført rad er eliminert fra hoper, og rader over eliminert rad er flyttet ned av en rad for å eliminere gapet, dette teller som en fullført "linje."
Når en brikke lander det blir en del av hoper.
Umiddelbart etter brikke lander, hoper er kontrollert for fullført rader, og alle fullførte rader er eliminert.
Opptil fire rader kan gjennomføres samtidig.
Tabellen nedenfor gir øvre grense på linjene avsluttet samtidig ved en enkelt brikke:
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 vanskelighetsgrader, nummerert 1 (en) gjennom 10 (ti), med nivået 1 være "minst vanskelig."
Nivået indeksen er den høyeste av to verdier:
actualLevel = max( initialLevel, earnedLevel );
Den initialLevel verdien er det nivået som spilleren velger når du starter et nytt spill.
Mønsteret av nivå som en funksjon av fullført linjer er lett observeres i den pre-kommersielle MS-DOS versjon 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
Dermed blir earnedLevel Verdien er beregnet i henhold til 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 fallende iteration forsinkelse
Standard Tetris har en real-time forsinkelse mellom etterfølgende linje fritt-fall-gjentakelser som er en funksjon av den gjeldende vanskelighetsgraden.
Følgende forhold mellom nivået indeksen og fallende iteration forsinkelsen er basert på gjentatte stoppeklokken målinger på alle nivåer i den pre-kommersielle MS-DOS versjon 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
Derfor har vi etablere følgende formel for gjennomkøyring forsinkelse verdien som en funksjon av det faktiske nivået indeksen:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Hvis brettet er tomt, og det er ingen brukerundersøkelser, en spawned stykke på faktiske nivået 1 lander på ca 10 sekunder, og en spawned stykke på faktiske nivået 10 lander på ca 1 sekund.
5.11 Standard Tetris "scorer"
Standard Tetris bare tildeler poeng etter loven av landing et stykke.
Det er ingen poeng tildeles for handle med å avslutte en enkelt linje, eller fullføre to, tre eller fire linjer samtidig.
[Merk: Noen varianter av Tetris tildele poeng for loven av å fullføre linjer med en eksponentielt økende bonus for et økende antall samtidig avsluttet linjer.
Dermed strategien for å maksimere scorer på slike varianter av Tetris går ut på å sette opp en mulighet til å "få en Tetris," slang for å bruke "I" form for å få fire samtidige linjer og få massevis av poeng. ]
Hvis du har et tomt brett, og du la en ikke-"I" stykke gjøre et fritt fall og land, eller du umiddelbart slippe en ikke-"I" brikke, kan du opprette følgende punkt diagram ved hjelp av pre-kommersielle MS-DOS versjon 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, ikke-"I" brikkene faller totalt 18 rader.
Dette kontoer til det punktet forskjellen mellom fritt-fall-og instant-slipp tilfeller.
Ved å eksperimentere med mellomliggende tilfeller er det lett å slutte seg til følgende punkt formel:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Merk at denne formelen har ingenting å gjøre med avstanden en brikke faller!
Det er ikke en funksjon av det faktiske nivået, og et gebyr for antall gjentakelser et stykke er tillatt å falle fritt.
Dette straffer en bruker til trenger tid til å tenke.
Vær også oppmerksom på at en brikke kan ikke i utgangspunktet være roteres når den første spawns, en spiller blir straffet med minst ett fritt-fall-iteration hvis rotasjoner er nødvendig for å plassere en brikke i det hoper.
Dette sannsynligvis aldri påvirker menneskelige spillere, med mindre de på en eller annen måte: gjenkjenne stykke, trykker oversettelse nøkler "(til venstre" eller "høyre)," trykker du "rotere" tasten en eller flere ganger, og trykker på "drop-tasten," alle innen mindre enn 0.5 sekunder på nivå 1, eller mindre enn 0.05 sekunder på nivå 10.
6. Standard Tetris strategi
6.1 Innledning
En strategi for å spille et spill er avhengig av reglene i spillet.
En strategi avhenger av hvilke parametere som skal være optimalisert.
I Standard Tetris, en survives ved å fylle rader, får poeng for landing stykker, og score mest mulig poeng for hver brikke ved gjennomføring av en slipp før en eller flere fritt-fall-gjentakelser svette.
En A.I. kan optimalisere tildelt poeng fo
