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 for hver brikke ganske enkelt ved å bestemme seg på en raskt og "trykke på tastene" for å gjennomføre flyttingen.
Mer viktig for en A.I. er overlevelse, fordi ubestemt overlevelse betyr en vilkårlig høy skåre kan oppnås. Fordi Tetris brikkene faller på en bestemt sats, A.I. må ta avgjørelser minst dette fort - og A.I. må foreta trekk den komplette rader med en hastighet som gjennomsnitt minst 1 rad med 2,5 brikker. (Hver brikke har 4 celler, og hver rad har 10 celler.)
Selvfølgelig kan man utsette fylle rader av accumulating stykker og bygge en stor bunke, men det er bare 200 celler på hele styret, som i prinsippet kan bare har 50 brikker, slik at alle spiller (for eksempel en A.I.) må ha fullført linjer som en grunnleggende prioritet.
I Standard Tetris, spillet staten inkluderer den gjeldende bord okkupasjon og gjeldende fallende brikker (type, posisjon og orientering). Spillet staten kan eventuelt inkludere "Neste Piece".
6.2 En alternerende rekkefølge av "S" og "Z" brikker
Heidi Burgiel, Ph.D., av Department of Mathematics, Statistics and Computer Science på University of Illinois at Chicago, har vist at en alternerende rekkefølge av "S" og "Z" brikkene vil tvinge frem en standard (10-kolonne, 20-raden) Tetris spill til utgangen innen en forutsigbar nummer av trekk.
Sitat fra artikkelen: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Tilknyttede trykt artikkel: Mathematical Gazette, juli 1997, "How to Lose at Tetris"
Heidi Burgiel tilbyr en Java applet som kjører i en nettleser som inkluderer en endret Tetris klone som spawns alternerende "S" og "Z" brikker.
[ "Standard Tetris" programvare som er tilknyttet dokumentet du leser har også en modus som spawns alternerende "S" og "Z" brikker. ]
Heidi Burgiel hevdet at et spill med alternerende "S" og "Z" brikker (for en standard Tetris bord på 10 kolonner og 20 rader) må slutte før færre enn 70000 brikker har falt.
Standard Tetris programvare følger med dette dokumentet gjør det mulig for en person å spille spill med alternerende "S" og "Z" brikkene, og endre styret bredde.
Det er lett å se at styremedlem som bredder er heltall Combi av fire kolonner (eksempler: 4 kolonner, 8 kolonner, 12 kolonner, osv.) kan bli spilt for alltid når brikkene veksle mellom "S" og "Z", med hoper stiger ikke høyere enn 4 rader. Jeg nevnte dette for å gjøre det klart at den begrensede survivability beskrevet i forskning dokument som er nevnt ovenfor er spesifikt for tilfellet av en standard Tetris bord (med 10 kolonner og 20 rader).
6.3 Uløselige stykke sekvenser generelt
Det er hele kategorier av patologisk sekvenser som ikke kan overlevd.
Det ville være interessant å beregne den totale sannsynligheten for møter en spill-avslutning sekvens, fordi dette ville sette en øvre bundet på resultatene av en strategi, selv med full kjennskap til alle fremtidige brikker på et gitt punkt i et spill.
6.4 Total mulig bord konfigurasjoner
Gitt at styret har 10 * 20 = 200 celler, og gitt at hver celle kan bare være i ett av to stater (tom eller opptatt), totalt antall bord konfigurasjoner må være mindre enn eller lik: (2 ^ 200).
Gitt at hver brikke legger til 4 celler til et bord, og hver rad ferdigstillelse eliminerer 10 celler fra styret, antall okkupert celler på brettet vil alltid være med. For eksempel (3*4 - 1*10) = 2, (1*4 - 0*10) = 4, (4*4 - 1*10) = 6, (2*4 - 0*10) = 8, (5*4 - 1*10) = 10, osv. Altså, bare halvparten av (2 ^ 200) bord konfigurasjoner kan nås ved å spille spillet.
Dermed blir totalt antall bord konfigurasjoner er ca: (2 ^ 199) = 8.03469... * 10^59.
Men vi må ekskludere fra våre totale noen som har fylt rader, fordi fylt radene er eliminert før slutten av hver avsluttet flytte. All konfigurasjon med én eller flere fylt rader vil kollapse til en annen konfigurasjon som ikke inneholder noen fylt rader.
I tillegg bør vi utelukke som inkluderer en ikke-tom rad over en eller flere tomme rader, fordi en ikke-tom rad over en tom rad vil alltid falle, og alle fallende stopper før slutten av hvert trekk.
Hver rad kan være i 2^10 = 1024 stater, en som er "tom", en som er "full", og (1024 - 2) = 1022 som er delvis okkupert. Vi ekskluderer "hele" saken fra behandling.
Hvis den nederste raden er tom, og deretter alle rader over nederste raden må også være tom.
Hvis den nederste raden er delvis okkupert, deretter den andre rad kan være tom eller delvis okkupert.
Fortsetter denne analysen, kan vi beregne antall bord konfigurasjoner som tar inn på konto utelukkelse av hele rader og restriksjoner på tomme rader: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), som er ca ((1022 ^ 19) * (1023)).
Således finner vi en mer nøyaktig anslag over det totale antallet stabilt bord konfigurasjoner: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199); dvs. omtrent 3,74% mindre enn (2 ^ 199) anslaget.
Men det faktiske antallet stabilt, tilgjengelig bord stater trolig vil være særlig lavere på grunn av det faktum at den øverste mest rader kan bare bli fylt på noen måter. Som øverste mest rader fylle en nylig utført brikke kan ikke flyttes eller roteres veldig mye. Dette begrenser antall måter øverst mest rader kan bli fylt.
6.5 I prinsippet, den beste flytte kan bli funnet på noen bord og brikke konfigurasjon
Fordi vi kan få noen av syv mulige deler av en gitt styret staten, det totale antall spill stater er ca 7 * (2 ^ 199) = 5.624... * 10^60.
Fordi vi kan i prinsippet gjøre et dypt søk i alle mulige framtid for alle mulige trekk for en gitt spillet staten, vi kan ha en enkelt "best" flytte i forbindelse med hvert spill.
Vi antar at vi ikke har tilgang til noen annen informasjon enn den nåværende styret og nåværende brikke, slik at "best" betyr "flytt som gir størst sjanse for å tilfredsstille våre langsiktige mål om å overleve".
Et trekk er bare en oversettelse (opptil 10 alternativer) og en rotasjon (opp til 4 alternativer), kan vi enkelt kode beste bevege seg i en enkelt byte.
Så i prinsippet kunne vi danne en tabell med 10^61 oppføringer (bytes) som fortalte oss den beste farten gitt noen bord stat og nåværende brikke.
Dette er selvfølgelig upraktisk, akkurat som opplisting alle "Go" styremedlem eller "Chess" boards er upraktisk. Men poenget er at det er en sann løsning, og det er best flytte til en gitt konfigurasjon. Det kan være like god trekk for en gitt konfigurasjon, men vi kan vilkårlig velge én enkelt flytte i dette tilfellet.
Mange spill-spiller algoritmer har tabeller som exhaustively nummerere alle spill stat muligheter innenfor begrensede sammenhenger, som for eksempel "åpning (første) trekk" eller "end-game (endelig) trekk i sjakk. Kategori uttømmende opplisting av Tetris hoper flater (ca. (20 ^ 10) stater) er gjennomførbart. Det er en interessant idé.
Omfattende brukerstøtte opplisting av alle landene i den nederst to rader, ganget med syv mulige stykker, og lagrer de beste bevege seg i én byte, ville være ganske enkelt; krever bare 7 MB av minnet. Kategori optimalisere ytelsen til disse syv millioner tilfeller ville gi rådata for både analyse og utvikling av enkle modeller for data; slike modeller kan betraktes som en del av den samlede ideelle Tetris-spiller.
Vær oppmerksom på at gjennomføring av beste trekk likevel ikke beskytte oss mot mulige patologisk spill-avslutning stykke sekvenser. Det er nettopp dette vi vil alltid gjøre trekk som gir oss den maksimale potensial for fremtidig overlevelse gitt at alle fremtidige brikker er helt tilfeldig (og ukjent på det tidspunktet vi skal bestemme hvordan du vil flytte én dagens kjente stykke).
6.6 Real-time performance
En begrensningen møter noen strategi algoritmer er behovet for real-time ytelse - noe som betyr at algoritmen må ta en beslutning innen en bestemt tidsperiode.
Når en menneskelig spiller Tetris, bitene ikke stoppe fallende å gi spilleren en sjanse til å tenke. Det er en del av utfordringen av Tetris. Altså, en A.I. system som er ment å simulere rollen av en menneskelig spiller må også ta avgjørelser på et rate diktert av Tetris spill.
6.7 Row og brikke totalene
Legg merke til at på lang sikt, vil antallet falt brikkene er svært nær 2.5 ganger antall fullførte rader - fordi hver rad har 10 celler, og hver brikke er 4 celler, og vi må fullføre en rad i gjennomsnitt én gang (10/4) = 2.5 brikkene falt.
Så vi kan bruke "avsluttet rader" og "falt brikkene" nesten interchangeably med riktig forholdsmessighet konstant. Den største feilen er når brettet er helt fylt med unntak for en enkelt gapet i hver rad (((10*20)-20)/4) = 45 brikkene falt men en mangel av den anslåtte (45/2.5) = 18 avsluttet rader.
6.8 Gjeldende-brikke (og styret) strategi
Hvis vi bare lar A.I. å ha kunnskap om gjeldende bord og gjeldende stykke, og vi bare vurdere resultatet av å flytte den nåværende brikke i bestemte måter, så dette kan bli kalt en "en brikke".
Her er en grov skisse av hvordan et en-brikke-analyse kan bestemme at et trekk i Tetris:
Gjeldende-stykke analyse av et Tetris spill stat
I utgangspunktet prøver vi alle mulige trekk og velge farten som gir det beste resultatet.
Den vanskelige delen er vurdering hvert resultat.
Vi må rangere en hypotetisk Kamp stat i henhold til hvor godt en slik tilstand støtter våre kortsiktige og langsiktige mål.
Vårt langsiktige mål er å overleve. Survival avhenger hindre hoper fra overfylte bordet. Vi kan redusere hoper høyde ved forming fullstendig rader som blir deretter fjernet fra hoper.
For å danne en komplett rad, må vi passe deler av brikker i hver kolonne i den raden. Derfor krever vi at alle deler av en rad for å bli utsatt for den fallende brikker hvis vi skal til slutt fylle ut hele raden.
Hvis for noen grunnen til at vi dekker opp tom deler av en rad av brikkene på en høyere rad, og vi er nå ikke i stand til å fylle inn de tomme deler av raden. Den eneste måten (forutsatt ingen skyve) for å få tilgang til disse "begravet hull" er å fjerne radene ovenfor som har deler fungerer som hindringer.
Følgende faktorer er blant de vi kan bruke for å rangere et bestemt bord status:
Overall pile height
Jo høyere bunke, verre vår situasjon synes å være, fordi vi er nærmere overfylte bordet.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
Den rougher det bunke, jo mer sannsynlig er det at det vil være vanskelig å fylle ut alle de innebygde komplekse konturer som de blir eksponert til overflaten.
Number of buried empty cells
Jo mer hullene vi har begravet, verre vår situasjon er, fordi vi må avdekke begravet hull før vi kan fullføre den tilhørende rader.
Du kan forestille seg andre faktorer som vanligvis rangere en hypotetisk bord på hvor godt det hoper kan imøtekomme alle mulige fremtidige brikker, og hvor godt den situasjonen ser ut for alle de mulige stykker.
Det neste spørsmålet er hvordan man skal fastslå den relative betydningen av disse faktorene.
En generell tilnærming er følgende. Tilordne et sett med "vekter" (relative betydning) til disse faktorene, og deretter simulere en rekke spill og registrere utfallet av disse spillene (endelig poengsum, osv.). Deretter tilordner et nytt sett med vekter og simulere et nytt sett av spill. Basert på hvorvidt eller ikke nytt sett av spill hadde bedre resultater enn tidligere satt av spill, så vet vi om det nye settet med vekter var bedre enn forrige sett med vekter.
I mine egne eksperimenter Jeg prøvde systematisk søking og tilfeldig søker etter god vekt kombinasjoner, men jeg gjorde ikke merke noen store trender at jeg kunne arbeide. Men jeg så mange overraskende jevne støt. Jeg syntes det var interessant at den gjennomsnittlige ytelsen kunne danne en jevn kurve når en parameter ble sakte variert med andre parametere holdt på noen verdi kombinasjon.
Den beste sanntid, en-brikke Tetris algoritmen i verden, laget av Pierre Dellacherie (Frankrike) i 2003, owes mye av suksessen til sine sett av målinger (eller beregninger). Finne vekt er nødvendig når du optimaliserer en strategi, men det er også avgjørende å starte med typer målinger som viser relevante kjennetegn for staten.
Pierre Dellacherie's oppfinnelse av nye måter å karakterisere hvert bord gjør sin algoritme virkelig utmerket; styret characterizations fange opp viktige strategiske dimensjoner av styret.
Man kan utvikle en svært forskjellige sett med karakterisering dimensjoner som fungerte like bra, jeg er sikker på at det er mulig å span relevant bord staten plass i mange forskjellige måter som kan brukes til å angi en strategi fungere. Nøkkelen er å finne kjennetegn på at prosjektet staten plass ned til et lite antall dimensjoner som kan brukes til å utvikle en enkel vurdering funksjon (eksempel: den lineære vektet kombinasjon av karakteristikker som brukes av Pierre's algoritme).
Den en-Piece algoritmen som brukes av "bot" i "xtris" programvare (1996) skrevet av Roger Espel Llima bruker vektene bestemmes av en omfattende utforskning av mulig vekt kombinasjoner av "genetiske algoritmer". Simulert Annealing er en annen mulig metode for å utforske flerdimensjonale plass i vekt kombinasjoner.
Det synes som, basert på ulike observasjoner, flerdimensjonale funksjon av gjennomsnittlig Tetris ytelsen som en funksjon av vekter, eksempel: F(w1,w2,w3,...), er "grov" (en mengde av lokale Minima og Maxima), noe som betyr at en enkel flerdimensjonale "Hill klatring" kanskje ikke fungere.
6.9 Strategi når gjeldende stykke, neste stykke, og styret er kjent
Hvis en strategi algoritmen er gitt gjeldende stykke, neste stykke, og bord, så den kan fatte beslutninger som kan dra nytte av kombinasjonen av brikkene.
Kjennskap til neste brikke kan forbedre suksessen av et Tetris spille algoritmen med flere bestillinger av omfanget. Det er lett å forstå hvordan vet neste brikke gjør en stor forskjell i strategien.
Man kan gjøre "crazy" trekk, som dekker store hull, osv., fordi de allerede vet at den neste brikken kan brukes til å "fikse" situasjonen. Hvis du ikke har kjennskap til neste stykke, er du hele tiden prøver å spille av sjanser, prøver å holde valgmulighetene åpne i tilfelle det neste stykke er ikke ideelt.
Følgende skisse viser hvordan alle mulige trekk for den nåværende brikke er vurdert, og for hver slik flytter vi vurdere alle mulige trekk med neste stykke.
Strategi med gjeldende brikke og neste brikke
Standard Tetris programvare bruker denne strategien når "Neste Piece" aktiveres av brukeren og er synlig på skjermen, og når en to-brikke A.I. er aktivert (slik som den er skrevet av meg, Colin Fahey). Hvis "Neste Piece" er ikke synlig på skjermen, min to-brikke faller tilbake til et en-brikke A.I..
Min ett stykke A.I. er forferdelig når i forhold til de andre AIs i Standard Tetris programvare, så dette viser fordelaktig mer informasjon (eksempel: den neste stykke) kan bli til en A.I. systemet, det er nok til å forbedre resultatene av mine egne middelmådig to-brikke A.I. av flere bestillinger av magnitude - enkelt surpassing resultatene av de beste en-brikke A.I. i verden.
(Men å konvertere de beste en-brikke A.I. i verden til å vurdere to stykker ville lett å forbedre det ved flere bestillinger av omfanget, too! Vite neste brikke er enorme!)
Mitt første teste spillet med mine to-brikke A.I. varte i omtrent 182 timer (7,6 dager) på en 800 MHz PC, fylle 7216290 rader. Jeg har ikke testet algoritmen på en raskere datamaskin.
Når du spare staten for en Tetris spill (Shift-W) til en tekstfil, kan du kopiere og lime inn listen over tallene fra seksjonen "heightHistogram", til en Excel-regneark.
Hvert bin i histogrammet angir antall fullførte trekk som endte med en bestemt hoper høyde (etter fullført rader er eliminert). Som du kan forestille deg, gjør et trekk som helt eliminerer en bunke er sjeldne, slik at det totale antallet trekk som ender med en bunke høyde på null er forholdsvis lav.
I mellomtiden kan du forvente at det hoper høyde som regel svinger rundt noen gjennomsnittet, slik at vinduer tilsvarende for disse radene vil dominere histogrammet. Til slutt, bønne til toppen-mest rader (der vi er i fare for overfylte styret) har svært lav tilsammen.
I løpet av mange timer, med A.I. spille et enkelt spill ved hjelp av strategien omfatter kunnskap om "Neste Piece", tok jeg tilfeldige prøver av spillet staten, kopiere hoper høyde histogrammer til et regneark som vist nedenfor:
Pile høyde histogrammer spilt inn på ulike punkter i et vanlig spill (med nåværende og neste stykke strategi)
Du kan skalere hvert histogram av det totale antall brikker (totalt antall fullførte trekk) for å få følgende data:
Scaled histogrammer, og en teori
Den bemerkelsesverdige ting er at disse skalert histogrammene ser identiske til tross for ulike bestillinger av omfanget av antall brikker (fullført trekk) som er involvert.
Bare ved å se på tallene jeg har gjort hypotesen om at halen av kurven er en eksponensiell decay. Ved prøving og feiling kom jeg opp med grov teorien at halen ble beskrevet av:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Følgende diagram viser skalert histogrammet over hele omfanget av rader.
Diagram over skalert histogrammer
Merk at kurven til 50000 stykker, og kurven på 2000000 brikker, og kurven med halen teori er nesten indistinguishable på denne skalaen.
Nedenfor finner du en nærmere titt på hodet av kurven.
Nedre del av høyden histogrammet
Følgende er en stor-forstørret bilde av den ekstreme halen slutten av målt og teoretisk histogrammet kurver.
Forstørret visning av ekstreme halen slutten av skalert histogrammer
Som du kanskje forventer, er det svært sjelden for hoper for å nå disse høyder i enda lang eksperimenter - men selv med våre begrensede bevis i denne ekstreme regionen, teorien fortsatt synes akseptabelt.
I den fullstendige listen teorien ser ut til å overlappe med halen av distribusjonen "nøyaktig", mens i forstørret diagram av halen av halen, ser vi åpenbare feil. Men jeg hevde at dette er på grunn av utilstrekkelige data på disse ekstreme hoper høyder. Hvis jeg økte spillet bord til, si, en høyde på 25 rader i stedet for 20 rader, slik at spill ikke avslutte brått, tror jeg teorien jeg presenterte ovenfor ville sammenfaller perfekt med trenden.
Min følelse er at dette histogrammet er en direkte kombinert resultat av Tetris A.I. og regler av Tetris. Så, den samme fordelingen vil bli observert av noen tilfeldige langsiktige spillet Tetris bruke mitt bestemt A.I. strategi for å spille med "Neste Piece" kunnskap.
Dessuten tror jeg denne typen histogrammet kan brukes til å sammenligne AIs som bruker den samme informasjonen mens du spiller. Dermed trenger du ikke å spille komplett spill (som kan vare i dager eller år) for å sammenligne de langsiktige resultatene av ulike strategi algoritmer.
For eksempel, til tross for enkelhet av min modell, jeg tror det kan bli brukt til å forutsi gjennomsnittlig spillet varighet! Vi ganske enkelt regne ut hvor mange brikker som gjør det "rad 21" hoper høyde et betydelig antall, for eksempel et antall.
Den relative frekvensen av rad 21, i henhold til min enkle teorien, er:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Du må mangedoble dette nummeret av (5.3 * 10^(7)), omtrent 50 millioner, for å få en verdi på én.
Altså, jeg omtrent forutse at min nåværende "Neste Piece" strategi er bare god for på rekkefølgen på om lag 10 millioner avsluttet rader. En grunn til at jeg gjør dette konservative anslag er det faktum at selv 18 rader kan være dødelig for min A.I. fordi jeg ikke tillate meg A.I. å vurdere stykker før de har falt med minst én rad! (Dette er så jeg trenger ikke å bekymre deg for ikke å være i stand til å rotere brikkene.)
Jeg er imponert av det faktum at du spiller bare 50000 stykker (og muligens mye færre brikker) kan gi deg en svært god anslaget for den langsiktige høyde histogrammet, og dermed et godt anslag over rekkefølgen av omfanget av fullført rader før spillet ender. Denne tilnærmingen er svært verdifull for raskt å vurdere subtile endringer i en A.I. som allerede driver svært godt.
6.10 Styret evaluering beregninger etterligne spekulativ utseende fremover
Hvis en algoritme, slik som den jeg presenterte med dette prosjektet, kan du bare prøver alle stykke orientering og oversetting til slippe, og priser hver resulterende bord konfigurasjon i henhold til en viss grad av fortjeneste, algoritmen er i vesentlig grad etterligne "utseende fremover".
Når en bruker for eksempel "hoper høyden", "begravet hull", "overflaten råhet" eller "godt dybder", en virkelig hjelp av en forenklet form av "se fremover". Disse generelle characterizations av styret gi noen indikasjon på den langsiktige levedyktigheten til styret.
Den ideelle tilnærming, gitt en uendelig mengde databehandling strøm, ville være å vurdere et styre konfigurasjonen gitt alle mulige stykke sekvenser som kan følge.
Selv om du må ta hensyn til alle 7 stykker som like sannsynlig at hvert nivå av utseende fremover, du trenger for å optimalisere den faktiske Oversettelsene (opptil 10) og orientering (opptil 4) for hver brikke i alle mulige sekvens! Det er opp til (7*10*4) = 280 greiner på hvert nivå av styret evaluering! Så det er opp til ((280)^(LookAheadLevels)) bord konfigurasjoner for å vurdere.
Fordi vi må avslutte analysen etter et endelig antall nivåer, må vi ha noen ikke-se-fram-metoden for evaluering av styret stat - en måte å gi verdier til leaf noder av våre søk treet. Så, for disse leaf noder, er vi tilbake til ved hjelp av en formel som omfatter generelle predictors av fremtidige levedyktighet av brettet!
Denne typen spekulasjon kan være forsøkt med One Piece-og to-Piece algoritmer i stedet for den forenklede bord evaluering beregninger. Anta alle etterfølgende bitene er like sannsynlige og oppsummere evnene av et styre å imøtekomme deler av alle slag i den best mulige måter. Dette kan gjennomføres med ett, to, eller et hvilket som helst antall spekulativ flytte dybder - med alle brikkene er like sannsynlig (p=1/7).
Terminalen noder i dette treet kan fortsatt kreve vektet beregninger for å evaluere, men spekulativ lag mer presist fange essensen av hva vi ønsker å gjøre: å avgjøre hvor godt et bestemt bord kan godta alle mulige stykker, inkludert positive faktorer som fullfører linjer og negative faktorer som øker den generelle hoper høyde, osv.
7. Tetris A.I. systemet demonstrasjon
7.1 System overview
Dette Følgende diagram viser mine eksperimentelle set-up.
Overall system for demonstrasjon
7.2 Utstyr
Her er en kort liste over utstyr som brukes i denne demonstrasjonen:
[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)
Åpenbart kan du bruke lignende utstyr for å oppnå de samme resultatene. Flere detaljer om utstyret er beskrevet i den tilhørende avsnittene i denne artikkelen.
Her finner du korte beskrivelser av personlige datamaskiner som brukes i denne demonstrasjonen:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Denne demonstrasjonen kan lett bli gjengitt med andre operativsystemer, for eksempel Linux. Det er mer viktig å ha et CPU hastighet på rekkefølgen av 800 MHz eller raskere for datamaskinen som å kjøre A.I. programvare, fordi denne maskinen vil være å gjøre real-time prosessering av video.
7.3 Videoopptak maskinvare
Jeg brukte et felles USB videokamera som en videooverføring enhet for min A.I. systemet. Nærmere bestemt, jeg brukte Creative "WebCam Pro", en USB videokamera med 640 * 480 oppløsning.
Creative(TM) USB videokamera beskrivelse
USB videokamera (og vinkel)
USB videokamera (front)
USB videokamera (bord med CCD)
USB videokamera (main chips)
OV511 viktigste blokker (merk: USB videokamera er OV511+)
7.4 OV511 datablad
ov511ds.pdf
OV511 Datablader
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "pluss") funksjonen forskjeller
ov511plus_101.pdf
OV511+ Feature Forskjeller
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Videoopptak programvare
Microsoft har en svært gammel API heter "Video for Windows" (VFW) at jeg med hell brukes til dette prosjektet. (Du link til "vfw32.lib" i C++ prosjektet, eller gjøre en DllImport "vfw32.dll" i C# kode.) Eksempler på ved hjelp av VFW API er allment tilgjengelig.
Et alternativ er å bruke Microsoft's "DirectShow" API å gjøre videooverføring.
Fordi VFW tok bare et dusin linjer med kode til å bruke, og utføres acceptably på min 800 MHz maskin, jeg gjorde ikke bry utforske alternative APIs. Men DirectShow er en mer moderne API for Windows videooverføring, og potensielt gir en mye høyere bildefrekvens på samme maskinvare.
Se på "CPF.StandardTetris.STVideoCapture" kildekoden filene i Standard Tetris programvare for å se hvor enkelt det er å få videooverføring til dine egne prosjekter.
7.7 Computer grensesnitt for rele (via RS232)
Hvis du vil ha en datamaskin "Trykk tastene på tastaturet til en annen datamaskin, jeg brukte en" relé bord "kontrolleres av tekst-kommandoer sendt fra en seriell kommunikasjon port (eksempel:" COM1 ") via en RS-232 kabel. Jeg brukte hvert relé for å koble de to ledninger av en bestemt tastaturet tasten for å simulere en nøkkel trykk.
Dette kreves for å åpne opp tastaturet og gjøre tilkoblinger. Det er mange enklere metoder for å simulere tasten du trykker på en datamaskin, men jeg ønsket å gjøre noe som virket så nært som mulig til en person virkelig skrive på et tastatur.
Et svært allsidig og godt gjort relé bord er ADR2200 gjort 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 se på "CPF.StandardTetris.STRS232" kildekoden filer for å se hvor enkelt det er å sende bytes gjennom en seriell port, som deretter kan brukes til å styre enheter som ADR2200 bord vist ovenfor.
8. Standard Tetris programvare
8.1 Last ned programvare
Gå til begynnelsen av denne artikkelen for å finne en link til å laste ned kildekoden (C# og C++ versjoner) og innebygd programvare (*.exe).
8.2 Oppsummering av funksjoner
Programvare funksjoner:
Undervisning skjermer og kreditter
Monochrome-modus
Shadow-modus
Tips modus
Juks rader
Sats kontroll
Neste brikke
Styret størrelse
S/Z brikker
Kalibrering modus
Videoopptak og anerkjennelse
Feilretting konsoll
Lagre spill
Sett spill
8.3 Starter utseende
Utseende når programvaren er i gang:
Utseende når programmet er startet
8.4 Monochrome-modus
Som standard styret vises i farge:
Som standard styret vises i farger.
Fargen modus kan endres til svart-hvitt (Shift + K):
Fargen modus kan endres til svart-hvitt.
8.5 Shadow-modus
Shadow viser hvor en brikke lander. Dette er svært nyttig for svært store boards, fordi det er vanskelig å bedømme hvor en brikke lander.
Shadow viser hvor en brikke lander.
8.6 Tips modus
Tips modus viser deg hvor tiden valgt AI ville flytte gitt dagens situasjon. (Shift + H)
Tips modus viser hvor tiden valgt AI ville flytte.
8.7 Juks rader
Sett inn "søppel" rader på bunnen av hoper, én etter én, manuelt. (Shift + J)
Sett inn "søppel" rader på bunnen av hoper.
8.8 Sats kontroll
Den '+' (pluss) og '-' (minustegn) nøklene styre hastigheten på spillet.
Som standard, spillet kjører på en standard hastighet, i henhold til reglene i Standard Tetris (hastighet basert på nivå).
Her er en tabell over innholdet i hastighet skjevhet:
-3,-4,...: treghet proporsjonal til skjevhet
-2: tregere enn nivået 1
-1: normal, men begrenset til nivå 6 (0,2 sek) hastighet;
0: normal; Standard Tetris hastighet kontroll;
+1: litt raskere enn nivået 9 (0.05 sec forsinkelser);
+2: grenser ved å gjengi rate (eksempel: 75 Hz);
+3,+4,...: flere gjentakelser per gjengis ramme;
Jeg liker å kjøre A.I. på en innstilling av "+2" (trykk '+' tasten to ganger hvis bias starter på null).
Speed skjevhet endrer hastigheten på spillet.
8.9 Vis neste brikke
Hit 'N "for å veksle" Neste Piece "skjerm. Den A.I. vil bruke "Neste Piece" bare hvis "Neste Piece" vises på skjermen.
Du kan være trygg på at AI er ikke ved hjelp av "Neste Piece" informasjon når du ikke kan se "Next Piece" på skjermen.
Vis neste brikke
8.10 Styret størrelse
Trykker Ctrl + (venstre, høyre, ned, opp), en kan justere bord størrelse til vilkårlige størrelser fra 4 * 4 opptil 200 * 400.
Styret størrelse: 4 * 8
Styret størrelse: 20 * 40
Styret størrelse: 40 * 80
Styret størrelse: 20 * 5
Styret størrelse: 4 * 100
8.11 S/Z stykker bare
Studer interessant alternerende S/Z mønster.
Dette mønsteret kan ikke løses av en 10 * 20 bord (bredde * høyde).
Men styremedlem som har bredder som er Combi av 4 er trivially vist til at uendelig overlevelse.
Den AIs overleve på ubestemt tid i slike tilfeller, selv om de ikke var spesielt tilpasset for å håndtere denne patologisk situasjon.
S/Z stykker bare
8.12 Video kalibrering modus
Hit 'C "for å angi" Calibration Mode ". Når i kalibrering modus, kan du trykke talltastene: {1,2,3,4,5,6,7} å velge et stykke {O,I,S,Z,L,J,T} øverst i spillefeltet bord.
Dette er nyttig som en referanse bildet for videooverføring på et sekund Standard Tetris programvare.
Hvis du treffer 0 (null)-tasten, vil det gjøre bord tomme.
Du kan late som produserer brikker ved å velge et stykke (1..7), og deretter velge en tom (0), mens en annen datamaskin gjør videooverføring klokker for brikker.
Du kan kjøre A.I. på den andre maskinen, og se hvordan det avtaler med manuelt angitt patologisk Tetris scenarier!
Calibration Mode er den eneste gangen du kan manipulere videooverføring image processing malen (4 * 2 rutenett). Du kan bruke musen til å tegne rektangler, men da kan du bruke markøren nøkler ( "opp", "ned", "venstre", "høyre") har fin kontroll over grenser - bruker Shift tasten for å velge motsatt grenser av rektangelet (eksempel: "Shift-venstre" kombinasjonsboksen er annerledes enn "left").
Video kalibrering modus
8.13 Videoopptak og anerkjennelse
Trykker 'V "skrur av videooverføring. Hvis riktig kalibrert (se "video kalibrering" i forrige avsnitt), deler av en ekstern video-skjermen vil bli fanget av videokameraet og klassifisert - og brikkene vil bli spawned i den lokale spill for A.I. å vurdere og reagere .
Den A.I. produksjon må da bli overført til (via RS-232 grensesnittet i demonstrasjon beskrevet i denne artikkelen) for den eksterne spillet inngang (eksempel: tastaturet) for A.I. å spille ekstern spillet.
Hvis til enhver tid dette lukket sløyfe er forstyrret (eksempel: videooverføring funksjonsfeil, eller output signal funksjonsfeil), deretter A.I. vil utvikle et falsk inntrykk av status for den eksterne spillet, og A.I. vil gjøre upassende beslutninger som raskt mister spillet .
(Merk: Dette problemet kan overvinnes med en beskjeden mengde arbeid: A.I. systemet bare trenger å undersøke hele ekstern Tetris skjermen til en pågående "reality check" av hele styret, og A.I. systemet bør være forberedt på noen utgang kommandoer til mislykkes på noen måte.)
Videoopptak og anerkjennelse
9. Opprinnelig Tetris AI eksperimentet (2003)
Følgende viser de første arbeider versjon av Tetris A.I. systemet i 2003.
Videokamera vender datamaskin # 1 kjører en ren Tetris spill
Computer # 2 kjører Standard Tetris programvare i A.I. modus
Venstre: Tegning rutenettet for å kalibrere videobilde anerkjennelse;
Høyre: Tetris stykke anerkjennelse tilfeller.
Ramme fra video av Tetris A.I. forsøket i 2003
10. Best ett stykke Tetris-spiller algoritmen i verden
10.1 Pierre Dellacherie (2003; Frankrike)
Pierre Dellacherie (2003, Frankrike), utvikleren av det beste en-brikke Tetris-spiller algoritmen i verden
Det beste en-brikke, real-time Tetris algoritmen til min kunnskap ble opprettet av Pierre Dellacherie av Frankrike.
Hans fantastiske algoritmen noen ganger fyller mer enn 2 millioner rader!
Den gjennomsnittlige ytelsen er på rekkefølgen av 650000 rader.
Algoritmen tar svært lite minne, og kjører i høy hastighet (ca 160 rader per sekund på 800 MHz datamaskin).
Ytelse av Pierre Dellacherie's algoritme:
Min nåværende modell for resultatene av Tetris AIS er at for et gitt stykke det er en konstant sannsynlighet for at spillet vil si, p.
Dermed, sannsynligheten for at en brikke vil ikke si et spill er q=(1-p).
Sannsynligheten for at spillet avsluttes etter k trekk er ganske enkelt produktet av sannsynligheten for overlevende (k-1) trekk, nemlig q^(k-1), og sannsynligheten for avslutning på neste trekk, nemlig p.
Dette tilsvarer en "Geometric Distribution":
Geometric Distribution:
P(k) = p * [(1-p)^(k-1)] = p * [q^(k-1)] = p * exp[ln(q) * (k-1)]
MEAN: [1/p]
VARIANCE: [q/(p*p)]
STANDARD DEVIATION: sqrt( VARIANCE )
For lite p, ln(q) er omtrent (-p), og vi har følgende:
Exponential Distribution:
P(k) = p * exp[-p * (k-1)]
= p * exp[-p * k ] approximately
MEAN: [1/p]
VARIANCE: [1/(p*p)]
STANDARD DEVIATION: sqrt( VARIANCE )
Vi forventer at brøkdel av det totale antall spilte kamper for å avslutte med en rekke avsluttet rader i intervallet [k1, k2] å være:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Etter å ha fullført 36 spill på maskinen min, over en periode på to dager, jeg fant en gjennomsnittlig 674827 fullført rader.
Ifølge den generelle teorien ovenfor, vil jeg forvente følgende forhold brøkdel av spill til slutt på følgende fullført rad serier:
p = (1/674827) = 0.000001482 = 1.482*10^(-6)
Completed Row Range Relative Fraction of Total Games
======================= =================================
0 ... 400 000 [exp( 0 )-exp(-0.59)] = 0.447
400 000 ... 800 000 [exp(-0.59)-exp(-1.19)] = 0.250
800 000 ... 1 200 000 [exp(-1.19)-exp(-1.78)] = 0.135
1 200 000 ... 1 600 000 [exp(-1.78)-exp(-2.37)] = 0.075
1 600 000 ... 2 000 000 [exp(-2.37)-exp(-2.96)] = 0.042
2 000 000 ... 2 400 000 [exp(-2.96)-exp(-3.55)] = 0.023
Her er en graf som sammenligner Exponential Distribution teori med den observerte fordeling av spill.
Ytelse av Pierre's algoritmen over 36 avsluttet spill
Selv om det er veldig få spill i denne datasett, er det tydelig at modellen er ganske god til å matche de observerte fordeling.
Pierre's introduksjon til hans algoritme:
Pierre startet arbeidet med en-brikke-algoritmen på 2003,1.
Pierre sendt meg en e-post om hans algoritme på 2003.4.9, rapportering følgende ytelse over 20 sammenhengende spill:
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 er implementert i Turbo Pascal og fullfører 7000 rader / min. Med en Athlon 1600+."
Jeg konverterte Pierre's algoritmen til C++ på 2003,6, etter flere e-post utveksling med Pierre. Vi bekreftet at A.I. i C++ versjon gjort samme vedtak i Pascal versjon.
Jeg observerte lignende ytelse til sin opprinnelige rapporten; gjennomsnittlig rundt 650000 ferdig rader, og noen spill som fullfører 2 millioner rader.
Utrolig!
10.2 Samtale med Pierre Dellacherie
[1] Når fikk du først opprette denne koden?
Jeg har jobbet på algoritme fra slutten av januar 2003 til nå.
[2] Hvor lenge har du jobbet på det?
Jeg jobbet på det nesten hver uke ... men ikke hverdagslig lenge fordi jeg har andre aktiviteter: dessverre har jeg å tjene penger som alle andre!
[3] Hva inspirert design av koden?
Jeg spilte Tetris 10 eller 15 år siden, men jeg hadde ikke spilt på nytt for en lang tid. Jeg vil si at jeg er en "gjennomsnittlig" spilleren som kjenner reglene og noen triks.
Men da jeg begynte å arbeide på algoritmen jeg ikke spille så mye fordi jeg fant var det snarere mer effektive for å se datamaskinen spille og analysere hans svakheter.
[4] Visste du bruker automatisering til å "trene" koden din til å utføre bedre? Visste du har tilbakemeldinger for å forbedre algoritmen?
Eller fikk du bare se på resultatene og bestemme seg for å gjøre endringer?
Jeg er fra "gamle skolen:" Jeg bare så på resultatene og besluttet å gjøre endringer.
"Automatisk læring" er en type meta-algoritmen, slik at jeg ikke er sikker på at du gjør det på denne måten vil få lettere som denne meta-algoritmen må være bygget for, og det er ikke så enkelt!
Hva mer, jeg er enig med Roger Penrose når han sier (i sin bok "Shadows of the mind") som menneskelig forståelse og intuisjon kan ikke være algoritmisk (eksempel: beregning).
[5] Når fikk du først begynner å spille Tetris, og når fikk du ideen om å løse Tetris med en A.I.?
Jeg underviser i algoritmer og programmering (Turbo Pascal og Scilab) for studenter som trener for inngangen eksamen på sivilingeniøren's skoler.
Ved første, "Computer spiller Tetris" var en idé jeg ønsket å utvikle for min neste års studenter.
Jeg var ikke klar over websiden din når jeg begynte å arbeide på algoritmen.
Faktisk var jeg heldig å være oppmerksomme på websiden din bare noen få uker siden, fordi jeg tror jeg ville ha blitt forbitret av resultatene dine (som du kan gjette, de tidlige versjonene av mine algoritmen ikke spille så bra!).
[6] Hva er din nåværende status?
Jeg er nesten 30 [før 2003 27 apr]. Jeg har flere aktiviteter: Jeg er en cellist, jeg skriver musikk og jeg undervise i programmering.
Jeg har en master-grad i musikkvitenskap (1994) og en "Artificial Intelligence and Algorithmic" diplom (1998).
I Frankrike denne prisen tilsvarer den 5 års studier ved University (4th år er master-/cand.scient.-grad og 6te år er avhandlingen).
Pierre's komposisjoner:
[7] Hvor du bor?
Jeg er fransk og jeg bor i Rouen (Normandie).
[8] Andre kommentarer:
Etter hvert har jeg ikke noen ny idé å forbedre den.
Jeg har prøvd så mye unyttig (og dum) ting som jeg tviler på det kan forbedres.
På den annen side, jeg tror det kan finnes helt forskjellige algoritmer som kunne ha bedre forestillinger.
Ved måte, en raskere test består i lanseringen av bitene i en halv boks (10 rader X 10 kolonner) i en halv-boksen min algoritmen gir et gjennomsnitt på 280 fullførte rader.
One more thing: Algoritmen kan enkelt endres i en dobbel tråd algoritmen ([Jeg vil] testene snart).
Jeg elsker film musikk: å bli en film komponisten er en del av mine største drømmer (men det er bare drømmen!).
11. Best menneskelige spilleren i verden
11.1 Japansk Tetris Master (2001 27 januar) video
Tetris master (2001; Japan) video
Arika presenterer Japansk Tetris Finals master (2001 27 januar). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Tilbakemelding
12.1 Slashdot tråd (2003)
I 2003, min Tetris A.I. Prosjektet ble diskutert på Slashdot Internet Forum (
http://slashdot.org).
Slashdot (http://slashdot.org) Internet forum overskrift for en diskusjon av mine Tetris A.I. prosjektet
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 inspirert av mine Tetris A.I. prosjektet (2003) (første gang jeg noen gang har inspirert en humoristisk!)
Comic inspirert av mine Tetris A.I. prosjektet (2003) (andre gang jeg noen gang har inspirert en humoristisk!)
13. Historien om Tetris A.I. prosjektet
I løpet av våren 1989 ble jeg opptatt hoppe (og ikke) andre semester freshman klasser på University of Pennsylvania.
En av mine roommates, Bill Matthews, hadde Mac Classic, og noen ganger spilte videospill.
Personer som får adgang til Ivy League skoler er vanligvis tilbøyelig til å konkurrere med andre mennesker til alle tider - slik at når Bill fikk spillet Tetris for hans Mac vi umiddelbart startet en langsiktig kamp for høy score.
Som score klatret, tidspunktet investeringene som kreves for å foreta en liten gevinst dramatisk økt.
For å gjøre en lang historie kort, Bill tilsynelatende har høy skåre mellom oss, men jeg mistenker ham for å bruke ResEdit og hacking poengsummen fil!
Bill hadde klasser i Wharton School of Business, alma mater av Michael Milken og Donald Trump, så det er ikke utenkelig at noen rigged en impossibly høy score ...
I løpet av sommeren 1990 jeg lånte en 30 MHz Intel 80386 IBM PC fra mitt rom, Alex Haidas.
Jeg kjøpte en Mac tastaturet på et loppe marked for $ 1.
Jeg bygde parallell-port krets for å tillate at PC å kontrollere Mac tastaturet.
(Jeg brukte en CMOS 4040 prosessoren til å fungere som en type solid-state relé til å bli med tastaturet kontakter innenfor Mac tastaturet.)
Jeg skrev et dataprogram som brukes en beslutning treet som sin strategi for å spille spillet Tetris. På bare noen få uker hadde jeg en PC spille Tetris spillet kjører på en Mac.
Men jeg var nødvendig å bruke PC tastaturet for å fortelle A.I. om hver fallende stykke på skjermen.
Jeg begynte å jobbe på en krets ved hjelp CdS (Cadmium Sulfide) lys detektorer som ville helle mot Mac skjermen og "se" den fallende brikker, men CdS sensorer reagert for langsomt til endringer i lysstyrke og kontrast mellom Tetris stykker og bakgrunnen på Mac Classic skjermen var for lavt til å pålitelig diskriminere.
I disse dager jeg ikke har mye penger, så det var for risikabelt å kjøpe en $ 2 Radio Shack phototransistor som kan ikke gjøre hva jeg ville.
Også gitt kontrast problem, ble jeg pessimistisk om hele tilnærming.
Når jeg kjøpte min første personlige datamaskin i 1996, kunne jeg ikke få programvaren under Windows 95 på en 100 MHz CPU å gjøre videobehandling rask nok til å gjøre en enkel visjon systemet fungerer.
Jeg skrev image processing koden i Assembler, men det var så mye overhead før koden faktisk mottatt video data som det syntes umulig å gjøre noe verdt.
I 2003, teknologi, spesielt CPU hastighet, hadde nådd et nivå som gjorde ferdig prosjektet nesten trivielt.
Jeg gravde opp mitt gamle prosjekt, og endelig ferdig med det, får noen følelse av nedleggelse.
Det var veldig spennende å se en datamaskin spille en annen datamaskin gjennom USB videokamera og reléer.
Lyden av reléer klikke, og ser bitene spinn og slipp på latterlig, superhuman hastigheter, gjorde opplevelsen veldig tilfredsstillende i flere måte.
I 2003 arbeidet mitt ble gjenkjent av Slashdot (
http://slashdot.org), og jeg fikk mange gode tilbakemeldinger.
Jeg ble invitert til å vises på "Screen Savers" TV-show på TechTV digitale TV-nettverk.
Jeg dro til San Francisco og ble vist på messen, og opplevelsen var stor.
Senere i 2003, fikk jeg en melding fra Henk Rogers, inviterer meg til Hawaii for å møte ham og Alexey Pajitnov å snakke om å etablere en slags standard for Tetris for å ha Tetris turneringer.
En spesiell interesse var aktiverte spillere til å bruke mobiltelefoner til å "konkurrere med hverandre," indirekte, via A.I. som imiterer spillere (etter forutgående analyse av hver spillers handlinger), og dermed unngår virkningene av mobil tilgang til Internett ventetid, og gjør det mulig spillere å "konkurrere mot" * Aller beste menneskelige spillere i verden (*..., eller snarere A.I. etterligne det aller beste menneskelige spillere i verden).
Jeg ble begeistret av utsiktene til å møte skaperen av Tetris. Dessverre, flyvende gjør meg engstelig, og jeg avviste invitasjonen.
I 2006 var jeg konvertert min "Standard Tetris" programvare fra C++ til C# å gjøre programvaren mer tilgjengelig og nyttig for moderne programmerere.
