Tetris
Colin Fahey
1. Software
2. Uvod
U ovom se članku opisuje kako se računalo može igrati klasični video igra Tetris uz dobivanje informacija o brodu, određivanje dobra akcija, i obavljanje te radnje.
Ovaj članak uključuje i softver, sposoban igrati Tetris u realnom vremenu.
Softver uključuje najbolje real-time Tetris igra algoritam u javnom vlasništvu.
Ovaj članak definira pravila za "Standard Tetris," specifikacija na temelju izvorne 1986 pre-komercijalna verzija Tetris za raèunalni (PC).
U 2003, softver uključen u ovaj članak je bio koristi za uključivanje računala igrati Tetris prikazuju na posebnom računalu.
Običnog USB video kamera je koristi za uključivanje računala "vidjeti" zaslon od drugih računala.
A relej zajednica je kontroliran putem jednog sučelja RS-232 omogućiti računalu da "pritisnite tipke" na tipkovnici od drugih računala.
Ovako, prvo računalo ima odnos na drugom računalu koje je slično tipično ljudskih igrača odnos na računalu kada igrati Tetris; igre drzava je samo poznat po looking at the screen, i igrač akcija može se pokrenuti samo putem tipkovnice .
Oblik demonstracije u ovoj utvrđeno da računalo može igrati Tetris bolje od ljudskih, pod normalnim real-time igrati Tetris uvjetima.
3. Povijest Tetris
U 1985, Alexey Pajitnov i Dmitry Pavlovsky računala su inženjeri na Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre od Russian Academy of Sciences
Alexey i Dmitry su zainteresirani za razvoj i prodaju zarazna računalnih igara.
Oni su testirani iz nekoliko različitih igara.
Alexey je bio nadahnut grčkog puzzle game, Pentaminos, koja je obuhvaćala organiziranje puzzle komada od pet kvadrata.
Alexey mislio na ideju o uređenju Pentamino komada kao i oni padoše u jednom pravokutnom čašu, ali shvatio da je dvanaest različitih pet kvadratnih oblika su previše složen za video igre.
Alexey prebacili na korištenje sedam "tetramino" komada, svaka sastavljena od četiri kvadrata.
U 1985.6, Alexey Pajitnov programirana prva verzija Tetris na Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov, i Tetris.
U 1985-1986, Vadim Gerasimov, 16-godišnjaka high-school računalo čudovište koji je radio na Akademiji, provodi Tetris za IBM PC trčanje MS-DOS operacijski sustav.
(Vadim Gerasimov kasnije je istraživanje na MIT Media Laboratory, od 1994 do 2003, nakon primitka dr.sc. popunjavanju mnogo zanimljivih projekata:
http://vadim.www.media.mit.edu)
Uvođenje ekrana od 1987-1988 pre-commercial release of Tetris za PC
Igra igrati ekrana od 1987-1988 pre-commercial release of Tetris za PC
Nakon 1987, Tetris proširila diljem svijeta.
The Tetris Company, LLC, vlasnik je Tetris zaštitni znak.
4. Projekti inspirirani Tetris
4.1 0-dimenzionalan Tetris
Not yet developed.
4.2 1-dimenzionalan Tetris
Ziga Hajdukovic je razvila 1-dimenzionalan Tetris softver koji se može igrao u Internet pregledniku.
Ziga Hajdukovic je također razvila 1-dimenzionalan Tetris softvera za mobilne telefone pomoću Java J2ME platforme.
4.3 2-dimenzionalan Tetris
Sve konvencionalnog Tetris varijante su u ovoj kategoriji.
Ovo poglavlje sadrži zanimljive varijante.
4.3.1 Najveća Tetris igra ikad: Delft University of Technology (1995)
Tetris igara na zgradi; 2000 m^2 površine; Delft University of Technology (1995)
Tetris igara na zgradi; 2000 m^2 površine; Delft University of Technology (1995)
4.3.2 Drugi Tetris igra igrao na zgradi: Brown University (2000)
Tetris igra prikazana pomoću svjetla u prozorima na zgradi u Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
"Mislim da je upravo najviše nevjerojatne jednodnevni što sam mogao zamisliti u moj život. Kao i uvijek, rekao je Steve Jobs, put je nagrada."
"To me mislite o projektima nismo u koledž. Stvari koje su bile gotovo undoable da drugi ljudi ne bi misliti radiš."
Steve Wozniak (2000)
4.3.3 Internet preglednik igra s MIT "Green Building" image
Vadim Gerisimov's Internet preglednik Tetris
Ovaj internet preglednik Tetris varijanta je izrađen od strane Vadim Gerasimov.
Ovaj internet preglednik Tetris features je "Green" zgrada na kampusu u MIT.
Ova varijanta Tetris samo je devet stupca, umjesto standardnog deset stupaca.
Ova varijanta Tetris predstavlja novi komada sa slučajnim usmjerenja.
Vadim Gerasimov je osoba koji je napisao računalo kod za PC verzija Tetris u 1986.
Vadim Gerasimov je dr.sc. istraživanja na MIT Media Laboratory tijekom 1994-2003, radite na mnogo zanimljivih projekata.
4.3.4 PIC16F84 12 MHz mikro-based NTSC / PAL video Tetris igra
PIC16F84 12 MHz mikro-based NTSC / PAL video Tetris igra
Slika iznad pokazuje NTSC / PAL video output produced by jednom PIC16F84 12 MHz sklop izvodi softver je napisao / la Rickard Gunee u 1998.
Video signal se generira softver kontrolu digitalnog izlaza.
4.3.5 "Scopetris" osciloskop Tetris by Lars Pontoppidan (2007.8)
"Scopetris" osciloskop Tetris by Lars Pontoppidan (2007.8)
Lars Pontoppidan napisao kod za AtMega32 mikro, i dodao jednostavan analogni strujni krugovi, kako bi izradili Tetris verziju da bi se igrati na osciloskop.
Neke se prijavljuje na AtMega32 mikro kontrole 8-bitni izlaz signala, i, kada je prolazio kroz "R-2R" električnih otpora sklop za digitalno-analogna pretvorba (D/A), rezultirajući analogni signali mogu kontrolirati (x,y) koordinate osciloskop jedan snop (kada je osciloskop postavljena na "X-Y mod)."
YouTube video:
FLV video:
4.3.6 Obfuscated code Tetris: C / Unix
Sljedeći je bio nagrađen "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 Obfuscated code Tetris: Perl code
Sljedeći je Tetris za Perl tumača: Perltris (verzija 20050717) by 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) je standard za opisuje grafički objekti pomoću XML.
Mozilla SVG Tetris: Tetris provodi pomoću Scalable Vector Graphics (SVG) opis
4.3.9 Google "widget" Tetris
Google, Yahoo!, i Microsoft, i druge tvrtke, imaju unaprijeđen minijaturne Internet-baziran softver pod nazivom "widgets" koje su obično karakterizira neke korištenje dinamičke podatke dostupne na internetu.
Jedan takav widget dostupni kroz Google je Tetris igra.
Sljedeći primjer je slatka, ali je oblika okretati u dosadnih načina:
Google "widget" Tetris
Ostalo Google widgets:
4.3.10 MIT istraživački rad: "Tetris is Hard, Even to Approximate" (2002)
Sljedeće istraživanje dokument sadrži dokaz da određene vrste Tetris varijanta je "NP-kompletna."
Erik D. Demaine, Susan Hohenberger, i David Liben-Nowell, "Tetris is Hard, Even to Approximate", Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
"NP-kompletna" je klasifikacija u vrijeme i prostor cijene troškova algoritam.
Ostale klasifikacije uključuju "P" i "NP".
A classification of "NP-kompletna" implicira da je za probleme veće od neke male veličine, algoritam je vjerojatno da bismo pronašli željeni rješenja u praktične vremena ili prostora.
4.3.11 Istraživanje dokumenta: "Applying reinforcement learning to Tetris"
Sljedeći rad, objavljen 2005.5.30, Donald Carr na Computer Science odjela na Rhodes University, South Africa, predstavlja primjenu "armature učenje" Tetris.
4.3.12 Tetris skut (2007.11)
Tetris skut (2007.11)
The Tetris suknja je izrađen od strane "Lucy" ("hissyfitoly" na etsy.com) prije 2007.11.
Od kreator je opis skut (ponuđena na prodaju na 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 komentare vezane uz ovu suknju:
"Čovjek koji skut sisanje i Tetris"
"Ahahahaha, mislio sam na istu stvar."
"Tu je kompletna linija dolje na dnu ... dovršene linije nestaju." "UČINITI VIŠE OD" "."
"Ima bi trebao biti mjesto u leđa ispred ili gdje dugo komad bi savršeno uklapaju ..."
"To je stvarno ružan iako suknje. Moj dragi nije mogao da kupi mi dovoljno čokolade i cvijeća da me uvjeriti da nose da stvar."
4.3.13 Tetris stage act (2007.4)
Tetris stage act (2007.4)
"Od onih koji vas je doveo Triforce u 2006 ... Dolazi sljedeću generaciju mrtav objekt komad ... Tetris."
Lokalno spremljeni video-u Flash video (FLV) format (VLC koristiti za reprodukciju):
4.3.14 Vrlo smiješan Tetris varijacije na japanskom televizijski show
Tetris varijacije na japanskom televizijski show
Ovaj video segment iz japanske televizije show uključuje vrlo smiješan varijacije Tetris, uključujući:
komada da nula na slijetanje, dio koji ispunjava cijeli red (tako da kompletirate red na slijetanje), više komada istodobno pada, irregularly shaped komada, dugo komad da je malo previše širok da stane u gap (sprečavanje 4-red završetak!), Mario tipku jednom gljiva i postaju ogromne i umiranje!, mali komad krhotine preostale nakon reda su uništene, naviše gravity izrade komada plutati na vrhu, itd.
Lokalno spremljeni video-u Flash video (FLV) format (VLC koristiti za reprodukciju):
4.3.15 "The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
"The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
Od opis na YouTube:
"TETRIS igrati real-ljudskih bića sjedi u auditorijem:"
TETRIS je 4 video performanse od GAME OVER Project, u režiji švicarskog umjetnika Guillaume REYMOND (NOTsoNOISY kreativna agencija).
To stop-motion video je pucao i igrao za "LES URBAINES" festival
http://www.urbaines.ch u Palais de Rumine (Lausanne, Švicarska) na November 24th 2007.
Lokalno spremljeni video-u Flash video (FLV) format (VLC koristiti za reprodukciju):
4.3.16 2,5-dimenzionalan Tetris
Izraz "2.5-dimenzionalan" ovdje se koristi da se označe ne-ortogonalna pogled na jedan dvodimenzionalni verzija Tetris, sa nekim debljina u trećoj dimenziji.
(Pronađite poveznicu "tetris3d" u "F7: GAMES".)
4.4 3D Tetris
Linux / GTK verzija
Trodimenzionalni Tetris u obliku jednog Java applet za Internet browseri:
Trodimenzionalni Tetris za Windows operacijski sustav:
4.5 4-dimenzionalan Tetris
Greg Kaiser's "HyperTetris" (1996): 4-dimenzionalan Tetris
U [1996], [...], Greg Kaiser staviti zajedno s četiri dimenzije varijanta na klasične igre.
Korištenje IrisGL (a.k.a. igl) stvorio je radni, ako je teško igrati, igra pomoću četiri pod-screens da prikazuju različite trodimenzionalni aspekte cijeli igra-prostor.
[Zbog] tamo nije lako [razumljiv] način privući četiri-D predmeta na dva-D zaslon, četiri pod-pregleda su praktične metode za upravljanje i zamišljati vrtnja i prijevod na komade kroz četiri dimenzije ( u igri zove x,y,z,w).
Nego kompletiranje linije blokova kao u originalu, na cilj u tom slučaju je popuniti potpuni kub u x,y,z subview (obično 4 do 4 po 4).
Drugi subviews koji sadrže "w" dimenziju su uređeni u zadanom 4 po 4 do 10 blok dogovoru s "w" budući da je dugo, "vertical" dimenzija u sva tri slučaja, s različitim bazama (x,y), (x,z), (y,z).
Gravity djela u "-w" smjeru, tako da komadi padaju "dolje" u tri duge subviews koji uključuju "w", i osim ako se ne krecu po igraču kontrolu u posljednjih (x,y,z) subview.
Potrebno je neko vrijeme da bi se, da kažem najmanje.
Ako neko čudo od strpljenje ili mijenjate parametre igre, jedna radi dovršetka kocka, ona će nestati kao dovršene linije učiniti u izvornoj Tetris, iako ne rezultat je zadržao u HyperTetris.
Benjamin Bernard (2000)
4.6 N-dimenzionalan Tetris
Polytope Tetris (2003): N-dimenzionalan Tetris igra varijanta
Polytope Tetris je n-dimensionally Tetris.
Inspirirani su HyperTetris program, Polytope Tetris omogućuje Vam tona igrati Tetris u bilo koje BROJ dimenziju.
Play Tetris u 3D, 4D, 5D, ili više.
HyperTetris je mnogo catchier ime od Polytope (ret) Tetris, ali ne mogu ukrasti ime.
5. "Standard Tetris" specifikacija
5.1 Uvod
Definicija "Standard Tetris" je jedna idealizirati model od najznačajnijih karakteristika i ponašanja od prvih IBM-PC implementacija od Tetris igra (oko 1986-1988).
The idealizirati model temelji se na inferring je jasno namjere, razvijen od strane od prvih IBM-PC implementacija od Tetris igra.
Na primjer, čini se razumnim da se zaključiti da je razvijen od strane od prvih IBM-PC implementacija od Tetris igra je namjeru da odaberete oblik svakog novog pada komad "nasumično," i da je upotreba u Borland C implementacija od rand() funkcija je samo praktičan usklađivanje namjerom.
Definicija "Standard Tetris" navodi da je u obliku svaki novi dio je padala biti odabrana "nasumično."
Ovo idealno ponašanje ne može se postići bilo koju implementaciju, ali implementacija može približan idealno ponašanje.
Iako se ne može savršeno implementirati implementacije definicija "Standard Tetris," ideala "Standard Tetris" uključivati objektivne karakteristike, i implementacija može biti u odnosu prema njihovu relativnu blizinu ideala "Standard Tetris."
Ovo poglavlje opisuje skup elemenata, ponašanja i pravila, koja, kolektivno, definirati "Standard Tetris."
5.2 Standard Tetris board
Upravni odbor je grid i stanice, vlasništvo 10 stupaca i 20 redaka, za ukupno 10 * 20 = 200 stanice.
Standard Tetris zajednica (10 stupaca, 20 redaka)
Svaka stanica može biti nezauzet (prazna) ili zauzete (full).
5.3 Standard Tetris komada
Postoji sedam (7) standard Tetris komada, sa sljedećim slovo imena:
{ O, I, S, Z, L, J, T }
U pismu imena su inspirirani su oblika i komada.
Sedam komada Standard Tetris i njihovih "usmjerenja"
The dot at (0,0) poklapa se s zajednica položaj (6,20) kada se pojavljuje prvi dio.
Prvi stupac prikazuje početne "orijentacije."
U sljedećem, riječ "orientation" se koristi za opisivanje bilo koje stanje komad, unutar skupa dopušteno država, koje mogu rezultirati iz suprotno kazaljci sata smjenjivanje događaja.
Promjena "orijentacije" iz određenog "orijentaciju" jednog "I, S," ili "Z" komad, zahtijeva kombinaciju od rotacije i prevođenje.
Dakle, riječ "orientation" is used here to znači nešto više od same rotacije.
Međutim, "orijentacije" može promijeniti samo u odgovoru na suprotno kazaljci sata smjenjivanje događaja, i ciklus različita "usmjerenja" za svaki komad approximates, ili utakmice, ciklus proizišli iz čiste rotacije.
Posebne upotrebe riječi "orijentacije" u tom kontekstu je gotovo ekvivalentan na značenje riječi ili "rotation angle," ali riječ "orijentaciju" se koriste umjesto "rotacije" će pokušati dovesti pozornost na činjenicu da neke dijelove zahtijevaju više od rotacija za izradu set dozvoljeno države rezultat suprotno kazaljci sata "rotation" događanja.
Komada može se prebaciti samo ORIJENTACIJE (ili podvrgnut određeni horizontalni ili vertikalni prijevod) ako je rezultat stanja u kom ne bi bilo koji zauzete (full) stanica izvan područja na ploči i ne bi bilo koji okupiranom stanice koje preklapaju bilo koji od trenutno zauzete stanice na brodu.
(U ovom pravilu, u okupiranom (full) stanice u kom se ne smatraju kao dio "trenutno zauzete stanice od board"
U sljedeće komentare, bilo kakve reference na rezultat je suprotno kazaljci sata rotation događaj je sklopio s pretpostavkom da takva zapravo rotacija može biti izvedena, s obzirom na postojeće uvjete u komadu i zajednica.
The "O" (box) komad samo je jedan orijentaciju, i ne mijenja bilo koje lokacije svojih okupiranih (full) stanice kao odgovor na bilo koje suprotno kazaljci sata smjenjivanje događaja.
The "I" (line) komad ima dvije moguće orijentacije, u početku se pojavljuju u horizontalne orijentacije.
The "I" komad zamjenika između dva usmjerenja u odgovoru na uzastopnim suprotno kazaljci sata smjenjivanje događaja.
The "S" i "Z" komada svaki ima dvije moguće orijentacije.
Ovi komadi svaki alternativni između dva usmjerenja u odgovoru na uzastopnim suprotno kazaljci sata smjenjivanje događaja.
The "L", "J", i "T" komada svaki ima četiri moguće orijentacije, usmjerenja i ove su rezultati jednostavne rotacije točke oko središta na oblike.
Kada se pojavi prvi dio na ploči, komad ima svoje "glavne osi" u horizontalnom orijentacijom, a dio je na vrhu ploče.
Stoga, nema komada u početku su sposobni da njihova promjena usmjerenja. The komad mora se spuštamo po jedan redak da ima mogućnost da svojim promjena orijentacije.
Nakon što je jedan komad pao po jedan red na brodu, sve komad orijentacije može biti dosegnut (uz pretpostavku je komad nije preblizu na strani zidova ili na trenutnu gomila komada).
5.4 Standard Tetris u dijagramu toka
Sljedeći je približan dijagram toka za Standard Tetris igra.
Približan dijagram toka za Standard Tetris igra
Približan dijagram toka za Standard Tetris igra
5.5 Standard Tetris komad stvaranje
Sljedeći dijagram prikazuje (4 stanica cell * 2) područje na ploči gdje svi komadi se pojaviti kada stvoreno.
Regija komada gdje se pojavljuju kada kreirana u Standard Tetris
Kada se pojavi novi dio prvi na brodu, njegova podrijetla poklapa s dot na ovaj dijagram, te dio će biti u potpunosti sadržane su u hladu na ovom prostoru dijagramom.
Kada je počela nova igra, puna free-fall kašnjenje elapses, i na prvom free-fall iteracija komad je spawned na vrhu ploče.
Tijekom normalne igre igrati, kada određeni free-fall iteracija komad "zemljišta," full free-fall kašnjenje elapses i na sljedećoj free-fall iteracija komad je spawned na vrhu ploče.
Kada je komad spawned, tip je komad odabrali koristeći sljedeći algoritam:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Budući da je konstantna p (= 1/7) priliku i odabirom određene vrste komad, i sve dijelove istog tipa su indistinguishable, vjerojatnost da točno k komada određenog tipa nakon n suđenja slijedi jedan binomna razdioba:
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 )
Kada smo birati između 7 (sedam) komada na slučajan, vjerojatnost dobivanja određeni dio je p=(1/7).
Ako smo to učinili n=70 puta, na primjer, vjerojatnost dobivanja točno k komada (s k u rasponu 0 da n) je dobio po binomna distribucija, kao što je prikazano u sljedećoj slici.
Binomna raspodjela za n=70, p=(1/7)
Dakle, može se predvidjeti prosjeku ukupno komada jedan tip dao ukupan broj slučajnih komada, a može se također izračunati očekivane varijanca i standardna devijacija (kvadratni korijen varijance):
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
Kada smo Pretvorba slučajnih vrijednosti na komad indeks, mi ga interpretirati kako slijedi:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[Pre-komercijalni MS-DOS verzija Tetris koristi slučajnog broja funkcija koje nude se Borland Pascal prevodilac.
Da se funkcija koristi 32-bitni drzava varijable.
Stoga, slijed slučajnih brojeva je ograničena na 2^32 različite vrijednosti.
Zato, u principu, jedan igrač mogao otkriti, nakon pada mozda 10 komada, točno mjesto u set 2^32 brojevima koji odgovaraju trenutno stanje u igri.
Ako Tetris simulacije su pogubljeni s fiksnom slijed 2^32 komada, zatim optimalne odluke mogu naći na svakom mjestu u slijed.
(Ima činiti se biti dovoljno mogućnosti da se na brodu na potpuno prazan zajednica drzava, dopuštajući nam da se sinkronizirati s precomputed optimalno rješenje put.)
Rizika pomoću jednostavnog slučajnog broja generatora u simulaciji namjerava naći optimalno rješenje za problem je da je optimalno rješenje će se samo za određeni put kroz problem prostora odabranih od strane Jednostavan slučajni broj generatora. ]
5.6 Standard Tetris kontrola
Tijekom igre igrati, sljedećih ulazi su na raspolaganju:
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
Svi ulazi stupiti na snagu na ustajanje-rubu je pozitivno ono što se umeće (pritisnite na gumb, za razliku gumb izdanje).
Kada pritisnete gumb pojavljuje, to broji kao jedan zahtjev.
Holding gumb dolje izvan određenog vremena može rezultirati u "auto-ponoviti" značajka tipkovnicu, stvaranja novih gumb preše - ali ovo je priča za vanjske igra motor.
Ulazi u skladu s gore naveden originalni Tetris igra.
Zakreni zahtjeva se izvršavaju ako ne postoji preklapanje između željenu orijentaciju i postaviti stanica na trenutnu pansion (izuzev pada komad), i ako željenu orijentaciju nema postaviti stanica izvan područja board.
Prevedi zahtjeva se izvršavaju ako ne postoji preklapanje između prevedene željenu konfiguraciju i skup stanica na trenutnu pansion (izuzev pada komad), i ako željeni preveden konfiguraciji nema postaviti stanica izvan područja board.
Ulazni zahtjevi su obrađeni s čekanja da ovisi o frame rate od igre (primjer: 75 Hz), i zahtjeva stupiti na snagu (ako je valjana) odmah.
A komad može biti odbačene bez linija pada korake pojavio.
A komad može biti preveden nekoliko puta na lijevo ili desno, te nakon toga pao, sve bez pojavljuje jedan službeni line pada korak.
Budući da je novo spawned dio ne može se zakrenuti moguće (jer je zaglavi na vrhu ruba ploče), igrač mora prihvatiti barem jedan dio pada korak ako rotacije su željenu ili zahtijeva.
Utjecaj na rezultat je beznačajan.
5.7 Standard Tetris komad "slijetanje"
Ako dio je jednostavno pada, ona pada po jedan red za vrijeme svaki komad pada iteracija.
Tu će biti jedna iteracija da se miče se s mjesta, bez kontakta s horizontalnim površinama na mjesto koje je kontakt s horizontalnim površinama. Kad se to ponavljanje se pojavljuje, u kom se odmara u kontakt.
Ako iteracija počinje sa komad odmara u kontakt s horizontal surface, komad "zemlje," te postaje dio statička gomila.
5.8 Standard Tetris "linije dovršen"
A dovršen red je red na kalup u kojem sve stanice su zauzete. Kada je dovršen red je eliminiran iz gomila, i redaka iznad eliminira red pomaknut su smanjena je za jedan red kako bi se uklonili jaz, to broji kao dovršen "line."
Kada jednom komadu zemljišta postaje dijelom Pile.
Odmah nakon komad zemljišta, Pile je označeno za dovršen redaka, i sve su završile redaka eliminira.
Do četiri reda može biti dovršen istovremeno.
U sljedećoj tablici daje gornji limit na linijama dovršen istovremeno po jednog komada:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Standard Tetris "razinama"
Standard 10 Tetris ima poteškoća razinama, broji 1 (jedan) kroz 10 (deset), s razini 1 se "najmanje teško."
Razini indeks je maksimalno dvije vrijednosti:
actualLevel = max( initialLevel, earnedLevel );
The initialLevel vrijednost je razini da je igrač odabire kada starta nova igra.
The pattern of razini kao funkciju dovršene linije je jednostavno promatraju u pre-komercijalni MS-DOS verzija 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
Ovako, earnedLevel vrijednost je kompjutorska prema sljedećim algoritmom:
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 pada iteracija kašnjenje
Standard Tetris ima real-time kašnjenje između sukcesivnih line free-fall ponavljanje da je funkcija trenutnog poteškoća razini.
Sljedeći odnos između razina indeksa i pad iteracija kašnjenje je na temelju ponovljenih mjerenja Zadaci na svim razinama od pre-komercijalni MS-DOS verzija 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
Tako smo uspostavili sljedećih formula za iteracija kašnjenje vrijednosti kao funkcija stvarne razine indeksa:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Ako je zajednica je prazna, i nema korisničkim podacima, spawned komad u stvarnoj razini 1 zemljama u oko 10 sekundi, a spawned komad u stvarnoj razini 10 zemljama u oko 1 drugi.
5.11 Standard Tetris "rezultat"
Standard Tetris samo nagrade bodova za čin slijetanja komad.
Nema bodova dodijeljenih za čin dovršite jedan redak, ili završavanjem dva, tri ili četiri linije istovremeno.
[Napomena: Neke od varijanti Tetris nagrada bodova za čin kompletiranje linije, s jedne exponentially povećanje udjela u dobiti za sve veći broj istovremeno dovršene linije.
Dakle, strategija za maksimiziranje rezultat u takvoj varijanti od Tetris uključuje postavljanje mogućnosti da biste "dobili Tetris," slangu za korištenjem "I" oblik da bi četiri linije i simultano uzimajući puno bodova. ]
Ako imate prazan odbora, i neka vam ne-"I" komad napraviti slobodno pada i zemlju, ili se odmah ispadne ne-"I" komad, možete uspostaviti sljedeće točke grafikon pomoću pre-komercijalni MS-DOS verzija 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, non-"I" komada pada ukupno 18 redaka.
Ova račune za bod razlike između slobodnog pada i instant-drop slučajevima.
By eksperimentiranje s intermediate slučajevima je lako zaključiti sljedeće točke formula:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Imajte na umu da ova formula je ništa za napraviti sa udaljenost komad padne!
To je strogo jedna funkcija stvarne razine, a kazna za broj ponavljanje komad je dozvoljeno da slobodno pada.
Ovaj korisnik kažnjen za siromaštvo vremena da misle.
Također, imajte na umu da zbog dio ne može se zakrenuti u početku, kada je prvi spawns, jedan igrač je kažnjen od strane najmanje jedan free-fall iteracija ako ophodnje su dužni da se komad u kalup.
To vjerojatno nikad ne utječe na ljudski igrači, osim ako se nekako: prepoznati dio, prijevod pritisnite tipke "(lijevo" ili "desno)," pritisnite tipku "okretati se" jedan ili više puta, i pritisnite tipku "drop," sve u roku od manje od 0.5 sekundi na razini 1, ili manje od sekunde 0.05 na razini 10.
6. Standard Tetris strategija
6.1 Uvod
A strategija za Igranje igre ovisi o pravilima igre.
A strategija ovisi o tome koji parametar je moguće je optimirati.
U standardnom Tetris, jedan preživi po dovršenju reda, dobiva bodove za slijetanje komada, a rezultate je moguće najviše bodova za svaki komad čije pad prije nego što jedan ili više free-fall ponavljanje znojiti.
An A.I. može optimizirati dodjeljuje bodove za svaki komad jednostavno odlučivanje o kretati brzo i "pritiskom tipke" na izvršenje potez.
Još jedna važna A.I. je opstanak, jer neodređeno opstanak znači jedan samovoljno high rezultat može biti dosegnut. Zbog toga Tetris komada pada na određenu stopu, A.I. mora donositi odluke koje najmanje ovaj brzo - i A.I. moraju napraviti poteze koji potpunu redaka na rate da prosjeci najmanje 1 redak po 2,5 komada. (Svaki dio ima 4 stanice, a svaki red ima 10 stanica.)
Naravno može se odgoditi popunjavanju redova po gomilajućim komada i izgradnju velikih naslaga, ali ima samo 200 stanica na cijeloj ploči, koji u načelu mogu držati samo 50 komada, tako da bilo koji player (kao što je jedan A.I.) moraju imati linijama kao kompletiranje temeljni prioritet.
U standardnom Tetris, igra drzava uključuje current board okupacije i trenutnog pada komad (vrsta, položaj, te orijentaciju). Igra drzava svibanj, opcionalno, uključite "Next Piece".
6.2 An izmjenične slijed "S" i "Z" komada
Heidi Burgiel, Ph.D., od Department of Mathematics, Statistics and Computer Science na University of Illinois at Chicago, je dokazao da je izmjenična slijed "S" i "Z" komada će snagu standard (10-column, 20-red) Tetris igra do kraja u roku od predvidivog broja od poteza.
Citat iz članka: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Associated tiskani članak: Mathematical Gazette, srpanj 1997, "How to Lose at Tetris"
Heidi Burgiel nudi Java applet da radi u jednom internet preglednik koji značajke jednog altered Tetris klon da spawns izmjenične "S" i "Z" komada.
[The "Standard Tetris" softver vezan uz dokument ste čitanje također ima modu koji spawns izmjenične "S" i "Z" komada. ]
Heidi Burgiel tvrdio da igra uključuje izmjenične "S" i "Z" komada (za standardni Tetris odbora od 10 stupaca i 20 redaka) mora završiti prije manje od 70000 komada su pale.
Standardni softver Tetris uključeni u ovaj dokument, omogućuje osobi da igramo s izmjenične "S" i "Z" komada, i promijeniti board širina.
Lako je vidjeti da su zajednice čiji je widths COMBI cijeli broj od četiri stupca (primjeri: 4 stupce, stupci 8, 12 stupaca, itd.) može se igrao zauvijek kad komada alternativni između "S" i "Z", s Pile ne diže veći od 4 redaka. I ovo spomenuti da bude jasno da je ograničena survivability opisano u istraživanje dokument je gore spomenuto je posebno za slučaj standard Tetris odbora (sa 10 stupaca i 20 redaka).
6.3 Nerješiv dio sekvence u cjelini
Postoje cijele kategorije patoloških sekvence koje ne mogu biti preživio.
Bilo bi zanimljivo izračunati ukupne vjerojatnost nailazi igra-konačni slijed, jer bi to stavi gornja granica na uspješnost bilo koje strategije, čak i sa ponudom na znanje svih budućih komada u bilo kojem trenutku u igri.
6.4 Ukupno je moguće board konfiguracije
S obzirom da zajednica ima 10 * 20 = 200 stanice, i dao da se svaka stanica može biti samo u jednoj od dvije države (prazna ili zauzete), ukupan broj board konfiguracija mora biti manja od ili jednaka: (2 ^ 200).
S obzirom da je svaki komad dodaje 4 stanice na brodu, i svaki redak završetku eliminira 10 stanica iz odbora, broj zauzete stanice na brodu će uvijek biti još. Na primjer, (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, itd., dakle, samo pola od (2 ^ 200) board konfiguracija se može doći igrati igru.
Dakle, ukupan broj board konfiguracije je otprilike: (2 ^ 199) = 8.03469... * 10^59.
Međutim, treba isključiti iz naše ukupne bilo koji oblik koji uključuje popunjena reda, jer je popunjena reda su ukinute prije kraja svake dovršene move. Bilo koja konfiguracija s jednim ili više redaka će ispunjena kolaps u drugu konfiguraciju koja ne sadrži bilo koji popunjena reda.
Također, treba isključiti bilo koji oblik koji uključuje ne-prazni redak iznad jedno ili više praznih redaka, jer ne-prazni redak gore prazan redak će uvijek pada, i pada sve zaustavlja prije kraja svaki potez.
Svaki redak može biti u 2^10 = 1024 država, od kojih je jedan "prazan", od kojih je jedan "pune", i (1024 - 2) = 1022 od kojih su djelomično okupacijom. Mi smo izuzeli "puni" slučaju iz razmatranja.
Ako dnu je prazan redak, a zatim sve retke iznad dna red također mora biti prazan.
Ako dnu red je djelomično okupacijom, a zatim u drugom redu može biti prazan ili djelomično okupacijom.
Nastavljajući ovu analizu, možemo izračunati broj od pansion konfiguracije koje uzima u obzir izuzeća od punog reda i ograničenja na prazne retke: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), što je oko ((1022 ^ 19) * (1023)).
Ovako, mi naći preciznije procijeniti od ukupnog broja zajednica stabilna konfiguracija: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199), tj. oko 3,74% manje od (2 ^ 199) procijeniti.
Međutim, stvarni broj stabilnih, dostupni zajednica država je vjerojatno da će biti osobito niže s obzirom na činjenicu da je većina prvih redaka može biti ispunjena samo u nekoliko načina. Kao i većina prvih redova popuniti, novo generiraju dio ne može se premjestiti ili zakrenuti vrlo mnogo. To ograničava broj načina na top-najviše redaka može biti popunjena.
6.5 U principu, najbolje kretati se mogu naći na bilo kojem brodu i dio konfiguracije
Zato što mogu dobiti bilo koju od sedam komada moguće za bilo koju danu zajednica drzava, ukupan broj država igra je oko 7 * (2 ^ 199) = 5.624... * 10^60.
Zato što se, u principu, čini dubokoj potrazi za sve moguće buduće za sve moguće poteze za određenu igru države, što može imati jednu "najbolje" move povezane sa svakim igra države.
Pretpostavljamo da mi nemamo pristup u bilo koje druge informacije od trenutnog odbora i aktualna komad, pa "najbolje" znači "move koja nudi najveće šanse da udovolji naš dugoročni cilj opstanak".
Potez je samo jedan prijevod (do 10 opcija) i rotacije (do 4 odrednice), možemo jednostavno kodirati najbolji potez u jedan bajt.
Tako se, u načelu, mogli bismo obliku tablice s 10^61 entries (bytes) je rekao da nam je najbolji potez dati bilo koju zajednica drzava i aktualna kom.
Naravno, ovo je nepraktičan, kao što enumerating sve "Go" zajednice ili "Chess" zajednice je nepraktičan. Ali stvar je da postoji jedan istiniti rješenje, i tu je najbolji potez za bilo koju danu konfiguraciju. Tamo mogu biti jednako dobre poteze za određenu konfiguraciju, ali se može proizvoljno odabrati jedan potez u tom slučaju.
Mnogi igre algoritmi su stolovi da exhaustively nabrojiti sve igra drzave unutar ograničenih mogućnosti kontekstima, kao što je "otvaranje (početno) poteze" ili "end-game (final) poteza" u Chess. Možda iscrpljujući nabrajanje od Tetris gomila površina (oko (20 ^ 10) država) je moguće. To je jedna zanimljiva ideja.
Iscrpljujući nabrajanje svih država na dnu dva reda, pomnožen sa sedam komada moguće, skladištenje i najbolji potez u jedan bajt, bilo bi prilično jednostavno; zahtijevaju samo 7 MB memorije. Možda optimizirati performanse za ovih sedam milijuna slučajeva će pružiti sirovi podaci za analizu i razvoj jednostavne modele za podatke; takvim modelima mogao smatrati dio sveukupne idealan Tetris-playing strategije.
Imajte na umu da izvršavanju najbolje poteze još uvijek ne štite nas od mogućih patoloških igra-završni dio sekvenci. To je samo da ćemo uvijek izvesti poteze koje nudi nam maksimalni potencijal za budućnost opstanka dano da sve buduće komada su potpuno slučajan (i nepoznata u to vrijeme smo se odlučiti kako se kretati jedan trenutni poznat komad).
6.6 Real-time performance
Jedan ograničenje suočavaju neke strategije algoritmi je potrebno za real-time performance - što znači da je algoritam mora donijeti odluku u roku od određenog vremena.
Kada ljudskih igra Tetris, komada ne prestanu padati dati igraču priliku da misle. To je dio izazov Tetris. Ovako, jedan A.I. sustav koji je značilo da simuliraju ulogu ljudskog igrača moraju donositi odluke na rate po diktiraju Tetris igra.
6.7 Redak i dio ukupne
Imajte na umu da u dugoročne, broj komada pao je u neposrednoj blizini 2.5 puta broj završenih reda - jer svaki redak ima 10 stanica, i svaki komad je 4 stanice, i mi moramo dovršiti za redom, u prosjeku, jednom svaka (10/4) = 2.5 komada pao.
Tako bismo mogli koristiti "dovršen redaka" i "pao je komada" gotovo zamijeniti s odgovarajućim konstanta proporcionalnosti. Najveća pogreška je kada je zajednica je u potpunosti popunjena, osim za jednu prazninu u svaki redak (((10*20)-20)/4) = 45 komada pao, a deficiency of predviđeni (45/2.5) = 18 dovršen redaka.
6.8 Trenutni-komad (i pansion) strategije
Ako mi samo dopustiti A.I. imati znanje o trenutnom odbora i trenutne komadu, i mi gledamo samo na rezultat premještanja trenutne komad posebno načine, onda se to zove "jednom komadu" analiza.
Ovo je grubi skeč o tome kako na jedan komad analiza može odlučiti na potez u Tetris:
Trenutni-komad analiza jednog Tetris igra drzava
Uglavnom smo isprobati sve moguće poteze i odabrati potez koji donosi najbolji rezultat.
U teškim dio je rating svaki rezultat.
Mi moramo ocijeniti zamišljena igra drzave prema tome kako dobro takve drzave podržava naše kratkoročne i dugoročne ciljeve.
Naš dugoročni cilj je opstanak. Opstanak ovisi o sprječavanju Pile iz overflowing odbora. Možemo smanjiti Pile visina formiranjem kompletne redaka koji se zatim eliminira iz Pile.
Da se formira kompletna red, moramo stati dijelovi komada u svakom stupcu tog reda. Ovako, mi zahtjevamo od svih dijelova za redom biti izložena do pada komada, ako smo na kraju popuniti cijeli redak.
Ako iz nekog razloga mi se cover empty dijelovi za redom po komada na bilo koji viši red, onda smo sada u mogućnosti ispuniti u onim dijelovima u prazan redak. Jedini način (uz pretpostavku nije klizni) za pristup tim "pokopali rupa" je uklonio retke iznad koje su dijelovi djelujući kao prepreke.
Sljedeći čimbenici su među onima koje možete koristiti da biste ocijenili danom zajednica drzava:
Overall pile height
Što je veći kalup, što je još gore naše situacije čini se da je, zato što smo bliže overflowing odbora.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
The rougher Pile, vjerojatnije je da će biti teško ispuniti sve je ugrađen kompleks konture kao i oni postati izlo `ene površine.
Number of buried empty cells
Što više rupa smo pokopali, što je još gore stanje je naš, jer mi moramo otkriti rupa pokopana prije nego što može dovršiti odgovarajuće retke.
Možete zamisliti druge čimbenike koji općenito ocijeniti zamišljena zajednica o tome i njen kalup može primiti sve moguce buducnosti komada, i kako dobro izgleda situacija za sve one moguće komada.
Sljedeći problem je kako odrediti relativna važnost tih faktora.
Jedan opći pristup je sljedeći. Dodijeliti skup "težine" (relativna važnost) u tim faktorima, a zatim simuliraju brojne igre i zapis na ishod ove igre (konačan rezultat, etc). Tada, dodijeliti novi set težine i simuliranje novi niz igara. Temeljem da li ili ne novi skup ishoda igre su bolje nego prethodne set igre, znamo, ako je novi skup težine je bolje nego prethodnog seta težine.
U svoje eksperimente sam pokušao sistematskog traženja i slučajnih potrazi za dobrim težina kombinacija, ali nisam primjetiti nikakve velikih razmjera trendovima da sam mogla nastaviti. Međutim, vidio sam mnoge iznenađujuće glatka bumps. Mislio sam da je zanimljivo da je prosječna učinkovitost mogao formira glatka krivulja kada je parametar je polako varirao s druge parametre održan na neke vrijednosti kombinaciju.
The best real-time, one-piece Tetris algoritam u svijetu, created by Pierre Dellacherie (Francuska) u 2003, duguje mnogo od svoje uspjehe na svojim skup mjerenja (ili mjerenja). Finding težine, kada je potrebno optimizirati strategiju, ali je također kritično za početak s vrste mjerenja koja otkrivaju relevantne karakteristike države.
Pierre Dellacherie's pronalazak novih načina za svaki karakterizira zajednica čini njegov algoritam zaista odličan, pansion karakterizacije zauzimanja strateški važne dimenzije odbora države.
Jedan mogao razviti vrlo različiti set karakterizacija dimenzije koje su funkcionirale jednako dobro, uvjeren sam da je moguće da span relevantnih zajednica drzava prostora u mnogo različitih načina na koje se može koristiti kako bi odredili strategiju funkcija. Ključ je pronaći karakteristike tog projekta državnom prostora dolje na mali broj dimenzija kojima se može razviti jednostavan rating funkcija (primjer: linearna ponderirana kombinacije karakteristika koristi Pierre's algoritam).
U jednom-Piece algoritam koristi "bot" u "xtris" softvera (1996) koju je napisao Roger Espel Llima koristi težine određuje se velikih istraživanja moguće kombinacije težinu "genetski algoritmi". Simulirane žarenje je još jedan mogući način istražiti višedimenzionalno prostoru težina kombinacije.
Čini se da, na osnovu različitih opažanja, višedimenzionalno funkcija prosječne Tetris performanse kao funkcija od težine, primjerice: F(w1,w2,w3,...), je "grubi" (mnogo lokalnih minima i Maxima), što znači da je jednostavan višedimenzionalno "brežuljku penjanje" možda neće raditi.
6.9 Strategija kada trenutni komadu, uz komad, i zajednica se zna
Ako je algoritam strategije je s obzirom na trenutne komadu, uz komad, i zajednica, a zatim ga mogu donositi odluke koje koriste kombinaciju od komada.
Poznavanje sljedeći komad može poboljšati uspjeh od igrati Tetris algoritam za nekoliko redova veličine. To je lako shvatiti kako znajući sljedeći komad čini velika razlika u strategiji.
One mogu učiniti "ludog" poteza, kao što su pokrivanje ogromna rupa, etc, jer su već znali da sljedeći dio može biti korišten za "popraviti" stanje. Ukoliko nemate znanje sljedeći dio, vi ste stalno pokušavate igrati nejednakost, pokušava da bi se mogućnosti otvoriti u narednih kom slučaju nije idealno.
Sljedeća skica pokazuje kako je sve moguće poteze u trenutnom kom se smatraju, i za svaki takav potez smatramo sve moguće poteze koji uključuju sljedeći komad.
Strategija uključuje current komad i pored komad
Tetris standardni softver koristi ovu strategiju kada je "Next Piece" je omogućen od strane korisnika i je vidljivo na zaslonu, i kada se dva-komad A.I. je omogućeno (kao što je jedan napisao me, Colin Fahey). Ako je "Next Piece" nije vidljiv na ekranu, moja dva-komad padne natrag u jednom komadu-A.I..
Moj-jedan komad A.I. je strašna kada je u odnosu na druge AIs u Standard Tetris softver, tako da to pokazuje Vam ugodnu Dodatne informacije (primjer: sljedeći komad) može biti na jednom A.I. sustav, to je dovoljno za poboljšanje performansi od svoje osrednji dva-komad A.I. nekoliko redova veličine - jednostavno nadmašuje performanse od najboljih one-piece A.I. u svijetu.
(Međutim, obraćajući najbolje jednom komadu A.I. u svijetu razmotriti dva komada bi jednostavno poboljšali je nekoliko redova veličine, previše! Poznavanje sljedeći dio je ogroman!)
Moj prvi test igra s moja dva-komad A.I. trajao otprilike 182 sati (7,6 dana) na 800 MHz PC, popunjavanju 7216290 redaka. Nisam testirao je brži algoritam na računalu.
Kada spremite stanje jednog Tetris igra (Shift-W) u tekstualnu datoteku, možete zatim kopirajte i zalijepite popis brojeva, iz odjeljka "heightHistogram", na jedan Excel spreadsheet-ovima.
Svaki bin u histogram pokazuje broj završenih poteze da je završila s određenom gomila visina (nakon potpune reda su ukinute). Kao što možete zamisliti, čini potez koji potpuno uklanja gomila je rijetka, tako da ukupni broj poteza koje završava s hrpa visine nula je relativno niska.
U međuvremenu, mogli biste očekivati da gomila visina općenito fluctuates oko neki prosjek, tako da grah koji odgovara na ove retke će dominirati na histogram. Konačno, grah za top-najviše redaka (gdje smo u opasnosti od overflowing odbora) imaju vrlo nizak iznosi.
Tijekom mnogo sati, s A.I. igrati jednu igru koristeći strategiju koja uključuje znanje "Next Piece", ja uzeo slučajnih uzoraka igra države, kopiranje Pile histograms do visine proračunske tablice kao što je prikazano u nastavku:
Pile visina histograms snimljenih na raznim punktovima u tipična igra (s trenutnim-i-next-dio strategije)
Možete razmjera svaki histogram sa ukupnim brojem komada (ukupan broj završenih poteza) da biste dobili sljedeće podatke:
Scaled histograms, i teorija
Na osobit je da ove scaled histograms izgled identičan bez obzira na različite veličine narudžbe na broj komada (završen poteza) koji su uključeni.
Just by looking at brojeve sam napravio je hipoteza da je rep od krivulja je eksponencijalna propadanja. By suđenje i pogreška sam došao gore sa sirovom teorija da je rep je opisano:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Sljedeći grafikon prikazuje histogram scaled preko cijelog raspona reda.
Graf od scaled histograms
Imajte na umu da je kriva za 50000 komada, i kriva za 2000000 komada, i krivulja u rep teorije su gotovo indistinguishable u ovom mjerilu.
Sljedeći je bliži pogled na glavu krivulje.
Donjem dijelu visina histogram
Sljedeći je uvelike-veliča pogled na ekstremnim rep kraja izmjeri i teorijskih histogram krivulje.
Povećan prikaz ekstremnim rep kraja scaled histograms
Kao što se može očekivati, to je vrlo rijetko za Pile do te visine u čak i dugo eksperimenti - ali čak i sa ograničenom dokaza u ovoj regiji ekstremnim, teorija još uvijek čini prihvatljivom.
U punoj shema u teoriji izgleda kao da se preklapaju u rep i distribuciju "točno", dok je u veliča Chart of the rep je rep, vidi se očito greška. Međutim, ja potvrditi da je to zbog nedovoljnih podataka na ovim ekstremnim hrpa visine. Ako sam povećao igru na ploči, recimo, visine od 25 redaka umjesto 20 redaka, tako da igre nisu prekinuti naglo, mislim da je teorija sam prezentirao gore bi savršeno podudarati s trend.
Moj osjećaj je da je to histogram je izravan rezultat u kombinaciji Tetris A.I. i pravila Tetris. Dakle, ova distribucija iste će biti zamijećene za bilo koji slučajni dugoročne igra Tetris koristeći moje posebno A.I. strategije za igranje s "Next Piece" znanje.
Osim toga, mislim da taj tip histogram može se koristiti za usporedbu AIs koji upotrebljavaju iste podatke dok igrate. Ovako, ne morate igrati kompletan igre (koji bi mogao trajati dana ili godina) da usporede dugoročne uspješnosti različitih strategija algoritmi.
Na primjer, unatoč jednostavnosti moj model, mislim da ga se može koristiti kako bi predvidjeli prosječna igra traje! Mi jednostavno izračunati koliko komada čini "red 21" gomila visina znatan broj, kao što je broj jedan.
The relativna učestalost za redom 21, prema mom jednostavna teorija, je:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Morate umnožiti taj broj po (5.3 * 10^(7)), oko 50 milijuna, da bi dobili vrijednošću jedan.
Ovako, ja okvirno predvidjeti da moje trenutne "Next Piece" strategije je samo dobar za po naređenju okvirno 10 milijuna dovršen redaka. Jedan od razloga ću ovom konzervativna procjena je činjenica da čak 18 redaka može biti smrtonosna za moje A.I. jer ja ne dozvoljavaju moje A.I. razmotriti komada dok se ste pali po barem jedan redak! (Ovo je tako da ne morate brinuti da ne bude u mogućnosti okretati se komada.)
Ja sam impresioniran i činjenica da igrate samo 50000 komada (i vjerojatno puno manje komada) mogu vam dati izuzetno dobre procjenu dugoročno visina histogram, i stoga, dobro procijeniti na red veličine završenih reda prije igre završava. Ovaj pristup je izuzetno vrijedna za brzo vrednovanje suptilne promjene u jednom A.I. da se već radi iznimno dobro.
6.10 Zajednica vrednovanje mjerenja nasljedovati spekulativne izgled ispred
Ako algoritam, kao što je jednom prezentirao sam s ovom projektu, jednostavno pokušava sve komad usmjerenja i prijevode za padaju, i svaka stopa je rezultat board konfiguraciju prema nekim mjera sposobnosti, algoritam je u bitnome oponašaju "izgled-naprijed".
Kada jednom zapošljava podatke kao što su "hrpa visine", "sahranjen rupa", "surface hrapavost" ili "i dubine", jedna je zaista koristeći pojednostavljeni oblik "GLEDAJTE NAPRIJED". Ove opće karakterizacije na brodu dati neke oznake za dugoročne isplativosti odbora.
Idealan pristup, dati beskonačnu količinu computing power, da bi se ocijeniti Uprave konfiguraciji sve moguće dati dio sekvence koji mogu slijediti.
Iako morate uzeti u obzir sve 7 komada kao jednako vjerojatno na svakom nivou izgled-naprijed, potreban vam da optimizirate stvarni prevođenje (do 10) i orijentacije (do 4) za svaki komad u svaki mogući slijed! To je do (7*10*4) = 280 grane na svakoj razini od procjena board! Dakle, da je do konfiguracije ((280)^(LookAheadLevels)) odbora da razmotre.
Budući da mi moramo prekinuti analizu nakon konačnih broj nivoa, potrebna nam je da su neke ne-izgled-ispred metode ocjenjivanja i zajednica drzava - način davanja vrijednosti na leaf čvorovi našeg pretraživanja stabla. Dakle, za ove leaf čvorovi, mi smo natrag pomoću formula koje embodies opće predictors budućih održivost, board!
Ova vrsta spekulacija može biti suđeno s One-Piece i dva-Piece algoritmi u mjesto od simplistic board vrednovanje mjerenja. Preuzme sve naknadne komada su jednako vjerojatno i sam se na sposobnosti na board kako bi bolje odgovarao komada svih vrsta na najbolji mogući način. To može biti izveden s jednim, dva, ili bilo koji broj spekulativne move dubinama - sa svim komada se jednako probable (p=1/7).
Terminal čvorovi ovog stabla, možda još uvijek zahtijevaju ponderirana podatke za procjenu, ali spekulativne razine točnije capture biti ono što želite učiniti: Odredite koliko dobro dano odbora može prihvatiti sve moguće dijelove, uključujući i pozitivnih faktora kao što su kompletiranje linije i negativne faktore kao što su povećanje sveukupne gomila visina, itd.
7. Tetris A.I. demonstraciju sustava
7.1 Pregled sustava
Ovaj dijagram pokazuje sljedeće moje eksperimentalne set-up.
Ukupni sustav za demonstraciju
7.2 Oprema
Ovdje je kratak popis opreme koji se koriste u ovu demonstraciju:
[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)
Jasno možete koristiti slična oprema za ispuniti iste rezultate. Više detalja u vezi sa opremom su opisane u odgovarajućim odjeljcima u ovom članku.
Evo kratki opisi osobnih računala koriste u ovom demonstraciju:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Ova demonstracije mogao lako se reproducirati s drugim operativnim sustavima, kao što su Linux. To je više važno da imaju CPU brzine na redu 800 MHz ili brži za računalo koje je izvoditi A.I. softver, jer ovo računalo će se radi real-time obradu videa.
7.3 Video capture hardver
Koristio sam čest USB video kamera kao video capture uređaj za moje A.I. sustav. Naime, sam koristio Creative "WebCam Pro", USB videokamere s 640 * 480 rezoluciji.
Creative(TM) USB video kamera opis
USB video kamera (u kut)
USB video kamera (front)
USB video kamera (pansion s CCD)
USB video kamera (glavni čipovi)
OV511 glavni blokova (napomena: USB video kamera je OV511+)
7.4 OV511 data sheet
ov511ds.pdf
OV511 Data Sheets
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "plus") značajka razlike
ov511plus_101.pdf
OV511+ Igrani Razlike
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Video capture software
Microsoft ima vrlo stare API pod nazivom "Video for Windows" (VFW) da sam uspješno koristi za ovaj projekt. (Link na "vfw32.lib" u svom C++ projekta, ili napraviti DllImport "vfw32.dll" u svom C# code.) Primjeri korištenja VFW API su široko dostupna.
Alternativa je korištenje Microsoft's "DirectShow" API učiniti video capture.
Zbog VFW je samo desetak linija koda za korištenje, a izvodi acceptably na moje 800 MHz stroj, ja ne smetaju istraživanje alternativnih APIs. Ali DirectShow je više suvremenih API za Windows video snimanje, i potencijalno donosi mnogo veći frame rate za isti hardver.
Pogledajte "CPF.StandardTetris.STVideoCapture" izvornog koda datoteke u standardnom Tetris softver da biste vidjeli kako ga je lako dobiti video capture u vlastite projekte.
7.7 Računalna sučelja za releje (preko RS232)
Da bi se jedno računalo "pritisnite tipke" na tipkovnici i drugo računalo, koristio sam "relej board" kontrolira tekst naredbe poslane od serijski komunikacijski port (primjer: "COM1") preko jednog RS-232 kabel. Koristio sam svaki relej za spajanje dvije žice za određenu tipku tipkovnice za simulaciju ključ press.
Ovo je potrebno otvaranje tipkovnice i stvaranje veze. Mnogo je lakše metode za simulacijom pritiskom na tipku na računalu, ali i ja sam htjela učiniti nešto da se činilo kao moguće zatvoriti kao osobu zaista tipkati na tipkovnici.
Jedan vrlo svestran i dobro je napravio relej zajednica je ADR2200 made by Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Možete pogledati na "CPF.StandardTetris.STRS232" izvornog koda datoteke da biste vidjeli kako ga je jednostavno poslati bytes preko serijskog porta, što može onda biti korišteni za kontrolu uređaja kao što su ADR2200 board gore.
8. Standard Tetris softver
8.1 Preuzimanje softvera
Idi na početku ovog članka da biste pronašli link za download izvornog koda (C# i C++ verzije) i gradi se softver (*.exe).
8.2 Sažetak mogućnosti
Softver značajke:
Poduka ekrana i krediti
Jednobojna mod
Shadow mod
Hint mod
Smeće redaka
Ocijenite kontrolu
Next komad
Zajednica veličini
S/Z komada
Kalibracija mod
Video capture i priznanja
Debugging konzole
Spremi igra
Učitaj igru
8.3 Početna izgled
Izgled kada je počeo program:
Izgled kada je softver je počeo
8.4 Jednobojna mod
Po defaultu je zajednica pojavljuje se u bojama:
Po defaultu je zajednica pojavljuje se u boju.
The kolor moda može biti promijenjen za monokromni (Shift + K):
The kolor moda može biti promijenjen za monokromni.
8.5 Shadow mod
Shadow način naznačiti gdje će se komad zemlje. Ovo je vrlo korisno za velike zajednice, jer je teško suditi, gdje će jedan komad zemlje.
Shadow način naznačiti gdje će se komad zemlje.
8.6 Hint mod
Hint način pokazuje gdje se trenutno odabrane-AI bi potez s obzirom na trenutnu situaciju. (Shift + H)
Hint način pokazuje gdje se trenutno odabrane-AI bi potez.
8.7 Smeće redaka
Insert "junk" redaka na dnu Pile, jednog po jednog, ručno. (Shift + J)
Insert "junk" redaka na dnu Pile.
8.8 Ocijenite kontrolu
The '+' (plus) i '-' (minus) tipke za kontrolu brzine igre.
Po defaultu, igra pokreće u standardnom brzinom, u skladu s pravilima Standard Tetris (brzina na temelju razini).
Tu je stol od značenja za brzinu prednapon:
-3,-4,...: sporost proporcionalnu prednapon
-2: sporije od razine 1
-1: normalan, ali su ograničene na razini 6 (0,2 sec) brzine;
0: normal; Standard Tetris kontrolu brzine;
+1: malo brže nego na razini 9 (0.05 sec odgode);
+2: omeđen pružanje stopa (primjer: 75 Hz);
+3,+4,...: više ponavljanje po izvedenih okvir;
Volim izvoditi A.I. i postavka "+2" (hit '+' ključ dva puta, ako prednapon počinje na nulu).
Speed prednapon mijenja brzinu igre.
8.9 Prikaži sljedeći komad
Hit 'N' to toggle "Next Piece" display. The A.I. će se koristiti "Next Piece" informacije samo ako "Next Piece" se pojavljuje na zaslonu.
Možete biti sigurni da se AI ne koristi "Next Piece" informacije kada se ne može vidjeti "Next Piece" na zaslonu.
Prikaži sljedeći komad
8.10 Zajednica veličini
Pritisak Ctrl + (lijevo, desno, dolje, gore), može se prilagoditi na ploči veličine do proizvoljne veličine od 4 * 4 do 200 * 400.
Zajednica size: 4 * 8
Zajednica veličina: 20 * 40
Zajednica veličina: 40 * 80
Zajednica veličina: 20 * 5
Zajednica size: 4 * 100
8.11 S/Z komada samo
Studija je zanimljiva izmjenične S/Z pattern.
Ovaj uzorak se ne može naći rješenje za 10 * 20 pansion (širina * visina).
Ipak, zajednice koje su widths da su COMBI od 4 su prikazane na trivially dozvola infinite opstanak.
The AIs preživjeti indefinitely u tim slučajevima, iako oni nisu bili posebno podešen da obrađuju ovu patoloških stanja.
S/Z komada samo
8.12 Video mjernim mod
Hit 'C' za ulazak u "Kalibracija Mode". Kada u mjernim način, možete pogoditi broj tipki: {1,2,3,4,5,6,7} odaberite jedan komad {O,I,S,Z,L,J,T} na vrhu se igrati board.
To je korisno kao referencu za slike, video capture na drugi Standard Tetris softver.
Ako ostvario 0 (nula) ključ, to će učiniti na ploči prazan.
Možete se pretvarati da spawn komada odabirom komad (1..7), a zatim odabirom prazno (0), a drugi računalo radi video capture za Satovi komada.
Možete pokrenuti A.I. na drugom računalu i vidjeti kako se bavi sa svojim ručno unijeli patoloških Tetris scenarija!
Mode kalibracije je samo vrijeme možete rukovati video capture obrada slike predloška (4 * 2 grid). Možete koristiti miša zahvatiti u pravokutnik, a zatim možete koristiti tipke kursor ( "up", "dolje", "left", "pravo") da su u redu kontrola granica - koristeći Shift tipku kako bi izabrali nasuprot granica od pravokutnika (primjer: "Shift-left" kombinirani razlikuje od "left").
Video mjernim mod
8.13 Video capture i priznanja
Pritisak 'V' toggles video capture načinu rada. Ako se pravilno izveden (vidi "video mjernim" u prethodnom odjeljku), komada daljinski video zaslonu će biti zarobljeni od strane video kamera i klasificiran - komada i biti će spawned u lokalnoj igra za A.I. razmotriti i reagirati .
The A.I. izlaz mora zatim biti odaslani (preko RS-232 sučelje u demonstraciju opisanog u ovom članku) na daljinskom igra ono što se umeće (primjer: keyboard) za A.I. uspješno igrati na daljinskom igra.
Ako u bilo koje vrijeme ovo zatvorena petlja je poremećen (primjer: video capture nepravilnost u radu, ili izlazni signal kvara), onda će razviti A.I. krivi dojam status daljinskog igra, i učinit će A.I. neprikladno odluke koje brzo gube igru .
(Napomena: Ovaj se problem može biti prevladana sa skromnim iznosu od napora: A.I. sustav je potrebno samo pregledati cijeli daljinski Tetris zaslon za ongoing "reality check" za cijeli odbora, i A.I. sustav bi trebao biti pripremljen za neki output naredbi na fail u neki način.)
Video capture i priznanja
9. Izvorni Tetris AI eksperiment (2003)
Sljedeće pokazuje da je prva radna verzija od Tetris A.I. sustava u 2003.
Video kamere okrenut računala # 1 prikazivati bilo koji običan Tetris igra
Računalna # 2 prikazivati Standard Tetris softver u A.I. mod
Lijevo: Crtanje mreža za priznavanje kalibrirati video snimke;
Desno: Tetris komad priznavanje predmeta.
Okvir od video i Tetris A.I. eksperiment u 2003
10. Best jednom komadu Tetris igra algoritam u svijetu
10.1 Pierre Dellacherie (2003, Francuska)
Pierre Dellacherie (2003, Francuska), razvijen od najboljih one-piece Tetris igra algoritam u svijetu
The best-jedan komad, real-time Tetris algoritam s mojim znanje je stvoreno po Pierre Dellacherie Francuske.
Njegov zapanjujući algoritam ponekad ispunjava više od 2 milijuna redaka!
Prosječna učinkovitost je na redu 650000 redaka.
The algoritam uzima vrlo malo memorije, i pokreće na velikom brzinom (oko 160 redaka u sekundi na mom 800 MHz računalo).
Nastup Pierre Dellacherie's algoritam:
Moj trenutni model za izvedbu Tetris AIS je da je za bilo koju danu komad ima stalna vjerojatnost da će igru prekinuti, p.
Dakle, vjerojatnost da komad neće prekinuti igru je q=(1-p).
Vjerojatnost igra završava nakon k poteza je jednostavno proizvod je vjerojatnost preživjelih (k-1) poteze, naime q^(k-1), i vjerojatnost je krajnji na sljedeći potez, naime p.
Ovo se odnosi na "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 )
Za male p, ln(q) je grubo (-p), i imamo sljedeće:
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 )
Očekujemo u djeliću ukupan broj odigranih igara raskida s nekoliko redaka dovršen u interval [k1, k2] biti:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Nakon završene 36 igara na mom računalu, tijekom razdoblja od dva dana, ja postaviti prosječno 674827 dovršen redaka.
Prema opće teorije gore, ja bi se očekivati sljedeće relativna djeliću igre do kraja dovršen u sljedećim redom rasponi:
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
Ovdje je graf koji uspoređuje Exponential Distribution teorija s promatranom distribuciju igara.
Nastup Pierre's algoritam preko 36 završene igre
Iako ima vrlo malo igara u ovom set podataka, što je jasno da model je prilično dobra i odgovara promatranom distribuciju.
Pierre's uvod u njegov algoritam:
Pierre započeli rad na ovom jednom komadu algoritam na 2003,1.
Pierre poslao mi e-mail o njegovoj algoritam na 2003.4.9, izvještavanje sljedeće performanse preko 20 uzastopne igre:
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.
"Algoritam je implementiran u Turbo Pascal i dovrši 7000 redaka / min. S Athlon 1600+."
I pretvaraju Pierre's algoritam za C++ u 2003,6, nakon nekoliko e-mail razmjene s Pierre. Mi provjerio da A.I. u C++ verzija je napravio isto odluke o Pascal verzija.
Sam promatrao sličnih performansi u njegovu izvornom izvješće; prosjeku oko 650000 dovršen redaka, i neke igre u dovršenju 2 milijuna redaka.
Incredible!
10.2 Razgovoru sa Pierre Dellacherie
[1] Kada ste prvi stvoriti ovaj broj?
Ja sam bio radi na algoritam sa krajem januara 2003 do sada.
[2] Koliko dugo ste radili na njemu?
Sam radio na njemu skoro svaki tjedan ... ali ne dugo jer svakodnevnom sam druge aktivnosti: nažalost moram zaraditi novac kao i bilo tko drugi!
[3] Što je inspiriran dizajn koda?
Sam igrao Tetris 10 ili 15 godina, ali sam igrao opet ne za dugo vremena. Rekao bih da sam ja jedan "prosječni" igrač koji zna pravila i neke trikove.
Međutim, kad sam počeo raditi na algoritam nisam igrati toliko, jer sam našao je prilično učinkovitije gledati na računalu igrajući i analizirati njegove slabosti.
[4] Da li ste koristiti bilo koji automatizacije na "vlak i" svoj kod na bolje? Da li imate bilo kakve povratne informacije za poboljšanje algoritma?
Ili ste jednostavno promatrati rezultate i odlučiti izvršiti izmjene?
Ja sam iz "stare škole:" jednostavno sam gledao rezultate i odlučili izvršiti izmjene.
"Automatsko učenje" je vrsta meta-algoritam tako da nisam uvjereni da se radi na taj način bi se lakše kao meta-ovog algoritma bi trebala biti izgrađena je i da nije tako jednostavno!
Što je više, ja činim slažete sa Roger Penrose kad je riječ (u svojoj knjizi "Shadows of the mind") da je ljudski razum i intuicija ne može biti algoritam (primjer: izračunljiv).
[5] Kada ste prvi početi igrati Tetris, a kad je imate ideje o rješavanju Tetris s A.I.?
I naučiti algoritam i računalno programiranje (Turbo Pascal i Scilab) za studente koji vlak za ulazak na diplomski ispit inženjer u školama.
U početku, "Računalna igra Tetris" je ideju i ja sam htjela da se razvije za moje iduće godine studenti.
I nije bio svjestan svoje web stranice, kada sam počeo raditi na algoritam.
Zaista sam sretan biti svjesni svoje web stranice samo nekoliko tjedana, jer mislim da bih se discouraged by svoje rezultate (kao što ste mogli pogoditi, ranim verzijama moj algoritam ne igraju tako dobro!).
[6] Koji je vaš trenutni status?
Ja sam gotovo 30 [prije 27 Travanj 2003]. Imam nekoliko aktivnosti: Ja sam cellist, ja sam nova glazba i naučiti računalo programiranje.
Imam specijalisticki studij muzikologije (1994) i "Artificial Intelligence and Algorithmic" diploma (1998).
U Francuskoj ovu diplomu odgovara 5 godine studira na Sveučilištu (4 godine je specijalisticki studij i 6 godina je rad).
Pierre's kompozicije:
[7] Gdje živite?
Ja sam francuski i ja živim u Rouen (Normandija).
[8] Ostali komentari:
Na kraju nisam nikakve nove ideje za poboljšanje.
Pokušao sam toliko beskoristan (i blesav) stvari koje sam sumnjam da bi se moglo poboljšati.
S druge strane, mislim da tamo možda postoje potpuno različite algoritme koji bi mogao imati bolje nastupe.
Usput, brži test sastoji se u pokretanje komada u pol-box (10 redaka x 10 stupaca): u pol-box, moj algoritam čini prosjek od 280 završile redaka.
Još jedna stvar: algoritam se može lako mijenjati u dvokrevetnoj-prometovati algoritam ([ću] testovi uskoro).
Volim film glazba: postaje filmski skladatelj je dio moje snove glavni (ali to je samo san!).
11. Najbolji igrač u ljudskom svijetu
11.1 Japanski Tetris Master (2001 sječnja 27) video
Tetris gospodar (2001, Japan) video
Arika predstavlja Japanski Tetris Finale gospodar (2001 sječnja 27). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Povratna informacija
12.1 Udarac nit (2003)
In 2003, moj Tetris A.I. Projekt je raspravljano na Slashdot Internet forum (
http://slashdot.org).
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 ]
Strip inspiriran mojim Tetris A.I. projekta (2003) (prvi put sam ikad inspirirao strip!)
Strip inspiriran mojim Tetris A.I. projekta (2003) (drugi put sam ikad inspirirao strip!)
13. Povijest je Tetris A.I. projekta
U proljeće 1989 bio sam zauzet preskakivanje (i nije)-drugi semestar brucoš nastava na University of Pennsylvania.
Jedan od mojih roommates, Bill Matthews, imao je Mac Classic, a ponekad i igrali video igre.
Ljudi koji bi priznao da Ivy League škole su obično inclined se natjecati s drugim osobama u svako doba - pa kad je dobio Bill igru Tetris za njegovu Mac, odmah smo počeli dugoročno borbi za visok rezultat.
Kao rezultate uspona, u vrijeme ulaganja potrebna da bi mali dobitak dramatično porasla.
Za izvršenje ne duljimo, Bill navodno ima visok rezultat između nas, ali sam se sumnja da ga koristite ResEdit i sjeckanje rezultat datoteku!
Bill je nastava u školi Wharton poslovanja, alma mater od Michael Milken i Donald Trump, tako da nije nezamisliv da netko rigged jedan impossibly high score ...
U ljeto 1990 sam jedan 30 MHz Intel 80386 IBM PC posuđene iz mog sustanarom, Alex Haidas.
Ja kupio jedan Mac keyboard buha na tržištu za $ 1.
Ja izgrađena na paralelnom portu strujni krugovi kako bi se omogućilo je PC za kontrolu Mac keyboard.
(Ja iskorišten CMOS 4040 čip djelovati kao vrsta čvrste države relej za pridruživanje keyboard kontakte unutar Mac tipkovnici.)
Ja napisao je računalni program koji koristi odluku stabla kao svoje strategije za igranje igre Tetris. U samo nekoliko tjedana sam PC igrajući igru Tetris prikazivati na Mac.
Međutim, sam je bio dužan da se koriste PC tipkovnica za reći o A.I. svaki komad pada na zaslonu.
Sam počeo raditi na sklop pomoću CdS (Cadmium Sulfide) detektora svjetlosti da bi lean protiv Mac zaslonu i "vidi" pada komada, ali CdS senzori previše sporo reagirali na promjene u svjetlina i kontrast između Tetris komada i pozadine na zaslonu Mac Classic bila je preniska da bi pouzdano diskriminirati.
U one dane nisam imati mnogo novca, tako da je previše rizično kupiti $ 2 Radio Shack phototransistor da ne bi mogli raditi ono što sam htjela.
Također, s obzirom na kontrast problem, bio sam pesimistički o cijelom pristup.
Kad sam kupila svoju prvu osobnih računala u 1996, ne bih mogao dobiti softver pod Windows 95 na 100 MHz CPU učiniti video obrada dovoljno brzo da napravi jednostavnu viziju rada sustava.
Sam napisao obrada slike kod u asemblerski jezik, ali tamo je toliko nadzemne pred moj broj zapravo primio video data to činilo nemoguće učiniti ništa isplatiti.
In 2003, tehnologija, posebno CPU brzinu, je dostigla razinu da se napravi dorada projekta gotovo trivijalan.
Kopao sam gore moj stari osobni projekt i konačno dovršio ga, uzimajući neke smislu zatvaranja.
Bilo je vrlo uzbudljivo vidjeti na jednome računalu igrajući drugo računalo putem USB video kamera i releji.
Zvuk i releji klikom, i promatranje komada spin i ispustite na komičan, superhuman brzinama, vrlo je napravio iskustvo u zadovoljavanju multisensory način.
In 2003, moj posao je bio sankcionisan Slashdot (
http://slashdot.org), i dobio sam dosta veliku povratne informacije.
Sam bio pozvan da se pojavi na "Screen Savers" televizijski show na TechTV digitalnih televizijskih mreža.
Sam otišao u San Francisco i pojavio se na show, i iskustvo je veliko.
Kasnije u 2003, dobio sam poruku od Henk Rogers, pozivaju me na Havajima mu u susret i Alexey Pajitnov da razgovaraju o uspostavi neki vrsta od standard za Tetris, za potrebe vlasništvo Tetris turnirima.
Jedan posebnoga interesa je omogućavanje igrača da koriste mobilne telefone kako bi "se natjecati međusobno," indirektno, preko A.I. da imitira igrača (analiza prije svakog igrača akcije), te na taj način izbjegavajući efekti mobilni telefon Internet pristup čekanja, i omogućujući da se igrači "natječu protiv" * Najboljih ljudskih igrača u svijetu (*... ili, pak, A.I. oponašaju najbolje ljudskih igrača na svijetu).
Bio sam thrilled by buduće sastanka i kreator Tetris. Nažalost, čini mi leti uznemiren, i sam odbio poziv.
In 2006, I pretvaraju moje "Standard Tetris" softver iz C++ da C# da softvera više dostupni i korisne suvremenoj programera.
