Tetris
Colin Fahey
1. Software
2. Inleiding
Dit artikel beschrijft hoe een computer kunt spelen de klassieke videospel Tetris door krijgen informatie over het bestuur, het bepalen van goede acties, en de uitvoering van deze acties.
Dit artikel bevat software die in staat is tot het spelen van Tetris in real time.
De software bevat de beste real-time Tetris-algoritme spelen in het publieke domein.
In dit artikel worden de regels voor „Standard Tetris,“ een specificatie gebaseerd op de originele 1986 pre-commerciële versie van Tetris voor de Personal Computer (PC).
In 2003, de software opgenomen in dit artikel werd gebruikt om een computer te spelen Tetris draaien op een aparte computer.
Een gewone USB video camera werd gebruikt om de computer te „zien“ op het scherm van de andere computer.
Een relais boord werd gecontroleerd via een RS-232 interface om de computer te „drukken toetsen“ op het toetsenbord van de andere computer.
Zo, de eerste computer heeft een relatie met de tweede computer die vergelijkbaar is met een typisch menselijke speler relatie tot een computer bij het afspelen van Tetris, het spel staat is alleen bekend door te kijken naar het scherm, en de speler acties kunnen alleen worden gestart door een toetsenbord .
De configuratie in deze demonstratie vastgesteld dat een computer kunt spelen Tetris beter dan een mens, onder normale real-time Tetris spelen.
3. Geschiedenis van Tetris
In 1985, Alexey Pajitnov en Dmitry Pavlovsky zijn computer ingenieurs van de Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre van de Russian Academy of Sciences
Alexey en Dmitry geïnteresseerd waren in het ontwikkelen en verkopen van verslavende computerspelletjes.
Zij getest op een aantal verschillende spellen.
Alexey is geïnspireerd op de oude Griekse puzzelspel, Pentaminos, die betrokken zijn bemiddeling puzzel stukjes gemaakt van vijf pleinen.
Alexey denken van het idee van het organiseren van Pentamino stukken omdat ze in een rechthoekige kop, maar realiseerde zich dat de twaalf verschillende vijf vierkante vormen zijn te ingewikkeld voor een video game.
Alexey overgeschakeld op het gebruik van zeven „tetramino“ stuks, elk gemaakt van vier pleinen.
In 1985.6, Alexey Pajitnov geprogrammeerd de eerste versie van Tetris op een Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov, en Tetris.
In 1985-1986, Vadim Gerasimov, een 16-jarige high-school computer Prodigy die werkte aan de academie, uitgevoerd Tetris voor de IBM PC draait de MS-DOS besturingssysteem.
(Vadim Gerasimov later deed onderzoek op het MIT Media Laboratory, van 1994 tot 2003, het ontvangen van een Ph.D. na voltooiing van tal van interessante projecten:
http://vadim.www.media.mit.edu)
De invoering van het scherm 1987-1988 pre-commerciële versie van Tetris voor de PC
Het spel spelen scherm van de 1987-1988 pre-commerciële versie van Tetris voor de PC
Na 1987, Tetris verspreid over de hele wereld.
The Tetris Company, LLC, is eigenaar van het handelsmerk Tetris.
4. Projecten geïnspireerd door Tetris
4.1 0-dimensionale Tetris
Nog niet ontwikkeld.
4.2 1-dimensionale Tetris
Ziga Hajdukovic heeft ontwikkeld 1-dimensionale Tetris software die kunnen worden afgespeeld op een Internet-browser.
Ziga Hajdukovic heeft ook 1-dimensionaal Tetris software voor mobiele telefoons met behulp van de Java J2ME platform.
4.3 2-dimensionale Tetris
Alle klassieke Tetris-varianten zijn in deze categorie.
In deze sectie wordt het interessant varianten.
4.3.1 Grootste Tetris game ooit: Delft University of Technology (1995)
Tetris gespeeld op een gebouw; 2000 m^2 oppervlakte; Delft University of Technology (1995)
Tetris gespeeld op een gebouw; 2000 m^2 oppervlakte; Delft University of Technology (1995)
4.3.2 Een ander Tetris-spel gespeeld op een gebouw: Brown University (2000)
Tetris game weergegeven met behulp van de verlichting in de ramen van een gebouw op Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
„Ik vind het alleen maar de meest indrukwekkende van een dag dat ik kon denken in mijn leven. Net als Steve Jobs altijd gezegd, de reis is de beloning.“
„Het deed me denken aan projecten die we nog terug op de universiteit. Dingen die zich vrijwel ongedaan worden gemaakt dat andere mensen niet zou doen denken.“
Steve Wozniak (2000)
4.3.3 Internet browser spel met MIT „Green Building“ afbeelding
Vadim Gerisimov's internet browser Tetris
Deze webbrowser Tetris variant is gemaakt door Vadim Gerasimov.
Deze webbrowser Tetris functies „Green“ het gebouw op de campus van MIT.
Dit Tetris variant heeft slechts negen kolommen in plaats van de standaard tien kolommen.
Dit Tetris variant presenteert nieuwe stukken met een willekeurige richting.
Vadim Gerasimov is de persoon die schreef de computer code voor de PC versie van Tetris in 1986.
Vadim Gerasimov heeft Ph.D. onderzoek op het MIT Media Laboratory tijdens 1994-2003, werkt op vele interessante projecten.
4.3.4 PIC16F84 12 MHz microcontroller-based NTSC / PAL video Tetris game
PIC16F84 12 MHz microcontroller-based NTSC / PAL video Tetris game
De afbeelding boven toont de video-uitgang NTSC / PAL geproduceerd door een PIC16F84 12 MHz microcontroller draait software geschreven door Rickard Gunee in 1998.
De video-signaal wordt gegenereerd door software controle van de digitale uitgangen.
4.3.5 „Scopetris“ oscilloscoop Tetris door Lars Pontoppidan (2007.8)
„Scopetris“ oscilloscoop Tetris door Lars Pontoppidan (2007.8)
Lars Pontoppidan schreef code voor de AtMega32 microcontroller, en de toegevoegde eenvoudige analoge schakelingen, voor het maken van een Tetris versie die kunnen worden afgespeeld op een oscilloscoop.
Sommige registers van de AtMega32 microcontroller controle 8-bit output-signalen, en, wanneer door een „R-2R“ elektrische weerstand circuit voor de digitaal-naar-analoog conversie (D/A), de daaruit analoge signalen kunt de (x,y) coördinaten van een oscilloscoop balk (wanneer de oscilloscoop is ingesteld op „X-Y modus).“
YouTube video:
FLV video:
4.3.6 Obfuscated code Tetris: C / Unix
Het volgende werd toegekend „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
Het volgende is Tetris voor de Perl tolk: Perltris (versie 20050717) door 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) is een standaard voor het beschrijven van grafische objecten met behulp van XML.
Mozilla SVG Tetris: Tetris uitgevoerd met behulp van een beschrijving Scalable Vector Graphics (SVG)
4.3.9 Google „widget“ Tetris
Google, Yahoo!, en Microsoft, en andere bedrijven, hebben bevorderd miniatuur op internet gebaseerde software genaamd „widgets“ dat zijn doorgaans gekenmerkt door enkele gebruik van de dynamische gegevens die beschikbaar zijn op het internet.
Een van die widget beschikbaar via Google is een spel Tetris.
Het volgende voorbeeld is schattig, maar de vormen draaien in vervelende manieren:
Google „widget“ Tetris
Andere Google widgets:
4.3.10 MIT onderzoek papier: „Tetris is Hard, Even to Approximate“ (2002)
Het volgende onderzoek document bevat een bewijs dat een bepaald soort Tetris variant is „NP-compleet.“
Erik D. Demaine, Susan Hohenberger, en David Liben-Nowell, „Tetris is Hard, Even to Approximate“, Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
„NP-compleet“ is een indeling van de kosten tijd en ruimte kosten van een algoritme.
Andere indelingen behoren „P“ en „NP“.
Een indeling van „NP-complete“ impliceert dat, voor de problemen groter zijn dan enkele kleine omvang is het algoritme is het onwaarschijnlijk dat het vinden van een gewenste oplossing in een concreet bedrag van tijd of ruimte.
4.3.11 Onderzoek document: „Applying reinforcement learning to Tetris“
De volgende papier, gepubliceerd 2005.5.30, door Donald Carr op het Computer Science-afdeling van het Rhodes University, Zuid-Afrika, presenteert de toepassing van „reinforcement leren“ om Tetris.
4.3.12 Tetris rok (2007.11)
Tetris rok (2007.11)
Tetris De rok is gemaakt door „Lucy“ („hissyfitoly“ op etsy.com) vóór 2007.11.
Van de maker van de beschrijving van de rok (te koop aangeboden op 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 opmerkingen over deze rok:
„Een man die rok zuigt op Tetris“
„Ahahahaha, ik dacht dat het hetzelfde.“
„Er is een complete lijn vast aan de onderkant ... afgesloten lijnen verdwijnen.“ „DOEN OVER“ „.“
„Er moet een plek in de rug of de voorzijde waar lange stuk zou perfect passen ...“
„Dat is echt een heel lelijke rok al is. Mijn vriendje niet kon kopen mij genoeg chocolade en bloemen te overtuigen mij om te dragen dat ding.“
4.3.13 Tetris stadium treden (2007.4)
Tetris stadium treden (2007.4)
„Van degenen die geleid heeft u de Triforce in 2006 ... Komt de volgende generatie van levenloze object skit ... Tetris.“
Lokaal-cachegeheugen video in Flash video (FLV)-formaat (gebruik VLC te spelen):
4.3.14 Hilarious Tetris variaties op een Japanse tv-show
Tetris varianten op Japanse tv-show
Deze video segment van een Japanse tv-show bevat hilarische varianten van Tetris, waaronder:
stukken die verdwijnen bij de landing, een stuk dat vult een hele rij (dus de voltooiing van een rij bij de landing), meerdere stuks tegelijk vallen, onregelmatig gevormde stukken, een lang stuk dat is iets te groot om te passen in een kloof (het voorkomen van een 4-rij voltooiing!), Mario raken een paddestoel en steeds enorm en sterven!, klein stukje van brokstukken die resteren na rijen worden vernietigd, stijgende ernst maken van stukken vlotter naar de top, enz.
Lokaal-cachegeheugen video in Flash video (FLV)-formaat (gebruik VLC te spelen):
4.3.15 „The Original Human TETRIS Performance by Guillaume Reymond“ (2007.11)
„The Original Human TETRIS Performance by Guillaume Reymond“ (2007.11)
Uit de beschrijving van YouTube:
„TETRIS gespeeld door echte menselijke wezens-vergadering in een auditorium:“
TETRIS is de 4e video prestaties van de GAME OVER Project, geregisseerd door de Zwitserse kunstenaar Guillaume REYMOND (NOTsoNOISY creatief bureau).
Deze stop-motion video werd neergeschoten en speelde voor „LES URBAINES“ festival
http://www.urbaines.ch op het Palais de Rumine (Lausanne, Zwitserland) op November 24th 2007.
Lokaal-cachegeheugen video in Flash video (FLV)-formaat (gebruik VLC te spelen):
4.3.16 2.5-dimensionale Tetris
De term „2.5-dimensionale“ wordt hier verstaan een niet-orthogonale oog van een twee-dimensionale versie van Tetris, met enkele dikte in de derde dimensie.
(Zoek de link „tetris3d“ in „F7: GAMES“.)
4.4 3-dimensionaal Tetris
Linux / GTK versie
Driedimensionale Tetris in de vorm van een Java applet voor Internet-browsers:
Driedimensionale Tetris voor de Windows besturingssysteem:
4.5 4-dimensionale Tetris
Greg Kaiser's „HyperTetris“ (1996): een 4-dimensionale Tetris
In [1996], [...], Greg Kaiser samen een vier-dimensionale variant op het klassieke spel.
Met behulp van IrisGL (a.k.a. igl) hij een werkgroep, zo hard te spelen, game met vier sub-schermen te tonen verschillende driedimensionale aspecten van de hele game-ruimte.
[Door] is er niet een gemakkelijk [begrijpelijke] weg te trekken vier-D objecten op een twee-D-scherm, de vier sub-standpunten zijn een praktische manier te manipuleren en te visualiseren, rotatie en vertaling van de stukken door de vier dimensies ( in het spel genaamd x,y,z,w).
In plaats van de voltooiing van lijnen van blokken zoals in het origineel, het doel is in dit geval in te vullen een complete kubus in de x,y,z subview (meestal 4 bij 4 bij 4).
De andere subviews die de „w“ dimensie zijn ingedeeld in een standaard 4 bij 4 met 10 blok regeling met „w“ wordt de lange, „vertical“ dimensie in alle drie de gevallen, met verschillende grondslagen van (x,y), (x,z), (y,z).
Zwaarte handelingen in de „-w“ richting, dus stukjes „vallen“ in de drie lange subviews die „w“, en niet verplaatsen, tenzij door de speler de controle in de laatste (x,y,z) subview.
Het duurt even wennen aan, op zijn zachtst gezegd.
Als door een wonder van geduld of het wijzigen van de parameters van het spel, heeft een complete een kubus, zal verdwijnen als de afgesloten lijnen doen in de originele Tetris, maar geen gast is gehouden in HyperTetris.
Benjamin Bernard (2000)
4.6 N-dimensionale Tetris
Polytope Tetris (2003): een N-dimensionale spel Tetris variant
Polytope Tetris is n-qua afmetingen Tetris.
Geïnspireerd door de HyperTetris programma, kunt u Polytope Tetris ton Tetris spelen in ieder AANTAL dimensie.
Speel Tetris in 3D, 4D, 5D, of meer.
HyperTetris is een veel catchier naam dan Polytope (def) Tetris, maar ik kan niet stelen van de naam.
5. „Standard Tetris“ specificatie
5.1 Inleiding
De definitie van „Standard Tetris“ is een geïdealiseerde model van de belangrijkste kenmerken en gedragingen van de eerste IBM-PC uitvoering van het spel Tetris (circa 1986-1988).
De geïdealiseerde model is gebaseerd op afgeleid van de zichtbare bedoelingen van de ontwikkelaars van het eerste IBM-PC uitvoering van het spel Tetris.
Zo lijkt het redelijk te concluderen dat de ontwikkelaars van het eerste IBM-PC uitvoering van het spel Tetris bestemd voor het selecteren van de vorm van elke nieuwe vallen stuk „willekeurig,“ en dat het gebruik van de Borland C uitvoering van de rand() functie was slechts een praktische aanpassing van de de bedoeling.
De definitie van „Standard Tetris“ is bepaald dat de vorm van elke nieuwe vallen stuk te worden „willekeurig“ geselecteerd.
Dit ideaal gedrag niet kan worden bereikt door een uitvoering, maar implementaties kan bij benadering de ideale gedrag.
Hoewel er geen uitvoering kan perfect de uitvoering van de definitie van „Standard Tetris,“ de idealen van „Standard Tetris“ betrekken objectieve kenmerken, en implementaties kunnen worden vergeleken op basis van hun relatieve afstand tot de idealen van „Standard Tetris.“
Dit hoofdstuk beschrijft een aantal elementen, gedrag en regels, die gezamenlijk bepalen „Standard Tetris.“
5.2 Standard Tetris boord
Het bestuur is een raster van cellen, met 10 kolommen en 20 rijen, voor een totaal van 10 * 20 = 200 cellen.
Standard Tetris boord (10 kolommen, 20 rijen)
Elke cel kan worden onbezet (leeg) of bezet (volledig).
5.3 Standard Tetris stuks
Er zijn zeven (7) standaard Tetris stukken, met de volgende brief namen:
{ O, I, S, Z, L, J, T }
De brief namen zijn geïnspireerd door de vormen van de stukken.
De zeven standaard Tetris stukken en hun „oriëntaties“
De stip op (0,0) samenvalt met raad standpunt (6,20) wanneer het stuk eerste gezicht lijkt.
De eerste kolom geeft het de eerste „richtsnoeren.“
In de volgende, het woord „geaardheid“ wordt gebruikt voor de beschrijving van de toestand van een stuk binnen een verzameling van toegelaten landen, die het gevolg kan zijn van een tegen de rotatie evenement.
Het veranderen van „richting“ van een bepaalde „oriëntatie“ van een „I, S,“ of „Z“ stuk, moet de combinatie van een rotatie en een vertaling.
Daarom is het woord „oriëntatie“ wordt hier verstaan iets meer dan de rotatie alleen.
Maar „geaardheid“ kan veranderen alleen als reactie op een tegen de rotatie gebeurtenis, en de cyclus van de verschillende „oriëntaties“ voor elk stuk benadert, of wedstrijden, de cyclus die uit pure rotaties.
De bijzondere gebruik van het woord „geaardheid“ in dit verband is nagenoeg gelijk is aan de betekenis van het woord of de „rotatie hoek,“ maar het woord „geaardheid“ wordt gebruikt in plaats van de „rotatie“ aan poging om de aandacht op het feit dat sommige stukken meer dan rotatie voor de productie van de verzameling van toegelaten staten die voortvloeien uit tegen de „rotatie“ evenementen.
Stukken kunnen alleen switch oriëntaties (of aan een specifieke horizontale of verticale vertaling) indien de resulterende toestand van het stuk niet zou hebben alle bezette (volledige) cellen buiten het gebied van de raad van bestuur en hebben zij geen bezette cellen die elkaar overlappen elk moment bezette cellen van de raad van bestuur.
(In deze regel, de bezette (volledige) cellen van de tunnel niet beschouwd als een deel van de „momenteel bezet cellen van de raad van bestuur“
In de volgende opmerkingen, elke verwijzing naar een resultaat van een tegen de rotatie geval is gemaakt met de veronderstelling dat een dergelijke rotatie daadwerkelijk kan worden uitgevoerd, gezien de huidige omstandigheden van het stuk en de raad van bestuur.
De „O“ (vak) stuk heeft slechts een enkele oriëntatie, en geen wijziging van de locaties van een van zijn bezet (volledige) cellen in reactie op elk geval tegen de roulatie.
De „I“ (lijn) stuk heeft twee mogelijke oriëntaties, die aanvankelijk in een horizontale richting.
De plaatsvervangers „I“ stuk tussen de twee oriëntaties in het kader van de opeenvolgende gebeurtenissen tegen de roulatie.
De „S“ en „Z“ stukken hebben elk twee mogelijke oriëntaties.
Deze stukken elk afwisselend twee oriëntaties in het kader van de opeenvolgende gebeurtenissen tegen de roulatie.
De „L“, „J“, en „T“ stukken hebben elk vier mogelijke oriëntaties, en deze richtsnoeren worden de resultaten van eenvoudige rotaties over punten van het centrum vormen.
Wanneer een stuk eerste gezicht lijkt op het bord, het stuk heeft een „belangrijke as“ in horizontale richting, en het stuk is aan de bovenkant van het bord.
Daarom is er geen stukken zijn in eerste instantie om te kunnen werken met hun uitgangspunten veranderd. Het stuk moet dalen door een rij te hebben aan de mogelijkheid van het oriënterend veranderd.
Zodra een stuk is gedaald door een rij op het bord, alle oriëntaties stuk kan worden bereikt (uitgaande van het stuk is niet te dicht aan de zijkanten of aan de huidige stapel stuks).
5.4 Standard Tetris stroomschema
Het volgende is een aanpassing van stroomschema voor een standaard Tetris spel.
Geschatte stroomdiagram voor een standaard Tetris spel
Geschatte stroomdiagram voor een standaard Tetris spel
5.5 Standard Tetris stuk oprichting
Het volgende diagram toont de (4 * 2 cel-cel) regio op het bord waar alle stukken verschijnen wanneer gemaakt.
Regio waar de stukken weergegeven als in Standard Tetris
Wanneer een nieuw stuk eerste gezicht lijkt op het bord, de herkomst ervan samenvalt met de stip op dit schema, en het stuk wordt volledig opgenomen door het gearceerde gebied op dit diagram.
Wanneer een nieuw spel gestart is, een volledige vrije val vertraging verstrijkt, en op de eerste vrije val iteratie een stuk is aanleiding tot aan de bovenkant van het bord.
Tijdens de normale spel spelen, wanneer een specifieke vrije val iteratie een stuk „land,“ een volledig vrije val vertraging verstrijkt en op de volgende vrije val iteratie een stuk is aanleiding tot aan de bovenkant van het bord.
Wanneer een stuk aanleiding is, het soort stuk is geselecteerd met behulp van de volgende algoritme:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Want er is een constante p (= 1/7) kans op het selecteren van een specifieke vorm van stuk, en alle stukken van dezelfde soort te onderscheiden, dan is de kans dat precies k stukken van een specifiek type na n proeven volgt een Binomiale verdeling:
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 )
Wanneer we kiezen uit de 7 (zeven) stukken willekeurig, dan is de kans op het krijgen van een bepaald stuk is p=(1/7).
Als we dit doen n=70 tijden, bijvoorbeeld de kans op het krijgen van exact k stuks (met k in de range 0 te n) wordt gegeven door de binomiale verdeling, zoals weergegeven in de volgende afbeelding.
Binomiale verdeling voor n=70, p=(1/7)
Zo kan men voorspellen van de gemiddelde totale stukken van een enkel type een aantal willekeurige stukken, en men kan ook berekenen de verwachte variantie en standaarddeviatie (vierkantswortel van de variantie):
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
Als we het omzetten van een willekeurige waarde aan een stuk index, interpreteren we het als volgt:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[De pre-commerciële MS-DOS versie van Tetris gebruikt de random number functie aangeboden door de Borland Pascal compiler.
Deze functie gebruikt een 32-bit staat variabele.
Daarom is de volgorde van de nummers willekeurig was beperkt tot 2^32 verschillende waarden.
Daarom is in principe een speler kon ontdekken, na te laten vallen misschien wel 10 stuks, de exacte plaats in de reeks van 2^32 nummers die overeenkomen met de huidige stand van het spel.
Als Tetris simulaties worden uitgevoerd met de vaste volgorde van de 2^32 stuks, dan optimale beslissingen kan worden gevonden voor elke plaats in de reeks.
(Er lijken voldoende mogelijkheden om in de raad aan een geheel leeg bord staat, waardoor we in staat zijn om gesynchroniseerd met de precomputed optimale oplossing weg.)
Het risico van het gebruik van een eenvoudige random number generator in een simulatie te vinden van een optimale oplossing voor een probleem is dat de optimale oplossing wordt alleen voor het specifieke probleem weg door de ruimte geselecteerd door de eenvoudige random number generator. ]
5.6 Standard Tetris controles
Tijdens het spel spelen, de volgende ingangen zijn beschikbaar:
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 ingangen van kracht op de stijgende-rand van de positieve inbreng (op de knop drukt, in tegenstelling tot de release-knop).
Als een knop drukt gebeurt, telt dit als een verzoek.
Holding een button down na een bepaalde tijd zouden kunnen resulteren in de „auto-herhaal“ functie van een toetsenbord, het genereren van nieuwe knop persen - maar deze functie is van buiten de game engine.
De ingangen hierboven omschreven in overeenstemming zijn met het originele spel Tetris.
Draai verzoeken kunnen worden uitgevoerd als er geen overlapping is tussen de gewenste koers en de cellen van de huidige raad (met uitzondering van de vallende stuk), en als de gewenste oriëntatie heeft geen vaste cellen buiten de raad.
Vertaal verzoeken kunnen worden uitgevoerd als er geen overlapping is tussen de gewenste vertaald configuratie en set-cellen op de huidige raad (met uitzondering van de vallende stuk), en als de gewenste configuratie vertaald heeft geen vaste cellen buiten de raad.
Input verzoeken worden verwerkt met een latency dat hangt af van de frame rate van het spel (bijvoorbeeld: 75 Hz), en de verzoeken van kracht (als geldig) meteen.
Een stuk kan worden weggelaten zonder enig lijn vallende stappen die zich voordoen.
Een stuk kan worden vertaald meerdere keren naar links of rechts, en vervolgens gedaald, zonder dat er een officiële lijn vallende stap.
Omdat een nieuw stuk was aanleiding kunnen onmogelijk worden gedraaid (want het is geplakt tegen de bovenrand van de raad van bestuur), moet de speler met ten minste een stuk vallende stap als rotaties zijn gewenst of nodig.
Het effect op de score, is te verwaarlozen.
5.7 Standard Tetris stuk „landing“
Als een stuk is gewoon vallen, komt het door een enkele rij tijdens elk stuk vallen iteratie.
Er wordt een iteratie dat beweegt hij van een plaats met geen contact met horizontale oppervlakken op een plek waar u contact opnemen met horizontale oppervlakken. Zodra dit gebeurt herhalingen worden de stukken in contact te rusten.
Als een iteratie begint met een stukje rust in contact komen met een horizontaal vlak, het stuk „land,“ en wordt onderdeel van de statische stapel.
5.8 Standard Tetris „lijnen afgesloten“
Een afgesloten rij is een rij van de stapel waarbij alle cellen zijn bezet. Wanneer een afgesloten rij wordt uit de stapel, en de rijen boven de geëlimineerd rij zijn verschoven naar een rij om een einde te maken van de kloof, telt dit als een afgesloten „lijn.“
Wanneer een pion wordt het deel van de paal.
Onmiddellijk na de pion, de paal wordt gecontroleerd op afgesloten rijen, en alle afgesloten rijen worden geëlimineerd.
Tot vier rijen tegelijk kunnen worden afgesloten.
De volgende tabel geeft de bovengrens op de lijnen, gelijktijdig door een enkel stuk:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Standard Tetris „niveaus“
Standard Tetris heeft 10 moeilijkheidsgraden, genummerd 1 (een) door middel van 10 (tien), met 1 niveau worden de „minste moeilijk.“
Het niveau van de index is de hoogste van twee waarden:
actualLevel = max( initialLevel, earnedLevel );
De initialLevel waarde is het niveau dat de speler kiest bij het starten van een nieuw spel.
Het patroon van niveau als functie van de lijnen afgerond is gemakkelijk waargenomen in de pre-commerciële MS-DOS versie van 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
Zo heeft de earnedLevel waarde wordt berekend volgens de volgende 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 vallen iteratie vertraging
Standard Tetris is een real-time vertraging tussen opeenvolgende regel de vrije val iteraties dat is een functie van het huidige niveau.
De volgende relatie tussen niveau-index en de dalende iteratie vertraging is gebaseerd op herhaalde metingen stopwatch op alle niveaus van de pre-commerciële MS-DOS versie van 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
Dus hebben we de volgende formule voor de iteratie vertraging waarde als functie van de werkelijke index:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Als het bord leeg is, en er is geen input van de gebruiker, was aanleiding tot een stuk in het werkelijke niveau 1 landt in ongeveer 10 seconden, en was aanleiding tot een stuk in het werkelijke niveau 10 landt in ongeveer 1 seconde.
5.11 Standard Tetris „gast“
Standard Tetris alleen kent punten toe voor het handelen van de aanvoer een stuk.
Er zijn geen punten voor het handelen van de voltooiing van een enkele regel, of het voltooien van twee, drie of vier tegelijk.
[NB: Sommige varianten van Tetris punten toekennen voor het handelen van de voltooiing van lijnen, met een exponentieel groeiende bonus voor een toenemend aantal gelijktijdig afgesloten.
Zo is de strategie voor het maximaliseren van gast in dergelijke varianten van Tetris brengt de instelling van de mogelijkheden „om een Tetris,“ jargon voor het gebruik van de „I“ vorm te krijgen vier gelijktijdige lijnen en krijg veel punten. ]
Als u een leeg bord, en je laat een niet-„I“ stuk doen een vrije val en land, of u onmiddellijk een daling van de niet-„I“ stuk, kunt u het volgende punt grafiek met behulp van de pre-commerciële MS-DOS versie van 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, niet-„I“ stukjes vallen op een totaal van 18 rijen.
Dit is goed voor het verschil tussen de vrije val en instant-drop gevallen.
Door te experimenteren met tussenliggende gevallen is het eenvoudig te concluderen het volgende punt formule:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Merk op dat deze formule heeft niets te maken met de afstand een stuk valt!
Het is enkel afhankelijk van de werkelijke niveau, en een boete voor het aantal iteraties een stuk moet vrij kunnen vallen.
Dit straft een gebruiker voor nodig is tijd om na te denken.
Merk ook op dat, omdat een stuk kan in eerste instantie niet worden gedraaid toen het voor het eerst spawns, een speler wordt gestraft met ten minste een vrije val iteratie als rotaties nodig zijn om een stuk in de stapel.
Dit is waarschijnlijk geen gevolgen voor de menselijke spelers, tenzij ze op de een of andere manier: herkent het stuk, druk op de vertaling-toetsen „(links“ of „rechts),“ druk op de toets „draaien“ een of meerdere keren, en druk op de „drop-toets,“ die allemaal op minder dan 0.5 seconde op niveau 1 of minder dan 0.05 seconde op niveau 10.
6. Standard Tetris strategie
6.1 Inleiding
Een strategie voor het spelen van een spel hangt af van de regels van het spel.
Een strategie hangt af van welke parameter moet worden geoptimaliseerd.
In de standaardversie Tetris, een overleeft door het invullen van rijen, krijgt punten voor de aanvoer van stukken, en scoort de meeste punten mogelijk voor elk stuk door het uitvoeren van een daling voor een of meer de vrije val herhalingen tot uiting komen.
Een A.I. kunnen optimaliseren van de punten voor elk stuk door gewoon een beslissing nemen over een snel en „op de toetsen drukken“ tot uitvoering van de verhuizing.
Meer belangrijk om een A.I. is de overleving, omdat voor onbepaalde tijd te overleven: een willekeurig hoge score kunnen worden bereikt. Omdat de Tetris stukjes vallen op een bepaald tarief, de A.I. moet beslissingen nemen ten minste deze snel - en de A.I. moeten zetten dat de volledige rijen tegen een tarief dat gemiddeld ten minste 1 rij per 2,5 stuks. (Elk stuk heeft 4 cellen, en elke rij heeft 10 cellen.)
Natuurlijk kan men uitstel van de voltooiing van rijen door de accumulatie van stukken en het creëren van een grote stapel, maar er zijn slechts 200 cellen over de gehele raad van commissarissen, die in principe alleen kan houden 50 stuks, dus elke speler (zoals een A.I.) moet beschikken over de voltooiing van lijnen als een fundamentele prioriteit.
In de standaardversie Tetris, het spel staat met de huidige bezetting boord en de huidige dalende stuk (type, plaats, en oriëntatie). Het spel staat mag eventueel ook de "Next Piece".
6.2 Een afwisselende reeks van "S" en "Z" stukken
Heidi Burgiel, Ph.D., van de Department of Mathematics, Statistics and Computer Science op de University of Illinois at Chicago, heeft aangetoond dat een wisselende volgorde van de "S" en "Z" stukken zal dwingen een standaard (10-kolom 20-rij) Tetris-spel te beëindigen binnen een voorspelbaar nummer zetten.
Citaat uit het artikel: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Associated gedrukt artikel: Mathematical Gazette, juli 1997, "How to Lose at Tetris"
Heidi Burgiel biedt een Java applet dat draait in een webbrowser die is voorzien van een gewijzigd Tetris-kloon dat spawns afwisselend "S" en "Z" stuks.
[De "Standard Tetris" software in verband met het document dat u leest heeft ook een modus die spawns afwisselend "S" en "Z" stuks. ]
Heidi Burgiel voerde aan dat een spel waarbij afwisselend "S" en "Z" stukken (voor een standaard Tetris boord van 10 kolommen en 20 rijen) moet vóór eind minder dan 70000 stuks zijn gedaald.
De Standaard Tetris software die bij dit document maakt het mogelijk om een persoon te spelen, afgewisseld met "S" en "Z" stukken, en wijzig de raad breedte.
Het is gemakkelijk om te zien dat platen waarvan de breedte zijn geheel getal een veelvoud van vier kolommen (voorbeelden: 4 kolommen, 8 kolommen, 12 kolommen, etc) kan worden afgespeeld voor altijd bij de stukken afwisselend "S" en "Z", met de stapel stijgende geen hoger dan 4 rijen. Ik zeg dit om duidelijk te maken dat de beperkte overlevingskansen beschreven in het document genoemde onderzoek is specifiek voor het geval van een standaard Tetris boord (met 10 kolommen en 20 rijen).
6.3 Onoplosbaar stuk sequenties in het algemeen
Er zijn hele categorieën van pathologische sequenties die niet kunnen worden bewaard gebleven.
Het zou interessant zijn om de totale kans te maken van een game-tot beëindiging van sequentie, omdat dit zou een bovengrens voor de prestaties van elke strategie, zelfs met volledige kennis van alle toekomstige stukken op een bepaald punt in een game.
6.4 Totaal mogelijk boord van configuraties
Gezien het feit dat de raad heeft 10 * 20 = 200 cellen, en gezien het feit dat elke cel kan alleen in een van de twee staten (leeg of bezet), het totale aantal boord configuraties moet minder dan of gelijk aan: (2 ^ 200).
Gezien het feit dat elk stuk voegt 4 cellen op een plank, en elke rij voltooiing elimineert 10 cellen van de raad, het aantal bezette cellen op het bord is altijd nog. Bijvoorbeeld, (3*4 - 1*10) = 2, (1*4 - 0*10) = 4, (4*4 - 1*10) = 6, (2*4 - 0*10) = 8, (5*4 - 1*10) = 10, etc. Dus, slechts de helft van de (2 ^ 200) boord configuraties kan worden bereikt door het spel te spelen.
Zo is het totale aantal boord van configuraties is ongeveer: (2 ^ 199) = 8.03469... * 10^59.
Maar we moeten uitsluiten van onze totale elke configuratie met gevulde rijen, omdat de rijen gevuld worden geëlimineerd vóór het einde van elk afgesloten verplaatsen. Alle configuratie met een of meer rijen gevuld zal instorten naar een andere configuratie die bevat geen enkele rijen gevuld.
Ook moeten we uitsluiten dat de configuratie bevat een niet-lege rij boven een of meer lege rijen, omdat een niet-lege rij boven een lege rij zal altijd vallen, en alle vallen stopt vóór het einde van elke beweging.
Elke rij kan worden in 2^10 = 1024 staten, waarvan er een "lege", waarvan er een "volle", en (1024 - 2) = 1022 van die deels bewoonde. Wij sluiten de "volle" geval uit te sluiten.
Als de onderste rij leeg is, dan zullen alle rijen boven de onderste rij moet ook leeg.
Als de onderste rij is voor een deel bezet, dan is de tweede rij kan leeg zijn of gedeeltelijk bewoonde.
Voortzetting van deze analyse kunnen we berekenen een aantal boord configuraties die rekening te houden met de uitsluiting van de volledige rijen en de beperkingen op de lege rijen: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), namelijk ongeveer ((1022 ^ 19) * (1023)).
Zo vinden we een nauwkeuriger schatting van het totale aantal stabiel boord configuraties: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199), dat wil zeggen, ongeveer 3,74% minder dan de raming (2 ^ 199).
Echter, het werkelijke aantal stabiel, toegankelijk boord staten wordt waarschijnlijk lager, met name te wijten aan het feit dat de top de meeste rijen kan alleen worden ingevuld op een aantal manieren. Zoals de meeste top-rijen vullen, een nieuw gegenereerde stuk niet kan worden verplaatst of gedraaid zeer. Dit beperkt het aantal manieren om de top-de meeste rijen kunnen worden gevuld.
6.5 In beginsel is de beste actie kan worden gevonden voor een stuk karton en configuratie
Want we kunnen krijgen elk van de zeven mogelijke stukken voor elk bord staat, het totale aantal spel staat is ongeveer 7 * (2 ^ 199) = 5.624... * 10^60.
Want we kunnen in principe wel een diepe zoek naar alle mogelijke futures voor alle mogelijke zetten voor een bepaald spel staat, kunnen we een "beste" verhuizen in verband met elk spel staat.
Wij gaan ervan uit dat wij geen toegang hebben tot enige andere informatie dan de huidige raad en het huidige stuk, zodat de "beste": "de verhuizing dat biedt de grootste kans op het voldoen aan onze doelstelling op lange termijn te overleven".
Een verhuizing is gewoon een vertaling (tot 10 opties) en een rotatie (tot 4 opties), kunnen we gemakkelijk het coderen van de beste verplaatsen in een byte.
Dus, in principe kunnen we vorm van een tabel met 10^61 items (bytes) vertelde ons dat de beste actie gegeven elk bord staat en de huidige stuk.
Uiteraard is dit onpraktisch, net als alle opsomt "Go" boards of "Chess" boards is onpraktisch. Maar het punt is dat er een echte oplossing, en er is een goede zet voor een bepaalde configuratie. Er zou een even goede stappen voor een bepaalde configuratie, maar we kunnen willekeurig kiezen voor een enkele beweging in die zaak.
Veel game-playing algoritmen hebben tabellen die uitputtend te sommen spel staat alle mogelijkheden binnen de beperkte context, zoals "opening (eerste) zetten" of "end-game (definitief) beweegt" in Chess. Misschien uitputtende opsomming van Tetris stapel oppervlakken (ongeveer (20 ^ 10) staten) is haalbaar. Het is een interessant idee.
Uitputtende opsomming van alle staten van de onderste twee rijen, vermenigvuldigd met de zeven mogelijke stukken, en de opslag van de beste verplaatsen in een enkele byte, zou vrij eenvoudig, er slechts 7 MB van het geheugen. Misschien is het optimaliseren van de prestaties voor deze zeven miljoen gevallen zou de ruwe gegevens voor de analyse en de ontwikkeling van eenvoudige modellen voor de gegevens; dergelijke modellen kunnen worden beschouwd als onderdeel van de algemene ideale Tetris-playing-strategie.
Merk op dat de uitvoering van de beste beweegt nog steeds niet naar ons beschermen tegen de mogelijke beëindiging van pathologische game-stuk-sequenties. Het is maar dat zullen we altijd beweegt, dat biedt ons de maximale mogelijkheden voor toekomstige overleving gezien het feit dat alle toekomstige stukken zijn volkomen willekeurig (en onbekend op het moment dat we zijn om te beslissen hoe het nu een enkele huidige bekende stuk).
6.6 Real-time prestatie
Een beperking gerichte strategie van een aantal algoritmes is de behoefte aan real-time prestatie - hetgeen betekent dat het algoritme moet een besluit binnen een bepaalde tijd op te schorten.
Wanneer een mens speelt Tetris, de stukken niet stoppen vallen geven de speler een kans om na te denken. Dat is onderdeel van de uitdaging van Tetris. Zo heeft een A.I. systeem dat is bedoeld voor de simulatie van de rol van een menselijke speler moet ook de beslissingen nemen in een tempo bepaald door het spel Tetris.
6.7 Rij-en stuk totalen
Merk op dat op de lange termijn, is het aantal gedaald stukken is zeer dicht bij 2.5 keer het aantal afgesloten rijen - omdat elke rij heeft 10 cellen, en elk stuk is 4 cellen, en we moeten een rij, gemiddeld, een keer per (10/4) = 2.5 stuks gedaald.
Dus we kunnen gebruiken "afgesloten rijen" en "gedaald stuks" bijna interchangeably met de juiste evenredigheid constant. De grootste fout is wanneer de raad volledig gevuld is met uitzondering van een enkel gat in elke rij (((10*20)-20)/4) = 45 stuks is gedaald, maar dat een tekort van de voorspelde (45/2.5) = 18 afgesloten rijen.
6.8 Huidige-stuk (en karton) strategie
Als we alleen de A.I. op de hoogte zijn van de huidige raad en het huidige stuk, en we alleen het gevolg van het verplaatsen van de huidige stuk in het bijzonder wijzen, dan kan dit worden genoemd een "one-piece"-analyse.
Hier is een ruwe schets van hoe een uit een stuk analyse kan beslissen over een stap in Tetris:
Huidige-stuk analyse van een Tetris-spel staat
In principe proberen we alle mogelijke stappen en kies de verhuizing dat de opbrengst het beste resultaat.
De moeilijke onderdeel is beoordeling van elk resultaat.
We moeten dan ook een hypothetische spel staat volgens hoe goed een dergelijke staat achter ons op korte termijn en lange termijn doelstellingen.
Onze lange-termijn doel is te overleven. Voortbestaan afhankelijk is van het voorkomen van de stapel uit overgelopen het bord. We kunnen de stapel hoogte door de vorming van complete rijen die vervolgens weggenomen uit de stapel.
Om een volledige rij, we moeten passen delen van stukken bij elke kolom van die rij. Dus, we eisen dat alle delen van een rij te worden blootgesteld aan de vallende stukken als we willen uiteindelijk vult u de gehele rij.
Als om een of andere reden die we met lege delen van een rij door stukken op een hogere rij, dan zijn we nu niet in staat in te vullen die lege delen van de rij. De enige manier (in de veronderstelling dat er geen glijdende) om toegang te krijgen tot deze "begraven gaten" is het verwijderen van de rijen boven die delen die als obstakels.
De volgende factoren zijn onder die we kunnen gebruiken om een bepaald percentage bord staat:
Overall pile height
Hoe hoger de stapel, hoe slechter onze situatie lijkt te zijn, want wij zijn dichter bij overvolle het bord.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
De ruwere de stapel, hoe waarschijnlijker het is dat het zal moeilijk zijn in te vullen het geheel van de embedded complexe contouren als ze worden blootgesteld aan de oppervlakte.
Number of buried empty cells
Hoe meer gaten we hebben begraven, hoe slechter onze situatie is, want we moeten ontdekken begraven gaten voordat we kunnen voltooien de overeenkomstige rijen.
U kunt zich ook andere factoren in het algemeen tarief een hypothetische boord van hoe goed de stapel kan al het mogelijke toekomstige stukken, en hoe goed de situatie ziet er voor al deze mogelijke stukken.
De volgende vraag is hoe de bepaling van het relatieve belang van deze factoren.
Een algemene aanpak is de volgende. Wijs een set van "gewicht" (relatieve belang) voor deze factoren, en dan simuleren tal van spelletjes en registreren van de resultaten van deze spellen (eindscore, etc). Dan, een nieuwe reeks van gewichten en simuleren van een nieuwe reeks wedstrijden. Gebaseerd op de vraag of de nieuwe reeks gespeeld hadden betere resultaten dan de vorige set gespeeld, we weten wanneer de nieuwe reeks van gewichten was beter dan de vorige reeks van gewichten.
In mijn eigen ervaringen heb ik geprobeerd te zoeken systematische en willekeurige het zoeken naar goede gewicht combinaties, maar ik heb nog geen mededeling enige grootschalige ontwikkelingen die ik kon uitoefenen. Maar ik zag veel verrassend goede hobbels. Ik vond het interessant dat de gemiddelde prestaties zouden kunnen vormen voor een soepele bocht wanneer een parameter is langzaam gevarieerd met de andere parameters gehouden op enkele waarde combinatie.
De beste real-time, een stukje Tetris-algoritme in de wereld, gecreëerd door Pierre Dellacherie (Frankrijk) in 2003, dankt veel van haar succes aan haar reeks metingen (of parameters). Het vinden van de gewichten is nodig wanneer het optimaliseren van een strategie, maar het is ook van cruciaal belang is om te beginnen met de aard van de metingen blijkt dat de relevante kenmerken van de staat.
Pierre Dellacherie's uitvinding van nieuwe manieren om de typering van elk bord maakt zijn algoritme echt uitstekend; de raad karakteriseringen een beeld geven van de belangrijke strategische dimensie van het bord staat.
Men kan de ontwikkeling van een heel andere set van kwalitatieve dimensies dat werkte even goed, ik ben ervan overtuigd dat het mogelijk is om span de desbetreffende raad staat de ruimte op veel verschillende manieren die kunnen worden gebruikt om een strategie functie. De belangrijkste is het vinden van kenmerken die het project staat de ruimte tot aan een klein aantal dimensies die kunnen worden gebruikt voor het ontwikkelen van een eenvoudige rating-functie (voorbeeld: de lineaire gewogen combinaties van kenmerken die worden gebruikt door Pierre's algoritme).
De uit een stuk algoritme gebruikt door de "bot" in het "xtris" software (1996) geschreven door Roger Espel Llima maakt gebruik van gewichten bepaald door een grootschalige verkenning van mogelijke combinaties gewicht door "genetische algoritmen". Gesimuleerde annealing is een andere methode van het verkennen van de multidimensionale ruimte van gewicht combinaties.
Het lijkt erop dat, op basis van diverse opmerkingen heeft de multidimensionale functie van de gemiddelde Tetris prestaties als een functie van het gewicht, bijvoorbeeld: F(w1,w2,w3,...), is "ruwe" (partijen van de lokale minima en maxima), wat betekent dat een eenvoudige multidimensionale "klimkoersen" kan niet werken.
6.9 Strategie bij het huidige stuk, volgende stuk, en karton zijn bekend
Als een strategie algoritme is gezien de huidige stuk, volgende stuk, en karton, dan kan beslissingen nemen die gebruik maken van de combinatie van stukken.
Kennis van de volgende stuk kunnen verbeteren het succes van een algoritme Tetris spelen door verschillende ordes van grootte. Het is gemakkelijk te begrijpen hoe de wetenschap het volgende stuk maakt een groot verschil in strategie.
Men kan doen "crazy" zetten, zoals die enorme gaten, etc, omdat ze al weten dat de volgende steen kan worden gebruikt voor de "fix" van de situatie. Indien u niet beschikt over de kennis van het volgende stuk, wordt u voortdurend probeert te spelen de kans om te winnen, probeert te houden van uw opties open voor het geval het volgende stuk is niet ideaal.
Het volgende schema laat zien hoe alle mogelijke stappen van het huidige stuk in behandeling worden genomen, en voor elk van deze verplaatsen we alle mogelijke zetten waarbij de volgende stuk.
Strategie met betrekking tot de huidige stuk en het volgende stuk
De Standaard Tetris-software gebruikt deze strategie als de "Next Piece" is ingeschakeld door de gebruiker en is zichtbaar op het scherm, en als een twee-delige A.I. geactiveerd is (zoals het geschreven is door mij, Colin Fahey). Als de "Next Piece" is niet zichtbaar op het scherm, mijn twee-delige valt terug naar een uit een stuk A.I..
Mijn uit een stuk A.I. is vreselijk als ten opzichte van de andere AIs in de Standaard Tetris-software, zodat deze toont je uiteindelijk meer informatie (bijvoorbeeld: het volgende stuk) kan worden tot een A.I. systeem, het is genoeg om het verbeteren van de prestaties van mijn eigen middelmatige twee delen A.I. door verschillende ordes van grootte - eenvoudig overtreffen de prestaties van de beste uit een stuk A.I. in de wereld.
(Echter, het omzetten van de beste uit een stuk A.I. in de wereld om twee stukken zou makkelijk te verbeteren door verschillende orden van grootte, ook! Kennis van het volgende stuk is enorm!)
Mijn eerste test spel met mijn twee-delige A.I. duurde ongeveer 182 uur (7,6 dagen) op een 800 MHz PC, de voltooiing van 7216290 rijen. Ik heb niet getest het algoritme op een snellere computer.
Wanneer u opslaat, de toestand van een Tetris game (Shift-W) naar een tekst bestand, kunt u vervolgens kopiëren en plakken de lijst van nummers uit de sectie "heightHistogram", naar een Excel-spreadsheet.
Elke bak in de histogram geeft het aantal afgesloten beweegt, dat werd afgesloten met een bijzonder stapel hoogte (na volledige rijen worden geëlimineerd). Zoals u zich kunt voorstellen, een stap die volledig opheffen van een stapel komt zelden voor, dus het totale aantal zetten dat eindigt met een stapel hoogte van nul is relatief laag.
Ondertussen, je zou verwachten dat de paal hoogte algemeen schommelt rond een gemiddelde, dus bakken met deze rijen zullen domineren de histogram. Tot slot, bakken voor de top-de meeste rijen (waar wij het gevaar van overvolle de raad) hebben een zeer lage bedragen.
In de loop van vele uren, met de A.I. het spelen van een spel met behulp van de strategie met betrekking tot de kennis van de "Next Piece", nam ik steekproeven van het spel staat, het kopiëren van de paal hoogte histogrammen naar een spreadsheet, zoals hieronder weergegeven:
Stapel hoogte histogrammen opgenomen op verschillende punten in een typisch spel (met de huidige en komende stuk-strategie)
U kunt elke schaal histogram door het totale aantal stuks (totaal aantal afgesloten beweegt) om de volgende gegevens:
Kleinere histogrammen, en een theorie
Het merkwaardige is dat deze op schaal histogrammen bekijken identiek zijn, ondanks de verschillende ordes van grootte van het aantal stuks (afgesloten beweegt).
Gewoon door te kijken naar de nummers die ik heb gemaakt voor de hypothese dat de staart van de curve is een exponentiële afname. Met trial and error "Ik kwam met de ruwe theorie dat de staart werd beschreven door:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
De volgende grafiek toont de grootte van histogram over het gehele bereik van de rijen.
Grafiek van de grootte van histogrammen
Merk op dat de curve voor 50000 stuks, en de curve voor 2000000 stuks, en de curve van de staart theorie zijn bijna te onderscheiden op deze schaal.
Het volgende is een kijkje op het hoofd van de curve.
Onderste deel van de hoogte histogram
Het volgende is een sterk vergrote beeld-van de extreem-staart einde van de gemeten en theoretische histogram curves.
Vergroot beeld van extreme staart einde van de grootte van histogrammen
Zoals u zou verwachten, is het zeer zelden voor dat de stapel om deze hoogten in nog lang experimenten - maar ook met onze beperkte informatie in deze extreme regio, de theorie nog steeds lijkt aanvaardbaar.
In de volledige plattegrond van de theorie lijkt te overlappen de staart van de distributie "precies", dat in het vergrote grafiek van de staart van de staart, zien we schijnbare fout. Maar ik stellen dat dit te wijten is aan onvoldoende gegevens op deze extreme hoogte stapel. Als ik verhoogde het spelbord te zeggen, een hoogte van 25 rijen in plaats van 20 rijen, zodat games niet abrupt een einde, ik denk dat ik de theorie van hierboven zou overeen met de trend.
Ik heb het gevoel dat dit histogram is een direct gevolg van de gecombineerde Tetris A.I. en de regels van Tetris. Dus, deze distributie zullen worden waargenomen voor elk willekeurig lange termijn spel Tetris van het gebruik van mijn bijzondere A.I. strategie voor het spelen met "Volgende Piece" kennis.
Verder vind ik dit soort histogram kan worden gebruikt voor het vergelijken AIs die gebruik maken van dezelfde informatie tijdens het afspelen. Zo hoef je niet te spelen volledige games (die lang kan duren dagen of jaren) te vergelijken op de lange termijn strategie van de prestaties van de verschillende algoritmes.
Bijvoorbeeld, ondanks de eenvoud van mijn model, ik denk dat het kan worden gebruikt voor het voorspellen van de gemiddelde duur spel! Wij hebben gewoon erachter te komen hoeveel stuks maakt de "rij 21" stapel hoogte van een aanzienlijk aantal, zoals een telling van een.
De relatieve frequentie voor rij 21, volgens mijn eenvoudige theorie, is:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
U moet dit aantal vermeerderen door (5.3 * 10^(7)), ongeveer 50 miljoen, voor een waarde van een.
Daarom had ik ongeveer voorspellen dat mijn huidige "Volgende Piece"-strategie is slechts goed voor op de orde van grootte van ongeveer 10 miljoen afgesloten rijen. Een reden waarom ik deze conservatieve schatting is dat zelfs 18 rijen kan dodelijk voor mijn A.I. omdat ik niet kan mijn A.I. om stukjes totdat ze gedaald met ten minste een rij! (Dit is dus ik hoef geen zorgen te maken over het niet kunnen draaien stuks.)
Ik ben onder de indruk van het feit dat het spelen van slechts 50000 stuks (en mogelijk veel minder stuks) kan u een zeer goede schatting van de lange termijn hoogte histogram, en dus een goede schatting van de orde van grootte van de rijen afgesloten vóór de wedstrijd eindigt. Deze aanpak is bijzonder waardevol voor het snel evalueren van subtiele veranderingen in een A.I. dat is nu al doet het buitengewoon goed.
6.10 Bestuur evaluatie statistieken imiteren speculatieve look-ahead
Als een algoritme, zoals het een heb ik met dit project, probeert gewoon alle stuk oriëntaties en vertalingen voor te laten vallen, en de tarieven als gevolg boord van elke configuratie volgens sommige maatregel van verdienste, het algoritme is in wezen imitatie van "look-ahead".
Wanneer een werk aan statistieken als "paal hoogte", "begraven gaten", "oppervlakteruwheid" of "goed diepten", een echt middel van een vereenvoudigde vorm van "kijken". Deze algemene karakterisering van de raad van bestuur geeft een indicatie van de levensvatbaarheid op lange termijn van de raad van bestuur.
De ideale benadering, gezien een oneindige hoeveelheid rekenkracht, zou zijn te evalueren boord van een configuratie krijgen alle mogelijke stukje sequenties die kunnen volgen.
Ook al moet je wel alle 7 stuks als gelijkelijk waarschijnlijk op elk niveau van de look-ahead, moet u het optimaliseren van de werkelijke vertalingen (tot 10) en uitgangspunten (maximaal 4) voor elk stuk in elke mogelijke volgorde! Dat is tot (7*10*4) = 280 branches op elk niveau van de raad evaluatie! Dus, dat is aan boord van ((280)^(LookAheadLevels)) configuraties te overwegen.
Want we moeten een einde maken aan het onderzoek na een eindig aantal niveaus, moeten er enkele niet-anticiperende wijze van evaluatie van de raad staat - een manier om met waarden aan de leaf nodes van onze zoektocht boom. Dus, voor deze leaf nodes, zijn we terug naar de hand van een formule die belichaamt algemene voorspellers van toekomstige levensvatbaarheid van de raad!
Deze vorm van speculatie kunnen worden geprobeerd met de uit een stuk en twee-delig algoritmen in de plaats van de simplistische boord evaluatie statistieken. Stel dat alle latere stukken zijn even waarschijnlijk en de som van de capaciteiten van de Raad van Bestuur aan de stukken van alle soorten in de best mogelijke manieren. Dit kan worden uitgevoerd met een, twee, of een aantal speculatieve verplaatsen diepte - met alle stukken gelijkelijk waarschijnlijke (p=1/7).
De terminal nodes van deze boom kan nog steeds de gewogen statistieken te evalueren, maar de speculatieve lagen meer in het bijzonder zijn de essentie van wat wij willen doen: Bepaal hoe goed een bepaalde raad kan zich met alle mogelijke stukken, met inbegrip van positieve factoren, zoals het invullen van lijnen en negatieve factoren, zoals een toename van de algemene stapel hoogte, enz.
7. Tetris A.I. systeem demonstratie
7.1 Systeem overzicht
Het volgende diagram toont mijn experimentele set-up.
Over het algemeen systeem voor demonstratie
7.2 Uitrusting
Hier is een korte lijst van de apparaten die worden gebruikt bij deze demonstratie:
[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)
Uiteraard kunt u gebruik maken van soortgelijke apparatuur voor de vervulling van dezelfde resultaten op. Meer details met betrekking tot de apparatuur zijn beschreven in de overeenkomstige punten van dit artikel.
Hier volgt een korte beschrijving van de personal computers die in deze demonstratie:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Deze demonstratie gemakkelijk kunnen worden gereproduceerd met andere besturingssystemen, zoals Linux. Het is belangrijker om een CPU snelheid op de orde van 800 MHz of sneller voor de computer, dat is het starten van de A.I. software, omdat deze computer zullen doen, real-time verwerking van de video.
7.3 Video-opname hardware
Ik gebruikte een gemeenschappelijk USB video camera als een video-opname-apparaat voor mijn A.I. systeem. Met name heb ik gebruik gemaakt van de Creative "WebCam Pro", een USB video camera met 640 * 480 resolutie.
Creative(TM) USB videocamera beschrijving
USB videocamera (hoek)
USB videocamera (voorkant)
USB video camera (karton met CCD)
USB videocamera (belangrijkste chips)
OV511 belangrijkste blokken (let op: USB video camera is OV511+)
7.4 OV511 data sheet
ov511ds.pdf
OV511 Datasheets
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "plus") kenmerk verschillen
ov511plus_101.pdf
OV511+ functie verschillen
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Video-opname-software
Microsoft heeft een zeer oude API de naam "Video for Windows" (VFW) dat ik met succes gebruikt voor dit project. (U link naar "vfw32.lib" in uw C++ project, of doen een DllImport van "vfw32.dll" in uw C# code.) Voorbeelden van het gebruik van de VFW API worden op grote schaal beschikbaar.
Een alternatief is het gebruik van Microsoft's "DirectShow" API video-opname te maken.
Omdat VFW duurde slechts een tiental regels code te gebruiken, en uitgevoerd aanvaardbaar op mijn 800 MHz machine, ik heb niet de moeite de verkenning van alternatieve APIs. Maar DirectShow is een meer hedendaagse API voor Windows video capture, en mogelijk levert een veel hogere beeldsnelheid voor dezelfde hardware.
Kijk naar de "CPF.StandardTetris.STVideoCapture" broncode-bestanden in de Standaard Tetris software om te zien hoe gemakkelijk het is om video-opname bij uw eigen projecten.
7.7 Computer interface met relais (via RS232)
Als u een computer "Druk op de toetsen op het toetsenbord van een andere computer, gebruikte ik een" relais boord van "de zeggenschap van tekst commando's worden verzonden vanaf een seriële poort (bijvoorbeeld:" COM1 ") via een RS-232 kabel. Ik gebruikte elke relais voor aansluiting van de twee draden van een specifieke toets toetsenbord voor de simulatie van een toets drukt.
Dit vereist de openstelling van het toetsenbord en het maken van verbindingen. Er zijn veel eenvoudiger methoden voor het simuleren toets te drukken op een computer, maar ik wilde iets doen dat leek zo dicht mogelijk bij een persoon echt te typen op een toetsenbord.
Een zeer veelzijdig en goed gemaakt relais boord is de ADR2200 gemaakt door Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
U kunt kijken naar de "CPF.StandardTetris.STRS232" broncode-bestanden om te zien hoe makkelijk het is voor het verzenden van bytes via een seriële poort, die vervolgens kunnen worden gebruikt voor de controle op apparaten zoals de ADR2200 boord hierboven weergegeven.
8. Standaard software Tetris
8.1 Software downloaden
Ga naar het begin van dit artikel vind je een link naar de source code (C# en C++ versies) en ingebouwde software (*.exe).
8.2 Samenvatting van de kenmerken
Software features:
Instructie schermen en kredieten
Monochrome mode
Shadow-modus
Tip mode
Junk rijen
Rate control
Volgende stuk
Bestuur grootte
S/Z stuks
Kalibratie-modus
Video-opname en erkenning
Debuggen console
Sla spel
Load game
8.3 Begin verschijning
Uiterlijk bij de software wordt gestart:
Uiterlijk bij de software wordt gestart
8.4 Monochrome mode
Standaard wordt het bord verschijnt in kleur:
Standaard wordt het bord verschijnt in kleur.
De kleur modus kan worden veranderd in zwart-wit (Shift + K):
De kleur modus kan worden veranderd in zwart-wit.
8.5 Shadow-modus
Shadow-modus geeft aan waar een stuk zal landen. Dit is zeer nuttig voor zeer grote platen, want het is moeilijk te beoordelen waar een stuk zal het land.
Shadow-modus geeft aan waar een stuk zal landen.
8.6 Tip mode
Tip-modus kunt u zien waar het momenteel geselecteerde AI zou verplaatsen, gezien de huidige situatie. (Shift + H)
Tip modus geeft aan waar het momenteel geselecteerde AI zou verplaatsen.
8.7 Junk rijen
Invoegen "junk" rijen aan de onderkant van de paal, een voor een, handmatig. (Shift + J)
Invoegen "junk" rijen aan de onderkant van de paal.
8.8 Rate control
De '+' (plus) en '-' (min) toetsen controle van de snelheid van het spel.
Standaard is het spel draait op een standaard snelheid, volgens de regels van Standard Tetris (snelheid gebaseerd op niveau).
Hier is een tabel van de betekenissen van de snelheid bias:
-3,-4,...: traagheid in verhouding staan tot bias
-2: trager dan niveau 1
-1: normaal, maar beperkt tot niveau 6 (0,2 sec) snelheid;
0: normaal; Standard Tetris snelheidsvoorschriften;
+1: iets sneller dan level 9 (0.05 sec vertragingen);
+2: begrensd door destructie-tarief (bijvoorbeeld: 75 Hz);
+3,+4,...: meerdere iteraties per frame gemaakt;
Ik vind het leuk om de A.I. bij een instelling van "+2" (hit '+' sleutel twee keer zo bias begint bij nul).
Speed bias verandert de snelheid van het spel.
8.9 Toon volgende stukje
Hit 'N' om te wisselen van de "Next Piece" display. De A.I. zal gebruik maken van de "Next Piece" informatie alleen als de "Next Piece" verschijnt op het scherm.
U kunt er zeker van zijn dat de AI is niet met behulp van "Volgende Piece" informatie als je niet kunt zien, de "Next Piece" op het scherm.
Toon de volgende stuk
8.10 Bestuur grootte
Te drukken Ctrl + (links, rechts, boven), kan men pas de grootte aan boord van willekeurige grootte van 4 * 4 tot 200 * 400.
Board afmetingen: 4 * 8
Board afmetingen: 20 * 40
Board afmetingen: 40 * 80
Board afmetingen: 20 * 5
Board afmetingen: 4 * 100
8.11 S/Z stukken alleen
Studie van de interessante afwisselende S/Z patroon.
Dit patroon kan niet worden opgelost voor een 10 * 20 boord (breedte * hoogte).
Maar platen die breedte, die een veelvoud van 4 zijn trivially getoond om oneindig te overleven.
De AIs overleven voor onbepaalde tijd in deze gevallen, ook al zijn zij niet specifiek is afgestemd op het behandelen van dit pathologische situatie.
S/Z stukken alleen
8.12 Video kalibratie-modus
Hit 'C' om in "Kalibratie Mode". Wanneer in de kalibratie-modus kan je het aantal toetsen: {1,2,3,4,5,6,7} voor het selecteren van een stuk {O,I,S,Z,L,J,T} aan de bovenkant van het bord te spelen.
Dit is handig als referentie beeld voor de video-opname op een tweede Standard Tetris software.
Als je de 0 (nul) toets, dan zal dat de raad leeg.
U kunt zich voor te doen paaien stukken door het selecteren van een stuk (1..7), en vervolgens de selectie van een blanco (0), terwijl een tweede computer doet video capture horloges voor de stukken.
U kunt de A.I. op de tweede computer en zie hoe het gaat met je handmatig ingevoerd pathologische Tetris scenario's!
Kalibratie-modus is de enige keer dat je kan manipuleren van de video-opname beeldverwerking sjabloon (4 * 2 grid). U kunt met de muis om de rechthoek, maar dan kun je gebruik maken van de cursor-toetsen ( "up", "down", "links", "rechts") te hebben fijne controle van de grenzen - Shift met behulp van de sleutel te selecteren tegenover de grenzen van de rechthoek (bijvoorbeeld: "Shift-links" combo is anders dan "links").
Video kalibratie-modus
8.13 Video-opname en erkenning
Op 'V' schakelt de video-opname modus. Indien correct gekalibreerd (zie "video kalibratie" in een vorig punt), de stukjes van een externe video-scherm wordt gevangen genomen door de video-camera en ingedeeld - en de stukken zullen worden batterij in de lokale game voor de A.I. te overwegen en reageren .
De A.I. output moet vervolgens worden doorgegeven (via de RS-232 interface in de demonstratie beschreven in dit artikel) op het afgelegen game input (bijvoorbeeld: toetsenbord) voor de A.I. met succes te kunnen spelen het spel op afstand.
Als op enig moment deze gesloten lus is verstoord (bijvoorbeeld: video capture storingen of output signaal storing), dan wordt de A.I. zal een verkeerde indruk te geven van de status van de afstandsbediening spel, en de A.I. zal ongepaste beslissingen die snel verliest het spel .
(Opmerking: Dit probleem kan worden verholpen met een bescheiden bedrag van de inspanning: De A.I. systeem hoeft alleen maar de hele afstand Tetris scherm voor een voortdurende "reality check" van de gehele raad, en de A.I. systeem moet worden opgesteld voor een aantal commando's naar de output niet in enkele manier.)
Video-opname en erkenning
9. Originele Tetris AI-experiment (2003)
Het volgende toont de eerste werkende versie van de Tetris A.I. systeem in 2003.
Video camera waarmee de computer # 1 draait gewoon elke Tetris-spel
Computer # 2 draait Standard Tetris software in A.I. mode
Links: Tekening grid te kalibreren videobeeld erkenning;
Rechts: Tetris stuk erkenning gevallen.
Frame uit video van Tetris A.I. experiment in 2003
10. Best een stuk Tetris-playing-algoritme in de wereld
10.1 Pierre Dellacherie (2003, Frankrijk)
Pierre Dellacherie (2003, Frankrijk), ontwikkelaar van de beste uit een stuk Tetris-playing-algoritme in de wereld
Het beste uit een stuk, real-time Tetris algoritme voor zover mij bekend is gemaakt door Pierre Dellacherie van Frankrijk.
Zijn geweldige algoritme vult soms meer dan 2 miljoen rijen!
De gemiddelde prestaties is in de orde van 650000 rijen.
Het algoritme is erg weinig geheugen, en loopt op hoge snelheid (ongeveer 160 rijen per seconde op mijn 800 MHz computer).
Prestaties van Pierre Dellacherie's algoritme:
Mijn huidige model voor de uitvoering van Tetris AI is dat voor een bepaald stuk is er een constante kans dat het spel zal beëindigen, p.
Zo is de kans dat het stuk niet zal beëindigen, een game is q=(1-p).
De kans van de wedstrijd na beëindiging van k beweegt is simpelweg het product van de kans op overleven (k-1) beweegt, namelijk q^(k-1), en de waarschijnlijkheid van de beëindiging op de volgende stap, namelijk p.
Dit komt overeen met een "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 )
Voor kleine p, ln(q) is ongeveer (-p), en we hebben de volgende tekst:
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 )
Wij verwachten dat de fractie van het totale aantal wedstrijden gespeeld te beëindigen met een aantal afgesloten rijen in het interval [k1, k2] te worden:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Na het voltooien van 36 gespeeld op mijn computer, over een periode van twee dagen, vond ik een gemiddeld 674827 afgesloten rijen.
Volgens de algemene theorie, ik zou verwachten dat de volgende relatieve fractie van games af te ronden in de volgende rij afgesloten reeksen:
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
Hier is een grafiek die vergelijkt de Exponential Distribution theorie met de waargenomen verdeling van de spellen.
Prestaties van Pierre's algoritme meer dan 36 afgesloten games
Hoewel er zeer weinig spellen in deze data set, is het duidelijk dat het model is vrij goed in het afstemmen van de waargenomen spreiding.
Pierre's inleiding van zijn algoritme:
Pierre begonnen met de werkzaamheden op dit algoritme uit een stuk in 2003,1.
Pierre me een e-mail op de hoogte zijn algoritme op 2003.4.9, de rapportage de volgende prestaties van meer dan 20 opeenvolgende games:
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.
"Het algoritme is geïmplementeerd in Turbo Pascal en voltooit 7000 rijen / min. Met een Athlon 1600+."
Ik omgezet Pierre's algoritme te C++ in 2003,6, na een aantal e-mail uitwisseling met Pierre. We geverifieerd dat de A.I. in de C++ versie gemaakt van dezelfde besluiten van de Pascal versie.
Ik waargenomen soortgelijke prestaties aan zijn oorspronkelijke verslag; gemiddeld ongeveer 650000 afgesloten rijen, en enkele spelletjes voltooiing van 2 miljoen rijen.
Ongelooflijk!
10.2 Gesprek met Pierre Dellacherie
[1] Wanneer heeft u eerst deze code?
Ik heb gewerkt aan het algoritme van eind januari 2003 tot nu.
[2] Hoe lang hebt u gewerkt?
Ik werkte op het bijna elke week ... maar niet elke dag lang, want ik heb andere activiteiten: Ik heb jammer genoeg geld te verdienen als iemand anders!
[3] Wat een inspiratiebron geweest voor het ontwerp van de code?
Ik speelde Tetris 10 of 15 jaar geleden, maar ik had niet gespeeld weer voor lange tijd. Ik zou zeggen dat ik een 'gemiddelde' speler die kent de regels en een paar trucjes.
Echter, toen ik begon te werken aan het algoritme heb ik niet zoveel spelen, want ik vond het was niet meer effectief te kijken hoe de computer afspelen en analyseren van zijn zwakke punten.
[4] Heb je enig automatisering voor de „opleiding“ van uw code beter te presteren? Heeft u nog een feedback naar de verbetering van het algoritme?
Of heb je gewoon kijken naar de resultaten en besluiten tot wijzigingen?
Ik ben van de „oude school:“ Ik zag de resultaten en heeft besloten om wijzigingen aan te brengen.
"Automatisch leren" is een soort meta-algoritme, dus ik ben er niet zeker van zijn dat deze manier wilt doen, zou makkelijker als deze meta-algoritme zou moeten worden gebouwd en ook dat is niet zo makkelijk!
Sterker nog, ik ben het eens met Roger Penrose als hij zegt (in zijn boek "Shadows of the mind") dat de menselijke begrip en intuïtie kan niet worden algoritmische (bijvoorbeeld: berekenbaar).
[5] Wanneer heeft u voor het eerst beginnen te spelen Tetris, en toen heeft u het idee van het oplossen van Tetris met een A.I.?
Ik leer algoritmische en computer programmeren (Turbo Pascal en Scilab) voor studenten die opleiden voor toelatingsexamen op afgestudeerd ingenieur scholen.
Op het eerste, "Computer speelt Tetris" was een idee die ik wilde ontwikkelen voor mijn volgend jaar studenten.
Ik was niet op de hoogte van uw webpagina toen ik begon te werken aan het algoritme.
Inderdaad was ik een beetje geluk op de hoogte te zijn van uw webpagina maar een paar weken geleden, omdat ik denk dat ik zou zijn ontmoedigd door de resultaten (zoals je wel kan raden, de eerste versies van mijn algoritme niet spelen zo goed!).
[6] Wat is uw huidige status?
Ik ben bijna 30 [vóór 27 april 2003]. Ik heb een aantal activiteiten: Ik ben een cellist, ik componeren van muziek en ik les computer programmering.
Ik heb een master diploma in de musicologie (1994) en een "Artificial Intelligence and Algorithmic"-diploma (1998).
In Frankrijk is dit diploma overeenkomt met het 5de jaar studeren aan de universiteit (4e jaar is de graad master en 6de jaar is het proefschrift).
Pierre's composities:
[7] Waar woont u?
Ik ben Frans en ik woon in Rouen (Frankrijk).
[8] Overige opmerkingen:
Uiteindelijk heb ik niet elk nieuw idee te verbeteren.
Ik heb geprobeerd zoveel nutteloos (en domme) dingen die ik betwijfel het verbeterd kan worden.
Aan de andere kant, ik denk dat er misschien sprake totaal verschillende algoritmes die van invloed kan zijn betere prestaties.
Trouwens, een snellere test bestaat in de lancering van de stukken in een half-box (10 rijen x 10 kolommen): in een half-box, mijn algoritme maakt een gemiddelde van 280 afgesloten rijen.
Nog iets: het algoritme kan eenvoudig worden veranderd in een dubbel-laags-algoritme ([ik zal] de tests binnenkort).
Ik hou van filmmuziek: steeds een film componist is een onderdeel van mijn grootste dromen (maar dat is slechts droom!).
11. Best menselijke speler in de wereld
11.1 Japanse Tetris Master (2001 januari 27) video
Tetris kapitein (2001; Japan) video
Arika presenteert de Japanse Tetris Finales kapitein (2001 januari 27). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Feedback
12.1 Slashdot draad (2003)
In 2003 is mijn Tetris A.I. project werd besproken op de Slashdot Internet-forum (
http://slashdot.org).
Slashdot (http://slashdot.org) Internet-forum kop voor een bespreking van mijn Tetris A.I. project
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 geïnspireerd door mijn Tetris A.I. project (2003) (de eerste keer dat ik ooit heb geïnspireerd een komisch!)
Comic geïnspireerd door mijn Tetris A.I. project (2003) (de tweede keer dat ik ooit heb geïnspireerd een komisch!)
13. Geschiedenis van de Tetris A.I. project
In het voorjaar van 1989 was ik druk bezig over te slaan (en niet) tweede semester Freshman klassen op de University of Pennsylvania.
Een van mijn kamergenoten, Bill Matthews, had de Mac Classic, en soms spelen videospelletjes.
Mensen die je toegelaten tot de Ivy League scholen zijn doorgaans geneigd zijn te concurreren met andere mensen te allen tijde - dus als Bill kreeg het spel Tetris voor zijn Mac, we onmiddellijk begonnen met een langdurige strijd voor de hoge score.
Zoals de scores beklommen, de tijd die investeringen die nodig zijn om een kleine winst sterk toegenomen.
Om een lang verhaal kort, Bill zogenaamd bezit is van de hoge score tussen ons, maar ik vermoed dat hij met behulp van ResEdit en het hacken van de gast bestand!
Bill had klassen in de Wharton school van het bedrijfsleven, de alma mater van Michael Milken en Donald Trump, dus het is niet ondenkbaar dat iemand opgetuigd een onmogelijk hoge score ...
In de zomer van 1990 een 30 MHz Intel 80386 IBM PC ik geleend van mijn kamergenoot, Alex Haidas.
Ik kocht een Mac toetsenbord op een rommelmarkt voor $ 1.
Ik gebouwd parallelle poort circuit toe te staan dat de PC om de Mac toetsenbord.
(Ik gebruik gemaakt van een CMOS 4040 chip te fungeren als een soort van solid-state relais toe te treden toetsenbord contacten binnen de Mac toetsenbord.)
Ik schreef een computerprogramma dat gebruikt een besluit boom als haar strategie voor het spelen van het spel Tetris. In slechts een paar weken had ik een PC het spelen van het spel Tetris draait op een Mac.
Ik was echter verplicht gebruik te maken van de PC toetsenbord te vertellen over de A.I. elke vallen stuk op het scherm.
Ik begon te werken aan een circuit met behulp van CdS (Cadmium Sulfide) licht detectoren die zou leunen tegen de Mac scherm en "zien" de vallende stukken, maar CdS sensoren te traag gereageerd op veranderingen in de helderheid en het contrast tussen Tetris stukken en de achtergrond op het scherm Mac Classic was te laag om betrouwbaar te discrimineren.
In die tijd heb ik niet veel geld, dus het was te riskant voor de aankoop van een $ 2 Radio Shack Fototransistor dat misschien niet doen wat ik wilde.
Ook, gezien het contrast probleem, ik ben pessimistisch over de hele aanpak.
Toen kocht ik mijn eerste computer in 1996, kon ik niet krijgen software onder Windows 95 op een 100 MHz CPU te doen video processing snel genoeg om een eenvoudige visie op het systeem zal werken.
Ik schreef het beeld verwerking code in assembler, maar er was zoveel overhead voor mijn code werkelijk ontvangen video-gegevens, dat het onmogelijk is om iets te doen de moeite waard.
In 2003 heeft de technologie, met name CPU snelheid, had een niveau heeft bereikt dat gedaan afwerking van het project bijna triviaal.
Ik gegraven tot mijn oude persoonlijk project en eindelijk klaar met het krijgen van enkele zin van sluiting.
Het was erg spannend om te zien spelen van een computer een andere computer via de USB videocamera en het relais.
Het geluid van de informatiecentra te klikken, en het kijken naar de stukken van spin-and-drop op belachelijk, bovenmenselijke snelheden, gemaakt van de ervaring heel bevredigend in een multisensorische manier.
In 2003, mijn werk is erkend door Slashdot (
http://slashdot.org), en ik ontving een groot aantal mooie feedback.
Ik was uitgenodigd om te verschijnen op de "Screen Savers" televisie-show op de TechTV digitale televisie netwerk.
Ik ging naar San Francisco en op de show, en de ervaring was great.
Later in 2003, Ik heb een bericht van Henk Rogers, uitnodiging tot Hawaii om hem en Alexey Pajitnov te praten over een soort standaard voor Tetris, voor de toepassing van die Tetris toernooien.
Een bijzonder belang was om spelers te gebruiken mobiele telefoons „met elkaar“ te „concurreren,“ indirect, via A.I. dat imiteert spelers (door voorafgaande analyse van elke speler van de acties), waardoor de effecten van de mobiele telefoon toegang tot internet latency, en om spelers te „concurreren tegen“ * De beste menselijke spelers in de wereld (*..., of liever gezegd A.I. imitatie van de beste menselijke spelers in de wereld).
Ik werd enthousiast door het vooruitzicht van de vergadering van de maker van Tetris. Helaas is het vliegen maakt me ongerust, en ik de uitnodiging.
In 2006 heb ik mijn omgezet "Standard Tetris" software van C++ te C# te maken van de software beter toegankelijk en nuttig is voor de hedendaagse programmeurs.
