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 - och A.I. måste vidta åtgärder för att fylla rader i en takt som genomsnitt minst 1 rad per 2,5 bitar. (Varje pjäs har 4 celler, och varje rad har 10 celler.)
Visst kan man skjuta fylla rader av ackumulera bitar och bygga en stor lugg, men det finns bara 200 celler i hela linjen, som i princip bara kan hålla 50 stycken, så alla spelare (som en A.I.) måste fylla rader som en grundläggande prioritering.
I Standard Tetris, turneringsstatus omfattar den nuvarande styrelsen ockupationen och den nuvarande hänförs bit (typ, position och orientering). Spelet staten får alternativt omfatta "Nästa Piece".
6.2 En alternerande sekvens av "S" och "Z" bitar
Heidi Burgiel, Ph.D., av Department of Mathematics, Statistics and Computer Science vid University of Illinois at Chicago, har visat att en alternerande serie "S" och "Z" bitar kommer att tvinga en standard (10-kolonn, 20-raden) Tetris spelet till slut inom en förutsägbar antal drag.
Citat ur artikeln: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Medverkande tryckt artikel: Mathematical Gazette, juli 1997, "How to Lose at Tetris"
Heidi Burgiel erbjuder en Java applet som körs i en webbläsare som innehåller en förändrad Tetris-klon som äggläggningar omväxlande "S" och "Z" bitar.
[Den "Standard Tetris" programvara som är associerade med dokumentet som du läser har också ett läge som äggläggningar omväxlande "S" och "Z" bitar. ]
Heidi Burgiel hävdade att ett spel som involverar omväxlande "S" och "Z" bitar (för en vanlig Tetris styrelse 10 kolumner och 20 rader) måste sluta innan färre än 70000 bitar har fallit.
The Standard Tetris som följer med detta dokument gör det möjligt för en person att spela spel med omväxlande "S" och "Z" bitar, och förändra styrelsen bredd.
Det är lätt att se att styrelserna vars bredder är heltal multiplar av fyra kolumner (exempel: 4 kolumner, 8 kolumner, 12 kolumner, etc) kan spelas alltid när styck växlar mellan "S" och "Z", med lugg stiger något högre än 4 rader. Jag nämner detta för att klargöra att det begränsad överlevnads beskrivs i forskningen dokumentet nämns ovan är specifikt för det rör sig om en vanlig Tetris styrelse (med 10 kolumner och 20 rader).
6.3 Olösliga pjäs sekvenser i allmänhet
Det finns hela grupper av patologiska sekvenser som inte kan överleva.
Det skulle vara intressant att beräkna den totala sannolikheten för att stöta på ett spel-avslutande fas, för det skulle sätta en övre gräns på resultatet för varje strategi, även med fullständig kunskap om alla framtida bitar i en viss punkt i ett spel.
6.4 Totalt möjligt board konfigurationer
Med tanke på att styrelsen har 10 * 20 = 200 celler, och med tanke på att varje cell kan endast i ett av två länder (tom eller ockuperad), det totala antalet styrelse-konfigurationer måste vara mindre än eller lika med: (2 ^ 200).
Eftersom varje pjäs tillägger 4 celler till en styrelse, och varje rad slutförande eliminerar 10 celler från styrelsen, antalet ockuperade celler i styrelsen kommer alltid att vara ännu. Exempelvis (3*4 - 1*10) = 2, (1*4 - 0*10) = 4, (4*4 - 1*10) = 6, (2*4 - 0*10) = 8, (5*4 - 1*10) = 10, etc. Därför har endast hälften av (2 ^ 200) board konfigurationer kan nås genom att spela spelet.
Det totala antalet styrelse-konfigurationer är ca: (2 ^ 199) = 8.03469... * 10^59.
Men vi bör undanta från vår totala någon konfiguration som innehåller fyllt rader, eftersom fyllt rader skall undanröjas före utgången av varje färdig flytta. Varje konfiguration med en eller flera fyllda rader kommer att kollapsa till en annan konfiguration som inte innehåller några fyllda rader.
Dessutom bör vi utesluta någon konfiguration som innehåller en icke-tomma raden ovanför en eller flera tomma rader, eftersom en icke-tomma raden ovanför en tom rad som alltid kommer att falla, och alla faller slutar före utgången av varje drag.
Varje rad kan i 2^10 = 1024 stater, varav en är "tomma", varav en är "full" och (1024 - 2) = 1022 som är delvis ockuperat. Vi utesluter "hela" fall av övervägande.
Om den nedersta raden är tom, sedan alla rader ovanför den nedersta raden måste också vara tomma.
Om den nedersta raden är delvis ockuperat, och sedan den andra raden kan tom eller delvis ockuperat.
Fortsatt denna analys kan vi beräkna ett antal styrelse-konfigurationer som tar in på kontot uteslutning av fulla rader och de restriktioner för tomma rader: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), vilket är ungefär ((1022 ^ 19) * (1023)).
Således finner vi en mer exakt uppskattning av det totala antalet stabil styrelse konfigurationer: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199), dvs ca 3,74% lägre än den (2 ^ 199) uppskattning.
Men det faktiska antalet stabila, lättillgängliga styrelse står sannolikt är väsentligt lägre beror på att de övre mest rader bara kan fyllas på ett par ställen. Som den universella mest rader fylla, en nyligen genererade pjäs kan inte flyttas eller roteras mycket. Detta begränsar antalet vägar början mest rader kan fyllas.
6.5 I princip är det bästa flytta finns för varje styrelse och verk-konfiguration
Eftersom vi kan få något av sju möjliga stycken för varje given board staten, det totala antalet spel stater är ungefär 7 * (2 ^ 199) = 5.624... * 10^60.
Eftersom vi kan i princip göra en djup sökning av alla möjliga terminer för alla möjliga drag för ett visst spel stat, vi kan ha en enda "bästa" flytta samband med varje spel.
Vi förutsätter att vi inte har tillgång till någon annan information än den nuvarande styrelsen och aktuell pjäs, så "bästa" betyder "väg" som erbjuder störst chans att tillgodose våra långsiktiga mål för överlevnad ".
En övergång är bara en översättning (upp till 10 optioner) och en rotation (upp till 4 alternativ), kan vi lätt koda den bästa flytta på en enda byte.
Så i princip skulle vi kunna bilda en tabell med 10^61 poster (bytes) som berättade för oss den bästa flytta någon styrelse staten och aktuell pjäs.
Naturligtvis är det opraktiskt, precis som anges alla "Go" boards eller "Chess" boards är opraktiskt. Men poängen är att det finns en verklig lösning, och det finns en bästa väg för en given konfiguration. Det kan vara lika bra drag för en viss konfiguration, men vi kan godtyckligt välja en enda röra i det fallet.
Många spel-playing algoritmer få tabeller att uttömmande räkna upp alla spel statens möjligheter inom begränsade sammanhang, som "öppning (första) flyttar" eller "end-game (slutlig) flyttar" i schack. Kanske uttömmande uppräkning av Tetris lugg ytor (cirka (20 ^ 10) stater) är genomförbart. Det är en intressant idé.
Uttömmande förteckning över alla stater i botten två rader, multiplicerat med de sju möjliga bitar, och lagra det bästa flytta på en enda byte, skulle vara ganska lätt, det krävs bara 7 MB minne. Kanske optimera prestanda för dessa sju miljoner fall skulle ge rådata för både analys och utveckling av enkla modeller för data, sådana modeller kunde betraktas som en del av den övergripande ideal Tetris-playing strategi.
Observera att verkställande bästa går fortfarande inte skydda oss mot eventuella patologiska vilt-avslutande pjäs sekvenser. Det är bara att vi alltid kommer att utföra åtgärder som ger oss den maximala potential för framtida överlevnad med tanke på att alla framtida bitar är helt slumpmässiga (och okända vid den tidpunkt då vi ska besluta hur man flyttar en enda nuvarande kända pjäs).
6.6 Realtidsprestanda
Ett tvång som en del strategi algoritmer är behovet av realtidsinformation prestanda - vilket innebär att algoritmen måste fatta ett beslut inom en viss tid.
När en mänsklig spelar Tetris, pjäserna stannar inte faller för att ge spelaren en chans att tänka. Det är en del av den utmaning som Tetris. Alltså, en A.I. system som är tänkt att simulera rollen av en mänsklig spelare måste också fatta beslut i en takt som dikteras av Tetris spelet.
6.7 Row och pjäs totalbeloppen
Observera att på lång sikt har antalet minskat bitar ligger mycket nära 2.5 gånger antalet genomförda rader - eftersom varje rad har 10 celler, och varje bit är 4 celler, och vi måste fylla en rad, i genomsnitt, gång var (10/4) = 2.5 bitar bort.
Så vi kan använda "färdig rader" och "bort bitar" nästan omväxlande med lämpliga proportionalitet konstant. Det största felet är när styrelsen är helt fyllda med undantag för en enda lucka i varje rad (((10*20)-20)/4) = 45 bitar fallit men en brist i förutspådde (45/2.5) = 18 färdig rader.
6.8 Aktuellt-bit (och kartong) strategi
Om vi bara tillåter A.I. att få kunskap om nuvarande styrelse och den aktuella pjäsen och vi bara betrakta ett resultat av att flytta den nuvarande pjäs särskilt sätt, då detta kan kallas en "hel" analys.
Här är en grov skiss av hur en hel analys kan besluta om en övergång i Tetris:
Aktuellt-bit analys av ett Tetris spel staten
I grunden vi provar alla möjliga drag och plocka ut den röra som ger det bästa resultatet.
Den svåra delen är betyg varje träff.
Vi måste bedöma ett hypotetiskt spel staten enligt hur väl en sådan stat stödjer våra kortsiktiga och långsiktiga mål.
Vårt långsiktiga mål är överlevnad. Överlevnad beror på att förebygga luggen från över linjen. Vi kan minska högen höjd genom att bilda kompletta rader som sedan elimineras ur högen.
Utgör en komplett rad, vi måste passa delar av bitar i varje kolumn i samma rad. Därför kräver vi att alla delar av en rad bör utsättas för de fallande bitar för att vi så småningom fylla i hela raden.
Om av någon anledning vi täcka upp tomma delar av en rad av bitar på någon högre raden, då vi nu inte kan fylla i de tomma delarna av raden. Det enda sättet (om man utgår ingen skjutdörr) för att komma åt dem "begravdes hål" är att undanröja de rader ovan att ha delar som fungerar som hinder.
Följande faktorer är bland dem som vi kan använda för att bedöma ett visst board state:
Overall pile height
Ju högre stapel, värre vår situation verkar vara, eftersom vi är närmare över linjen.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
De tuffare högen, desto troligare är det att det kommer att bli svårt att fylla i alla de inbäddade komplexa konturer när de blir utsatta för ytan.
Number of buried empty cells
Ju fler hål vi har begravts, värre vår situation, för vi måste avslöja begravdes hål innan vi kan slutföra motsvarande rader.
Du kan tänka sig andra faktorer som generellt sats en hypotetisk ombord på hur väl sin lugg kan rymma alla de möjliga framtida bitar, och hur bra ser det för alla dessa möjliga bitar.
Nästa fråga är hur man skall bedöma den relativa betydelsen av dessa faktorer.
En allmän strategi är följande. Tilldela en uppsättning "vikter" (relativ betydelse) till dessa faktorer och sedan simulera många spel och spela på resultatet av dessa spel (slutlig värdering etc). Sedan, ge den en ny uppsättning vikter och simulera en ny uppsättning spel. Baserat på huruvida den nya uppsättning spel hade bättre resultat än föregående uppsättning spel, vet vi om den nya uppsättning vikter var bättre än föregående uppsättning vikter.
I mitt eget experiment försökte jag systematisk sökning och slumpmässig som söker efter bra vikt kombinationer, men jag har inte märker några stora trender som jag skulle kunna fortsätta. Men jag såg många förvånansvärt smidigt gupp. Jag tyckte det var intressant att den genomsnittliga resultat kunde bilda en mjuk kurva när en parameter var långsamt varierade med andra parametrar som hölls vid något värde kombination.
Det bästa realtid, ett stycke Tetris algoritmen i världen, skapad av Pierre Dellacherie (Frankrike) i 2003, beror mycket av sin framgång med sin uppsättning mätningar (eller statistik). Hitta vikter är nödvändigt när optimera en strategi, men det är också kritiska till att börja med de typer av mätningar som visar relevanta egenskaper av staten.
Pierre Dellacherie's uppfinning av nya sätt att karakterisera respektive styrelse gör hans algoritm alldeles utmärkt; styrelsen characterizations fånga den viktiga strategiska dimensioner i styrelsen.
Man skulle kunna utveckla en mycket annorlunda uppsättning karakterisering dimensioner som fungerade lika bra, jag är övertygad om att det är möjligt att spänna den relevanta board state space på många olika sätt som kan användas för att ange en strategi funktion. Nyckeln är att hitta egenskaper som projektet staten rymden ner till ett litet antal dimensioner som kan användas för att utveckla en enkel betyg funktion (exempel: den linjära vägt kombinationer av egenskaper som används av Pierre's algoritm).
I ett stycke algoritm som används av "bot" i "xtris" programvara (1996) skriven av Roger Espel Llima använder vikter bestäms av en storskalig undersökning av möjliga vikt kombinationer med "genetiska algoritmer". Simulated annealing är en annan möjlig metod för att utforska den flerdimensionella rymd av vikt kombinationer.
Det verkar som, baserade på olika iakttagelser, flerdimensionell funktion genomsnittliga Tetris prestanda som en funktion av vikter, t.ex.: F(w1,w2,w3,...), är "grov" (massor av lokala minima och maxima), vilket innebär att en enkel flerdimensionell "hill climbing" kanske inte skulle fungera.
6.9 Strategi när nuvarande pjäs, nästa pjäs, och kartong är kända
Om en strategi algoritm ges den aktuella pjäsen, nästa pjäs, och kartong, så kan fatta beslut om att utnyttja den kombination av bitar.
Kunskaper i nästa pjäs kan öka framgången för ett Tetris spelar algoritm som flera tiopotenser. Det är lätt att förstå hur veta nästa pjäs gör en stor skillnad i strategin.
Man kan göra "Crazy" drag, som täcker stora hål, etc, eftersom de vet redan att nästa pjäs kan användas för att "korrigera" situationen. Om du inte har kunskap om nästa pjäs, du är ständigt försöker spela odds, försöker hålla möjligheterna öppna vid nästa pjäs är inte idealisk.
Följande skiss visar hur alla de möjliga drag i det nuvarande pjäs anses, och för varje sådant flyttar vi överväga alla möjliga drag innebär nästa pjäs.
Strategin omfattar nuvarande stycke och nästa pjäs
The Standard Tetris Programvaran använder denna strategi när "Nästa Piece" är aktiverad av användaren och finns på skärmen, och när en tvådelade A.I. är aktiverat (t.ex. en skriven av mig, Colin Fahey). Om "Nästa Piece" är inte synliga på skärmen, min tvådelade faller tillbaka till en hel A.I..
Mitt i ett stycke A.I. är hemskt när man jämför med andra AIs i Standard Tetris programvara, så detta visar du välgörande mer information (exempel: nästa stycke) kan vara att en A.I. systemet, det räcker med att förbättra resultatet för min egen mediokra tvådelade A.I. av flera tiopotenser - lätt att överträffa resultatet för det bästa i ett stycke A.I. i världen.
(Men att omvandla de bästa i ett stycke A.I. i världen att överväga två bitar enkelt skulle förbättra den genom att flera gånger också! Veta nästa pjäs är enorm!)
Min första test spelet med min tvådelade A.I. varade ungefär 182 timmar (7,6 dagar) på en 800 MHz PC, slutföra 7216290 rader. Jag har inte testat algoritmen på en snabbare dator.
När du sparar staten en Tetris spelet (Shift-W) till en textfil kan du sedan kopiera och klistra in den lista med siffror, från avsnittet "heightHistogram", till ett Excel-ark.
Varje bin i histogrammet visar antalet genomförda flyttar det slutade med en viss stapel höjd (efter kompletta rader skall elimineras). Som ni förstår, gör en rörelse som helt eliminerar en stapel är sällsynt, så det totala antalet drag som slutar med en hög höjd på noll är relativt låg.
Under tiden kan du räkna med att högen höjd allmänhet varierar runt en del i genomsnitt, så bins motsvarar dessa rader kommer att dominera histogrammet. Slutligen, lådor för de universella mest rader (där vi riskerar att över linjen) har mycket låga belopp.
Under många timmar, med A.I. spela ett enda spel som använder den strategi som innefattar kunskap om "Nästa Piece" Jag tog stickprover av spelet stat, kopiering högen höjd histogram till ett kalkylblad som visas nedan:
Pile höjd histogram inspelade på olika punkter i ett typiskt spel (med nuvarande och nästa-pjäs strategi)
Du kan skala varje histogram av det totala antalet bitar (totala antalet genomförda åtgärder) för att få följande uppgifter:
Scaled histogram, och en teori
Det märkliga är att dessa skalas histogram ser identiska trots de olika tiopotenser av antalet bitar (avslutad flyttar).
Bara genom att titta på de siffror jag gjorde hypotesen att den svans av kurvan är en exponentiell förruttnelse. Genom Trial and error jag kom med grov teorin att svansen beskrevs av:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Följande diagram visar skalas histogram över hela rader.
Diagram av förminskad histogram
Observera att kurvan för 50000 bitar, och kurvan för 2000000 bitar, och kurvan i svansen teori är nästan omöjlig att skilja på denna skala.
Nedan följer en närmare titt på toppen av kurvan.
Nedre delen av höjd histogram
Följande är en stor-förstorad bild av den extrema svans slutet av uppmätta och teoretiska histogram kurvor.
Förstorad bild av extrema svans slutet av förminskad histogram
Som du kanske tror, är det mycket ovanligt att högen för att nå dessa höjder i och med långa experiment - men även med våra begränsade bevis på detta extrema regionen, i teorin fortfarande är godtagbar.
I full chart teorin verkar överlappa svans av distribution "exakt", medan det i den förstorade chart av svansen i svansen, vi ser uppenbara fel. Men jag hävdar att detta beror på otillräckliga uppgifter i dessa extrema lugg höjder. Om jag ökade spelet styrelsen att, säg, en höjd av 25 rader istället för 20 rader, så att spelen inte abrupt avsluta tycker jag att den teori jag presenterat ovan skulle sammanfaller helt med den trenden.
Min känsla är att detta histogram är en direkt sammanlagda resultatet av ett Tetris A.I. och reglerna för Tetris. Så, detta samma fördelning kommer att noteras för några slumpmässigt långsiktiga omgång Tetris använda min särskilda A.I. strategi för att leka med "Nästa Piece" kunskap.
Dessutom tror jag att den här typen av histogram kan användas för att jämföra AIs att använda samma information samtidigt som du spelar. Alltså, du behöver inte spela komplett spel (som kan pågå i dagar eller år) att jämföra de långsiktiga prestanda för olika strategi algoritmer.
Till exempel, trots att det är så enkelt att min modell, jag tror att det kan användas för att förutse den genomsnittliga spelet längd! Vi har helt enkelt räkna ut hur många bitar gör "row 21" högen höjd ett betydande antal, t.ex. en räkna med en.
Den relativa frekvensen för rad 21, enligt min enkla teori, är:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Du måste multiplicera detta antal till (5.3 * 10^(7)), ungefär 50 miljoner, för att få ett värde på ett.
Alltså, jag grovt förutsäga att min nuvarande "Nästa Piece" är bara bra för på order av cirka 10 miljoner ifyllda rader. En anledning jag göra detta försiktig uppskattning är att även 18 rader kan vara dödliga för min A.I. eftersom jag inte låta min A.I. att överväga bitar tills de har sjunkit med minst en rad! (Detta är så att jag inte behöver oroa sig för att inte kunna rotera styck.)
Jag är imponerad av att spela bara 50000 stycken (och eventuellt betydligt färre enheter) kan ge er en mycket god uppskattning av den långsiktiga höjd histogram, och därmed en god uppskattning av storleksordningen av avslutade rader innan spelet slutar. Detta synsätt är oerhört värdefullt för att snabbt utvärdera subtila förändringar i en A.I. som redan gör mycket bra.
6.10 Styrelsens utvärdering statistik imitera spekulativa look-ahead
Om en algoritm, som jag presenterade med detta projekt, helt enkelt försöker alla pjäs riktlinjer och översättningar för att släppa, och skattesatser varje följd board konfiguration enligt vissa mått på meriter, algoritm är i huvudsak imitera "look-ahead".
När en anställd variabler som till exempel "högen höjd", "begravdes hål", "yta råhet" eller "bra djup", en som verkligen använder en förenklad form av "se framåt". Dessa allmänna characterizations i styrelsen ge en fingervisning om den långsiktiga lönsamheten i styrelsen.
Det idealiska schemat, eftersom en oändlig mängd datorkraft, skulle vara att utvärdera en styrelse konfiguration med tanke på alla möjliga bit-sekvenser som kan följa.
Även om du måste överväga alla 7 stycken som är lika sannolik på varje nivå i look-ahead, du behöver för att optimera den faktiska översättningar (upp till 10) och riktlinjer (upp till 4) för varje bit i alla möjliga sekvens! Det är upp till (7*10*4) = 280 grenar på varje nivå av styrelsens utvärdering! Så, det är upp till ((280)^(LookAheadLevels)) board konfigurationer att överväga.
Eftersom vi måste avsluta analysen efter ett begränsat antal nivåer, vi behöver en viss icke-look-ahead metod för att utvärdera styrelsens stat - ett sätt att ge värden till leaf noder i vår sökning träd. Så, för dessa blad noder är vi tillbaka till att använda en formel som förkroppsligar allmänna prediktorer för framtida lönsamhet i styrelsen!
Denna typ av spekulation kan man försökt med One-Piece och tvådelade algoritmer i stället för det förenklade styrelsens utvärdering statistik. Antag att alla efterföljande bitar är lika sannolika och sammanfatta vilken kapacitet som en styrelse för att ta bitar av alla slag på bästa möjliga sätt. Detta kan utföras med ett, två, eller valfritt antal spekulativa flytta djup - med alla bitar är lika sannolika (p=1/7).
Terminalen noder i detta träd kan det fortfarande krävs det vägda mått för att bedöma, men det spekulativa skikt mer exakt fånga essensen av vad vi vill göra: Ta reda på hur väl en viss styrelse kan godta alla möjliga pjäser, inklusive positiva faktorer såsom att fylla raderna och negativa faktorer såsom ökande totala högen höjd, etc.
7. Tetris A.I. system demonstration
7.1 System översikt
Det här diagrammet nedan visar min experimental set-up.
Övergripande system för demonstration
7.2 Utrustning
Här är en kort lista över den utrustning som används i denna 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)
Självklart kan du använda liknande utrustning för att uppnå samma resultat. Mer information om den utrustning som beskrivs i motsvarande avsnitt i denna artikel.
Här följer korta beskrivningar av de persondatorer som används i denna demonstration:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Denna demonstration lätt skulle kunna reproduceras med andra operativsystem, såsom Linux. Det är viktigare att ha en CPU hastighet på order av 800 MHz eller snabbare för datorn att köra A.I. programvara, eftersom den här datorn kommer att göra realtid bearbetning av video.
7.3 Video capture hardware
Jag använde en gemensam USB videokamera som en video capture enhet för min A.I. systemet. Specifically, jag använde Creative "WebCam Pro", en USB videokamera med 640 * 480 resolution.
Creative(TM) USB videokamera beskrivning
USB videokamera (i vinkel)
USB videokamera (framsida)
USB videokamera (kartong med CCD)
USB videokamera (främst flis)
OV511 huvudsakliga block (notera: USB videokamera är OV511+)
7.4 OV511 datablad
ov511ds.pdf
OV511 varuinformationblad
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "plus") funktionen skillnader
ov511plus_101.pdf
OV511+ Feature Skillnader
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Videotillfångatagandemjukvara
Microsoft har en mycket gammal API heter "Video for Windows" (VFW) att jag med framgång använts för detta projekt. (Du länkar till "vfw32.lib" i din C++ projektet, eller göra en DllImport "vfw32.dll" i din C# koden.) Exempel på att använda VFW API är allmänt tillgängliga.
Ett alternativ är att använda Microsoft's "DirectShow" API att göra video capture.
Eftersom VFW tog bara ett dussin rader kod att använda, och utfördes acceptabelt på min 800 MHz maskin jag inte brydde sig om att utforska alternativa APIs. Men DirectShow är en mer nutida API för Windows videoinläsning, och potentiellt ger en mycket högre frekvenser för samma hårdvara.
Titta på "CPF.StandardTetris.STVideoCapture" källkodsfiler i Standard Tetris programvara för att se hur lätt det är att få video capture in på ditt eget projekt.
7.7 Computer gränssnitt till reläer (via RS232)
Att ha en dator "trycka på tangenterna" på tangentbordet på en annan dator jag använt en "relay board" som kontrolleras av text kommandon som skickas från en seriell kommunikationsport (exempel: "COM1") via en RS-232 kabel. Jag använde varje relä för att ansluta de två trådar av ett specifikt tangentbord för att simulera en nyckel pressen.
Det krävs öppna tangentbordet och göra anslutningar. Det finns många enklare metoder för att simulera viktiga att trycka på en dator, men jag ville göra något som verkade så nära som möjligt till en person verkligen skriva på tangentbordet.
En mycket mångsidig och välarbetat relay board är ADR2200 gjorts av 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 titta på "CPF.StandardTetris.STRS232" källkodsfiler att se hur lätt det är att skicka bytes via en serieport, som sedan kan användas för att styra enheter såsom ADR2200 styrelse som visas ovan.
8. Standard Tetris programvara
8.1 Ladda ned programvara
Gå till början av denna artikel att finna en länk för att ladda ner källkoden (C# och C++ versioner) och byggt programvara (*.exe).
8.2 Sammanfattning av funktioner
Software funktioner:
Instruktion skärmar och krediter
Monokrom läge
Shadow läge
Tips läge
Junk rader
Rate kontroll
Nästa pjäs
Styrelsens storlek
S/Z bitar
Kalibrering läge
Video capture och erkännande
Debugging konsolen
Spara spel
Load spel
8.3 Startlista utseende
Utseende När programvaran startat:
Utseende när programvaran startas
8.4 Monokrom läge
Som standard linjen visas i färg:
Som standard linjen visas i färg.
Färgläget som kan ändras till svartvitt (Shift + K):
Färgläget som kan ändras till svartvitt.
8.5 Shadow läge
Shadow anger när en pjäs kommer att landa. Detta är till stor hjälp för mycket stora nämnder, eftersom det är svårt att bedöma när en pjäs kommer att landa.
Shadow anger när en pjäs kommer att landa.
8.6 Tips läge
Tips-läge kan du se var de nu utvalda AI skulle gå med tanke på den nuvarande situationen. (Shift + H)
Tips läge visar vart närvarande utvalda AI skulle flytta.
8.7 Junk rader
Sätt "skräp" rader längst ner i högen, en efter en, manuellt. (Shift + J)
Sätt "skräp" rader längst ner i högen.
8.8 Rate kontroll
Den '+' (plus) och '-' (minus) tangenter kontrollera hastigheten på spelet.
Som standard spelet körs på en vanlig hastighet, enligt reglerna i Standard Tetris (hastighet grundas på nivå).
Här är en tabell med de betydelser av hastighet bias:
-3,-4,...: långsamhet proportion till bias
-2: långsammare än nivå 1
-1: normal, men begränsad till nivå 6 (0,2 sek) speed;
0: normal; Standard Tetris hastighetsbestämmelser;
+1: något snabbare än nivå 9 (0.05 sec förseningar);
+2: avgränsas av rendering sats (exempel: 75 Hz);
+3,+4,...: flera iterationer per utsmält frame;
Jag gillar att köra A.I. vid en inställning av "+2" (träff '+' gånger om partiskhet börjar på noll).
Speed bias ändrar hastigheten på spelet.
8.9 Visa nästa pjäs
Hit "N" för att växla "Nästa Piece" display. Den A.I. kommer att använda "Nästa Piece" information endast om "Nästa Piece" visas på skärmen.
Du kan vara säker på att AI är inte att använda "Nästa Piece" information när du inte kan se "Nästa Piece" på skärmen.
Visa nästa pjäs
8.10 Styrelsens storlek
Tryck Ctrl + (vänster, höger, ner, upp) kan man justera styrelsens storlek för godtyckliga storlekar från 4 * 4 upp till 200 * 400.
Styrelsens storlek: 4 * 8
Styrelsens storlek: 20 * 40
Styrelsens storlek: 40 * 80
Styrelsens storlek: 20 * 5
Styrelsens storlek: 4 * 100
8.11 S/Z bitar bara
Undersöka intressanta alternerande S/Z mönster.
Detta mönster kan inte lösas för en 10 * 20 ombord (bredd * höjd).
Men skivor som har en bredd som är multiplar av 4 är trivially visat att tillåta oändlig överlevnad.
Den AIs överleva på obestämd tid i dessa fall, även om de inte var speciellt anpassat för att hantera detta patologiska situation.
S/Z bitar bara
8.12 Video kalibrering läge
Hit "C" för att ange "Calibration Mode". När i kalibrering läge kan du trycker på sifferknapparna: {1,2,3,4,5,6,7} att välja en pjäs {O,I,S,Z,L,J,T} överst på playing board.
Detta är användbart som en referens bild för video capture på en andra Standard Tetris programvara.
Om du trycker på 0 (noll) tangenten, kommer att göra linjen tom.
Du kan låtsas att leka bitar genom att välja en bit (1..7), och sedan välja en tom (0), medan en annan dator gör videoinläsning klockor för bitar.
Du kan köra A.I. på den andra datorn och se hur det behandlar din manuellt patologiska Tetris scenarier!
Calibration Mode är enda gången du kan manipulera videoinläsning bildbehandling mallen (4 * 2 galler). Du kan använda musen för att dra rektangeln, men då kan du använda piltangenterna ( "up", "ner", "vänster", "rätt") för att få fina kontroll av gränser - med hjälp av Shift tangenten för att välja motsatt gränser rektangeln (exempel: "Shift-vänster" combo är annorlunda än "vänster").
Video kalibrering läge
8.13 Video capture och erkännande
Tryck "V" Växlar videoinläsning läge. Om rätt kalibrerad (se "video kalibrering" i ett tidigare avsnitt), bitar av en avlägsen videoskärm kommer att fångas upp av videokamera och klassificerats - och bitarna blir givit i den lokala spel för A.I. att fundera och reagera .
Den A.I. produktionen måste sedan överföras (via RS-232 gränssnittet i demonstrationen beskrivs i denna artikel) till avlägsna spelet input (t.ex. tangentbord) för A.I. att framgångsrikt spela fjärrkontrollen spelet.
Om när som helst detta kretslopp är störd (exempel: video capture felaktighet eller utsignal fel), sedan A.I. kommer att utveckla ett falskt intryck av status för de avlägsna spelet, och A.I. kommer att göra olämpliga beslut som snabbt förlorar spelet .
(Observera: Detta problem kan lösas med ett mindre belopp insats: A.I. systemet behöver bara undersöka hela avlägsna Tetris skärmen för en pågående "verkligheten" över hela linjen, och A.I. system skall upprättas för vissa output kommandon till inte på något sätt.)
Video capture och erkännande
9. Original Tetris AI experiment (2003)
Följande visar den första arbetsdagen version av Tetris A.I. systemet under 2003.
Videokamera med dator # 1 kör vanlig Tetris spelet
Dator # 2 körs Standard Tetris programvara i A.I. läge
Vänster: Drawing nätet för att kalibrera videobilden erkännande;
Höger: Tetris pjäs erkännande fall.
Frame från video av Tetris A.I. experiment år 2003
10. Best hel Tetris-playing algoritm i världen
10.1 Pierre Dellacherie (2003, Frankrike)
Pierre Dellacherie (2003, Frankrike), utvecklare av det bästa i ett stycke Tetris-playing algoritm i världen
Det bästa i ett stycke, realtid Tetris algoritm till min kännedom skapades av Pierre Dellacherie av Frankrike.
Hans otroliga algoritm ibland fyller mer än 2 miljoner rader!
Den genomsnittliga resultat är på order av 650000 rader.
Algoritmen tar väldigt lite minne och kör i hög hastighet (ca 160 rader per sekund på min 800 MHz dator).
Fullgörande av Pierre Dellacherie's algoritm:
Min nuvarande modell för utförandet av Tetris AIS att för varje given piece det finns en konstant sannolikhet att spelet kommer att upphöra, p.
Alltså, sannolikheten att en del kommer inte avsluta spelet q=(1-p).
Sannolikheten för spelet avslutande efter k flyttar helt enkelt är en produkt av sannolikheten att överleva (k-1) drag, nämligen q^(k-1), och sannolikheten för den avslutande om nästa steg, nämligen p.
Detta motsvarar 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 )
För små p, ln(q) är ungefär (-p), och vi har följande:
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 förväntar oss att den andel av det totala antalet spelade matcher att med ett antal ifyllda rader i intervallet [k1, k2] vara:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Efter att ha fyllt 36 spel på min dator, under en period på två dagar, jag hittade en i genomsnitt 674827 färdig rader.
Enligt den allmänna teorin ovan, skulle jag förvänta följande relativa andel av spel till slut i följande fyllas rad områden:
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
Här är ett diagram som jämför Exponential Distribution teori med den observerade fördelningen av spel.
Fullgörande av Pierre's algoritm över 36 fyllas spel
Även om det finns väldigt få spel i denna uppsättning uppgifter framgår det att modellen är ganska bra på att matcha de observerade distribution.
Pierre's introduktion till hans algoritm:
Pierre börjat arbeta med detta i ett stycke algoritm på 2003,1.
Pierre skickat mig ett e-mail om hans algoritm för 2003.4.9, rapporterar följande resultat under 20 på varandra följande spel:
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.
"Algoritmen genomförs i Turbo Pascal och slutför 7000 rader / min. Med en Athlon 1600+."
Jag konverterade Pierre's algoritm till C++ på 2003,6, efter flera e-mail utbyte med Pierre. Vi kontrollerade att de A.I. i C++ version gjort samma beslut av Pascal version.
Jag observerade liknande prestanda till sin ursprungliga rapport; genomsnitt omkring 650000 färdig rader, och vissa spel fyller 2 miljoner rader.
Incredible!
10.2 Samtal med Pierre Dellacherie
[1] När fick du först skapa denna kod?
Jag har arbetat med den algoritm från slutet av januari 2003 fram till nu.
[2] Hur länge har du arbetat med det?
Jag arbetade på det nästan varje vecka ... men inte vardagliga länge eftersom jag har andra verksamheter: Tyvärr måste jag tjäna pengar gärna någon annan!
[3] Vad inspirerade designen av koden?
Jag spelade Tetris 10 eller 15 år sedan men jag hade inte spelat en gång för länge. Jag skulle säga att jag är en "genomsnittlig" spelare som vet reglerna och en del knep.
Men när jag började arbetet med den algoritm jag inte spela så mycket eftersom jag tyckte det var lite mer effektivt att titta på datorn spelar och analyserar hans svagheter.
[4] Visste du använda någon automatik att ”utbilda” din kod för att prestera bättre? Du har kommentarer att förbättra algoritmen?
Eller har ni helt enkelt titta på resultatet och besluta att göra ändringar?
Jag är från ”gamla skolan:” Jag bara tittade på resultaten och beslutat att göra ändringar.
"Automatisk lärande" är en typ av meta-algoritmen så jag är inte säker på att göra det på detta sätt skulle få lättare eftersom detta meta-algoritm skulle behöva byggas för och det är inte så lätt!
Vad mer kan jag hålla med Roger Penrose när han säger (i sin bok "Shadows of the mind") att människors förståelse och intuition kan inte algoritmisk (exempel: beräkningen).
[5] När började du först börja spela Tetris, och när gjorde du har tanken på att lösa Tetris med en A.I.?
Jag undervisar algoritmisk och datorprogrammering (Turbo Pascal och Scilab) för studenter som tåget för prov i examen ingenjör: s skolor.
Vid första, "Datorn spelar Tetris" var en idé jag ville utveckla min nästa års studenter.
Jag var inte medveten om din webbsida när jag började arbeta på algoritmen.
Jag hade tur att vara uppmärksam på din webbsida bara några veckor sedan eftersom jag tror att jag skulle ha blivit avskräckta av dina resultat (som ni kan gissa, de första versionerna av mina algoritm inte spelade så bra!).
[6] Vilken är din nuvarande status?
Jag är nästan 30 [före 2003 april 27]. Jag har flera verksamheter: Jag är en cellist, jag komponera musik och jag undervisar i datorprogrammering.
Jag har en magisterexamen i musikvetenskap (1994) och en "Artificial Intelligence and Algorithmic" diploma (1998).
I Frankrike denna examen motsvarar den 5: e år studerar på universitet (4: e år är det magisterexamen och 6 år är den avhandling).
Pierre's kompositioner:
[7] Var bor du?
Jag är franska och jag bor i Rouen (Normandie).
[8] Andra kommentarer:
Så småningom har jag inte någon ny idé att förbättra den.
Jag har försökt så mycket onyttig (och dumt) saker som jag tvivlar på det kan förbättras.
Å andra sidan tycker jag att det kan finnas helt olika algoritmer som skulle kunna få bättre prestanda.
Förresten, en snabbare test bestå i att lansera de bitar i ett halv-box (10 rader X 10 kolumner): i en halv-box, min algoritm gör ett genomsnitt på 280 ifyllda rader.
En sak till: den algoritm kan lätt ändras till en dubbel-skikt algoritm ([Jag kommer att göra] testerna snart).
Jag älskar film musik: att bli en film kompositör är en del av mina största drömmar (men det är bara drömma!).
11. Best mänskliga spelare i världen
11.1 Japanese Tetris Master (2001 den 27 januari) video
Tetris mästare (2001, Japan) video
Arika presenteras de japanska Tetris Finals mästare (2001 den 27 januari). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Feedback
12.1 Slashdot thread (2003)
År 2003, mitt Tetris A.I. projektet diskuterades om Slashdot Internetforum (
http://slashdot.org).
Slashdot (http://slashdot.org) Internetforum rubrik för en diskussion om mitt Tetris A.I. projektet
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 inspirerad av min Tetris A.I. projektet (2003) (första gången jag någonsin inspirerats en komisk!)
Comic inspirerad av min Tetris A.I. projektet (2003) (andra gången jag någonsin inspirerats en komisk!)
13. History of the Tetris A.I. projektet
På våren 1989 var jag upptagen hoppar (och inte) andra halvåret Freshman klasser vid University of Pennsylvania.
En av min rumskompis, Bill Matthews, hade Mac Classic, och ibland spelade videospel.
Människor som får tas upp till Ivy League skolor är oftast benägen att konkurrera med andra människor hela tiden - så när Bill fick spelet Tetris för hans Mac vi genast startat en långsiktig kamp för hög värdering.
När poängen klättrade, tidpunkten investeringar som krävs för att göra en liten vinst ökat dramatiskt.
För att göra en lång historia kort, Bill förment innehar höga värdering mellan oss, men jag misstänker honom för att använda ResEdit och hacka den värdering fil!
Bill hade klasser i Wharton School of Business, alma mater av Michael Milken och Donald Trump, så det är inte otänkbart att någon manipulerat en oändligt hög värdering ...
På sommaren 1990 jag lånade en 30 MHz Intel 80386 IBM PC från min rumskompis, Alex Haidas.
Jag köpte en Mac tangentbordet på en loppmarknad för $ 1.
Jag byggde parallellport kretssystem för att tillåta PC att kontrollera Mac tangentbord.
(Jag använde en CMOS 4040 chip att fungera som en typ av solid-state relä att ansluta tangentbordet kontakter innanför Mac tangentbord.)
Jag skrev ett datorprogram som används ett beslut träd som sin strategi för att spela spelet Tetris. På bara några veckor hade jag en PC spela Tetris spelet körs på en Mac.
Men jag var tvungen att använda PC tangentbordet för att tala om för A.I. om varje bit som faller på skärmen.
Jag började arbeta på en krets som använder CdS (Cadmium Sulfide) ljus detektorer som skulle luta mot Mac skärmen och "se" de fallande bitar, men CdS sensorer reagerade för långsamt på förändringar i ljusstyrka och kontrast mellan Tetris bitar och bakgrunden om Mac Classic skärmen var för låg för att tillförlitligt diskriminera.
På den tiden jag inte har mycket pengar, så det var för riskabelt att köpa en $ 2 Radio Shack phototransistor som kanske inte göra vad jag ville.
Också med tanke på kontrasten problemet, var jag pessimistisk om hela tillvägagångssättet.
När jag köpte min första dator år 1996, jag kunde inte få mjukvaran enligt Windows 95 på en 100 MHz CPU att göra video-behandling snabbt för att göra en enkel vision system fungerar.
Jag skrev bildbehandling koden i Assembler, men det fanns så mycket overhead innan mitt nummer faktiskt fått videodata att det verkade omöjligt att göra något meningsfullt.
År 2003, teknik, särskilt CPU hastighet, hade nått en nivå som gjorde avslutar projektet nästan trivial.
Jag grävde fram mitt gamla personligt projekt och slutligen färdigt den, få lite känsla av nedläggning.
Det var väldigt spännande att se en dator spelar en annan dator via USB videokamera och reläer.
Ljudet av reläer klicka, och tittade på de bitar spinn och släppa på löjligt, övermänsklig hastigheter, som gjorts av erfarenheterna mycket tillfredsställande i en flera sätt.
Under 2003 arbetade jag som erkänts av Slashdot (
http://slashdot.org), och jag fick en massa bra feedback.
Jag var inbjuden att finnas på "Screen Savers" TV visar på TechTV digitala tv-nätet.
Jag åkte till San Francisco och visades på utställningen, liksom erfarenheterna was great.
Senare under 2003, jag fick ett meddelande från Henk Rogers, bjudit in mig till Hawaii för att träffa honom och Alexey Pajitnov att tala om upprättande av något slags standard för Tetris, för att ha Tetris turneringar.
Ett särskilt intresse var att möjliggöra spelare att använda mobiltelefoner för att ”konkurrera med varandra,” indirekt, via A.I. som imiterar spelare (genom analys av varje spelares insatser) och på så sätt undvika effekterna av mobiltelefon till Internet latency, och aktiverar spelare att ”konkurrera” med * De allra bästa mänskliga spelarna i världen (*... eller snarare A.I. imitera de allra bästa mänskliga spelarna i världen).
Jag blev glada av utsikten till mötet skaparen av Tetris. Tyvärr flyger gör mig ängslig, och jag avböjde inbjudan.
År 2006, jag konverterade min "Standard Tetris" programvara från C++ att C# att göra programvaran mer tillgänglig och användbar för nutida programmerare.
