Tetris
Colin Fahey
1. Software
2. Úvod
Tento článek popisuje, jak může počítač přehrávat klasické video hry Tetris o získávání informací o desce, určování dobrých akcí a plnění těchto akcí.
Tento článek obsahuje software schopný hrát Tetris v reálném čase.
Software obsahuje nejlepší real-time hře Tetris-algoritmus ve veřejné doméně.
Tento článek definuje pravidla pro "standardní Tetris," upřesnění na základě původní 1986 pre-komerční verze Tetris pro počítačový (PC).
V 2003, software zahrnuty v tomto článku byl použit k tomu, aby v počítači hrát Tetris běží na samostatném počítači.
Řádné USB video kamera byla použita k tomu, aby počítače na obrazovce "vidět" z jiného počítače.
Relé palubě bylo kontrolováno prostřednictvím RS-232 rozhraní, které umožní, aby počítač "tisku kláves" na klávesnici z jiného počítače.
Proto byl první počítač má vztah k druhým počítači, který je podobně jako typické lidské hráče vztah k počítači při přehrávání Tetris; hry stavu je jediným známým pohledu na obrazovku, a hráč akce může být zahájena pouze prostřednictvím klávesnice .
Konfigurace v této demonstrace, že se počítače mohou hrát Tetris lepší než lidské, za běžných real-time hře Tetris podmínek.
3. Historie Tetris
V 1985, Alexey Pajitnov a Dmitry Pavlovsky byly počítačové techniky na Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre z Russian Academy of Sciences
Alexey a Dmitry byly zájem o rozvíjení a prodej počítačových her návykové.
Jsou testovány v několika různých her.
Alexey byl inspirován řeckého puzzle hra, Pentaminos, které se účastní pořádání puzzle kusů vyrobených z pěti čtverců.
Alexey myslel, že na myšlenku pořádání Pentamino kousky jako padli do pravoúhlého kalich, ale uvědomili, že dvanáct různých pěti-hranatých tvarů, jsou příliš složitá na video hry.
Alexey přešel na použití "tetramino" sedm kousků, z nichž každá se čtyřmi čtverci.
V 1985.6, Alexey Pajitnov naprogramován první verze Tetris na Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov, a Tetris.
V 1985-1986, Vadim Gerasimov, což je 16-letý vysoký-školní počítače prodigy kteří pracovali v akademii, provedeny Tetris pro IBM PC provoz MS-DOS operačního systému.
(Vadim Gerasimov později udělal výzkumu na MIT Media Laboratory, v letech 1994 až 2003, který obdrží po absolvování Ph.D. mnoho zajímavých projektů:
http://vadim.www.media.mit.edu)
Zavedení obrazovky z 1987-1988 pre-komerční verze Tetris pro PC
Hra hrát obrazovky z 1987-1988 pre-komerční verze Tetris pro PC
Po 1987, Tetris šíří po celém světě.
The Tetris Company, LLC, Tetris vlastní ochrannou známku.
4. Projekty inspirované Tetris
4.1 0-dimenzionálním Tetris
Dosud vyvinuty.
4.2 1-dimenzionální Tetris
Ziga Hajdukovic vyvinula 1-dimenzionální Tetris software, který lze přehrát v internetovém prohlížeči.
Ziga Hajdukovic vyvinula i 1-dimenzionální Tetris software pro mobilní telefony pomocí Java J2ME platformu.
4.3 2-dimenzionálním Tetris
Všechny tradiční Tetris varianty jsou v této kategorii.
Tato sekce obsahuje zajímavé varianty.
4.3.1 Největší Tetris hra vůbec: Delft University of Technology (1995)
Tetris hrál na budovy; 2000 m^2 rozlohy; Delft University of Technology (1995)
Tetris hrál na budovy; 2000 m^2 rozlohy; Delft University of Technology (1995)
4.3.2 Dalším Tetris hru hrají v budově: Brown University (2000)
Tetris hru zobrazit pomocí světla na okna budovy v Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
"Myslím, že to byl právě nejvíce neuvěřitelný jeden den-to bych si v mém životě. Stejně jako Steve Jobs vždycky říkal, že cesta je odměnou."
"Je mi myslím projektů jsme se zpátky do školy. Věci, které byly téměř undoable, že ostatní lidé by nevidí dělá."
Steve Wozniak (2000)
4.3.3 Internetové prohlížeče hra s MIT "Zelená Stavební" obrázek
Vadim Gerisimov's internetový prohlížeč Tetris
Tento internetový prohlížeč Tetris varianta byl vytvořen Vadim Gerasimov.
Tento internetový prohlížeč Tetris má uvedenu "Green" budovy v areálu MIT.
Tato varianta Tetris má pouze devět sloupců namísto standardních deset sloupců.
Tato varianta představuje Tetris nové kousky s libovolnou orientací.
Vadim Gerasimov je osoba, kteří napsal počítačový kód pro PC verze Tetris v 1986.
Vadim Gerasimov udělal Ph.D. výzkumu na MIT Media Laboratory během 1994-2003, pracujeme na několika zajímavých projektech.
4.3.4 PIC16F84 12 MHz mikrokontrolér založený NTSC / PAL-video hry Tetris
PIC16F84 12 MHz mikrokontrolér založený NTSC / PAL-video hry Tetris
Obrázku výše zobrazí NTSC / PAL video výstup vyrábí se PIC16F84 12 MHz mikrokontrolér běží software, který napsal Rickard Gunee v 1998.
Video signál je generován pomocí softwaru ovládání digitálních výstupů.
4.3.5 "Scopetris" Osciloskop Tetris o Lars Pontoppidan (2007.8)
"Scopetris" Osciloskop Tetris o Lars Pontoppidan (2007.8)
Lars Pontoppidan napsal kód pro AtMega32 mikrokontrolér, a dodala, jednoduché analogové obvody, aby vytvořily Tetris verze, která by mohla být přehrávány na osciloskopu.
Některé registry ze AtMega32 mikrokontrolér kontrola 8-bitové výstupní signály, a když prošel přes "R-2R" elektrický odpor obvodu pro digital-to-analog konverze (D/A), výsledná analogové signály je možné ovládat (x,y) souřadnice osciloskopu nosníku (jestliže je osciloskopu nastavena na "X-Y režimu)."
YouTube video:
FLV video:
4.3.6 Zatemnil kód Tetris: C / Unix
Následující byla udělena "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 Zatemnil kód Tetris: Perl kód
Následuje Tetris pro Perl interpret: Perltris (verze 20050717), kterou 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 standardem pro popis grafických objektů pomocí XML.
Mozilla SVG Tetris: Tetris prováděna pomocí Scalable Vector Graphics (SVG) popis
4.3.9 Google "widget" Tetris
Google, Yahoo!, a Microsoft, a další společnosti, mají podporovat miniaturní Internet-založený software pojmenovaný "widgets", které jsou obvykle charakterizovány některými použití dynamických dat je k dispozici na internetu.
Jedním z takových widget k dispozici prostřednictvím Google je Tetris hry.
V následujícím příkladu je roztomilá, ale tvary střídat v otravné způsoby:
Google "widget" Tetris
Ostatní Google widgets:
4.3.10 MIT výzkumu papíru: "Tetris is Hard, Even to Approximate" (2002)
Následující výzkum dokument obsahuje důkaz, že určitý druh Tetris varianta je "NP-kompletní."
Erik D. Demaine, Susan Hohenberger, a David Liben-Nowell, "Tetris is Hard, Even to Approximate", Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
"NP-kompletní" je zařazení době náklady a náklady na prostor algoritmus.
Jiné klasifikace zahrnují "P" a "NP".
Třídění "NP-úplné" znamená, že pro větší problémy, než některé malé velikosti, algoritmus je nepravděpodobné nalézt požadované řešení v rámci praktického množství času nebo prostoru.
4.3.11 Výzkum dokumentu: "Applying reinforcement learning to Tetris"
Následující dokument, zveřejněný 2005.5.30, o Donald Carr na oddělení výpočetní techniky v Rhodes University, Jižní Afrika, představuje žádost o "posílení vzdělávání" na Tetris.
4.3.12 Tetris Sukně (2007.11)
Tetris Sukně (2007.11)
Tetris na sukni byl vytvořen "Lucy" ("hissyfitoly" na etsy.com) před 2007.11.
Od autora je popis cípu (nabízeny k prodeji 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."
Fórum připomínky týkající se tohoto sukně:
"Muž, který sukně naštve na Tetris"
"Ahahahaha, myslel jsem, že to samé."
"K dispozici je kompletní řádek dolů na dno ... dokončena řádky zmizí." "PŘELAKOVAT" "."
"K dispozici by měly být na místě v zadní nebo přední dlouhý kus, kde by se perfektně hodí ..."
"To je opravdu ošklivý když sukně. Můj přítel nemohl koupit mi dost čokolády a květiny přesvědčit, abych se nosí, že věc."
4.3.13 Tetris fázi jednat (2007.4)
Tetris fázi jednat (2007.4)
"Od těch, které přinesli ti Triforce v 2006 ... Přichází další generace neživý předmět parodie ... Tetris."
Lokálně z cache-video v Flash video (FLV) formátu (použijte VLC hrát):
4.3.14 Veselý Tetris variace na japonské televizní show
Tetris variace na japonské televizní show
Tento segment video z japonské televizní show patří veselý variace na Tetris, včetně:
kousky, které zmizelo na přistání, což je kus, který vyplní celý řádek (tedy řádek po dokončení vykládky), více kusů současně spadající, nepravidelně tvarované kusy, dlouhý kus, který je trochu příliš široká, aby se vešly do rozdílu (s vyloučením 4-řady dokončení!) Mario mlátit a hub a stávají obrovskými a umírá! malý kus trosek po zbývající řádky jsou zničeny, vzestupný závažnosti procesu kusů akcií na trhu k vrcholu, atd.
Lokálně z cache-video v Flash video (FLV) formátu (použijte VLC hrát):
4.3.15 "The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
"The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
Z popisu na YouTube:
"TETRIS hraje o skutečné lidské bytosti-zasedání v sále:"
TETRIS je 4. video plnění z GAME OVER Project, režie švýcarského umělce Guillaume REYMOND (NOTsoNOISY kreativní agentury).
Tento stop-motion video byl zastřelen a hrál na "LES URBAINES" festivalu
http://www.urbaines.ch v Palais de Rumine (Lausanne, Švýcarsko) v November 24th 2007.
Lokálně z cache-video v Flash video (FLV) formátu (použijte VLC hrát):
4.3.16 2.5-dimenzionálním Tetris
Termín "2.5-dimenzionálním" zde slouží k "je mimo-ortogonální pohled ze dvou-dimenzionálním verze Tetris, s tloušťkou ve třetí dimenzi.
(Najděte si odkaz "tetris3d" v "F7: GAMES".)
4.4 3-dimenzionálním Tetris
Linux / GTK verze
Tří-dimenzionálním Tetris v podobě, Java applet pro internetové prohlížeče:
Tří-dimenzionálním Tetris pro Windows operační systém:
4.5 4-rozměrné Tetris
Greg Kaiser's "HyperTetris" (1996): 4-rozměrné Tetris
V [1996], [...], Greg Kaiser dohromady čtyř-dimenzionálním variantou na klasické hře.
Použití IrisGL (a.k.a. igl) vytvořil pracovní, pokud je těžké hrát, hra pomocí čtyř sub-obrazovky o zachycení různých tří-dimenzionálním aspekty celého hra-prostoru.
[Proto] není snadno [srozumitelné] způsob, jak využít čtyř-D objekty na obrazovce dva-D, čtyři sub-pohledy jsou praktické metody pro manipulaci a vizualizaci rotace a překlady jednotlivých kusů přes čtyři rozměry ( ve hře zvané x,y,z,w).
Spíše než na dokončení okruhů bloky jako v původní, cíl je v tomto případě vyplnit kompletní kostky v x,y,z subview (obvykle 4 o 4 o 4).
Ostatní subviews, které obsahují "w" dimenze jsou uspořádány ve výchozím nastavení 4 o 4 o 10 bloku ujednání s "w" je dlouhá, "vertical" rozměr ve všech třech případech s různými základy (x,y), (x,z), (y,z).
Závažnosti činu v "-w" směrem, tak kusy "padají" ve třech dlouhých subviews, které zahrnují "w", a nemají pohybovat, pokud by hráč kontrolu v poslední (x,y,z) subview.
Bere na chvíli zvykat na to, aby přinejmenším.
Pokud by některé zázračné trpělivosti, nebo změnou parametrů hry, jedna se kompletní kostka, to zmizí jako dokončena řádky se v původní Tetris, i když ne skóre je držena v HyperTetris.
Benjamin Bernard (2000)
4.6 N-dimenzionálním Tetris
Polytope Tetris (2003): o N-dimenzionálním Tetris hru varianta
Polytope Tetris je n-rozměrově Tetris.
Vychází HyperTetris program, Polytope Tetris vám umožňuje hrát Tetris tun v každém POČET rozměr.
Hrát Tetris v 3D, 4D, 5D, nebo více.
HyperTetris je mnohem catchier jméno než Polytope (def) Tetris, ale nemohu ukrást jméno.
5. "Standardní Tetris" specifikace
5.1 Úvod
Definice "Standard Tetris" je idealizovaný model z nejdůležitějších vlastností a chování na prvním IBM-PC provádění této hře Tetris (cca 1986-1988).
Na idealizovaný model je založen na usuzující na zjevně záměr vývojářů z prvních IBM-PC provádění této hře Tetris.
Například se zdá rozumné, aby se domnívám, že vývojáři z prvních IBM-PC plnění ze hry Tetris určená pro výběr tvaru každý nový kus spadající "náhodně," a že použití těchto Borland C při rand() funkce byla pouze praktické sbližování záměru.
Definice "Standard Tetris" upřesňuje, že tvar každého nového spadající kus má být vybrána "náhodně."
Toto ideální chování nemůže být dosaženo žádné plnění, ale implementace může sblížit ideální chování.
I když ne zcela provedení lze provádět definici "standardní Tetris," ideály "Standard Tetris" zahrnovat objektivní vlastnosti a implementace může být porovnány podle jejich relativní blízkost k ideály "Standard Tetris."
Tento oddíl popisuje soubor prvků, chování a pravidla, která společně definují "standard Tetris."
5.2 Standardní Tetris palubě
Tato deska je mřížka buněk, s 10 sloupců a 20 řádků, pro celkem 10 * 20 = 200 buněk.
Standardní Tetris palubě (10 sloupců, 20 řádků)
Každá buňka může být buď neobydlených (prázdný), nebo obsazené (plné).
5.3 Standardní Tetris kusů
K dispozici je sedm (7) standardní Tetris kusů, s tímto dopisem názvy:
{ O, I, S, Z, L, J, T }
V dopise názvy jsou inspirovány tvary jednotlivých kusů.
Sedm Standard Tetris kusů a jejich "zaměření"
Tečka v (0,0) shoduje s palubě místo (6,20) kdy se poprvé objevila figurka.
První sloupec ukazuje počáteční "orientací."
V následujícím se slovo "orientace" se používá k popisu jakéhokoliv státu, na kus, ve stanovené povolené státy, které mohou vyplývat z proti směru otáčení událost.
Změna "orientace" z určitého "orientace" na "I, S," nebo "Z" kus, vyžaduje kombinaci otáčení a překlad.
Proto se slovo "orientace" je zde použito ve smyslu, který znamená něco více než střídání sám.
Nicméně, "orientace" může změnit pouze v reakci na otáčení proti směru hodinových akce a cyklus odlišné "směry" pro každý kus blíží, nebo zápasy, cyklus vyplývající z čistého obrátek.
Zvláštní použití slova "orientaci" v této souvislosti je téměř rovnocenné význam slova "otáčení" nebo "úhel," ale slovo "orientace" je použít místo "střídání" se pokusí přivést pozornost k tomu, že některé kusy vyžadují více než střídání vyrábět soubor povolena států vyplývající z akcí proti směru "otáčení."
Kusy mohou pouze přepínat zaměření (nebo se podrobil konkrétní horizontální nebo vertikální překlad), pokud výsledný stav této skladby by neměla mít žádné obydlené (plné) buňkách mimo oblast představenstva a nebude mít žádné obydlené buněk, které se překrývají jakékoli současné době buněk předsednictva.
(V tomto platí, že obsazené (full) buňky této skladby nejsou považovány za součást "aktuálně obsazené buňky představenstva"
V následujících komentáře, jakýkoliv odkaz na výsledek proti střídání případě je při předpokladu, že takový střídání může být ve skutečnosti provedeno, vzhledem k stávajícím podmínkám této skladby a hrací plochy.
Na "O" (krabice) kus pouze jediné orientace, a nemění umístění některého z jeho obsazené (full) buňky v reakci na každém případě proti směru otáčení.
Na "I" (linii) kus má dva možné směry, původně uvedené v horizontální orientace.
Na "I" kus náhradníky mezi oběma směry v reakci na po sobě jdoucí proti směru rotace událostí.
Na "S" a "Z" figurky mají dva možné směry.
Tyto kusy každého náhradníka mezi dvěma směry v reakci na po sobě jdoucí proti směru rotace událostí.
Na "L", "J", a "T" figurky mají čtyři možné směry, a tyto směry jsou výsledky jednoduché střídání centrum o body na tvary.
Když se poprvé objevila figurka na desce, tato skladba má své "hlavní osu" v horizontální orientace, a kousek je v horní části desky.
Proto žádné figurky jsou zpočátku schopné mají své zaměření změnila. Skladba musí klesnout o jeden řádek, který chcete mít možnost má své zaměření změnila.
Jednou za kus klesla o jeden řádek na palubu, všechna kus směry lze dosáhnout (za předpokladu, Skladba je ne příliš blízko u boční stěny nebo do současné pilot kusů).
5.4 Standardní Tetris vývojový diagram
Toto je přibližný, vývojový diagram pro standardní Tetris hry.
Přibližné vývojový diagram pro standardní Tetris hra
Přibližné vývojový diagram pro standardní Tetris hra
5.5 Standardní Tetris kus tvorba
Následující graf ukazuje (4 buněk * 2 buněk) regionu na palubě, kde jsou všechny figurky objeví, když vytvořili.
Kraj, kde figurky objeví, když vytvořena ve standardní Tetris
Při vytváření nového kusu poprvé objevila na palubě, její původ se shoduje s tečkou na tomto schématu, a tato skladba bude zcela obsažených v šrafované oblasti v tomto schématu.
Pokud je nová hra je spuštěna, plný volný-pád zpoždění uplyne, a na první volný-pád iterační kus je zplozený v horní části desky.
Při běžném hraní hry, kdy konkrétní volný-pád iterační "přistane" kousek, plný volný-pád zpoždění uplyne a na další volný-pád iterační kus je zplozený v horní části desky.
Když kus je zplozený, typ kus je vybrán pomocí následujícího algoritmu:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Protože tam je konstantní p (= 1/7) šanci na výběru konkrétního druhu na kus, a všechny kusy stejného typu jsou neodlišitelné, pravděpodobnost, s přesně k kusů na konkrétní typ po n zkoušek následuje Binomické rozdělení:
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 )
Když jsme se vybrat z 7 (sedm) kusů náhodně, pravděpodobnost získání konkrétního kusu je p=(1/7).
Pokud bychom to udělat n=70 časy, například, je pravděpodobnost získání přesně k kusů (s k v rozmezí 0 k n) je dána binomického rozdělení, jak ukazuje následující obrázek.
Binomické rozdělení na n=70, p=(1/7)
Takto je možno odhadnout průměrné celkové kusů jednoho typu uveden celkový počet náhodných kousků, a lze také vypočítat očekávané rozdíly a směrodatná odchylka (odmocnina z variance):
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
Když jsme převodu náhodné hodnoty na kus rejstřík, my to interpretovat takto:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[Předběžné-obchodní MS-DOS verze Tetris použili náhodné číslo funkce, kterou poskytují Borland Pascal kompilátor.
Tato funkce používal 32-bitové stav proměnné.
Proto se posloupnost náhodných čísel byl omezen na 2^32 odlišné hodnoty.
Proto v zásadě hráč mohl objevit po shození asi 10 kusů, přesné místo v souboru 2^32 čísla odpovídající aktuálnímu stavu hry.
Pokud Tetris simulace se provádějí s pevnou posloupnost 2^32 kusů, pak optimální rozhodnutí, lze nalézt na každém místě v pořadí.
(Zde se zdají být dostatečné příležitosti, aby byly na palubě zcela prázdné palubě stavu, umožní nám získat synchronizovány s precomputed optimální řešení, cesta.)
Riziko pomocí jednoduchého generátor náhodných čísel v simulací určených k nalezení optimálního řešení problému je v tom, že toto řešení bude optimální pouze na zvláštní cestu přes problém prostor určen jednoduchý generátor náhodných čísel. ]
5.6 Standardní Tetris kontrol
Během hraní hry, tyto vstupy jsou k dispozici na adrese:
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
Všechny vstupy v platnost na rostoucí-okraj pozitivní vstup (na stisknutí tlačítka, na rozdíl od tlačítka zpráva).
Při stisknutí tlačítka dojde, to se počítá jako žádost.
Držení tlačítka se po určitém čase by mohl vést k tomu, že "auto-repeat" funkce na klávesnici, vytváří nové stiskne tlačítko - ale tato vlastnost je mimo hru motoru.
Jednotlivé vstupy se stanoví výše v souladu s původní hře Tetris.
Otočit žádosti mohou být provedeny, pokud není žádný přesah mezi požadovanou orientaci a soubor buněk v současné radě (kromě klesající kus), a je-li požadované orientace nemá žádný soubor buněk mimo palubu oblasti.
Přeložit žádosti mohou být provedeny, pokud není žádný přesah mezi požadovanou přeložen konfigurace a nastavit buněk v současné radě (kromě klesající kus), a je-li přeložen požadovaný konfigurační soubor nemá buňky mimo oblast palubě.
Vstup žádosti jsou zpracovány s latencí, že záleží na rámu sazba hry (příklad: 75 Hz), a požádá v platnost (je-li to aktuální) okamžitě.
Figurka může být upuštěno, aniž by linie spadají kroky, k nimž dochází.
Figurka může být přeloženy několikrát do levé nebo pravé, a následně poklesla, to vše bez zažívá oficiální linie spadají krok.
Vzhledem k tomu, že nově zplozený kus nemůže být případně otáčet (protože to je přilepená na horní hraně desky), hráč musí přijmout alespoň jednoho kusu spadající krok, pokud jsou požadované střídání nebo požadované.
Vliv na skóre je nevýznamné.
5.7 Standardní Tetris kus "přistání"
Je-li figurka je prostě spadají, to spadá do jedné řady během každého kusu spadající iteraci.
Bude iterační že přesune z místa, bez kontaktu s horizontální povrchy, do místa, že má kontakty s horizontální povrchy. Jakmile tato iterace dojde, figurky jsou v klidové kontaktu.
Pokud iterační začíná kousek turistika v kontaktu s horizontálním povrchu, kus "pozemku," a stává se součástí statické pilot.
5.8 Standardní Tetris "linky dokončena"
Vyplněná řádku je řada na hromady, v níž všechny buňky jsou obsazené. Když vyplněný řádek je vylučován z hromady, a řádky nad sebou jsou odstraněny přesunula dolů o jeden řádek k odstranění mezery, to se počítá jako vyplněný "řádek."
Když se to stane kus pozemky část z hromady.
Ihned poté, co kus pole, hromady, je kontrolovat, zda jsou vyplněny řádky, a všech řádcích, se zruší.
Až čtyři řádky, může být dokončeny současně.
Následující tabulka uvádí horní hranice na tratích dokončeny současně o jediný kus:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Standardní Tetris "úroveň"
Standardní Tetris má 10 úrovní obtížnosti, očíslované 1 (jeden) prostřednictvím 10 (desítky), s úrovní 1 je "nejméně obtížné."
Úroveň indexu je nejvýše dvou hodnot:
actualLevel = max( initialLevel, earnedLevel );
initialLevel hodnota je na úrovni, že hráč si vybere při spuštění nové hry.
Toků na úrovni jako funkce dokončených řádky je snadno pozorovat v předvstupním-obchodní MS-DOS verze 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
Proto byl earnedLevel hodnota je vypočítána podle následujícího algoritmu:
if (linesCompleted <= 0)
{
earnedLevel = 1;
}
else if ((linesCompleted >= 1) && (linesCompleted <= 90))
{
earnedLevel = 1 + ((linesCompleted - 1) / 10);
}
else if (linesCompleted >= 91)
{
earnedLevel = 10;
}
5.10 Standardní Tetris spadající iterační zpoždění
Standardní Tetris má skutečnou-časové zpoždění mezi po sobě jdoucích řádek volný-pád iterace, která je v závislosti na aktuální úrovni obtížnosti.
Následující vztah mezi úrovní indexu a které spadají iterační prodlení je založen na opakovaném měření stopky na všech úrovních před-obchodní MS-DOS verze 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
Proto jsme se stanoví následující vzorec pro iterační prodlení hodnoty v závislosti na aktuální úrovni indexu:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Pokud se deska je prázdná, a neexistuje žádný vstup uživatele, což je zplozený kus na skutečné úrovni 1 pozemky v přibližně 10 sekund, a zplozený kus na skutečné úrovni 10 pozemky v přibližně 1 sekundu.
5.11 Standardní Tetris "skóre"
Standardní Tetris ocenění pouze body za úkon na přistání za jeden kus.
Neexistují žádné body udělené za tento akt na dokončení jednom řádku, nebo dokončení dva, tři, nebo čtyři řádky současně.
[Poznámka: Některé varianty Tetris udělování bodů za úkon na dokončení okruhů, se exponenciálně zvyšuje bonus pro stále větší počet současně ukončeny linky.
Proto se jedná o strategii pro maximalizaci skóre v těchto variant Tetris zahrnuje vytvoření příležitostí "získat Tetris," slang pro použití "I" tvar získat čtyři souběžné linie a získat spoustu bodů. ]
Pokud máte prázdné palubě, a nechat bez-"I" kus udělat volný-pád a zemi, nebo jste hned napsat pár "I" non-kus, můžete vytvořit následující bod grafu pomocí pre-obchodní MS-DOS verze 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" kusů pokles celkového počtu 18 řádků.
Jedná se o bod rozdílu mezi volným a instant-podzim-pokles případů.
Do experimentování s meziprodukty případech ji lze snadno odvodit následující bod vzorce:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Všimněte si, že tento vzorec nemá nic společného s vzdálenost kus spadne!
Je naprosto v závislosti na skutečné úrovni, a sankci pro počet iterací kus je dovoleno volně spadají.
Tento trestá uživatele pro potřebují čas na přemýšlení.
Upozorňujeme také, že proto, že kousek nemůže být na počátku otočit, když první tření, hráč je potrestán alespoň jeden volný pád iterační-li střídání jsou povinni umístit figurku do pilot.
To asi nikdy ovlivňuje lidské hráče, pokud nějak: uznávají kus, stiskněte překlad klíče "(vlevo" nebo "vpravo)," stiskněte "otočit" klíčem jednou nebo vícekrát, a stiskněte "pokles" klíče, to vše v méně než 0.5 sekund na úrovni 1, nebo méně než 0.05 sekund na úrovni 10.
6. Standardní Tetris strategie
6.1 Úvod
Strategie pro hraní hry závisí na pravidla hry.
Strategie závisí na parametru, který má být optimalizována.
Ve Standardní Tetris, jeden přežívá o vyplnění řádků, dostane body za přistání kusů, a skóre nejvíce možných bodů za každý kus příkazem poklesu před jedním nebo více volného pádu-iterace přihodit se.
An A.I. lze optimalizovat body uděleny za každý kus jednoduše tím, že rozhodla o přesunu rychle a "stisknutím klávesy" k výkonu tah.
Důležitější je A.I. na přežití, protože neurčitou přežití znamená libovolně vysoké skóre může být dosaženo. Vzhledem k tomu, že Tetris kusů pokles na zvláštní sazby, A.I. musí učinit rozhodnutí, alespoň toto rychle - a A.I. musí táhnout, že kompletní řady v míře, která v průměru nejméně 1 řádek za 2,5 kusů. (Každý kus má 4 buněk, a každý řádek má 10 buněk.)
Samozřejmě je možné odložit dokončení řádky akumulací kusů a budování velkých pilot, ale tam jsou jen 200 buněk na celé desky, která v zásadě může vlastnit pouze 50 kusů, takže každý hráč (např. A.I.) musí mít dokončení tratě základní prioritu.
Ve Standardní Tetris, hra obsahuje aktuální stav palubě povolání a aktuální spadající kus (typ, umístění a orientace). Hra stavu může volitelně obsahovat "Další kousek".
6.2 Střídavým posloupnost "S" a "Z" kousky
Heidi Burgiel, Ph.D., z Department of Mathematics, Statistics and Computer Science na University of Illinois at Chicago, se ukázal, že se střídají sekvence ze "S" a "Z" kousků bude platit standardní (10-sloupci, řádku-20) Tetris hru do konce v předvídatelném číslo tahů.
Citace z článku: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Přidružen tištěné článku: Mathematical Gazette, červenec 1997, "How to Lose at Tetris"
Heidi Burgiel nabízí Java applet, že běží v internetovém prohlížeči, že funkce upravené Tetris klon, že tření střídavý "S" a "Z" kusy.
[Tento "standardní Tetris" software související s dokumentem Čtete má také režim, který tření střídavý "S" a "Z" kusy. ]
Heidi Burgiel tvrdil, že hra s účastí střídavý "S" a "Z" kusy (pro standardní Tetris palubě o 10 sloupců a 20 řádků) musí být ukončen před méně než 70000 kusů poklesly.
Standardní Tetris softwaru obsažených v tomto dokumentu lze hrát hry s střídavý "S" a "Z" kusy, a změnit penze šířku.
Je snadno vidět, že prkna, jejichž šířkách jsou integer násobky čtyř sloupců (příklady: 4 sloupcích, 8 sloupy, 12 sloupů, atd.) mohou být přehrávány navždy, když kusů náhradníka mezi "S" a "Z", s pilot stoupá ne vyšší než 4 řádky. Uvádím to, aby bylo zřejmé, že omezená schopnost přežití je popsáno ve výzkumu dokumentu bylo uvedeno výše, je zvlášť pro případ standardní Tetris desky (s 10 sloupců a 20 řádků).
6.3 Neřešitelný kus posloupnosti obecně
Existuje celá kategorie patologické sekvence, které nemohou být přežil.
Bylo by zajímavé spočítat celkové pravděpodobnosti se potýká s hra-ukončuje sekvence, protože by to dát horní vázané na výkon jakékoliv strategie, dokonce s úplnou znalostí všech budoucích kusů v určitém bodě ve hře.
6.4 Celkem palubě možné konfigurace
Vzhledem k tomu, že deska má 10 * 20 = 200 buněk, a vzhledem k tomu, že každá buňka může být pouze v jednom ze dvou stavů (prázdné nebo obsazené), celkový počet konfigurací palubě musí být menší nebo roven: (2 ^ 200).
Vzhledem k tomu, že každý kus dodává, 4 buňky na palubě, a každý řádek dokončení eliminuje 10 clanku z hrací plochy, počet obsazených buněk na palubě bude vždy večera. Například (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, atd. Takto, pouze polovina z (2 ^ 200) palubě konfigurace může být dosaženo prostřednictvím hraní hry.
Čímž se celkový počet na palubě konfigurace je přibližně: (2 ^ 199) = 8.03469... * 10^59.
Nicméně, měli bychom vyloučit z našeho celkového jakékoli konfiguraci, která zahrnuje obsazena řádky, protože obsazena řádky se odstraní do konce roku každý ukončený tah. Každá konfigurace s jedním nebo více řádky budou obsazena kolaps na jinou konfiguraci, která nebude obsahovat žádné plněné řádků.
Také by měl vyloučit jakoukoli konfiguraci, která zahrnuje non-prázdný řádek nad jedním nebo více prázdných řádků, protože ne-prázdný řádek nad prázdnou řádku bude vždy klesat, a všechny spadají zastaví před koncem každého pohybu.
Každý řádek může být v 2^10 = 1024 států, z nichž jedna je "prázdný", z nichž jedna je "plná", a (1024 - 2) = 1022 na které jsou částečně-obsazeno. Jsme se vyloučit "plné" případ od projednání.
Je-li na spodní řádek je prázdný, pak všechny výše uvedené řádky, spodní řádek musí být prázdný.
Je-li na spodní řádek je částečně-obydlené, pak v druhé řadě může být prázdný nebo částečně-obsazeno.
Pokračování této analýzy, můžeme vypočítat řadu palubě konfigurace, která bere v úvahu pro vyloučení plné řádky a omezení na prázdné řádky: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), což je přibližně ((1022 ^ 19) * (1023)).
Proto jsme se najít přesnější odhad celkového počtu stabilní palubě konfigurace: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199), tj. zhruba 3,74% méně než (2 ^ 199) odhad.
Nicméně, skutečný počet stabilní, přístupný palubě státy bude pravděpodobně výrazně nižší vzhledem k tomu, že top-většina řádků může být vyplněna v několika způsoby. Vzhledem k tomu, že top-většina řádků vyplňte, nově vytvářené kus nemůže být přesunuta nebo otočena velmi mnoho. Toto omezení počtu cest the top-většina řádků je možné vyplňovat.
6.5 V zásadě platí, že nejlepší tah je možné najít na každém kusu lepenky a konfigurace
Vzhledem k tomu, že se můžeme dostat nějakou ze sedmi možných kusů pro jakýkoli daný rady státu, celkový počet hře jsou přibližně 7 * (2 ^ 199) = 5.624... * 10^60.
Vzhledem k tomu, že můžeme v zásadě udělat hluboký hledání všech možných budoucností pro všechny možné tahy pro danou hru stavu, můžeme mít jediný "nejlepší" tah, spojené s každou hru stavu.
Předpokládáme, že nemáme přístup k jakékoli jiné informace, než je aktuální rady a současným kus, tak "nejlepší" znamená "tah, který nabízí největší šanci na uspokojení našich dlouho-horizontu cílem přežití".
Posun je jen překlad (až 10 možností) a rotace (do 4 možnosti), můžeme snadno zakódovat nejlepší tah v jednom byte.
Ano, v zásadě jsme mohli vytvořit tabulku s 10^61 položky (bytů), který nám řekl, nejlepší tah žádný palubě stav a současné kus.
Samozřejmě, je to nepraktické, stejně jako výčet všech "Go" prken nebo "Chess" desky je nepraktické. Ale hlavní je, že neexistuje jediný pravý roztok, a tam je nejlepší tah pro dané konfiguraci. Tam by mohla být stejně dobré tahy na dané konfiguraci, ale může libovolně zvolit jediný tah v této věci.
Mnoho hra-hrací algoritmy mají tabulky, které taxativně vyjmenovat všechny hry stavu omezené možnosti v souvislostech, jako "otevření (původní) tahů" nebo "end-hra (v konečném znění) se pohybuje" v šachy. Snad vyčerpávající výčet Tetris pilot plochy (přibližně (20 ^ 10) států) je proveditelná. Je to zajímavý nápad.
Vyčerpávající výčet všech států na spodní dva řádky, vynásobený sedmi možných kusů, skladování a nejlepší tah v jednom byte, by bylo docela snadné, vyžadují pouze 7 MB paměti. Možná optimalizaci výkonu pro těchto sedm miliónů případů by poskytla prvotní údaje pro analýzu a vývoj jednoduchých modelů pro data, tyto modely by mohly být považovány za součást celkového ideální Tetris-hrací strategie.
Všimněte si, že nejlepší vykonávajícího pohybuje stále nemá chránit nás před možným patologickým hra-zastavuje kousek sekvencí. Je to, že budeme vždy provádět pohyby, které nám nabízí maximální potenciál pro budoucí přežití vzhledem k tomu, že všechny budoucí díly jsou zcela náhodné (a neznámá v době, kdy jsme se rozhodnout, jak přejít jediný současný známý kus).
6.6 Real-time performance
Jedním z omezení, kterým čelí některé strategie algoritmu je nutnost pro real-time výkon - což znamená, že algoritmus musí vydat rozhodnutí v určité množství času.
Když se lidské hraje Tetris, figurky se nezastaví na něž se dá hráč šanci přemýšlet. To je součástí této výzvy na Tetris. Proto může A.I. systém, který je určen k simulovat roli lidský hráč musí také učinit rozhodnutí, jehož míra je dána tím, Tetris hry.
6.7 Řádek a kousek součty
Všimněte si, že v dlouhodobém horizontu-, počet kusů, je upuštěno velmi blízko k 2.5 krát počet dokončených řádky - protože každý řádek má 10 buněk, a každý kus je 4 buněk, a musíme dokončit řádek, v průměru jednou za (10/4) = 2.5 kusů poklesly.
Takže můžeme použít "dokončena řádky" a "poklesl kusů" téměř zaměnitelně s odpovídající konstanta úměrnosti. Největší chyba je, když deska je zcela zaplněny, kromě jediné mezery v každém řádku (((10*20)-20)/4) = 45 kusů klesl, ale nedostatek, na předpokládané (45/2.5) = 18 dokončena řádků.
6.8 Aktuální-kusu (a fórum) strategie
Pokud bychom jen umožnit A.I. mít znalosti o aktuální rady a aktuální kus, a my jsme pouze tehdy, je výsledek pohybující současné kus a to zejména tak, pak to může být jmenován "one-kus" analýzy.
Zde je hrubý náčrt toho, jak s jedním-kus analýzy může rozhodnout o krok v Tetris:
Aktuální-kus rozbor, a Tetris hru stav
V podstatě se snažíme všech možných tahů a vybrat krok, který přináší nejlepší výsledek.
Obtížná je součástí hodnocení každého výsledku.
Musíme sazba hypotetického stavu zvěře podle toho, jak dobře tento stav podporuje naši-krátké a dlouhé období-období cílů.
Naše dlouho-horizontu cílem je přežití. Přežití závisí na prevenci pilot z přetékání desky. Můžeme snížit pilot výšku tvořící kompletní řádky, které jsou následně odstraněny z pilot.
Chcete-li vytvořit kompletní řada, my se musí vejít částí kusů v každém sloupci na této řadě. Proto je třeba všechny části po sobě mohli být vystaveni klesající kousky, chceme-li nakonec vyplnit celou řadu.
Pokud z nějakého důvodu si zakrýt prázdné části po sobě figurkami na případné vyšší řady, pak jsme nyní schopni vyplnit ty prázdné části řádku. Jediným způsobem (za předpokladu, ne posuvné) pro přístup k těm "pohřben děr" je pro odstranění výše uvedených řádků, které části působí jako překážky.
Následující faktory jsou mezi těmi, které můžete použít na kurzu dané palubě stav:
Overall pile height
Čím vyšší je pilot, je horší, naše situace se zdá být, protože jsme blíže k přetékání desky.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
Na hrubší hromady, tím pravděpodobnější je, že bude velmi obtížné vyplnit všechny vložené složitých kontur, jakmile budou vystaveny na povrch.
Number of buried empty cells
Čím více děr jsme pochovali, že naše situace je horší, protože musíme odhalit pohřben jamek před tím, než může splnit odpovídající řádky.
Můžete si představit jiné faktory, které obecně sazba hypotetického rady o tom, jak dobře jeho pilot může ubytovat všechny možné budoucí kusů, a jak dobré situace vypadá na všech těch možných kusů.
Dalším problémem je, jak určit relativní důležitost těchto faktorů.
Jeden obecný postup je následující. Přiřadit soubor "závaží" (relativní význam), aby tyto faktory, a potom simulovat mnoho her a rekordní výsledek z těchto her (konečný počet bodů, atd.). Poté, jmenovat novou sadu závaží a simulovat nový soubor her. Založen na tom, zda nová sada her měl lepší výsledky než předchozí soubor her, víme-li nový soubor vah byla lepší než předchozí sadu závaží.
V mé vlastní pokusy jsem se pokusil systematické vyhledávání a náhodné hledání na dobré hmotnost soupravy, ale jsem si vůbec nevšimne žádné velké měřítko-trendy, které bych mohl pokračovat. Nicméně, viděl jsem mnohé překvapivě hladké hrboly. Myslel jsem, že to bylo zajímavé, že průměrná výkonnost by mohla tvořit plynulé křivky, kdy parametr byl pomalu pestrá s ostatními parametry, které se konalo v některých hodnota kombinace.
Nejlepší real-time, jeden-kus Tetris algoritmus na světě, kterou vytvořil Pierre Dellacherie (Francie) v 2003, vděčí za mnohé ze svého úspěchu na své série měření (nebo údaje). Hledání váhy je nutné při optimalizaci strategie, ale že je rovněž důležité pro start s druhy měření, které odhalují relevantní charakteristiky státu.
Pierre Dellacherie's vynález na nové způsoby, jak charakterizovat každé palubě jeho algoritmus je opravdu vynikající, desce characterizations zachytit důležité strategické rozměry hrací plochy státu.
Jeden by mohl vytvořit velmi odlišné soubor popisu rozměry, které fungovaly stejně dobře, jsem přesvědčen, že je možné spojit příslušné palubě stavový prostor v mnoha různými způsoby, které mohou být použity k zadání strategie funkce. Nejdůležitější je najít charakteristiky, které projekt stavový prostor až na malý počet rozměrů, který může být použit k vytvoření jednoduchého hodnocení funkce (například: vážená lineární kombinace charakteristik používaných Pierre's algoritmus).
Ten-Piece algoritmu, které jsou používány "bot" v "xtris" software (1996) napsané Roger Espel Llima používá váhy stanoví velký-měřítko zkoumání možných kombinací hmotnosti o "genetické algoritmy". Simulované žíhání je další možný způsob zkoumání vícerozměrný prostor hmotnost soupravy.
Zdá se, že na základě různých vyjádření, vícerozměrné funkce Tetris průměrný výkon v závislosti na hmotnosti, například: F(w1,w2,w3,...), je "drsné" (šarže na místní minima a maxima), což znamená, že jednoduchá vícerozměrný "výstupu na vrchol" nemusí fungovat.
6.9 Strategie při současné kus, další kus, a desky jsou známé
Pokud strategii algoritmus je uveden současný kus, další kus, a rady, pak to může učinit rozhodnutí, které využívají kombinace kusů.
Znalost další kus může zvýšit úspěšnost na Tetris hraní algoritmus o několik řádů. Je snadné pochopit, jak jsou známy další kousek je velký rozdíl ve strategii.
Jeden může dělat "šílený" tahů, jako pokrývající obrovské otvory, atd., protože již víme, že další kus je možné použít na "opravu" situaci. Pokud nemáte znalosti o další kus, ty jsi stále se snaží hrát s kurzy, snaží se, aby se vaše možnosti v případě, že další kus není ideální.
Následující nákres ukazuje, jak všichni z možných tahů na současné jsou považovány za kus, a pro každý takový tah jsme v úvahu všechny možné tahy zahrnující vedle tyče.
Strategii, zahrnující současnou kus a další kus
Standardní Tetris software používá tuto strategii, kdy se "Další kousek" je povolen uživateli a je viditelná na obrazovce, a když se dvou-A.I. je povolena (například ten, který napsal mnou, Colin Fahey). Je-li "Next kousek" a není vidět na obrazovce, má dvou-padá zpět na jedno-kus A.I..
Můj jedno-kus A.I. je hrozné, když v porovnání s ostatními AIs ve standardní Tetris software, tak toto ukazuje prospěšné více informací (příklad: další kus) může být na A.I. systému, to je dost zlepšit účinnost svých vlastních průměrná dvou-A.I. o několik řádů - snadno překonal výkon nejlepší-kus A.I. na světě.
(Nicméně, konverze nejlepší-kus A.I. ve světě, aby zvážily dva kusy by snadno vylepšit o několik řádů taky! Vědět další kus je obrovský!)
Moje první zkušební hře se svým dvou-A.I. trvala zhruba 182 hodin (7,6 dnů) o 800 MHz PC, dokončení 7216290 řádků. I nebyly testovány algoritmu na rychlejší počítače.
Při ukládání stavu a Tetris hru (Shift-W) do textového souboru, můžete pak zkopírovat a vložit do seznamu čísel, z části "heightHistogram", aby aplikace Excel tabulku.
Každý koš v histogram udává počet dokončených tahů, že skončil s určitým pilot výšky (po kompletní řádky jsou odstraněny). Jak jste si jistě umíte představit, tedy krok, který zcela ruší pilot je vzácné, takže celkový počet tahů, že končí s pilot výšku na nulu je poměrně nízká.
Mezitím můžete očekávat, že pilot výšky obvykle pohybuje kolem některé průměrné, tak v bednách odpovídajících těchto řádků bude dominovat histogramu. Nakonec koše pro top-většina řádků (kde jsme v nebezpečí přetékání desky) mají velmi nízké součty.
V průběhu mnoha hodin, s A.I. hraje jediný zápas pomocí strategie zahrnující znalosti o "Další kousek", vzal jsem náhodný vzorek ze hry stavu, kopírování pilot výšky histogramy do tabulky tak, jak je uvedeno níže:
Pile výška histogramy zaznamenaných na různých místech v typické hry (s aktuální-a-next-kus strategie)
Můžete rozsahu každý histogramu o celkovém počtu kusů (celkový počet dokončených tahů), aby si tyto údaje:
Okujeným histogramy, a teorie
Pozoruhodné je, že tyto šupinatý histogramy pohled shodný i přes různé řádů na počtu kusů (dokončeno tahů) podílí.
Jen při pohledu na čísla jsem vytvořil hypotézu, že za ocas na křivce je exponenciální útlumu. Dle pokusů a omylů jsem přišel s teorií, že surové ocas byl popsán podle:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Následující graf ukazuje měřítko histogramu na celé spektrum řádků.
Graf šupinatý histogramy
Všimněte si, že křivka na 50000 kusů a křivka na 2000000 kusů, a křivku ocasu teorie je téměř nerozeznatelný v tomto rozsahu.
Následuje bližší pohled na hlavu křivky.
Výška spodní část histogramu
Toto je velice-zvětšený pohled na krajní zadní část z naměřených a teoretických histogram křivky.
Zvětšený pohled na extrémní konce šupinatý ocas histogramy
Jak můžete očekávat, to je velmi vzácné pro pilot k dosažení těchto výškách ještě dlouho experimenty - ale dokonce i s naší omezené důkazy v této extrémní oblasti, teorie se zdá být stále ještě přijatelné.
V plné grafů a teorie se zdá, že se překrývají ocasu na distribuci "přesně", vzhledem k tomu, že ve veliké graf z ocasu na ocasu, vidíme zjevné chyby. Nicméně, já tvrdit, že je to způsobeno nedostatečným údajům v těchto extrémních výškách pilot. Pokud jsem zvýšil hra na palubě, jak se říká, výška 25 řádků namísto 20 řádků tak, aby hry nebyly ukončit náhle, myslím, že teorie jsem uvedeny výše, by se dokonale shoduje s trendem.
Můj pocit je, že tento histogram je přímým důsledkem kombinované s Tetris A.I. a pravidla na Tetris. Ano, je tato distribuce bude třeba dodržovat při jakékoliv náhodné-dlouhé období hře Tetris pomocí mého zejména A.I. strategii pro hraní s "Další kousek" znalostí.
Kromě toho si myslím, že tento typ histogramu je možné použít k porovnání AIs, které zaměstnávají stejné informace při přehrávání. Proto nemusíte hrát kompletní hry (což by mohlo trvat dny nebo roky) porovnat dlouho-termín plnění odlišnou strategii algoritmy.
Pro příklad, i přes jednoduchost můj vzor, myslím, že to může být použit k odhadnout průměrnou dobu trvání hry! Prostě na to, kolik kusů je "řádek 21" pilot výšky značný počet, jako je například počítat jednoho.
Relativní četnosti na řádku 21, podle mého jednoduchá teorie, je:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Ty musí vynásobit tento počet o (5.3 * 10^(7)), zhruba 50 milionů, abyste získali hodnotu jedna.
Proto jsem zhruba předpovědět, že naše současná "Další kousek" strategie je pouze dobrým o pořadí na zhruba 10 milionů dokončena řádků. Jedním z důvodů, proč jsem to konzervativní odhad je skutečnost, že dokonce 18 řádků může být smrtící pro mé A.I. protože jsem neumožňují můj A.I. zvážit kusů až do doby, kdy jste snížil o nejméně jeden řádek! (To je tak nemám bát, že nemohly střídat kusy.)
Jsem ohromen tím, že hraje pouze 50000 kusů (a možná i mnohem méně kusů), může vám velmi dobrý odhad na dlouhodobém horizontu-výška histogram, a tudíž i dobrý odhad z řádově dokončených řádky před hra končí. Tento přístup je nesmírně cenný pro rychlé posouzení, jemné změny v A.I. to již dělá velmi dobře.
6.10 Radě hodnocení metriky napodobit spekulativní vypadat před -
Pokud algoritmus, jako je například představil jsem se na tomto projektu, prostě se snaží všemi směry kus a překlady pro výsadky, a sazby vyplývající palubě každé konfigurace podle některých opatření na zásluh, algoritmus je v podstatě napodobují "vzhled-ahead".
Když jeden zaměstnává metriky jako "pilot výšky", "pohřben děr", "drsnost povrchu" nebo "i hloubkách", jedna se opravdu používají zjednodušené formě na "pohled dopředu". Tyto obecné characterizations představenstva poskytnout údaje o dlouhodobém-dlouhodobé životaschopnosti představenstva.
Ideální přístup, vzhledem k tomu, nekonečné množství výpočetní výkon, by bylo, aby zhodnotil palubě dané konfiguraci všech možných kus sekvencí, které mohou následovat.
I když je třeba zvážit všech 7 kusů za stejně pravděpodobné, na každé úrovni, na pohled-vpřed, je třeba optimalizovat skutečné překlady (do 10) a směry (až 4) pro každý kus ve všech možných pořadí! To je až (7*10*4) = 280 pobočky na každé úrovni představenstva hodnocení! Tak, to je až na palubě ((280)^(LookAheadLevels)) konfigurace, aby zvážila.
Protože musíme ukončit analýzy po konečný počet úrovní, musíme mít nějaký ne-look-napřed způsob hodnocení palubě stav - jako způsob, jejichž hodnoty se listy uzly na naši vyhledávací strom. Takže pro tyto listové uzly, jsme zpět podle vzorce, který obsahuje obecné ukazatele budoucnosti životaschopnost tohoto palubě!
Tento druh spekulací mohou být souzen s One-Piece a Two-Piece algoritmů v místě jednoduchými palubě vyhodnocení měření. Předpokládejme, všechny následující díly jsou stejně pravděpodobné a shrnul znalosti na základní desku, aby se kousky všeho druhu v nejlepším možným způsobem. To může být provedena s jedním, dvěma, nebo libovolný počet spekulativní tah hloubky - se všechny kusy jsou stejně pravděpodobné (p=1/7).
Terminál uzly tohoto stromu může ještě požadovat, aby vážený metriky pro vyhodnocení, ale spekulativní vrstev přesněji zachytit podstatu toho, co chceme dělat: Zjistěte, jak dobře dané palubě může přijmout všechny možné kousky, včetně pozitivních faktorů, jako je dokončení linky a negativní faktory, jako zvýšení celkové pilot výšky, atd.
7. Tetris A.I. systém demonstrace
7.1 Přehled systému
Tento Následující graf ukazuje mé experimentální set-up.
Celý systém pro demonstrační
7.2 Vybavení
Zde je stručný seznam zařízení použitých v této demonstrace:
[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)
Je zřejmé, můžete použít obdobné zařízení pro dosažení stejných výsledků. Více informací o zařízení jsou popsány v příslušných částech tohoto článku.
Zde je stručný popis na osobní počítače používané v této demonstrace:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Tato demonstrace by mohly být snadno opakovat s jinými operačními systémy, jako jsou Linux. Je důležitější mít CPU rychlosti o řádově 800 MHz nebo rychleji k počítači, který je ke spuštění A.I. software, protože tento počítač bude dělat real-time zpracování videa.
7.3 Video zachycování hardware
Využil jsem společné USB videokamera jako zařízení pro digitalizaci videa na mé A.I. systému. Konkrétně jsem použil Creative "WebCam Pro", je USB video kamera s 640 * 480 usnesení.
Creative(TM) USB videokamery popis
USB video kamery (v úhlu)
USB video kamery (přední)
USB video kamery (deska s CCD)
USB videokamery (hlavní čipy)
OV511 hlavních bloků (poznámka: USB video kamera je OV511+)
7.4 OV511 list
ov511ds.pdf
OV511 listy
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "plus"), což rozdíly
ov511plus_101.pdf
OV511+ Motiv Rozdíly
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Video zachycování software
Microsoft má velmi staré API názvem "Video for Windows" (VFW), že jsem úspěšně použit pro tento projekt. (Chcete odkaz na "vfw32.lib" ve vašem C++ projektu, nebo udělat DllImport na "vfw32.dll" ve vašem C# kód.) Příklady použití VFW API jsou široce dostupné.
Alternativou je použití Microsoft's "DirectShow" API udělat pro digitalizaci videa.
Protože VFW trvalo jen několik řádků kódu k použití, a provedena přijatelně na mých 800 MHz stroj, jsem se obtěžovat prozkoumání alternativních APIs. Ale DirectShow je více současných API pro Windows digitalizaci videa, výnosy a potenciálně mnohem vyšší rám sazba pro stejný hardware.
Podívejte se na "CPF.StandardTetris.STVideoCapture" zdrojový kód soubory ve standardní Tetris software a uvidíte, jak snadné je získat pro digitalizaci videa se ke své vlastní projekty.
7.7 Počítačové rozhraní pro relé (přes RS232)
Chcete-li mít jeden počítač "stiskněte klávesy" na klávesnici na jiném počítači jsem používal "relé board" řízené textové příkazy poslal ze sériového komunikačního portu (příklad: "COM1") prostřednictvím RS-232 kabel. Využil jsem každé relé pro připojení dvou vodičů na konkrétní klávesnici klíč k simulovat stisku tlačítka.
To vyžadovalo otevření klávesnice a tvorby spojů. Existuje mnoho jednodušší metody simulující stisknutí klíče na počítači, ale já chtěl udělat něco, aby se zdála tak blízko, jak je to možné, aby osoba, opravdu napsáním na klávesnici.
Jeden z velmi univerzální a dobře provedené-relé palubě je ADR2200 provedené Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Můžete se podívat na "CPF.StandardTetris.STRS232" zdrojový kód souborů, aby viděli, jak snadné je odeslat bytů prostřednictvím sériového portu, které potom mohou být použity k ovládání zařízení, jako je ADR2200 palubě je uvedeno výše.
8. Standardní Tetris software
8.1 Stažení software
Přejít na začátku tohoto článku najdete odkaz na stažení zdrojového kódu (C# a C++ verze) a postaven software (*.exe).
8.2 Shrnutí funkcí
Softwarové funkce:
Pokyn obrazovek a úvěry
Monochromatický režim
Stínová režimu
Tip režimu
Junk řádky
Hodnotit kontroly
Další kus
Rada velikosti
S/Z kusů
Kalibrační režim
Video zachycování a uznávání
Ladění konzole
Uložit hru
Zatížení hra
8.3 Počínaje vzhled
Vzhled, kdy software je zahájeno:
Vzhled, kdy je software začala
8.4 Monochromatický režim
Ve výchozím nastavení hrací plochy se jeví v barvě:
Ve výchozím nastavení hrací plochy se jeví v barvě.
Barevný režim může být změněn na černobíle (Shift + K):
Barevný režim může být změněn na černobíle.
8.5 Stínová režimu
Stínová režim označuje za jeden kus, kde přistane. To je velmi užitečné pro velmi velké kluby, protože je těžké posoudit, kdy bude kus země.
Stínová režim označuje za jeden kus, kde přistane.
8.6 Tip režimu
Tip režim vám ukáže, kde se v současné době AI-selected by pohybovat vzhledem ke stávající situaci. (Shift + H)
Tip režimu ukazuje, kde se v současné době AI-selected by tah.
8.7 Junk řádky
Vložit "smetí" řádky v dolní části pilot, jeden po druhém ručně. (Shift + J)
Vložit "smetí" řádky v dolní části pilot.
8.8 Hodnotit kontroly
Na '+' (plus) a '-' (minus) klíče kontrolovat rychlost hry.
Ve výchozím nastavení je hra běží na standardní rychlosti, podle pravidel Standard Tetris (rychlost založenou na úrovni).
Zde je přehled význam rychlost zkreslení:
-3,-4,...: pomalost v poměru k zaujatosti
-2: pomalejší než úroveň 1
-1: normální, avšak s omezením na úrovni 6 (0,2 sec) rychlosti;
0: normální, standardní Tetris kontrolu rychlosti;
+1: mírně rychleji, než na úrovni 9 (0.05 sec zpoždění);
+2: ohraničené scény míra (příklad: 75 Hz);
+3,+4,...: více iterací za poskytované rámu;
Líbí se mi spustit A.I. v nastavení na "+2" (hit '+' klíč dvakrát, pokud zkreslení začíná na nule).
Speed zkreslení nemění na rychlost hry.
8.9 Zobrazit další kus
Hit 'N' přepnete "Další kousek" displej. Na A.I. bude používat "Další kousek" informace pouze v případě, že "Následující kousek" se objevuje na obrazovce.
Můžete si být jisti, že AI je nepoužíváte "Další kousek" informace, když nemůžete vidět "Další kousek" na obrazovce.
Zobrazit další kus
8.10 Rada velikosti
Stiskem Ctrl + (vlevo, vpravo, dolů, nahoru), lze upravit velikost hrací plochy, aby z libovolných velikostí 4 * 4 do 200 * 400.
Rada velikosti: 4 * 8
Rada velikosti: 20 * 40
Rada velikosti: 40 * 80
Rada velikosti: 20 * 5
Rada velikosti: 4 * 100
8.11 S/Z kusů pouze
Studijní zajímavé střídavý S/Z vzor.
Tento model nelze řešit na palubě 10 * 20 (šířka x výška).
Nicméně, desky, které mají šířky, které jsou dělitelné 4 jsou triviálně prokázáno, že povolení k nekonečné přežití.
Na neurčito AIs přežít v těchto případech, i když nebyly výslovně sladěny tak, aby s tímto patologickým situace.
S/Z kusů pouze
8.12 Video kalibrační režim
Hit 'C' a zadejte "Kalibrace Mode". Když v kalibračním režimu, můžete kliknout na počet kláves: {1,2,3,4,5,6,7} vybrat kus {O,I,S,Z,L,J,T} v horní části hrací desky.
To je užitečné jako referenční obraz pro digitalizaci videa na druhou Standard Tetris software.
Pokud jste narazila na 0 (nula) klíč, to učiním desky prázdné.
Můžete předstírat, že třít kusů výběrem kus (1..7), a tak výběr prázdným (0), zatímco druhý počítač dělá pro digitalizaci videa hodinky na kusy.
Můžete spouštět A.I. na druhém počítači a uvidíte, jak to se zabývá váš manuálně zadaných patologických Tetris scénáře!
Způsob kalibrace je jediným času můžete ovládat video zachytit zpracování obrazu šablonu (4 * 2 sítě). Můžete použít myš k tomu obdélníku, ale pak můžete využít kurzorových kláves ( "up", "dolů", "vlevo", "právo"), aby byly v pohodě kontrolu nad hranicemi - používá Shift klíč k výběru opak hranice obdélníku (příklad: "Shift-left" kombo je jiný než "levice").
Video kalibrační režim
8.13 Video zachycování a uznávání
Stiskem 'V' přepíná video zachytit režimu. Pokud správně kalibrované (viz "video kalibraci" v předchozí části), figurky na vzdálený video obrazovky budou ošetřena v rámci videokamery a klasifikované - a kousky bude zplozený v místní hru pro A.I. zvážit a reagovat .
A.I. na výstupu pak musí být předány (přes rozhraní RS-232 v demonstraci popsané v tomto článku) pro vzdálený hra vstupu (např.: klávesnice) pro A.I., aby se úspěšně hrát vzdálený hry.
Pokud kdykoliv tento uzavřený cyklus je narušený (příklad: zachytávání videa porucha, nebo výstupní signál porucha), pak se bude rozvíjet A.I. klamnou představu o stavu vzdáleného hra, a A.I. bude nevhodně rozhodnutí, která rychle ztrácí hru .
(Poznámka: Tento problém lze překonat za skromné množství úsilí: V A.I. systému potřebujete pouze prozkoumat celou obrazovku vzdáleného Tetris pro pokračování "Reality Check" v rámci celé desky a A.I. systém by měl být připraven na některé výstupní příkazy k selhání v některých způsobem.)
Video zachycování a uznávání
9. Původní Tetris AI experiment (2003)
Následující ukazuje první pracovní verzi tohoto Tetris A.I. systému v roce 2003.
Video kamery čelí počítačové # 1 běžet žádné obyčejné hře Tetris
Počítač # 2 Standard Tetris software běžící v režimu A.I.
Vlevo: Kresba mřížka pro kalibraci video obrazu;
Právo: Tetris kus uznání případech.
Rám z videa na Tetris A.I. experimentu v roce 2003
10. Nejlepší jedno-kus Tetris-hrací algoritmus ve světě
10.1 Pierre Dellacherie (2003, Francie)
Pierre Dellacherie (2003, Francie), vývojář z nejlepších jedno-kus Tetris-hrací algoritmus ve světě
Nejlepší jedno-kus, real-time Tetris algoritmus k mé znalosti byl vytvořen Pierre Dellacherie z Francie.
Jeho úžasný algoritmus někdy vyplní více než 2 miliony řádků!
Průměrná výkonnost je v pořadí 650000 řádků.
Algoritmus bere velmi málo paměti a běží na vysoké otáčky (asi 160 řádků za sekundu na mých 800 MHz počítač).
Výkonnost Pierre Dellacherie's algoritmus:
Můj současný model pro plnění Tetris ověření pravosti je, že pro daný kus je konstantní pravděpodobnost, že hra skončí, p.
Proto pravděpodobnost, že kus nebude ukončit hru je q=(1-p).
Pravděpodobnost, že hra se zastavuje po k tahů je prostě součin pravděpodobností přežít (k-1) tahů, a to q^(k-1), a pravděpodobnost, že se zastavuje na příští tah, a to p.
To odpovídá 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 )
Pro malé p, ln(q) je zhruba (-p), a máme následující:
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čekáváme, že zlomek z celkového počtu hrají hry vypovědět s řadou dokončených řádků v intervalu [k1, k2] být:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Po dokončení 36 her na počítač, po dobu dvou dnů jsem našel v průměru 674827 dokončena řádků.
Podle obecné teorie výše, bych se očekávat, že tyto relativní podíl na hry, aby mohl dokončit v následujících řádek vyplněn rozsahy:
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
Zde je graf, který porovnává Exponential Distribution teorie s pozorovanou distribuci her.
Výkonnost algoritmu Pierre's dokončeno více než 36 her
Přestože existuje jen velmi málo her v tomto souboru údajů, je zřejmé, že model je poměrně dobrá shoda v pozorovaných distribuce.
Pierre's úvod k jeho algoritmus:
Pierre začal pracovat na tenhle kus-algoritmus v 2003,1.
Pierre mi poslal e-mail o jeho algoritmus na 2003.4.9, hlášení následující funkční po dobu 20 po sobě jdoucích zápasů:
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.
"Algoritmus je implementován v Turbo Pascal a završuje 7000 řádků / min. S Athlon 1600+."
I převedeny Pierre's algoritmus k C++ ve 2003,6, po několika e-mailových výměn s Pierre. Máme ověřeno, že A.I. v C++ verzi učinil stejné rozhodnutí ze Pascal verzi.
I pozorovat podobný výkon na jeho původní zprávy; průměru kolem 650000 dokončena řádky, a některé hry dokončení 2 miliony řádků.
Neuvěřitelné!
10.2 Konverzace s Pierre Dellacherie
[1] Pokud jste si nejprve vytvořit tento kód?
Byl jsem pracovat v algoritmu od konce ledna 2003 až do současnosti.
[2] Jak dlouho jste pracoval na to?
Pracovala jsem na to skoro každý týden ... ale ne každý den dlouho, protože jsem jiné aktivity: bohužel musím vydělávat peníze jako kdokoli jiný!
[3] Co inspirovalo návrhu kód?
Já jsem hrál Tetris 10 nebo 15 lety, ale neměl jsem hrál opět na dlouhou dobu. Řekl bych, že jsem "průměrné" hráče kteří ví, pravidla a některé triky.
Nicméně, když jsem začal pracovat na algoritmu jsem nehrál tolik, protože jsem to byl spíše účinnější sledovat v počítači hraje a analyzuje jeho slabiny.
[4] Měli byste používat žádné automatizace do "vlaku" váš kód pro výkon lepší? Líbilo se máte nějaké náměty na zlepšení algoritmus?
Nebo jste prostě dívat na výsledky a rozhodnout, aby se změny?
Jsem ze "staré školy:" prostě jsem koukal na výsledky a rozhodl se provést úpravy.
"Automatické učení" je druh meta-algoritmus, takže jsem neměla jistotu, že když to takhle bude mít snazší, protože meta-algoritmus by musel být postaven příliš a že není tak jednoduché!
Co víc, já souhlasím s Roger Penrose, když říká (ve své knize "Shadows of the mind"), že lidské porozumění a intuice nemůže být algoritmické (příklad: vyčíslitelné).
[5] Kdy jste poprvé začít hrát Tetris, a když to máte představu o řešení Tetris s A.I.?
Učím algoritmické a počítačové programování (Turbo Pascal a Scilab) pro studenty, kteří vlakem na přijímací zkoušky na postgraduální technických školách.
Na první, "Počítačové hry Tetris" byl nápad jsem chtěl vyvinout pro mé studenty v příštím roce.
Nebyl jsem si vědom své webové stránky, když jsem začal pracovat na algoritmu.
Ve skutečnosti jsem byl šťastný, aby si byl vědom své webové stránky pouze v několika málo týdny, protože si myslím, že bych byl znechucený tím, vaše výsledky (jak můžete hádat, raných verzí můj algoritmus nehrál tak dobře!).
[6] Jaký je Váš současný stav?
Je mi skoro 30 [před rokem 2003 27. dubna]. Mám několik činností: Já a violoncellista, jsem komponovat hudbu a učím počítačové programování.
Mám magisterského studia v oboru hudební vědy (1994) a "Artificial Intelligence and Algorithmic" diplom (1998).
Ve Francii tento diplom odpovídá 5. rok studia na univerzitě (4. rok je magisterského studia a 6. rokem je práce).
Pierre's skladby:
[7] Pokud bydlíte?
Já jsem francouzsky a žiji v Rouen (Normandie).
[8] Další komentáře:
Nakonec jsem neměla žádné nové nápad na zlepšení.
Jsem zkoušel tolik zbytečné (a hloupé) věci, které já pochybuji, že by mohla být lepší.
Na druhé straně si myslím, že by mohla existovat zcela jiné algoritmy, které by mohly mít lepší výsledky.
Mimochodem, rychlejší test skládají při zahájení kusů v půl-box (10 řádků x 10 sloupců): v půl-box, můj algoritmus činí v průměru na 280 dokončených řádků.
Ještě jedna věc: algoritmus lze snadno měnit v dvojitou-vrstvou algoritmu ([Udělám] zkoušek brzy).
Mám rád filmové hudby: čím filmový skladatel je součástí mé hlavní sny (ale je to jen sen!).
11. Nejlepší hráč lidí na světě
11.1 Japonsky Tetris Master (2001 27. ledna) video
Tetris mistr (2001, Japonsko) video
Arika představuje japonsky Tetris Finále mistr (2001 27. ledna). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Zpětná vazba
12.1 Slashdot nit (2003)
V roce 2003, můj Tetris A.I. projekt byl projednán na Slashdot internetové fórum (
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 ]
Comic inspirován mým Tetris A.I. projektu (2003) (první chvíle, co jsem si kdy inspirován komiksu!)
Comic inspirován mým Tetris A.I. projektu (2003) (podruhé jsem si kdy inspirován komiksu!)
13. Historie z Tetris A.I. projektu
Na jaře roku 1989 jsem byl zaneprázdněn přeskakuji (a jinak) za druhé pololetí-nováček třídy na University of Pennsylvania.
Jeden z mých spolubydlící, Bill Matthews, kdyby Mac Classic, a někdy hráli videohry.
Lidé kteří si přijaty k Ivy League školy jsou obvykle nakloněny soutěžit s ostatními lidmi v každé době - tak při Bill tu hru Tetris pro jeho Mac, jsme ihned začali dlouhou-období bitvy na vysoké skóre.
Vzhledem k tomu, že skóre vyšplhal, čas investic nutných k tomu, aby malý zisk dramaticky zvýšil.
Chcete-li udělat dlouhý příběh krátký, Bill údajně drží na vysoké skóre mezi námi, ale myslím si ho pomocí ResEdit a hacking skóre soubor!
Bill měl tříd v Wharton škola podnikání, alma mater na Michael Milken a Donald Trump, tak to není nemyslitelné, že někdo o zmanipulované nemožně vysoké skóre ...
V létě roku 1990 jsem vypůjčené a 30 MHz Intel 80386 IBM PC z mého spolubydlícího, Alex Haidas.
Koupil jsem Mac klávesnice na bleší trh za 1 dolar.
I vybudoval paralelní port obvody, které umožní PC kontrolovat Mac klávesnice.
(I used a CMOS 4040 čip, aby jednala jako typ solid-state-relé, aby se připojili klávesnice kontakty uvnitř Mac klávesnice.)
Napsal jsem počítačový program, který použili rozhodovací strom, protože jeho strategie pro hraní hry Tetris. Jen v několika málo týdnů jsem měl PC hrající Tetris Hra běží na Mac.
Nicméně jsem se požaduje, aby používaly PC klávesnice sdělit A.I. o každém pádu kusu na obrazovce.
Začal jsem pracovat na obvodu pomocí CdS (Cadmium Sulfide) světlo detektory, které by libového proti Mac obrazovku a "vidět" klesající kousky, ale CdS senzory reagovala příliš pomalu na změny v jasu a kontrastu mezi Tetris kusů a pozadí na obrazovce Mac Classic byla příliš nízká na to, aby spolehlivě diskriminovat.
V těch dnech jsem neměl moc peněz, takže to bylo příliš riskantní, aby si koupili $ 2 Radio Shack fototranzistor, že nemusí dělat to, co jsem chtěla.
Také vzhledem k tomu, kontrast problém, byl jsem pesimistický o celý přístup.
Když jsem koupil můj první osobní počítač v roce 1996, jsem nemohli získat software pod Windows 95 na 100 MHz CPU udělat video zpracování dostatečně rychlý, aby se vize jednoduchého systému práce.
Napsal jsem obraz zpracování kódu v jazyce symbolických, ale tam bylo tolik režijních před mým kód skutečně obdržela video data, která to zdálo nemožné udělat něco užitečné.
V roce 2003, technologie, zejména CPU rychlost, dosáhly takové úrovni, aby se vypracování projektu téměř bezvýznamné.
Já jsem vykopal můj starý osobní projekt a konečně dokončil to, dostat některé smysl pro uzavření.
Bylo to velmi vzrušující vidět na jednom počítači hraje jiného počítače prostřednictvím USB videokamery a relé.
Zvuk také relé kliknutím, a dívají se na kusy spin a pokles na směšné, nadlidskou rychlostí, učinili zkušenost velmi vyhovuje v Multismyslové způsobem.
V roce 2003, moje práce byla uznána Slashdot (
http://slashdot.org), a obdržel jsem hodně důležitý.
Byl jsem vyzván k účasti na "Screen Savers" televizní show na TechTV digitální televizní sítě.
Šel jsem do San Francisca a objevil na show, a zkušenost byla veliká.
Později v 2003 jsem obdržel zprávu od Henk Rogers, pozvání na Havaj k němu a Alexey Pajitnov hovořit o založení jakési normy pro Tetris, kterým se pro účely s Tetris turnajů.
Jeden zvláštní zájem byl umožní hráči používat mobilní telefony "konkurovat navzájem," nepřímo, prostřednictvím A.I. že imitates hráčů (po předchozí analýzy každého hráče činnosti), čímž by se zabránilo jejich účinky na mobilní telefon latence přístupu k internetu, a umožňuje hráčům "soupeřit proti" * Nejlepší lidské hráče na světě (*... nebo spíše A.I. napodobují ty nejlepší lidské hráče na světě).
Byla jsem nadšená z vyhlídky na zasedání tvůrce Tetris. Bohužel, létání je mi starosti, a já jsem odmítl pozvání.
V roce 2006 jsem převedeny můj "Standardní Tetris" software z C++ k C# aby se tento software více přístupné a užitečné pro současné programátory.
