Tetris
Colin Fahey
1. Oprogramowanie
StandardTetris_2007June4.zip
Tetris kodu źródłowego (C# i C++ wersje) oraz program ("exe");
4068277 bajtów
MD5: 4e957e0ead66064183e9f7e04e618ec0
2. Wstęp
W tym artykule opisano, w jaki sposób komputer może odtwarzać wideo klasyczna gra Tetris przez uzyskiwać informacje dotyczące zarządu, określające dobrego działania i skuteczności tych działań.
Ten artykuł zawiera oprogramowanie zdolne do gry Tetris w czasie rzeczywistym.
Program obejmuje najlepszych czasie rzeczywistym Tetris-algorytm gry w domenie publicznej.
Artykuł ten określa zasady "Standard Tetris," specyfikację w oparciu o oryginalne 1986 pre-komercyjna wersja Tetris na komputer osobisty (PC).
W 2003, oprogramowanie zawarte w tym artykule została użyta, aby włączyć komputer do gry Tetris działa na osobnym komputerze.
Zwykły USB kamery wideo został wykorzystany w celu umożliwienia komputera, aby "zobaczyć" ekran innego komputera.
A przekaźnik pokładzie było kontrolowane za pomocą interfejsu RS-232 aby umożliwić komputera "naciśnij klawisze" na klawiaturze z innego komputera.
Tak, pierwszy komputer ma stosunek do drugiego komputera, który jest podobny do typowego gracza stosunek człowieka do komputera podczas gry Tetris; gra państwa jest jedynym znanym patrząc na ekran, i odtwarzacz działań może być wszczęte jedynie za pośrednictwem klawiatury .
Konfiguracja w tej demonstracji ustalono, że komputer może grać lepiej niż Tetris człowieka, w ramach normalnego czasu rzeczywistego gry Tetris.
3. Historia Tetris
W 1985, Alexey Pajitnov i Dmitry Pavlovsky były na komputerze inżynierów Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre z Russian Academy of Sciences
Alexey i Dmitry były zainteresowane w tworzeniu i sprzedaży uzależniających gier komputerowych.
One testowane w różnych grach.
Alexey był inspirowany przez starożytnych Grecki układanka gra, Pentaminos, którego zorganizowanie kawałki układanki w pięciu kwadratów.
Alexey myśl idei organizowania Pentamino sztuk, jakie spadły na prostokątnym kielich, ale zdajesz sobie sprawę, że dwanaście różnych pięciu kwadratowe kształty były zbyt skomplikowane dla gier wideo.
Alexey włączony do korzystania "tetramino" siedem sztuk, z których każdy złożony z czterech kwadratów.
W 1985.6, Alexey Pajitnov zaprogramowane pierwsza wersja Tetris na Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov i Tetris.
W 1985-1986, Vadim Gerasimov, 16-letni wysokiej szkole komputer prodigy którzy pracowali w Akademii, realizowane Tetris na IBM PC uruchomiony MS-DOS system operacyjny.
(Vadim Gerasimov później zrobił badania na MIT Media Laboratory, od 1994 r. poprzez 2003, otrzymując tytuł doktora po wypełnieniu wiele ciekawych projektów:
http://vadim.www.media.mit.edu)
Wprowadzenie na ekranie 1987-1988 e-wydania Tetris na PC
Do gry na ekranie 1987-1988 pre-handlowych uwolnienia Tetris na PC
Po 1987, Tetris rozpowszechniania na całym świecie.
The Tetris Company, LLC, Tetris jest właścicielem znaku towarowego.
4. Projekty inspirowane Tetris
4.1 0-wymiarowych Tetris
Dotychczas nie opracowano.
4.2 1-wymiarowej Tetris
Ziga Hajdukovic opracowała 1-wymiarowej Tetris oprogramowania, które mogą być odtwarzane w przeglądarce internetowej.
Ziga Hajdukovic posiada również 1-wymiarowej Tetris oprogramowania dla telefonów komórkowych z wykorzystaniem platformy Java J2ME.
4.3 2-wymiarowy Tetris
Wszystkie warianty są Tetris konwencjonalnych w tej kategorii.
Ta sekcja zawiera interesujące warianty.
4.3.1 Największy tetris game ever: Delft University of Technology (1995)
Tetris zagrał w budynku; 2000 m^2 powierzchni; Delft University of Technology (1995)
Tetris zagrał w budynku; 2000 m^2 powierzchni; Delft University of Technology (1995)
4.3.2 Kolejna gra Tetris zagrał w budynku: Brown University (2000)
Tetris gry wyświetlane przy użyciu światła w oknach budynku na Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
"Myślę, że był po prostu najbardziej niesamowite jednego dnia mogę sobie wyobrazić rzeczą w moim życiu. Jak zawsze powiedział Steve Jobs, podróż jest nagroda."
"It made me think projektów zrobiliśmy z powrotem w kolegium. Rzeczy, które były niemal można cofnąć, że inne osoby nie myśleć robi."
Steve Wozniak (2000)
4.3.3 Internetowej grze z MIT "Zielona Budowanie" wizerunku
Vadim Gerisimov's internetowej Tetris
Ta przeglądarka internetowa Tetris wariant został utworzony przez Vadim Gerasimov.
Ta przeglądarka internetowa Tetris funkcje "Green" budynku na kampusie MIT.
Tetris Ten wariant ma tylko dziewięć kolumn zamiast standardowego dziesięć kolumn.
Ten wariant Tetris prezentuje nowe utwory z losowo kierunki.
Vadim Gerasimov jest osoba, którzy napisali do komputera kod do PC wersja Tetris w 1986.
Vadim Gerasimov zrobił dr badań na MIT Media Laboratory podczas 1994-2003, pracujących na wielu interesujących projektów.
4.3.4 PIC16F84 12 MHz mikrokontrolera opartego na NTSC / PAL wideo gry Tetris
PIC16F84 12 MHz mikrokontrolera opartego na NTSC / PAL wideo gry Tetris
Obrazek powyżej pokazuje NTSC / PAL wideo wyjście wyprodukowane przez PIC16F84 12 MHz mikrokontrolerem uruchomione oprogramowanie pisane przez Rickard Gunee w 1998.
Sygnału wideo jest generowane przez oprogramowanie do sterowania wyjściami cyfrowymi.
4.3.5 "Scopetris" Oscyloskop Tetris przez Lars Pontoppidan (2007.8)
"Scopetris" Oscyloskop Tetris przez Lars Pontoppidan (2007.8)
Lars Pontoppidan pisał kod dla mikrokontrolera AtMega32, proste i dodaje analogowe obwodów, aby stworzyć wersję Tetris, które mogą być odtwarzane na oscyloskop.
Niektóre z rejestrów kontroli AtMega32 mikrokontrolera 8-bitowego sygnału wyjściowego oraz, gdy przeszedł przez "R-2R" rezystora obwodu elektrycznego na cyfrowy-analogowy (D/A) konwersji, wynikające z sygnałów analogowych może kontrolować (x,y) współrzędne oscyloskopu wiązki (jeżeli jest oscyloskop ustawiony na "tryb X-Y)."
YouTube wideo:
FLV wideo:
4.3.6 Kod ukrywane Tetris: C / Unix
Następujące została wyróżniona "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 Tetris ukrywane kod: kod Perl
Poniżej Tetris na Perl tłumacza: Perltris (wersja 20050717) 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) jest standardem opisu obiektów przy użyciu graficznego XML.
Mozilla SVG Tetris: Tetris realizowane za pomocą Scalable Vector Graphics (SVG) opis
4.3.9 Google "widget" Tetris
Google, Yahoo! i Microsoft, i inne spółki, mają promować miniaturowych do Internetu oparty na oprogramowaniu o nazwie "widgets", które są zazwyczaj charakteryzuje się dynamicznym wykorzystania niektórych danych dostępnych w Internecie.
Jednym z takich widget dostępny jest za pośrednictwem Google gry Tetris.
W poniższym przykładzie jest cute, ale kształty obracać w irytujące sposoby:
Google "widget" Tetris
Inne Google widgets:
4.3.10 MIT badań papieru: "Tetris is Hard, Even to Approximate" (2002)
Następujące badania dokument zawiera dowód, że pewnego rodzaju Tetris "NP-wariant" jest "kompletny."
Erik D. Demaine, Susan Hohenberger i David Liben-Nowell, "Tetris is Hard, Even to Approximate", Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
"NP-kompletne" jest klasyfikacja kosztów w czasie i przestrzeni koszt algorytmu.
Inne klasyfikacje obejmują "P" i "NP".
Klasyfikacja "NP-kompletne" oznacza, że dla niektórych problemów większych niż niewielki rozmiar, algorytm jest mało prawdopodobne, aby znaleźć żądane rozwiązanie w praktyce czas i przestrzeń.
4.3.11 Badania dokumentu: "Applying reinforcement learning to Tetris"
Następujące papieru, opublikowany 2005.5.30, Donald Carr w Informatyka w departamencie Rhodes University, Południowa Afryka, przedstawia wniosek o "wzmocnienie uczenia" się Tetris.
4.3.12 Tetris Spódniczka (2007.11)
Tetris Spódniczka (2007.11)
Tetris w spódnicy została utworzona przez "Lucy" ("hissyfitoly" na etsy.com) przed 2007.11.
Od twórca opis w spódnicy (oferowanych do sprzedaży na etsy.com):
"Okay, so I was a secret, closet Tetris fanatic from about, oh, 1993 to 1996. It was a bitter-sweet obsession. My life wasn't so great, but I could control the stacking of a few measly blocks, [damn it]! Or could I? Video games have been coming back to haunt my dreams as of late, and I find myself stacking blocks, jumping away from a frighteningly-large Q*Bert, and slipping off of logs next to a pixellated frog. This skirt is the result of those nightmares."
Forum uwagi dotyczące tego spódnica:
"Mężczyzna, że w spódnicy sucks Tetris"
"Ahahahaha, myślałam to samo."
"Nie ma pełną linię w dół na dole ... zakończone linie znikają." "TO PONAD" "."
"Nie powinno być w miejscu, z przodu lub z tyłu, gdzie będzie długi kawałek idealnie pasuje ..."
"To naprawdę brzydki chociaż spódnica. Mój chłopak nie mógł kupić mi wystarczy czekolada i kwiaty, aby przekonać mnie do tego, co nosić."
4.3.13 Tetris etapie aktu (2007.4)
Tetris etapie aktu (2007.4)
"Od tych, którzy cię na Triforce w 2006 ... Comes następnej generacji obiektów przyrody nieożywionej skit ... Tetris."
Lokalnie buforowanych Flash wideo w formacie wideo (FLV) (wykorzystanie VLC do gry):
4.3.14 Hilarious Tetris Japoński różnice w telewizji pokazują
Japoński Tetris różnice w telewizji pokazują
Ten fragment filmu z telewizji pokazują Japoński obejmuje hilarious odmian Tetris, w tym:
sztuk, które zniknie po wyładunku, utwór, że wypełnia cały wiersz (wypełniając tym samym wierszu po wylądowaniu), kilka sztuk objętych jednocześnie, kawałków o nieregularnych kształtach, długi utwór, który jest nieco zbyt szeroki, by zmieścić się w lukę (zapobieganie 4-rzędowy zakończenie!), uderzanie Mario grzyb i stają się ogromne i umierania!, kawałek gruzu pozostałych po wiersze są zniszczone, co sztuk wzwyż ciężkości pływaka do góry, itp.
Lokalnie buforowanych Flash wideo w formacie wideo (FLV) (wykorzystanie VLC do gry):
4.3.15 "The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
"The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
Z opisu na YouTube:
"TETRIS odgrywaną przez rzeczywistych ludzi-istot posiedzenia w audytorium:"
TETRIS jest 4 wideo z GAME OVER Project, kierowane przez szwajcarskiego artysty Guillaume REYMOND (NOTsoNOISY kreatywnych agencji).
Ten stop-motion video was shot "LES URBAINES" i zagrali na festiwalu w
http://www.urbaines.ch Palais de Rumine (Lausanne, Szwajcaria) na November 24th 2007.
Lokalnie buforowanych Flash wideo w formacie wideo (FLV) (wykorzystanie VLC do gry):
4.3.16 2,5-wymiarowej Tetris
Termin "2,5-wymiarowej" jest używany tutaj oznacza nie ortogonalnych widok dwuwymiarowy wersja Tetris, z grubość w trzeci wymiar.
(Link "tetris3d" Znajdź w "F7: GAMES".)
4.4 3-wymiarowy Tetris
Linux / GTK wersji
Trójwymiarowy Tetris w formie z Java aplet do przeglądarki Internet:
Trójwymiarowy Tetris na Windows system operacyjny:
4.5 4-wymiarowej Tetris
Greg Kaiser's "HyperTetris" (1996): 4-wymiarowej Tetris
W [1996], [...], Greg Kaiser ułożyła czterech wariantów wymiarowych na klasyczne gry.
Korzystanie IrisGL (a.k.a. igl) on stworzył pracy, jeżeli trudno jest grać, gra przy użyciu czterech podprogramów ekrany do zobrazowania trójwymiarowego różnych aspektów całej przestrzeni gry.
[Z powodu], nie jest łatwo [zrozumiały] sposobem na rozwój czterech obiektów na ekranie D dwóch, czterech podprogramów poglądy są praktyczne metody do manipulacji i wizualizację rotacji i tłumaczenia części za pośrednictwem czterech wymiarach ( w grze o nazwie x,y,z,w).
Zamiast zakończenia linii bloków, jak w pierwotnym, w tym przypadku celem jest wypełnienie kompletne kostki w x,y,z subview (zazwyczaj 4 na 4 przez 4).
W innych subviews, które zawierają wymiar "w" są ułożone w domyślnej 4 o 4 przez 10 blokować porozumienie z "w" jest długi, "vertical" wymiar we wszystkich trzech przypadkach, z różnych podstaw (x,y), (x,z), (y,z).
Gravity działa w kierunku "-w", klocki spadają w "dół" trzy długie subviews, które zawierają "w", a nie przenosić, chyba że kontrola przez gracza w ciągu ostatnich (x,y,z) subview.
To trwa już od jakiegoś czasu, aby się do, co najmniej.
Jeśli jakimś cudem cierpliwości lub zmiany parametrów gry, jedna ma wypełnić kostka, znikną jak linie zakończone zrobić w oryginalnym Tetris, choć nie jest trzymany w gości HyperTetris.
Benjamin Bernard (2000)
4.6 N-wymiarowej Tetris
Polytope Tetris (2003): N-wymiarowej wariant gry Tetris
Polytope Tetris jest n-wymiarach Tetris.
Zainspirowany przez HyperTetris program, Polytope Tetris ton pozwala grać w każdym Tetris LICZBA wymiar.
Zagraj w Tetris 3D, 4D, 5D lub więcej.
HyperTetris jest znacznie catchier nazwę niż Polytope (def) Tetris, ale nie mogę ukraść nazwę.
5. "Standard Tetris" specyfikacji
5.1 Wstęp
Definicja "Standard Tetris" jest idealized model z najważniejszych cech i zachowań w pierwszym IBM-PC realizacji w gry Tetris (ok. 1986-1988).
W idealized model oparty jest na powodując widocznej intencji twórców pierwszego wykonania IBM-PC z gry Tetris.
Na przykład, wydaje się uzasadnione, by wywnioskować, że deweloperzy z pierwszych IBM-PC wykonania przeznaczone do gry Tetris, aby wybrać kształt każdego nowego kawałka objętych "losowo," i że korzystanie z Borland C wprowadzenia w życie rand() funkcja była jedynie praktyczne zbliżenia zamiar.
Definicja "Standard Tetris," że kształt każdego nowego kawałka objętych ma być wybrane "losowo."
To idealne zachowanie nie może być osiągnięty poprzez realizację wszelkich, ale implementacje mogą zbliżenie idealne zachowanie.
Chociaż nie można w pełni realizować wdrożenie definicji "Standard Tetris," ideałów "Standard Tetris" obejmować obiektywne cechy i implementacje mogą być porównywane zgodnie z ich względną bliskość do ideałów "Standard Tetris."
Ta sekcja opisuje szereg elementów, zachowań i zasad, które wspólnie definiują "Standard Tetris."
5.2 Standard Tetris pokładzie
Na pokładzie jest siatki komórek, posiadający 10 kolumn i 20 wierszy, dla całkowitej liczby komórek 10 * 20 = 200.
Standard Tetris pokładzie (10 kolumn, 20 wierszy)
Każda komórka może być pustostanów (pusta) lub zajmowane (pełna).
5.3 Standard Tetris sztuk
Istnieje siedem standardowych (7) Tetris sztuk, z następującą literę nazwiska:
{ O, I, S, Z, L, J, T }
W piśmie z nazwy są inspirowane przez kształtów części.
Siedem Standard Tetris sztuk i ich "kierunki"
Kropki na pokładzie (0,0) zbiega się z pozycji (6,20) kiedy pojawi się pierwszy utwór.
Pierwsza kolumna pokazuje wstępnej "orientacji."
W następnym, słowo "orientacja" jest używany do opisania każdego państwa na sztukę, w zestawie dozwolone stwierdza, że mogą wynikać z zegara przypadku rotacji.
Zmiana "orientacji" z określonej "orientacji" z "I, S" lub "Z" sztukę, wymaga połączenie rotacji i tłumaczenia.
W związku z tym słowo "orientacja" jest używany tutaj oznacza coś więcej niż sama rotacji.
Jednakże, "orientację" można zmienić tylko w odpowiedzi na zdarzenie zegara rotacji i cyklu odrębne "wytyczne" dla każdego utworu zbliżona, lub mecze z cyklu wynikające z czystej rotacji.
Specjalne użycia słowa "orientację" w tym kontekście jest niemal równoważne w rozumieniu tego słowa "rotacji" lub "kąt," ale słowo "orientacja" jest używany zamiast "rotacji" próby dostosowania uwagę na fakt, że niektóre fragmenty wymagają więcej niż rotacja do produkcji zestaw dozwolonych Członkowskich wynikające z "rotacji" zegara wydarzeń.
Kawałki można tylko przełączać kierunki (lub poddane szczególnej poziomej lub pionowej tłumaczenia), jeśli wynikające z tego stanu w kawałku nie ma żadnego okupowanych (pełne) komórek poza obszar rady nadzorczej i nie miałby żadnych zajmowanych komórek, które pokrywają wszystkie aktualnie zajmowanych komórek rady nadzorczej.
(W tej reguły, zajmowane (pełne) komórek kawałku nie są uważane za część "obecnie zajmowanych komórek na pokładzie"
W poniższych uwag, wszelkie odniesienia do związku z zegara przypadku rotacji jest z założenia, że taka rotacja może być rzeczywiście wykonywane, ze względu na istniejące warunki kawałku i zarządu.
W "O" (ramka) kawałek tylko jednym kierunku, i nie zmienia lokalizacje wszystkich swoich okupowanych (pełne) komórek w odpowiedzi na wszelkie zegara przypadku rotacji.
W "I" (linia) kawałek ma dwa możliwe kierunki, znajdujących się początkowo w orientacji poziomej.
W "I" kawałek zastępców między dwoma kierunkami w odpowiedzi na kolejne imprezy zegara rotacji.
W "S" i "Z" sztuk każdy ma dwa możliwe kierunki.
Te sztuk każdego zastępcy między dwoma kierunkami w odpowiedzi na kolejne imprezy zegara rotacji.
W "L", "J" i "T" sztuk każdego cztery możliwe kierunki, i te kierunki są wyniki prostych obr. o punkty w centrum kształty.
Kiedy pierwszy utwór pojawi się na pokładzie, utwór ma swoją "głównych osi" w orientacji poziomej, a kawałek jest na górze planszy.
Dlatego początkowo nie są zdolne sztuk o ich zmianie orientacji. Utwór musi descend przez jeden wiersz, aby mieć możliwość posiadania zmienił kierunek.
Po kawałku spadła o jeden wiersz na pokładzie, wszystkie kierunki sztuki można osiągnąć (przy założeniu, że utwór nie jest zbyt blisko ścian bocznych lub do bieżącego stosu sztuk).
5.4 Standard Tetris diagram
Poniższy diagram jest orientacyjna dla standardowego Tetris gry.
Szacunkowe diagram dla standardowego Tetris gry
Szacunkowe diagram dla standardowego Tetris gry
5.5 Standard Tetris sztukę tworzenia
Poniższy wykres pokazuje (4 * 2 komórki komórki) na pokładzie regionie, gdzie wszystkie elementy pojawiają się, gdy utworzony.
Region, w którym pojawiają się fragmenty, gdy utworzono w Tetris Standard
Kiedy po raz pierwszy pojawia się nowy kawałek na pokładzie, jego pochodzenie zbiega się z kropką na ten schemat, a utwór będzie zawierał całkowicie zasłonięte przez ten obszar na wykresie.
Gdy gra zostanie uruchomiona nowa, w pełni wolnego spadek opóźnienia upływa, a na pierwszym wolnym spadek iteracja utwór zrodził się na górze planszy.
Podczas normalnej gry, gdy szczególne wolnego spadek iteracja "ląduje" kawałek, pełnego wolnego spadek opóźnień i upływa w dniu następnym wolnym spadek iteracja utwór zrodził się na górze planszy.
Gdy utwór jest piedestał, rodzaj sztuki jest zaznaczona przy użyciu następującego algorytmu:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Ponieważ istnieje stały p (= 1/7) szansę wybrania konkretnego rodzaju sztukę, a wszystkie elementy tego samego typu są indistinguishable, prawdopodobieństwo posiadania dokładnie k sztuk danego typu po n prób następstwem Rozkład dwumianowy:
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 )
Kiedy wybierać spośród 7 (siedem) sztuk losowe, prawdopodobieństwo uzyskania konkretnego utworu jest p=(1/7).
Jeśli chcemy to zrobić n=70 razy, na przykład, prawdopodobieństwo uzyskania dokładnie k sztuk (z k w zakresie 0 do n) jest podany przez dwumianowy dystrybucji, jak pokazano na poniższym obrazie.
Rozkład dwumianowy dla n=70, p=(1/7)
Tak, można przewidzieć, średnia całkowita sztuk jednego typu biorąc pod uwagę całkowitą liczbę losową sztuk, można również obliczyć oczekiwane wariancji i odchylenie standardowe (pierwiastek kwadratowy z wariancji):
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
Kiedy przekonwertować wartość losową utwór do indeksu, interpretować je w następujący sposób:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[Pre-handlowych MS-DOS wersji Tetris użyto losowo numer funkcji oferowanych przez Borland Pascal kompilatora.
Ta funkcja używane 32-bitowej zmiennej stanu.
W związku z tym, sekwencji liczb losowych został ograniczony do 2^32 odrębne wartości.
Dlatego, w zasadzie, gracz może odkryć, po upuszczeniu może 10 sztuk, dokładne miejsce w zestawie 2^32 numery odpowiadające na aktualny stan gry.
Jeśli Tetris symulacje są wykonane ze stałych sekwencji 2^32 sztuk, a następnie podejmowania optymalnych decyzji można znaleźć w każdym miejscu w sekwencji.
(Nie wydaje się wystarczające możliwości, aby będąc na pokładzie statku stanie całkowicie pusty, co pozwoliło nam uzyskać zsynchronizowane z precomputed optymalne rozwiązanie ścieżkę).
Ryzyko przy użyciu prostych generator liczb losowych w symulacji przeznaczone do znalezienia optymalnego rozwiązania problemu jest to, że optymalnym rozwiązaniem będzie tylko dla danej drogi problem przestrzeń wybranych przez prosty generator liczb losowych. ]
5.6 Standard Tetris kontroli
Podczas gry, dostępne są następujące komponenty:
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
Wszystkich wejść w życie na krawędzi-rosnące pozytywny wkład (naciśnij przycisk, w przeciwieństwie do przycisku prasowa).
Gdy występuje naciśnij przycisk ten liczy się jako jeden wniosek.
Holding przycisku w dół po pewnym czasie może doprowadzić do "automatycznego powtarzania" funkcji z klawiatury, generowanie nowych naciska przycisk - ale ta funkcja jest zewnętrzną w stosunku do silnika gry.
Wejścia określone powyżej są zgodne z pierwotnym gry Tetris.
Obróć wnioski mogą być wykonywane, jeżeli nie istnieje podobieństwo między pożądany kierunek i ustaw komórek na pokładzie bieżącego (z wyłączeniem objętych sztukę), a jeśli nie ma pożądanej orientacji zestaw komórek poza planszy.
Przetłumacz wnioski mogą być wykonywane, jeżeli nie istnieje podobieństwo między pożądanego przetłumaczone i ustawić konfigurację komórek na pokładzie bieżącego (z wyłączeniem objętych sztukę) i, jeśli pożądane przetłumaczone konfiguracji ma ustawione komórek poza planszy.
Wejście wnioski są przetwarzane z tego opóźnienia zależy od klatek w grze (np.: 75 Hz), a wnioski w życie (jeśli ważnych) natychmiast.
A kawałek może zostać pominięte bez linii występujących objętych kroki.
A kawałek można przetłumaczyć kilka razy w lewo lub w prawo, a następnie spadł, doświadcza wszystkich bez oficjalnej linii objętych kroku.
Ponieważ nowo zrodził utwór nie może być obracany (bo tkwi w stosunku do górnej krawędzi tablicy), gracz musi zaakceptować co najmniej jeden utwór objętych krok, jeżeli obroty są pożądane lub konieczne.
Wpływ na wynik jest znikomy.
5.7 Standard Tetris kawałek "wyładunku"
Jeśli kawałek jest po prostu spadają, wchodzi ona w jednym rzędzie podczas każdego kawałka objętych iteracja.
Nie będzie iteracja, że przenosi go z miejsca bez kontaktu z poziomej powierzchni na miejscu, że ma kontakt z poziomych powierzchniach. Gdy występuje powtórzeń, kawałki są w spoczynku kontakt.
Jeśli iteracja rozpoczyna się kawałek odpoczynku w kontakcie z poziomej powierzchni, sztukę "ziemie," i staje się częścią statycznego stosu.
5.8 Standard Tetris "linie zakończone"
A wiersz jest wypełniony wiersz stos, w którym wszystkie komórki są zajmowane. Gdy zakończona zostanie wyeliminowana z rzędu stos, i wiersze powyżej rzędzie są przesunięte wyeliminowane przez jeden wiersz, aby wyeliminować luki, ten liczy się jako wypełniony "wiersz."
Gdy ląduje kawałek staje się częścią stos.
Natychmiast po kawałku ziem, stos jest sprawdzana za zakończone wiersze, wypełnione wszystkie wiersze są eliminowane.
Do czterech wierszy może być zakończone jednocześnie.
Poniższa tabela przedstawia górną granicę na linii zakończone jednocześnie przez jeden utwór:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Standardowe "poziomy" Tetris
Standard Tetris ma 10 poziomów trudności, ponumerowane 1 (jeden) poprzez 10 (dziesięć), z poziomu 1 jest "co najmniej trudne."
Poziom wskaźnika jest maksymalnie dwóch wartości:
actualLevel = max( initialLevel, earnedLevel );
W initialLevel wartość to poziom, że gracz wybiera przy uruchamianiu nowej gry.
W strukturze poziomu jako funkcja zakończone linii jest łatwo zaobserwować w pre-handlowych MS-DOS wersja 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
Tak, earnedLevel wartość jest obliczana według następującego algorytmu:
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 objętych iteracja opóźnienia
Standard Tetris jest w czasie rzeczywistym opóźnienie między kolejnymi wiersza wolnego spadek powtórzeń, że jest funkcją bieżącego poziomu trudności.
W poniższej relacji między poziomem indeksu i objętych iteracja opóźnienia jest oparty na powtarzające się stoper pomiarów na wszystkich poziomach sprzed handlowych MS-DOS wersję 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
Dlatego ustalenie następującego wzoru dla iteracji wartości opóźnienia w zależności od rzeczywistego poziomu wskaźnika:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Jeżeli na pokładzie jest pusty, nie ma użytkownika, piedestał sztuki na rzeczywisty poziom 1 ląduje w przybliżeniu 10 sekund, a na piedestał sztuki rzeczywisty poziom 10 ląduje w 1 około sekundy.
5.11 Standard Tetris "gości"
Standard Tetris tylko nagrody za punkty aktu wyładunku utwór.
Nie ma punktów za akt ukończenia jednej linii, lub wypełniając dwóch, trzech lub czterech linii jednocześnie.
[Uwaga: Niektóre warianty Tetris przyznawania punktów do akt zakończenia linii, z wykładniczo rosnącej premii dla coraz większej liczby linii jednocześnie zakończone.
Tak, strategii dla maksymalizacji gości w takich wariantów Tetris obejmuje tworzenie możliwości "uzyskania Tetris," Dziękujemy za korzystanie z "I" kształt, aby uzyskać cztery linie i jednoczesnego pobierania wielu punktów. ]
Jeśli masz pusty pokładzie, i niech was nie "I" zrobić kawałek wolnego spadku i ziemi, ani razu nie spadnie "I" kawałek, można ustalić w następujący punkt wykresu za pomocą e-MS-DOS wersja 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, nie "I" sztuk spadek łącznie 18 wierszy.
Z tego punktu różnicy między wolnym i natychmiastowy spadek-spadek przypadków.
Do eksperymentowania z pośrednich przypadkach jest łatwo wyprowadzić następujący punkt wzoru:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Należy pamiętać, że ta formuła nie ma nic wspólnego z odległości utwór spada!
Jest to ściśle funkcja rzeczywistego poziomu, a kary za liczbę powtórzeń utwór jest dopuszczone do swobodnego upadku.
Ten użytkownik karze dla wymagających czasu do myślenia.
Również pamiętać, że utwór nie może być obracany początkowo, gdy po raz pierwszy spawns, gracz jest karane przez co najmniej jednego wolnego spadek iteracji, jeżeli obroty są zobowiązane do umieszczenia utworu w stos.
To prawdopodobnie nie wpływa na ludzkie graczy, chyba że w jakiś sposób: rozpoznać utwór, naciśnij klawisze tłumaczenia "(w lewo" lub w "prawo)," naciśnij "obracać" klucz jednego lub więcej razy, a następnie naciśnij "spadku" klucz, wszystkie w terminie krótszym niż sekunda 0.5 na poziomie 1, lub mniej niż 0.05 sekund na poziomie 10.
6. Standard Tetris strategii
6.1 Wstęp
Strategia gry gry zależy od reguł gry.
Strategia zależy od parametru, który ma zostać zoptymalizowana.
Tetris w normie, jeden przetrwa, wypełniając rubryki, dostaje punkty do wyładunku części, oraz ocenę w większości punktów możliwych do wykonania przez każdego kawałka spadku przed jednym lub więcej wolnego widoczny spadek powtórzeń.
W A.I. można zoptymalizować punktów za każdy kawałek po prostu podejmowanie decyzji w sprawie szybkiego i "naciskając klawisze" do wykonania ruchu.
Więcej ważne do A.I. jest przetrwanie, ponieważ przetrwanie nieokreślony oznacza arbitralnie wysokich gości mogą zostać osiągnięte. Ponieważ Tetris klocki spadają na konkretne stawki, A.I. musi podejmować decyzje co najmniej taki szybki - i A.I. musi zakończyć wierszy, które przenosi się na poziomie średnich co najmniej 1 wiersz na 2,5 sztuk. (Każdy utwór ma 4 komórki, a każdy wiersz posiada 10 komórek).
Oczywiście można odroczyć wypełnienie wierszy przez nagromadzone sztuk i budowanie dużych stosie, lecz istnieją tylko 200 komórek na całym pokładzie, które w zasadzie można tylko 50 sztuk, więc wszelkie gracza (takich jak A.I.) muszą mieć zakończenia linii, podstawowym priorytetem.
Tetris w normie, gra zawiera stanu obecnego zarządu i obecnych zawodu spadającym klockiem (rodzaj, miejsce, i orientację). Gra państwa może zawierać "Dalej Piece".
6.2 An zmienny sekwencji "S" i "Z" sztuk
Heidi Burgiel, Ph.D., z Department of Mathematics, Statistics and Computer Science na University of Illinois at Chicago, okazało się, że zmianę kolejności "S" i "Z" kawałki będą obowiązywać norma (kolumna 10, wiersz 20) Tetris gry do końca w sposób przewidywalny numer z ruchów.
Cytat z artykułu: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Uczestniczący wydrukowany artykuł: Mathematical Gazette, lipiec 1997, "How to Lose at Tetris"
Heidi Burgiel oferuje Java applet, że działa w przeglądarce internetowej, że funkcje zmienionej Tetris klon że spawns zmianę "S" i "Z" sztuk.
[ "Standard Tetris" oprogramowania związanego z dokumentem jest czytanie posiada również tryb które spawns zmianę "S" i "Z" sztuk. ]
Heidi Burgiel twierdził, że gra z udziałem zmianę "S" i "Z" sztuk (o standardowej Tetris pokładzie 10 kolumn i 20 wierszy) musi się zakończyć przed mniej niż 70000 sztuk spadły.
Standard Tetris oprogramowanie dołączone do tego dokumentu pozwala osoby do zabawy ze zmiennym "S" i "Z" kawałki, a także zmieniać szerokość pokładzie.
Łatwo zobaczyć, że są tablice, których szerokość całkowita wielokrotność czterech kolumnach (przykłady: 4 kolumny, 8 kolumn, 12 kolumn, itp.) mogą być odtwarzane na zawsze, gdy sztuk zastępców między "S" i "Z", z rosnącego stosu nie wyższa niż 4 wiersze. Wspominam o tym jasno, że ograniczoną przeżywalność badania opisane w dokumencie wspomniano powyżej jest specjalnie dla przypadku standardowego Tetris zarządu (z 10 kolumn i 20 wierszy).
6.3 Unsolvable kawałek sekwencji w ogóle
Istnieje cały kategorii patologicznych sekwencji, które nie mogą być przetrwał.
Byłoby interesujące obliczyć całkowite prawdopodobieństwo spotkania gra-kończące kolejności, ponieważ to mogłoby górny w wykonywaniu wszelkich strategii, nawet z pełną wiedzą o wszystkich przyszłych sztuk w danym punkcie w grze.
6.4 Razem pokładzie możliwe konfiguracje
Biorąc pod uwagę, że na pokładzie ma 10 * 20 = 200 komórek, a biorąc pod uwagę, że każda komórka może być tylko w jednym z dwóch stanów (pusta lub zajmowane), całkowita liczba pokładzie konfiguracji musi być mniejsza lub równa: (2 ^ 200).
Biorąc pod uwagę, że każdy kawałek dodaje 4 komórek na pokładzie, a każdy wiersz zakończenie eliminuje z 10 komórek zarządu, liczbę komórek zajętych na pokładzie będzie zawsze nawet. Na przykład, (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, itp. Dlatego też, jedynie połowa z (2 ^ 200) pokładzie konfiguracje mogą zostać osiągnięte przez gry.
W związku z tym łączna liczba wynosi około pokładzie konfiguracjach: (2 ^ 199) = 8.03469... * 10^59.
Jednakże, należy wykluczyć z naszej całkowitej dowolnej konfiguracji, która zawiera wiersze wypełnione, bo wypełnione wiersze są wyeliminowane przed końcem każdego ukończone przenieść. Wszelkie konfiguracji z jednym lub więcej wierszy będzie wypełniona do upadku innego konfiguracji, która nie zawiera żadnych wypełnionych wierszy.
Ponadto, należy wykluczyć wszelkie konfiguracji, która zawiera nie pusty wiersz powyżej jednego lub więcej pustych wierszy, gdyż nie pusty wiersz powyżej pusty wiersz będzie zawsze spadek, a wszystkie objęte przystanki przed końcem każdego przenieść.
Każdy wiersz może być w 2^10 = 1024 państw, z których jeden to "pusty", z których jeden jest "pełna", a (1024 - 2) = 1022, które są częściowo zajmowane. My wykluczyć "pełne" od przypadku.
Jeśli dołu wiersz jest pusty, a następnie wszystkie wiersze powyżej dolnego wiersza musi być pusty.
W dolnym wierszu jest częściowo zajmowanych, a następnie w drugim rzędzie może być pusta lub częściowo zajmowane.
Kontynuując tę analizę, możemy obliczyć liczbę pokładzie konfiguracjach, że bierze w celu uwzględnienia wyłączenia pełnego wierszy i ograniczeń w pustych wierszy: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), która wynosi około ((1022 ^ 19) * (1023)).
Tak więc, znajdujemy bardziej dokładne oszacowanie całkowitej liczby pokładzie stabilne konfiguracje: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199), tj. około 3,74% mniej niż (2 ^ 199) szacunek.
Jednakże rzeczywista liczba stabilny, dostępny jest członkiem zarządu może być niższa zwłaszcza ze względu na fakt, że większość wierszy górę-mogą być wypełnione na kilka sposobów. W prawym górnym najbardziej wypełnić rubryki, nowo generowane utwór nie może być przeniesiona lub obrócić bardzo dużo. To ogranicza liczbę sposobów na górę najbardziej wierszy może być wypełnione.
6.5 W zasadzie, najlepiej przenieść można znaleźć na pokładzie jakiegokolwiek kawałka i konfiguracja
Ponieważ możemy uzyskać wszelkie możliwe siedmiu sztuk na pokładzie danego państwa, całkowita liczba jest gra stanowi około 7 * (2 ^ 199) = 5.624... * 10^60.
Ponieważ możemy w zasadzie zrobić głęboki wyszukiwania wszystkich możliwych futures na wszystkie możliwe posunięcia dla danego stanu gry, możemy mieć jeden "najlepszy" przenieść związane z każdej gry.
Zakładamy, że nie mamy dostępu do wszelkich informacji innych niż obecne obecnego zarządu i sztuki, tak "najlepsze" oznacza, że przejście oferuje największą szansę spełnienia naszych długoterminowego celu, jakim jest przetrwanie ".
Przejście jest tylko tłumaczeniem (do 10 opcji) i rotacji (do 4 opcji), możemy łatwo kodować najlepiej poruszać się w jeden bajt.
Więc w zasadzie moglibyśmy formie tabeli z 10^61 wpisy (bajtów) powiedział nam, że najlepiej przenieść danym pokładzie jakiegokolwiek stanu obecnego i sztukę.
Oczywiście jest to niewykonalne, podobnie jak wyliczanie wszystkich "Go" desek lub "Chess" desek jest niepraktyczne. Ale jest to, że istnieje tylko jedna prawda rozwiązanie, i tam jest najlepiej przejść do danej konfiguracji. Nie może być równie dobre posunięcia dla danej konfiguracji, ale możemy dowolnie wybrać jedno przejście w tym przypadku.
Wiele gier, gry algorytmy tabel, które mają enumeratywnie wyliczyć wszystkich gier w ramach ograniczonych możliwości państwa kontekstach, takich jak "otwarcie (początkowy) przenosi" lub "koniec gry (końcowy) porusza się" w szachach. Składnia wyczerpujące wyliczenie Tetris stos powierzchni (około (20 ^ 10) członkowskich) jest wykonalne. To ciekawy pomysł.
Wyczerpujące wyliczenie wszystkich państw dole dwa rzędy, pomnożona przez siedem sztuk to możliwe, przechowywania i najlepiej poruszać się w jeden bajt, byłoby dość łatwe; wymagające jedynie 7 MB pamięci. Składnia optymalizacji wydajności dla tych siedem milionów przypadków będzie dostarczać surowiec dla analizy danych i rozwój prostych modeli danych, takich modeli może być traktowana jako część ogólnego idealne Tetris-strategia gry.
Należy pamiętać, że najlepiej wykonującego porusza wciąż nie chroni nas przed ewentualnym patologicznych gry kończąca utwór sekwencji. It's just, że zawsze będziemy wykonywać ruchów, które oferuje nam maksymalne możliwości przetrwania w przyszłości biorąc pod uwagę, że w przyszłości wszystkie kawałki są całkowicie losowo (i nieznane w chwili jesteśmy do decydowania, w jaki sposób przenieść do jednego obecnego znany kawałek).
6.6 Real-time performance
Jeden stoi ograniczenie niektórych algorytmów strategii jest konieczność wykonywania w czasie rzeczywistym - co oznacza, że algorytm musi podjąć decyzję w określonym czasie.
Kiedy ludzi gra Tetris, sztuk objętych przystanku nie dać szansę gracza do myślenia. To część wyzwanie Tetris. Tak, A.I., że system ma za zadanie symulować roli człowieka Gracz musi również podejmować decyzje na poziomie podyktowane przez gry Tetris.
6.7 Wiersz i kawałek sumy
Zauważ, że w perspektywie długoterminowej, spadła liczba sztuk jest bardzo zbliżony do 2.5 razy liczba zakończonych wiersze - ponieważ każdy wiersz posiada 10 komórek, a każdy kawałek jest 4 komórki, i musimy wypełnić wiersz, średnio raz (10/4) = 2.5 sztuk spadła.
Tak więc możemy użyć "zakończona wierszy" i "spadła sztuk" prawie zamiennie z odpowiednią stałą proporcjonalności. Największym błędem jest, gdy zarząd jest całkowicie wypełniona z wyjątkiem jednego luki w każdym wierszu (((10*20)-20)/4) = 45 sztuk spadła, ale niedobór przewidywane (45/2.5) = 18 zakończone wierszy.
6.8 Aktualna-kawałek (i wyżywienie) strategii
Jeśli tylko pozwalają na A.I. mieć wiedzę na temat obecnego zarządu i obecnych kawałek, a my tylko rozważyć wyniku ruchu bieżącego utworu, w szczególności drogi, a następnie może być nazwany "jednym kawałku" analizy.
Tutaj jest szorstka szkic, jak jeden kawałek analiza może zdecydować się na przejście w Tetris:
Aktualna-kawałek z analizy stanu gry Tetris
Zasadniczo staramy wszystkich możliwych kroków i wybrać, aby przenieść daje najlepsze wyniki.
W części trudno jest ocena każdego wyniku.
Musimy ocenić stan hipotetyczny zgodnie z gry, jak również taki stan popiera nasze krótkoterminowe i długoterminowe cele.
Naszym długoterminowym celem jest przetrwanie. Przetrwanie zależy na zapobieganiu stos program z zarządu. Możemy zmniejszyć wysokość stosu przez tworzące kompletny wierszy, które następnie są eliminowane z pile.
Aby utworzyć pełny wiersz, musi mieścić się w części sztuk do każdej kolumnie tego wiersza. Tak więc, potrzebujemy wszystkich części wiersza, które mają być narażeni na spadające kawałki, jeśli mamy ostatecznie wypełnić cały wiersz.
Jeśli z jakiegoś powodu nam na pokrycie części pustego wiersza przez sztuk na wszelkie wyższe wiersz, a następnie jesteśmy obecnie w stanie wypełnić te części pusty wiersz. Jedynym sposobem (przy założeniu, że nie przesuwanymi) w celu uzyskania dostępu do tych "dziur pochowane" w celu wyeliminowania powyższych wierszy, które działając jako części przeszkody.
Następujące czynniki są wśród tych możemy użyć, aby ocenić stan danej rady:
Overall pile height
Im wyższy stos, sytuacja wydaje się gorsza nasze by być, bo jesteśmy bliżej program na pokładzie.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
W chropowatych stos, tym bardziej prawdopodobne jest to, że trudno będzie wypełnić wszystkie osadzone w skomplikowanych konturów, jak stają się one narażone na powierzchni.
Number of buried empty cells
Im więcej dziur mamy pochowany, w naszej sytuacji jest gorsze, ponieważ musimy odsłonić otwory pochowany zanim będziemy mogli ukończyć odpowiednie rubryki.
Można sobie wyobrazić inne czynniki, które zazwyczaj stawka hipotetycznej na pokładzie, jak również jej stos może pomieścić wszystkich możliwych przyszłych kawałków, jak i dobra sytuacja wygląda w przypadku wszystkich tych kawałków to możliwe.
Kolejnym zagadnieniem jest sposób, aby ustalić względną wagę tych czynników.
Jeden ogólne podejście jest następujące. Przypisywanie zestawu "wagi" (względne znaczenie) do tych czynników, a następnie symulować wiele gier i zapis wyników tych gier (końcowy gości, itp). Następnie przypisać nowy zestaw wag i symulacji nowy zestaw gier. Na podstawie tego, czy nowy zestaw gier miała lepsze wyniki niż w poprzednich zestaw gier wiemy, czy nowy zestaw wag był lepszy niż poprzedni zestaw wag.
W moich własnych doświadczeń Ja postarałem systematyczne poszukiwania i losowych w poszukiwaniu dobrych połączeń masy, ale nie zauważą żadnej dużą skalę tendencji, które mogłyby prowadzić. Jednakże, widziałem wiele zaskakująco gładka bumps. I thought it was interesujące, że średnia wydajność mogłyby stanowić sprawne krzywej, gdy parametr był zróżnicowany powoli z innymi parametrami, które odbyły się w pewnych kombinacji wartości.
Najlepiej w czasie rzeczywistym, jedną sztukę Tetris algorytm w świat, stworzony przez Pierre Dellacherie (Francja) w 2003, wiele zawdzięcza swój sukces swojego zestawu pomiarów (lub metryka). Znalezienie wagi jest niezbędne podczas optymalizacji strategii, ale także krytycznej, aby rozpocząć z rodzaju pomiary wykazują, że istotne cechy państwa.
Pierre Dellacherie's wynalazek nowych sposobów na pokładzie sprawia, że każdy charakteryzuje jego algorytm naprawdę wspaniałe; zarządu characterizations uchwycić istotne wymiary strategicznego zarządu.
Można opracować zestaw bardzo różnych wymiarach, że charakterystyka pracował równie dobrze, ja jestem przekonana, że możliwe jest odpowiednie wyżywienie span stan przestrzeń na wiele różnych sposobów, które mogą być wykorzystane do określenia strategii funkcji. Kluczem jest znalezienie cech, że projekt stanie przestrzeń do niewielkiej liczby wymiarów, które mogą być wykorzystane do opracowania prostych ocena funkcji (np.: liniowy ważonej kombinacji cech Pierre's wykorzystywane przez algorytm).
Jednoczęściowe algorytm używany przez "bot" w "xtris" oprogramowanie (1996) napisany przez Roger Espel Llima zastosowań wagi ustalane przez zakrojone na szeroką skalę poszukiwania możliwych kombinacji wagi "algorytmy genetyczne". Symulowane wyżarzanie jest możliwe inne metody poszukiwania w wielowymiarowej przestrzeni masa kombinacji.
Wydaje się, że oparte na różnych uwag, wielowymiarowych funkcji Tetris średniej wydajności w zależności od wagi, np.: F(w1,w2,w3,...), jest "surowe" (partie lokalne minima i maksima), co oznacza, że proste wielowymiarowy "hill climbing" może nie działać.
6.9 Strategia gdy bieżący utwór, następny utwór, i wyżywienie są znane
Jeżeli strategia jest algorytm biorąc pod uwagę obecny kawałek, następny utwór, i rady, to może podejmować decyzje, aby skorzystać z kombinacji sztuk.
Wiedza na temat następnego utworu można poprawić na sukces gry Tetris algorytm o kilka rzędów wielkości. Łatwo zrozumieć, jak znając następnego utworu sprawia, że duże różnice w strategii.
Można robić "crazy" ruchów, takich jak obejmującej ogromne dziury, itp, bo już wiedzą, że następnego utworu mogą być wykorzystywane do "naprawić" sytuację. Jeśli nie masz wiedzy na temat następnego utworu, jest nieustannie próbuje odtworzyć kursy, starając się zachować swoje możliwości w przypadku następnego utworu nie jest idealny.
Poniższy schemat pokazuje w jaki sposób wszystkich możliwych ruchów w bieżącym są uważane za sztukę i dla każdego z takich przejść uważamy wszystkich możliwych ruchów z udziałem w kolejnym kawałku.
Strategia udziałem obecnych i kawałek następnego utworu
Standard Tetris oprogramowania korzysta z tej strategii, gdy "Dalej Piece" jest włączony przez użytkownika i jest widoczny na ekranie, a gdy dwie sztuki A.I. jest włączona (takich jak z jednej napisane przeze mnie, Colin Fahey). Jeśli przycisk "Dalej Piece" nie jest widoczna na ekranie, moje dwie sztuki wchodzi z powrotem do jednego kawałka A.I..
Moje jednoczęściowe A.I. jest straszna w porównaniu do innych AIs w Standard Tetris oprogramowania, więc tym bardziej korzystne pokazuje informacje (np.: następny fragment) może być do A.I. systemu, jest wystarczający do poprawy skuteczności własnej mediocre Dwuczęściowy A.I. o kilka rzędów wielkości - łatwo wyższe niż wydajność z jednego kawałka najlepszej A.I. w świat.
(Jednak, przebudowę najlepszych jedną sztukę A.I. w świat, aby rozważyć dwa kawałki byłoby łatwo go poprawić o kilka rzędów wielkości, too! Wiedząc następny utwór jest ogromne!)
Mój pierwszy test mecz z mojej Dwuczęściowy A.I. trwało około 182 godzin (7,6 dni) na 800 MHz PC, wypełniając 7216290 wierszy. Ja nie testowałem algorytm na szybszy komputer.
Podczas zapisywania stanu z gry Tetris (Shift-W) do pliku tekstowego, można następnie skopiować i wkleić listę numerów, z sekcji "heightHistogram", do arkusza kalkulacyjnego Excel.
Każdy bin w histogramie wskazuje liczbę zakończonych ruchów, które się zakończyły w szczególności wysokość stosu (po zakończeniu wiersze są eliminowane). Jak można sobie wyobrazić, co czyni ruch, że całkowicie eliminuje stos jest rzadko, więc łączna liczba ruchów, które kończy się stos wysokości zero jest stosunkowo niska.
Tymczasem można oczekiwać, że wysokość stosu na ogół oscyluje wokół kilka średniej, tak pojemnikach odpowiadających na te wiersze będą dominować histogramu. Wreszcie, pojemnikach na górę najbardziej wierszy (gdzie jesteśmy w niebezpieczeństwie program na pokładzie) mają bardzo niskie sumy.
W ciągu wielu godzin, z A.I. gry pojedynczej gry z wykorzystaniem strategii obejmującej wiedzę na temat "Dalej Piece", wziął próbki do gry państwa, kopiowanie stos wysokość histogramy do arkusza kalkulacyjnego, jak pokazano poniżej:
Pile wysokość histogramy zapisane w różnych punktach w typowej gry (z obecnych i nowej strategii utwór)
Możesz skali każdego histogramu przez łączną liczbę sztuk (całkowita liczba zakończonych przenosi), aby uzyskać następujące dane:
Scaled histogramy, a teoria
W zadziwiające jest to, że te skalowane histogramy wygląd identyczny pomimo różnych rzędów wielkości od liczby sztuk (zakończone przenosi).
Po prostu patrząc na numery zrobiłem hipotezę, że ogon z krzywą rozkładu jest gwałtowny. Do prób i błędów I wyruszyli z nieobrobionego teorii, że ogon został opisany przez:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Poniższy wykres pokazuje pomniejszone histogramu w ciągu całego zakresu wierszy.
Wykres pomniejszone o histogramy
Zauważ, że krzywa na 50000 sztuk, a krzywa na 2000000 sztuk, a krzywa ogona teorii są prawie indistinguishable na taką skalę.
Poniżej znajduje się bliżej na czele krzywej.
Dolna część wysokość histogramu
Poniżej znajduje się znacznie powiększony-widzenia skrajnych końca ogona mierzone i teoretyczne krzywe histogramu.
Widok powi skrajnego końca ogona skalowane histogramy
Jak można się spodziewać, jest to bardzo rzadko na stos, aby osiągnąć te w wysokości nawet długo eksperymentów - ale nawet z naszymi ograniczone dowody w tym regionie ekstremalnych, teoretycznie wciąż wydaje się do zaakceptowania.
W pełni wykres teorii wydaje się pokrywać ogona do dystrybucji "dokładnie", mając na uwadze, że w powiększony wykres z ogona do ogona, widzimy wynika błąd. Jednakże, utrzymują, że to z powodu niewystarczających danych w tych ekstremalnych wysokości stosu. Jeśli wzrosła gry na pokładzie, powiedzmy wysokości 25 wierszy zamiast 20 wierszy, tak aby gry nie kończy nagle, I think I teorii przedstawionych powyżej idealnie zbiegnie się to z tendencją.
Moje uczucie jest, że ten histogram jest bezpośrednim połączeniu w wyniku Tetris A.I. i zasady Tetris. Tak, ten sam podział będzie przestrzegać wszelkich losowo długoterminowej gry Tetris przy użyciu mojego szczególności A.I. strategię gry "Dalej Piece" wiedzy.
Ponadto, myślę, histogram tego typu mogą być wykorzystywane do porównania AIs, które zatrudniają tych samych informacji podczas gry. Tak, nie ma do odegrania pełną gier (które może trwać kilka dni lub lat) w celu porównania skuteczności długoterminowej strategii różnych algorytmów.
Na przykład, pomimo prostoty mojego modelu Myślę, że mogą być wykorzystane do przewidzenia średni czas gry! My po prostu dowiedzieć się, ile sztuk sprawia, że "wiersz 21" stos wysokość znaczna liczba, takie jak liczbę.
Względne częstotliwość dla wiersza 21, zgodnie z moją zwykłą teorią, jest:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Należy pomnożyć tę liczbę przez (5.3 * 10^(7)), około 50 milionów euro, aby otrzymać wartość.
Tak, z grubsza przewidzieć, że moje obecne "Dalej Piece" strategia jest dobra tylko dla porządku na około 10 milionów wierszy zakończone. Jedną z przyczyn I to konserwatywne oszacowanie jest fakt, że nawet 18 wierszy może być śmiercionośne dla mojej A.I. bo nie pozwalają mojej A.I. do rozważenia sztuk, dopóki nie został obniżony o co najmniej jeden wiersz! (Jest to więc nie musisz się martwić o nie jest w stanie obrócić sztuk).
Jestem pod wrażeniem faktu, że gra tylko 50000 sztuk (i ewentualnie o wiele mniej sztuk) można uzyskać bardzo dobrą prognozę długoterminową wysokość histogramu, a co za tym idzie, dobrą prognozę na rząd wielkości z wierszy zakończone przed gra kończy. Takie podejście jest bardzo cenne dla szybkiej oceny subtelnych zmian w A.I., że jest już bardzo dobrze.
6.10 Zarząd oceny charakterystyki imitować spekulacyjnych patrzeć z wyprzedzeniem
Jeśli algorytm, takich jak z jednej z przedstawionych I ten projekt, po prostu próbuje wszystkich kierunków sztuki i tłumaczenia spadał, i stawek wynikających pokładzie każdej konfiguracji według niektórych miarą zasług, algorytm jest w istocie naśladujące "patrzeć z wyprzedzeniem".
Kiedy zatrudnia wskaźniki, takie jak "stos wysokość", "pochowany dziur", "chropowatości powierzchni" lub "oraz głębi", jeden jest naprawdę za pomocą uproszczonej formie "spojrzenia w przyszłość". Te ogólne characterizations na pokładzie dają pewne wskazówki dotyczące długoterminowej rentowności na pokładzie.
Idealnym podejściem, biorąc pod uwagę nieskończonej ilości mocy obliczeniowej, byłoby ocenić pokładzie wszystkich możliwych konfiguracji danego utworu, które mogą się sekwencji.
Chociaż trzeba rozważyć wszystkie 7 sztuk za równie prawdopodobne, na każdym poziomie szukać z wyprzedzeniem, musisz zoptymalizować rzeczywistych tłumaczenia (do 10) i kierunków (do 4) dla każdego elementu w kolejności wszelkie możliwe! To do (7*10*4) = 280 oddziałów na każdym poziomie rady nadzorczej z oceny! Tak więc, że na pokładzie do ((280)^(LookAheadLevels)) konfiguracje do rozważenia.
Ponieważ musimy zakończyć analizy po skończonej liczby poziomów, musimy mieć pewne nie patrzeć z wyprzedzeniem metody oceny stanu statku - w ten sposób podając wartości do liści węzły naszego drzewa wyszukiwania. Tak więc, dla tych węzłach liści, jesteśmy z powrotem do używania formuły, która zawiera ogólne prognozę przyszłej rentowności na pokładzie!
Tego typu spekulacje mogą być wypróbowany z jednoczęściowe i dwuczęściowe algorytmów w miejscu uproszczeniom pokładzie oceny charakterystyki. Załóżmy, wszystkie kolejne utwory są równie prawdopodobne i Podsumowując możliwości na pokładzie w celu uwzględnienia wszystkich rodzajów sztuk w najlepszy możliwy sposób. Może to być przeprowadzone z jednego, dwóch, lub dowolną liczbę spekulacyjnych przenieść głębi - wszystkie utwory są jednakowo prawdopodobne (p=1/7).
W końcowych węzłach tego drzewa mogą nadal wymagać ważona miar do oceny, ale spekulacyjnych warstw dokładniej uchwycić istotę tego, co chcemy zrobić: Ustal, jak również w danym pokładzie może zaakceptować wszystkich możliwych sztuk, w tym pozytywne czynniki, takie jak ukończenie linii i negatywne czynniki, takie jak zwiększenie ogólnej wysokości stosu, itp.
7. Tetris A.I. systemu demonstracji
7.1 Przegląd systemu
Poniższy diagram pokazuje to mój experimental set-up.
Ogólnie system demonstracji
7.2 Wyposażenie
Oto krótka lista urządzeń wykorzystywanych w tej demonstracji:
[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)
Oczywiście można użyć podobnego do osiągnięcia tych samych wyników. Więcej szczegółów dotyczących sprzętu są opisane w odpowiednich sekcjach tego artykułu.
Oto krótkie opisy do komputerów osobistych używanych w tej demonstracji:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Ta demonstracja może być łatwo reprodukowane z innych systemów operacyjnych, takich jak Linux. Jest ważne, aby mieć na CPU prędkości rzędu 800 MHz lub szybszy na komputerze, na którym jest do uruchomienia A.I. oprogramowania, ponieważ ten komputer będzie robić w czasie rzeczywistym przetwarzanie wideo.
7.3 Video wychwytywania sprzętu
Użyłem wspólnej USB kamery wideo jako urządzenia wideo do mojego A.I. systemu. Dokładniej mówiąc, użyłem w Creative "WebCam Pro", USB kamery wideo z 640 * 480 rezolucji.
Creative(TM) USB kamery wideo opis
USB kamery wideo (kąt)
USB kamery wideo (z przodu)
USB kamery wideo (z CCD pokładzie)
USB kamery wideo (głównych chipy)
OV511 głównych bloków (uwaga: USB kamery wideo jest OV511+)
7.4 OV511 arkuszu danych
ov511ds.pdf
OV511 Data Sheets
1136328 bajtów
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "plus") funkcja różnice
ov511plus_101.pdf
OV511+ funkcji Różnice
56271 bajtów
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Video wychwytywania oprogramowania
Microsoft ma bardzo stare API nazwie "Video for Windows" (VFW), że z powodzeniem stosowane w odniesieniu do tego projektu. (Link do Poszukać "vfw32.lib" w Twojej C++ projektu, lub zrobić DllImport "vfw32.dll" w Twojej C# kod.) Przykłady wykorzystania VFW API są powszechnie dostępne.
Alternatywą jest wykorzystanie Microsoft's "DirectShow" API do wideo.
Ponieważ VFW miało tylko kilkanaście linii kodu do wykorzystania, i zaakceptowane w moim wykonaniu 800 MHz maszyny, nie martwić poszukiwania alternatywnych APIs. Ale DirectShow jest bardziej współczesny API dla Windows wideo, i potencjalnie znacznie wyższe plony klatek na tym samym sprzęcie.
Spójrz na "CPF.StandardTetris.STVideoCapture" kod źródłowy plików w standardowy Tetris oprogramowania, aby zobaczyć, jak łatwo jest uzyskać wideo do własnych projektów.
7.7 Przekaźniki interfejsu do komputera (poprzez RS232)
Aby mieć jeden komputer "naciśnij klawisze" na klawiaturze z innego komputera, użyłem "relay pokładzie" kontrolowane przez tekst polecenia wysyłane z szeregowy port komunikacyjny (na przykład: "COM1") za pomocą kabla RS-232. I każdy przekaźnik używane do łączenia dwóch kabli o szczególnych klawiatury kluczem do symulacji kluczowym prasy.
To wymaga otwarcia klawiatury i dokonywania połączeń. Istnieje wiele prostsze metody symulowania klucza naciskając na komputerze, ale chciałem zrobić coś, co wydawało się jak najbliżej osoby naprawdę wpisując na klawiaturze.
Jednym z bardzo wszechstronnych i dobrze wykonane przekaźnik pokładzie jest ADR2200 dokonane przez Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Można spojrzeć na "CPF.StandardTetris.STRS232" kod źródłowy plików, aby zobaczyć, jak łatwo jest wysyłać bajtów przez port szeregowy, który może być następnie wykorzystane do sterowania urządzeniami, takimi jak wykazano powyżej ADR2200 pokładzie.
8. Standardowe oprogramowanie Tetris
8.1 Pobierz oprogramowanie
Przejdź do początku tego artykułu, aby znaleźć link, aby pobrać kod źródłowy (C# i C++ wersje) oraz wbudowanym oprogramowaniem (*.exe).
8.2 Podsumowanie funkcji
Oprogramowanie funkcje:
Instrukcja ekrany i kredytów
Tryb monochromatyczny
Cień trybie
Wskazówka trybie
Junk wiersze
Oceń kontroli
Następny utwór
Zarząd rozmiar
S/Z sztuk
Kalibracja w trybie
Video wychwytywania i uznawania
Uruchamianie konsoli
Save do gier
Załaduj grę
8.3 Początek wygląd
Wygląd gdy oprogramowanie zostanie uruchomiony:
Wygląd, gdy oprogramowanie jest uruchamiany
8.4 Tryb monochromatyczny
Domyślnie na pokładzie pojawia się w kolorze:
Domyślnie na pokładzie pojawia się w kolorze.
Kolor może być zmieniony w trybie monochromatycznym do (Shift + K):
Tryb kolorów można zmienić na monochromatyczny.
8.5 Cień trybie
Cień trybie wskazuje, gdzie będzie kawałek ziemi. Jest to bardzo pomocne w przypadku bardzo dużych planszach, ponieważ trudno jest ocenić, gdzie będzie kawałek ziemi.
Cień trybie wskazuje, gdzie będzie kawałek ziemi.
8.6 Wskazówka trybie
Wskazówka tryb pokazuje, gdzie aktualnie wybrane AI byłoby przenieść ze względu na obecną sytuację. (Shift + H)
Wskazówka tryb pokazuje, gdzie aktualnie wybrane AI byłoby przenieść.
8.7 Junk wiersze
Wstaw "śmieci" wierszy na dole stos, jeden po drugim, ręcznie. (Shift + J)
Wstaw "śmieci" wierszy na dole stos.
8.8 Oceń kontroli
W '+' (plus) i '-' (minus) klawisze kontroli prędkości gry.
Domyślnie gra działa na standardowych prędkości, zgodnie z zasadami Standard Tetris (prędkość w oparciu o poziom).
Poniżej znajduje się tabela z znaczeń prędkości stronniczości:
-3,-4,...: powolność proporcjonalna do stronniczości
-2: wolniej niż poziom 1
-1: normalne, ale jest ograniczona do poziomu 6 (0,2 sek) prędkości;
0: normal; Standard Tetris kontroli prędkości;
+1: nieco szybciej niż poziom 9 (0.05 sec opóźnienia);
+2: ograniczone stawki utylizacji (na przykład: 75 Hz);
+3,+4,...: wiele powtórzeń na świadczone ramki;
Podoba mi się uruchomić A.I. na ustawienie "+2" (hit '+' klucz dwa razy, jeśli zaczyna się od zera, stronniczości).
Szybkość stronniczości zmienia szybkość gry.
8.9 Pokaż następny utwór
Hit "N", aby włączyć przycisk "Dalej Piece" wyświetlacz. W A.I. będzie używać "Dalej Piece" informacji tylko wtedy, gdy "Dalej Piece" pojawia się na ekranie.
Możesz mieć pewność, że AI nie jest przy użyciu "Dalej Piece" informacji, gdy nie można zobaczyć "Piece Dalej" na ekranie.
Pokaż następny utwór
8.10 Zarząd rozmiar
Naciśnięcie Ctrl + (lewo, prawo, w dół, aż), można dostosować do dowolnych rozmiarów pokładzie rozmiarach od 4 * 4 do 200 * 400.
Zarząd rozmiar: 4 * 8
Zarząd rozmiar: 20 * 40
Zarząd rozmiar: 40 * 80
Zarząd rozmiar: 20 * 5
Zarząd rozmiar: 4 * 100
8.11 S/Z sztuk tylko
Badanie ciekawe S/Z zmianę wzorca.
Ten wzór nie może zostać rozwiązany na pokładzie 10 * 20 (szerokość * wysokość).
Niemniej jednak, że mają szerokości desek, które są wielokrotności 4 są trivially wykazano, aby umożliwić przetrwanie nieskończony.
Na czas nieokreślony AIs przetrwać w tych przypadkach, nawet jeśli nie zostały specjalnie dostrojone do obsługi tej sytuacji patologicznych.
S/Z sztuk tylko
8.12 Wideo w trybie kalibracji
Hit "C" wejść "Tryb kalibracji". Gdy w trybie kalibracji, można nacisnąć klawisze numer: {1,2,3,4,5,6,7}, aby wybrać utwór {O,I,S,Z,L,J,T} w górnej części gry pokładzie.
Jest to przydatne jako odniesienie do obrazu wideo na drugi Standard Tetris oprogramowania.
Jeśli nacisnąć 0 (zero) kluczowych, na pokładzie będzie pusty.
Można udawać, aby odbyć tarło sztuk, wybierając sztukę (1..7), a następnie wybierając (0) pusty, natomiast drugi komputer robi wideo zegarki na kawałki.
Możesz uruchomić A.I. na drugim komputerze i zobaczyć, jak go ofert z ręcznie wprowadzonych patologicznych Tetris scenariusze!
Kalibracja jest w trybie tylko do czasu można manipulować przetwarzania obrazu wideo szablon (4 * 2 sieci). Możesz użyć myszy, aby narysować prostokąt, ale możesz go użyć klawiszy kursora ( "up", "dół", "lewo", "prawo") mają grzywny kontroli granic - przy użyciu Shift kluczowych, aby wybrać naprzeciwko granicach prostokąta (na przykład: "Shift lewej" kombi jest inny niż "lewo").
Wideo w trybie kalibracji
8.13 Video wychwytywania i uznawania
Naciśnięcie "V" Włącza tryb wideo. Jeśli prawidłowo skalibrowany (patrz "wideo kalibracji" w poprzedniej sekcji), kawałki zdalnego ekranu zostanie złapany przez kamery wideo i niejawnych - i sztuk zrodził się w lokalnym gra na A.I. do rozważenia i reagować .
W A.I. wyjście musi następnie zostać przekazana (poprzez interfejs RS-232 w demonstracji opisanego w tym artykule) do zdalnego gra wejściowe (np. klawiatura) do A.I. z powodzeniem grać w gry zdalnego.
Jeśli w dowolnym momencie tego zamkniętego obiegu jest zakłócony (np.: wideo wadliwe działanie lub sygnał niesprawności), a następnie A.I. stworzy fałszywe wrażenie status zdalnego gra, a A.I. będzie niewłaściwe decyzje, które szybko tracą gry .
(Uwaga: Ten problem można przezwyciężyć z niewielką wysokość nakładu: A.I. systemu trzeba tylko zbadać cały ekran zdalnego Tetris na bieżąco "reality check" całego zarządu, a A.I. system powinien być przygotowany na pewne wyjście poleceń do nie w niektórych sposób.)
Video wychwytywania i uznawania
9. Tetris oryginalny eksperyment AI (2003)
Następujące pokazuje po raz pierwszy pracy w wersji Tetris A.I. systemu w roku 2003.
Kamery wideo stoi komputer # 1 uruchomione żadne zwykły tetris game
Komputer # 2 Standard Tetris oprogramowanie działa w trybie A.I.
Pozostało: Rysowanie siatki do kalibrowania obrazu wideo uznania;
Prawo: Tetris kawałek uznawania przypadków.
Ramka z wideo w Tetris A.I. eksperymentu w 2003 r.
10. Najlepsze jedną sztukę gry Tetris-algorytm w świat
10.1 Pierre Dellacherie (2003; Francja)
Pierre Dellacherie (2003; Francja), programista z najlepszych jedną sztukę gry Tetris-algorytm w świat
Najlepszym jeden kawałek, w czasie rzeczywistym Tetris algorytm do mojej wiedzy została utworzona przez Pierre Dellacherie z Francja.
Jego niesamowity algorytm czasami wypełnia więcej niż 2 miliony wierszy!
Średnia wydajność jest na porządku 650000 wiersze.
Algorytm zajmuje bardzo mało pamięci, a także z dużą prędkością (około 160 wierszy na 800 sekund na moim komputerze MHz).
Wydajność algorytmu Pierre Dellacherie's:
Mój obecny model do wykonywania Tetris OA jest, że dla każdej sztuki jest stałym prawdopodobieństwo, że gra będzie rozwiązać, p.
W związku z tym prawdopodobieństwo, że utwór nie będzie zakończenie gry jest q=(1-p).
Prawdopodobieństwo gra kończące k przemieszcza się po prostu produktem prawdopodobieństwo przetrwania (k-1) porusza, a mianowicie q^(k-1), a prawdopodobieństwo kończące się przenieść na następny, a mianowicie p.
Odpowiada to "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 )
Dla małych p, ln(q) jest około (-p), i mamy następujące:
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 )
Spodziewamy się, że ułamek całkowitej liczby grach do rozwiązania z wielu wierszy zakończone w przedziale [k1, k2] się:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Po ukończeniu 36 gier na moim komputerze, na okres dwóch dni, znalazł średnio 674827 zakończone wierszy.
Zgodnie z ogólną teorię powyżej, mogą oczekiwać, że w stosunku następujących części gry, aby zakończyć w następujących zakresach wypełniony wiersz:
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
Poniżej znajduje się wykres, że porównuje Exponential Distribution teorii z zaobserwowanych dystrybucji gier.
Wydajność algorytmu Pierre's ponad 36 zakończonych gier
Chociaż istnieją bardzo niewielu gier, w tym zestaw danych, jest oczywiste, że model jest dość dobre dopasowanie obserwowane w dystrybucji.
Pierre's wprowadzenie do jego algorytmu:
Pierre rozpoczęła prace w tym jeden utwór w algorytm 2003,1.
Pierre wysłał do mnie e-mail o jego algorytm na 2003.4.9, raportowania wyników następujących po sobie ponad 20 gier:
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.
"Algorytm jest realizowany w Turbo Pascal i zakończy 7000 wierszy / min. Z Athlon 1600+".
I przeliczone Pierre's algorytm do C++ w 2003,6, po kilku e-mail z Pierre wymiany. Mamy sprawdzone, że A.I. w wersji C++ się tym samym decyzje z Pascal wersji.
I obserwowano podobną wydajność do swego pierwotnego sprawozdania; średnio około 650000 wierszy zakończone, a niektóre gry ukończeniu 2 miliony wierszy.
Wspaniały!
10.2 Rozmowa z Pierre Dellacherie
[1] Kiedy po raz pierwszy tworzyć ten kod?
Mam w pracy na algorytm od końca stycznia 2003 do dnia dzisiejszego.
[2] Jak długo pracował Pan na niego?
Pracowałem w nim niemal co tydzień ... ale nie długo, bo codziennie mam inne działania: Niestety muszę zarabiać pieniądze jak każdy inny!
[3] Co zainspirowało projektowania kodu?
Grałem Tetris 10 lub 15 lat temu, ale nie zagrał ponownie na długi czas. Chciałbym powiedzieć, że jestem "przeciętnym" gracz wie, którzy z zasady i niektóre sztuczki.
Jednak, kiedy zacząłem pracę na algorytm nie odgrywają tak dużo, ponieważ znalazłem było bardziej skuteczne aby obejrzeć gry komputerowe i analizujemy jego słabości.
[4] Czy można użyć dowolnego automatyki do "pociągu" do wykonywania kodu lepiej? Czy masz jakieś opinie na celu poprawę algorytmu?
Albo po prostu nie można obejrzeć wyniki i podjąć zmian?
Ja jestem od "starej szkoły:" Ja po prostu zobaczyliśmy wyniki i postanowiła dokonać zmian.
"Automatyczne uczenia się" jest rodzajem meta-algorytm tak mam pewność, że nie sposób go w ten sposób łatwiej będzie uzyskać w tym meta-algorytm musiałby być zbudowany i zbyt, że nie jest tak proste!
Co więcej, nie zgadza się z Roger Penrose kiedy mówi (w swojej książce "Shadows of the mind"), że zrozumienie człowieka i intuicja nie może być algorytmiczny (przykład: computable).
[5] Kiedy po pierwszym uruchomieniu gry Tetris, i kiedy masz pomysł na rozwiązywanie Tetris z A.I.?
I uczyć algorytmiczny komputerowego i programowania (Turbo Pascal i Scilab) dla studentów, którzy pociągiem do egzaminu wstępnego na inżyniera absolwenta szkoły.
W pierwszym, "Komputer odgrywa Tetris" był pomysł chciałem się rozwijać dla mojego przyszłego roku studentów.
I nie był świadomy swojej stronie internetowej, gdy zacząłem pracę nad algorytmem.
Faktycznie miałem szczęście być świadomi swojej stronie internetowej zaledwie kilka tygodni temu, ponieważ sądzę, by były poprzez swoje wyniki (jak można się domyślać, wczesne wersje mojego algorytm nie grać tak dobrze!).
[6] Jaki jest obecny status?
Jestem prawie 30 [27 kwietnia przed 2003]. Mam kilka działań: Jestem wiolonczelista, komponowanie muzyki, a ja uczyć programowania.
I have a Master Degree in muzykologii (1994) i "Artificial Intelligence and Algorithmic" dyplomu (1998).
W tym Francja dyplomu odpowiada 5 lat studiów na uniwersytecie (4 lata ma stopień kapitana i 6. roku jest magisterskiej).
Pierre's kompozycje:
[7] Gdzie mieszkasz?
Ja jestem Francuski, a ja mieszkam w Rouen (Normandia).
[8] Inne uwagi:
Ostatecznie nie mam żadnego nowego pomysłu na jej poprawę.
Próbowałem tyle bezużyteczne (i głupi) to mam wątpliwości, że mogłaby ona zostać ulepszona.
Z drugiej strony, myślę, że nie może istnieć zupełnie różne algorytmy, które mogłyby mieć lepsze występy.
Swoją drogą, szybciej testu polega na rozpoczęcie sztuk w pół-box (10 wierszy x 10 kolumn): w pół-box, mój algorytm sprawia, że średnio 280 wiersze zakończone.
Jeszcze jedno: algorytm może być łatwo zmieniony w dwukrotnie laminowanych algorytm ([będę robić] testy wkrótce).
I love muzyki filmowej: film staje się kompozytor jest częścią mojego marzenia głównej (ale to tylko sen!).
11. Najlepszy gracz człowieka w świat
11.1 Japoński Tetris Master (2001 27 stycznia) video
Tetris kapitan (2001, Japonia) video
Arika przedstawia Japoński Tetris Finals kapitana (2001 27 stycznia). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Opinie
12.1 Slashdot wątku (2003)
W 2003 roku, mój Tetris A.I. projekt został omówiony na internetowym forum Slashdot (
http://slashdot.org).
Slashdot (http://slashdot.org) nagłówek internetowe forum do dyskusji na moim Tetris A.I. projektu
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 ]
Komiks zainspirowany przez moją Tetris A.I. projektu (2003) (po raz pierwszy w historii zostały zainspirowane komiksu!)
Komiks zainspirowany przez moją Tetris A.I. projektu (2003) (po raz drugi w historii zostały zainspirowane komiksu!)
13. History of the Tetris A.I. projektu
Na wiosnę 1989 roku byłem zajęty pomijam (i nie) drugi semestr studiów zajęcia na University of Pennsylvania.
Jeden z moich osob, Bill Matthews, miał Mac Classic, a czasami zagrał gier wideo.
Ludzie którzy przyznał się do Ivy League szkoły są zazwyczaj skłonni do konkurowania z innymi ludźmi w każdym czasie - tak, gdy dostał Bill gry Tetris na jego Mac, natychmiast rozpoczęła długoterminową walkę o wysokiej gości.
Ponieważ ocenę wspinał, czas inwestycji wymaganych w celu uzyskania małej dramatycznie wzrosła.
Aby długą historię krótkiego, Bill rzekomo posiada wysokiej gości między nami, ale podejrzewać go o użyciu ResEdit i rąbanie wynik pliku!
Bill miał zajęć w Wharton School of Business, alma mater z Michael Milken i Donald Trump, więc nie jest to niewyobrażalne, aby ktoś osadzone jeden impossibly wysokiej gości ...
W lecie 1990 I 30 MHz Intel 80386 IBM PC wypożyczony jeden z moich roommate, Alex Haidas.
Kupiłem Mac klawiatury na rynku pcheł 1 dolar.
I zbudował port równoległy obwody w celu umożliwienia PC kontroli Mac klawiatury.
(I wykorzystała CMOS 4040 chip do działania w rodzaju stałej stan klawiatury przekaźnik do wstąpienia do kontaktów wewnątrz Mac klawiatury).
Napisałem, że program komputerowy używany decyzji drzewo jako swoją strategię gry Tetris. W zaledwie kilka tygodni Miałem PC grać w gry Tetris działa na Mac.
Jednak byłem zobowiązany do korzystania z klawiatury PC do A.I. powiedzieć o każdym spadającym klockiem na ekranie.
Zacząłem pracować na obwodzie przy pomocy CdS (Cadmium Sulfide) detektory światła, które chudego Mac przed ekranem i "zobaczyć" objętych sztuk, ale CdS czujniki zbyt wolno zareagowała na zmiany jasności i kontrastu pomiędzy Tetris sztuk i tło na ekranie Mac Classic była zbyt niska, aby wiarygodnie dyskryminacji.
W te dni nie mają dużo pieniędzy, tak więc nie było zbyt ryzykowne kupić 2 dolary Radio Shack Fototranzystor, że nie mogą robić tego, co chciałem.
Ponadto, biorąc pod uwagę kontrast problem, byłem na temat całego pesymistyczne podejście.
Kiedy kupił swój pierwszy komputer osobisty w 1996 r., nie można uzyskać pod Windows 95 oprogramowania na 100 MHz CPU do szybkiego przetwarzania wideo wystarczy dokonać prostego widzenia systemu pracy.
Napisałem do obróbki obrazu w montażu kod języka, ale nie było tak wiele ogólnych przed moim kod faktycznie otrzymane dane wideo, które wydawało się niemożliwe, aby zrobić coś warto.
W 2003 roku, technologii, szczególnie CPU prędkości, osiągnęły poziom, że w ukończeniu projektu prawie trywialne.
Drążyłem moich osobistych starego projektu i wreszcie zakończeniu, dostawanie pewnym sensie zamknięcia.
To było bardzo ekscytujące, aby zobaczyć jeden komputer gry na innym komputerze za pomocą kamery wideo USB i przekaźniki.
Dźwięk z przekaźniki kliknięcie, oglądanie i części spadku na spin i śmieszne, superhuman prędkości, dokonane doświadczenia satysfakcjonującą w multisensory sposób.
W 2003 roku, moja praca została uznana przez Slashdot (
http://slashdot.org) i otrzymała wiele bardzo zwrotne.
Byłem zaproszony do stawienia się na "Screen Savers" telewizji pokazują na TechTV telewizji cyfrowej sieci.
I udał się do San Francisco i pojawił się na imprezie, i doświadczenie was great.
Później w 2003, Otrzymałem wiadomość od Henk Rogers, zapraszając mnie na Hawaje, aby sprostać Alexey Pajitnov go i porozmawiać o ustanowienie pewnego rodzaju standard Tetris, do celów mających Tetris turniejach.
Jeden szczególnego zainteresowania było umożliwienie graczy do korzystania z telefonów komórkowych do "konkurowania ze sobą," pośrednio, poprzez które imituje A.I. zawodników (we wcześniejszej analizie każdego gracza działań), co pozwoli uniknąć skutków telefon komórkowy dostęp do Internetu opóźnienia, pozwalając, aby gracze "rywalizują" * Najlepszych zawodników człowieka w świat (*..., lub raczej, naśladując A.I. najlepszych zawodników człowieka w świat).
I was thrilled przez perspektywę spotkania twórcy Tetris. Niestety, latanie czyni mnie troszczy, i odrzucił zaproszenie.
W 2006 roku, przeliczone moje "Standard Tetris" oprogramowanie z C++ do C# do oprogramowania bardziej dostępne i użyteczne dla współczesnych programistów.
