Tetris
Colin Fahey
1. Софтуер
2. Въведение
В тази статия се описва как един компютър може да играе на класическия видеоиграта Tetris от получаване на информация за съвет, определяне на добрите действия, както и извършването на тези дейности.
Тази статия включва софтуер, които могат да играят Tetris в реално време.
Софтуерът включва най-добрите в реално време, Tetris-игра алгоритъм в публичното пространство.
В тази статия се определя правилата за "стандартни Tetris," спецификация на базата на оригинални 1986 предварително търговска версия на Tetris за персонален компютър (PC).
В 2003, софтуера, включени в тази статия е използвана за да може компютърът да играе Tetris вървят на отделен компютър.
Обикновен USB видео камера е използвана за да може компютърът да "видите" на екрана на друг компютър.
А реле борда бе контролирано чрез RS-232 интерфейс да се позволи на компютъра да "натиснете клавишите" на клавиатурата на друг компютър.
Така, първият компютър има връзка към втория компютър, който е подобен на обикновения играч отношенията на човека към компютъра, когато играете Tetris; играта държава е единственият известен с гледате екрана, както и действия, играчът може да се образува чрез клавиатурата .
В конфигурацията в тази демонстрация установи, че един компютър могат да играят Tetris по-добре от човека, при нормални в реално време Tetris игра условия.
3. История на Tetris
В 1985, Alexey Pajitnov и Dmitry Pavlovsky бяха компютърни инженери по Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre на Russian Academy of Sciences
Alexey и Dmitry са заинтересовани в разработването и продажбата пристрастяване компютърни игри.
Те изпитват в няколко различни игри.
Alexey е вдъхновено от древните гръцки пъзел игра, Pentaminos, които участват организирането на пъзел фигури, направени от пет квадрата.
Alexey мисъл на идеята за организиране Pentamino парчета като те паднаха в правоъгълен чашка, но разбрах, че дванадесет различни пет квадратни форми бяха твърде сложни за видео играта.
Alexey преминали към използването на седем "tetramino" фигури, направени от всеки четири полета.
В 1985.6, Alexey Pajitnov програмирани първия вариант на Tetris на Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov и Tetris.
В 1985-1986, Vadim Gerasimov, 16-годишният гимназия компютър prodigy които работи в Академията, която се осъществява Tetris за IBM PC вървят MS-DOS на операционната система.
(Vadim Gerasimov не по-късно изследванията на MIT Media Laboratory, от 1994 през 2003, получаване на докторска степен след завършване много интересни проекти:
http://vadim.www.media.mit.edu)
Въвеждането на екрана на 1987-1988 предварително търговско съобщение на Tetris за PC
Играта играе на екрана на 1987-1988 предварително търговско съобщение на Tetris за PC
След 1987, Tetris разпространение по целия свят.
The Tetris Company, LLC, собственик на търговската марка Tetris.
4. Проекти вдъхновено от Tetris
4.1 0 тримерно Tetris
Още не е развита.
4.2 1-квадрат Tetris
Ziga Hajdukovic е разработил 1-квадрат Tetris софтуер, които могат да бъдат възпроизвеждани в Интернет браузър.
Ziga Hajdukovic също е разработена 1-квадрат Tetris софтуер за мобилни телефони използват Java J2ME платформа.
4.3 2-квадрат Tetris
Всички варианти са конвенционални Tetris в тази категория.
Този раздел съдържа интересни варианти.
4.3.1 Водещи Tetris игра някога: Delft University of Technology (1995)
Tetris играе на сградата; 2000 m^2 площ; Delft University of Technology (1995)
Tetris играе на сградата; 2000 m^2 площ; Delft University of Technology (1995)
4.3.2 Друг Tetris игра играе на сградата: Brown University (2000)
Tetris игра на екрана чрез Светлини в прозорците на сградата на Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
"Мисля, че това е просто най-невероятни един ден мога да си представим нещо в живота ми. Подобно на Пристанищен хамалин Jobs винаги заяви, пътуването е от отсрещната страна."
"Тя ме прави мислите на проекти, направихме обратно в колеж. Нещата, които бяха почти undoable, че други хора не мислят за това."
Steve Wozniak (2000)
4.3.3 Интернет браузър игра с MIT "Зелена сграда" на изображението
Vadim Gerisimov's интернет браузъра Tetris
Тази Интернет браузър Tetris вариант е създаден от Vadim Gerasimov.
Тази Интернет браузър Tetris характеристики на "Green" сграда на колежа на MIT.
Tetris Този вариант има само девет колони, вместо на стандартния десет колони.
Този вариант на Tetris представя новите парчета с произволни ориентации.
Vadim Gerasimov е човек които пише компютърен код за PC вариант на Tetris в 1986.
Vadim Gerasimov не доктор изследвания в MIT Media Laboratory през 1994-2003, работа по много интересни проекти.
4.3.4 PIC16F84 12 MHz микроконтролера базирани NTSC / PAL видео игра Tetris
PIC16F84 12 MHz микроконтролера базирани NTSC / PAL видео игра Tetris
В изображението по-горе показва NTSC / PAL видео продукцията, произведена от PIC16F84 12 MHz микроконтролера вървят софтуер, написани от Rickard Gunee в 1998.
Видеото е сигнал, генериран от софтуера за контрол на цифрови изхода.
4.3.5 "Scopetris" Oscilloscope Tetris от Lars Pontoppidan (2007.8)
"Scopetris" Oscilloscope Tetris от Lars Pontoppidan (2007.8)
Lars Pontoppidan пише кода за AtMega32 микроконтролера, и добавя просто аналогов движение, за да създадете Tetris версия, която може да се играе на един oscilloscope.
Някои регистри на AtMega32 микроконтролера контрол на 8-битов изход сигнали, и, когато е преминала през един "R-2R" електрически резистори схема за цифрово-аналогово към (D/A) преобразуване, в резултат на аналогови сигнали могат да контролират (x,y) координати на oscilloscope лъч (oscilloscope, когато е зададена "X-Y режим)."
YouTube видео:
FLV видео:
4.3.6 Obfuscated код Tetris: C / Unix
Следните бе връчена "1989 IOCCC Best Game".
long h[4];t(){h[3]-=h[3]/3000;setitimer(0,h,0);}c,d,l,v[]={(int)t,0,2},w,s,I,K
=0,i=276,j,k,q[276],Q[276],*n=q,*m,x=17,f[]={7,-13,-12,1,8,-11,-12,-1,9,-1,1,
12,3,-13,-12,-1,12,-1,11,1,15,-1,13,1,18,-1,1,2,0,-12,-1,11,1,-12,1,13,10,-12,
1,12,11,-12,-1,1,2,-12,-1,12,13,-12,12,13,14,-11,-1,1,4,-13,-12,12,16,-11,-12,
12,17,-13,1,-1,5,-12,12,11,6,-12,12,24};u(){for(i=11;++i<264;)if((k=q[i])-Q[i]
){Q[i]=k;if(i-++I||i%12<1)printf("\033[%d;%dH",(I=i)/12,i%12*2+28);printf(
"\033[%dm "+(K-k?0:5),k);K=k;}Q[263]=c=getchar();}G(b){for(i=4;i--;)if(q[i?b+
n[i]:b])return 0;return 1;}g(b){for(i=4;i--;q[i?x+n[i]:x]=b);}main(C,V,a)char*
*V,*a;{h[3]=1000000/(l=C>1?atoi(V[1]):2);for(a=C>2?V[2]:"jkl pq";i;i--)*n++=i<
25||i%12<2?7:0;srand(getpid());system("stty cbreak -echo stop u");sigvec(14,v,
0);t();puts("\033[H\033[J");for(n=f+rand()%7*4;;g(7),u(),g(0)){if(c<0){if(G(x+
12))x+=12;else{g(7);++w;for(j=0;j<252;j=12*(j/12+1))for(;q[++j];)if(j%12==10){
for(;j%12;q[j--]=0);u();for(;--j;q[j+12]=q[j]);u();}n=f+rand()%7*4;G(x=17)||(c
=a[5]);}}if(c==*a)G(--x)||++x;if(c==a[1])n=f+4**(m=n),G(x)||(n=m);if(c==a[2])G
(++x)||--x;if(c==a[3])for(;G(x+12);++w)x+=12;if(c==a[4]||c==a[5]){s=sigblock(
8192);printf("\033[H\033[J\033[0m%d\n",w);if(c==a[5])break;for(j=264;j--;Q[j]=
0);while(getchar()-a[4]);puts("\033[H\033[J\033[7m");sigsetmask(s);}}d=popen(
"stty -cbreak echo stop \023;sort -mnr -o HI - HI;cat HI","w");fprintf(d,
"%4d from level %1d by %s\n",w,l,getlogin());pclose(d);}
4.3.7 Obfuscated код Tetris: Perl код
По-долу е Tetris за Perl преводач: Perltris (версия 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) е стандарт, описващ за използване на графични обекти XML.
Mozilla SVG Tetris: Tetris осъществява чрез Scalable Vector Graphics (SVG) описание
4.3.9 Google "widget" Tetris
Google, Yahoo! и Microsoft, както и други дружества, са насърчавани миниатюрни интернет базирани софтуерни име "widgets", че обикновено се характеризира с някои използването на динамични данни по Интернет.
Една от тези widget достъпни чрез Google е Tetris игра.
Следният пример е сладък, но се въртят в досадни форми начини:
Google "widget" Tetris
Други Google widgets:
4.3.10 MIT изследвания хартия: "Tetris is Hard, Even to Approximate" (2002)
Следните изследователски документ съдържа доказателство, че на определен вид Tetris вариант е "NP-пълно."
Erik D. Demaine, Susan Hohenberger и David Liben-Nowell, "Tetris is Hard, Even to Approximate", Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
"NP-пълна" е класификацията на времето, разходите и пространството цената на един алгоритъм.
Други класификации включват "P" и "NP".
А класирането на "NP-пълно" предполага, че по-големи проблеми, отколкото някои малки размери, на алгоритъм е малко вероятно да намерите желания от разтвор в практически период от време и пространство.
4.3.11 Проучване на документа: "Applying reinforcement learning to Tetris"
След доклада, публикуван 2005.5.30, от Donald Carr по компютърни науки в катедрата Rhodes University, Южна Африка, представи приложението на "засилване изучаването" на Tetris.
4.3.12 Tetris пола (2007.11)
Tetris пола (2007.11)
В Tetris пола е създадена от "Lucy" ("hissyfitoly" на etsy.com) преди 2007.11.
От създателя описание на пола (предлагат за продажба на 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."
Форум коментари за тази пола:
"Човекът, че пола суча в Tetris"
"Ahahahaha, Мислех, че едно и също нещо."
"Има пълен ред определени в дъното ... завършени линии изчезне." "ГО НАД" "."
"Трябва да има място в предната или задната част, където отдавна би в перфектно ..."
"Това е наистина грозно пола все пак. Моята приятелка не можа да закупят достатъчно ми шоколад и цветя, за да ме убеди, че да носят нещо."
4.3.13 Tetris етап акт (2007.4)
Tetris етап акт (2007.4)
"Заведени от онези, които ви Triforce в 2006 ... Идвам на следващото поколение на обекта пък Скит ... Tetris."
Местните кеширана видео в Flash видео (FLV) формат (използване VLC да играят):
4.3.14 Весел Tetris вариации по телевизията показват, японски
Tetris вариации на японски телевизор показват
Това видео сегмент от японски телевизор показват включва весел варианти на Tetris, включително:
фигури, които изчезват при кацане, частица, че изпълва целия ред (като по този начин решаването на един ред при кацане), няколко парчета, включени едновременно, неправомерно оформени фигури, дълго парче, че е малко прекалено голям за да побере в една пропаст (предотвратяване на 4-ред завършването!), Mario натискането на един морков и стават огромни и да изчезне!, малко парче отпадъци, останали след редове са унищожени, повишаване на тежестта на вземане парчета плаваш в началото на страницата и др
Местните кеширана видео в Flash видео (FLV) формат (използване VLC да играят):
4.3.15 "The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
"The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
От описанието на YouTube:
"TETRIS играе с реални човешки същества заседание в аудитория:"
TETRIS е 4-ти видео изпълнение на GAME OVER Project, насочени от швейцарски художник Guillaume REYMOND (NOTsoNOISY творческа агенция).
Това стоп-движение видео е бил застрелян и играе за "LES URBAINES" фестивала
http://www.urbaines.ch в Palais де Rumine (Лозана, Швейцария) на November 24th 2007.
Местните кеширана видео в Flash видео (FLV) формат (използване VLC да играят):
4.3.16 2.5 тримерно Tetris
Терминът "2.5-квадрат" е използван тук, за да означават не-ортогонална оглед на двуизмерен вариант на Tetris, с дебелина в третото измерение.
(Намерете връзката "tetris3d" в "F7: GAMES".)
4.4 3-квадрат Tetris
Linux / GTK версия
Триизмерна Tetris във формата на ябълка Java за интернет браузъри:
Триизмерна Tetris за Windows операционна система:
4.5 4-квадрат Tetris
Greg Kaiser's "HyperTetris" (1996): 4-измерение Tetris
В [1996], [...], Greg Kaiser съберат четири квадрат вариант на класическата игра.
Използването IrisGL (a.k.a. igl) той създал работна, ако е трудно да се играе, играта използва четири под-екрани с изобразен на триизмерната различни аспекти на цялата игра-пространство.
[Защото] там не е лесно [разбираема] начин да се съставят четири-D обекти по два-D екран, четирите подгрупи мнения са практически начин да манипулират и визуализира ротация и превод на парчета през четирите измерения ( в играта, наречена x,y,z,w).
Вместо да попълните линии на блока, както в оригинал, като целта в този случай е да попълните пълния куб в x,y,z subview (обикновено 4 от 4 от 4).
Другите subviews, които съдържат "w" измерение са подредени по подразбиране 4 от 4 до 10 блок споразумение с "w" е най-дълго, "vertical" измерение в трите случаи, с различни бази на (x,y), (x,z), (y,z).
Гравитация актове в "-w" посока, така фигури попадат "в" три дълги subviews, които включват "w", и не се движат, освен ако играч от контрол през последните (x,y,z) subview.
Отнема известно време да се използва за, да кажем най-малко.
Ако някои от чудо на търпение или промяна на параметрите на играта, един дошли на завършване на куб, тя ще изчезне като приключи линии, които в първоначалния Tetris, макар и не висок резултат се пази в HyperTetris.
Benjamin Bernard (2000)
4.6 N тримерно Tetris
Polytope Tetris (2003): N една триизмерна игра Tetris вариант
Polytope Tetris е n-dimensionally Tetris.
Изхождайки от HyperTetris програма, Polytope Tetris ви позволява т играят Tetris във всеки БРОЯТ НА измерение.
Play Tetris в 3D, 4D, 5D, или повече.
HyperTetris е много по catchier име, отколкото Polytope (def) Tetris, но не мога да открадне името.
5. "Стандартно Tetris" спецификация
5.1 Въведение
Определението на "Стандарт Tetris" е idealized модел от най-важните характеристики и поведение на първия IBM-PC изпълнението на Tetris игра (circa 1986-1988).
В idealized модел се основава на inferring явното намеренията на разработчиците на първия IBM-PC изпълнението на Tetris игра.
Така например, изглежда разумно да infer, че разработчиците на първия IBM-PC изпълнението на Tetris игра, предназначени за избор на формата на всяко ново парче попадат "случайно," и че използването на Borland C изпълнението на rand() функция беше само практически сближаване на намерение.
Определението на "Стандарт Tetris" уточнява, че формата на всяко ново парче, попадащи е да бъдат избрани "на случаен принцип."
Това поведение на сигурност не може да бъде постигнат от всяка институция, но изпълнението може да сближи сигурност поведение.
Макар че не може перфектно изпълнение на изпълнението на определението за "Стандарт Tetris," идеалите на "Стандарт Tetris" включва обективни характеристики и приложения могат да бъдат сравнени в съответствие с тяхната относителна близост до идеалите на "Стандарт Tetris."
Този раздел описва набор от елементи, поведение, както и правилата, които колективно, се определят "стандартни Tetris."
5.2 Стандартно Tetris борда
В борда е мрежа от клетки, като 10 колони и 20 реда, в продължение на общо 10 * 20 = 200 клетки.
Стандартно Tetris борда (10 колони, 20 реда)
Всяка клетка може да бъде или unoccupied (празен), или заети (пълно).
5.3 Стандартно Tetris фигури
Има седем (7) стандарт Tetris фигури, със следните имена на писмото:
{ O, I, S, Z, L, J, T }
В писмото имена са вдъхновени от формите на парчета.
Седемте Стандарт Tetris фигури и техните "ориентации"
В точка в (0,0) съвпада с позицията (6,20) съвет, когато се появява първото парче.
Първата колона показва първоначална "ориентация."
В следващата, думата "ориентация" е използвана за описание на състоянието на всяко едно парче, в рамките на набор от позволени състояния, които могат да са резултат от една авъртане ротация на събитието.
Промяна на "ориентацията" от определена "ориентация" на "I, S," или "Z" парче, изисква комбинация от въртене и превод.
Следователно, думата "ориентация" е използван тук, за да означава нещо повече от ротация самостоятелно.
Въпреки това, "ориентация" може да се променя само в отговор на авъртане ротация на събитието, както и цикъл на отделни "ориентири" за всяка фигура се доближава или мачове, на цикъла в резултат на чисто ротации.
Специалните използването на думата "ориентация" в този контекст е почти равна на смисъла на думата "ротация" или "ъгъл," но думата "ориентация" е използван вместо това на "ротационен принцип" да се опитват да въвеждат внимание на факта, че някои парчета изискват повече от ротация за производство на набор от позволени състояния, произтичащи от авъртане "ротация" събития.
Фигури могат да преминат само насоки (или подложени на специфични хоризонтални или вертикални превод), ако в резултат на състоянието на парче няма да имат всички заети (пълно) клетки отвъд зоната на борда и няма да имате някакви заети клетки, които се застъпват всички заети в момента клетки на борда.
(В това правило, заемани (пълно) клетки на парче не се считат за част от "клетките в момента заема на борда"
В следващите коментари, всяко позоваване в резултат на авъртане ротация случай се прави с допускането, че такава ротация може действително да се извършва, като се има предвид съществуващите условия на парче и на борда.
В "O" (кутия) фигура е само една ориентация, и не се променят местата на всеки от неговите заети (пълно) клетки в отговор на всяко събитие авъртане ротация.
В "I" (ред) парче има два възможни ориентации, първоначално включени в хоризонтална ориентация.
В "I" парче заместници между двете насоки, в отговор на последователно редуване на авъртане събития.
В "S" и "Z" парчета всеки има два възможни ориентации.
Тези фигури всеки алтернативен между две насоки, в отговор на последователно редуване на авъртане събития.
В "L", "J", както и всяка "T" парчета са четири възможни ориентации, както и тези насоки са резултатите от прости ротации около центъра точки на форми.
Когато фигура първо се появява на борда, е "основна" фигура "ос" в хоризонтална ориентация, както и парче е в горния край на борда.
Следователно, не са фигури, първоначално в състояние на техните ориентации се промени. Парчето трябва да спускат от един ред да имат възможността да си ориентация се промени.
След като е паднала част от един ред на борда, всички парче ориентация може да бъде постигната (поемането на парче не е твърде близко до страничните стени, или на настоящите Инструменти на фигурите).
5.4 Стандартно Tetris flowchart
По-долу е приблизителна flowchart за стандартен Tetris игра.
Приблизителна flowchart за стандартен Tetris игра
Приблизителна flowchart за стандартен Tetris игра
5.5 Стандартно Tetris парче създаването
Следната диаграма показва (4 клетки * 2 клетки) район на борда, когато всички фигури се появяват, когато създаден.
Регион, където се появяват, когато парчета, създадени през Стандарт Tetris
Когато едно ново парче първо се появява на борда, неговия произход съвпада с точка по тази схема, както и парче ще бъде напълно овладяна с щрихованото зона на тази схема.
Когато се стартира нова игра, пълен свободни попадат забавяне elapses, както и на първата свободна попадат итерация частица се зареди в горния край на борда.
По време на нормалната игра играят, когато определена за свободна попадат итерация "земи" частица, пълен свободни попадат забавяне elapses и на следващата свободни попадат итерация частица се зареди в горния край на борда.
Когато дадена фигура се зареди, типа на парче е избран с помощта на следните алгоритъм:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Тъй като има предвид, че е константа p (= 1/7) шанс за избор на конкретен вид на парче, както и всички части от същия вид са различавани, вероятността за точно като k броя на определен вид след n опитите следва Тригонометрия разпространител:
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 )
Когато избирате измежду 7 (седем) броя на случаен принцип, вероятността за получаване на конкретна фигура е p=(1/7).
Ако направите това n=70 пъти, например, вероятността за получаване на точно k фигури (с k в диапазона 0 да n) е дадено от Тригонометрия разпределение, както е показано в следната картинка.
Тригонометрия разпределение за n=70, p=(1/7)
По този начин, може да се предскаже средното общо бройки от един вид дава общия брой на произволни фигури, а може също така да изчислявате очаква дисперсията и стандартното отклонение (корен квадратен от дисперсията):
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
Когато конвертирате една случайна стойност на индекса на парче, ние го интерпретират както следва:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[Предварително търговски MS-DOS версия на Tetris използва случайни брой функции, предлагани от Borland Pascal съставител.
Тази функция използва 32-битово състояние променлива.
Ето защо, последователността на случайни числа е ограничен до 2^32 отделни ценности.
Следователно, по принцип, играчът може да разгледате, след отпадането може би 10 парчета, точното място в стаята на 2^32 номера, съответстващ на текущото състояние на играта.
Ако Tetris симулации са извършени с определена последователност на 2^32 парчета, а след това оптимални решения могат да бъдат намерени на мястото на всеки в редицата.
(Не изглежда да е достатъчно възможности да бъдат на борда на напълно празна дъска състояние, което ни позволява да получите синхронизирани с precomputed оптимално решение път.)
Рискът от помощта на обикновен генератор на случайни номера в симулация за цел да се намери оптимално решение на проблема е, че решението ще бъде оптимално само за конкретния път чрез проблем пространство, избрани от прост генератор на случайни номера. ]
5.6 Стандартно Tetris контрол
По време на игра играят, следните елементи са на разположение:
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
Всички материали в сила от покачващите се край на положителния принос (за натиснете бутона, за разлика от съобщение на бутон).
Когато натиснете бутона се случва, това се брои за искането.
Провеждане на бутона установени извън рамките на определен период от време може да доведе до "автоматичното повтаряне" функция на клавиатурата, генериране на нови бутона преси - но тази функция е външен за игра на двигателя.
Суровините, посочени по-горе съответства на оригиналната игра Tetris.
Завъртане искания могат да бъдат изпълнявани, ако няма припокриване между желаната ориентация и клетки, в стаята на текущата борда (с изключение на парче, попадащи), и ако желаната ориентация не е клетки извън борда област.
Преведи искания могат да бъдат изпълнявани, ако няма припокриване между желаната конфигурация и е преведен клетки на текущата борда (с изключение на парче, попадащи), и ако е преведен на желаната конфигурация не е клетки извън борда област.
Въвеждане на заявки се обработват с латентност, че зависи от рамката курс на играта (пример: 75 Hz), както и искания в сила (ако е валидно) мигновено.
А може да се падна парче без ред, включени стъпки, настъпили.
А фигура може да се преведе на няколко пъти да се наляво или надясно, и впоследствие падна, на всички, без да изпитва официална линия, попадащи стъпка.
Тъй като наскоро зареди фигура не може евентуално да се редуват (идват, защото е против горния ръб на борда), играчът трябва да приеме най-малко една фигура, попадащи стъпка, ако желаете или ротации са задължителни.
Ефектът на рейтинг е незначително.
5.7 Стандартно Tetris парче "площадка"
Ако една бройка е просто попадат, тя попада в един ред по време на всяко парче, попадащи итерация.
Там ще бъде итерация, че тя се движи от едно място без да се свържете с хоризонтални повърхности на място, че има контакт с хоризонтални повърхности. След това се случва, повторения, на парчета, са в почивка за контакт.
Ако една итерация започва с едно парче на почивка в контакт с хоризонтална повърхност, на парче "земи," и става част от статично Инструменти.
5.8 Стандартно Tetris "линии приключи"
А попълнен ред е ред на пилотни, в която всички клетки са заети. Когато приключи ред е отстранен от пилотни и реда над елиминира ред са изместен от един ред за отстраняване на пропуск, това се счита за завършена "линия."
Когато фигура земи, той става част от пилотни.
Веднага след като парче земи, на пилотни се проверяват за завършено редове, както и всички попълнени редове са преустановени.
До четири реда може да бъде едновременно приключен.
Таблицата по-долу дава горната граница на линии едновременно приключен с едно парче:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Стандартно Tetris "нива"
Стандартно Tetris има 10 нива на трудност, номерирани 1 (един) чрез 10 (десет), с нивото 1 е "малко трудно."
Равнището индексира е най-много на две стойности:
actualLevel = max( initialLevel, earnedLevel );
В initialLevel стойност е нивото, че играчът избира при започване на нова игра.
Конфигурацията на ниво, като функция на завършени линии е лесно да наблюдават в предприсъединителния търговски MS-DOS вариант на 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
Така, earnedLevel стойност е изчислена по следния алгоритъм:
if (linesCompleted <= 0)
{
earnedLevel = 1;
}
else if ((linesCompleted >= 1) && (linesCompleted <= 90))
{
earnedLevel = 1 + ((linesCompleted - 1) / 10);
}
else if (linesCompleted >= 91)
{
earnedLevel = 10;
}
5.10 Стандартно Tetris, попадащи итерация закъснение
Стандартно Tetris е в реално време закъснение между последователни линия за свободна попадат повторения, че е функция на сегашното ниво на сложност.
Следните връзка между нивото на индекса и попадащи итерация незабавно се основава на повтарящи се stopwatch измервания на всички нива на предприсъединителните търговски MS-DOS вариант на 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
По този начин, ние се установи следната формула за итерация забавяне стойност, като функция на реалното ниво на индекса:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
В случай, че Съветът е празен и няма приноса на потребителите, зареди една бройка от реалното ниво 1 земи в приблизително 10 секунди, както и зареди парче от реалното ниво 10 земи в приблизително 1 секунди.
5.11 Стандартно Tetris "рейтинг"
Стандартно Tetris само награди точки за действие на разтоварване парче.
В момента няма точки, издадени за акта на завършване на един ред или попълване на две, три или четири реда едновременно.
[Забележка: Някои варианти на Tetris възлагане точки за акта на завършване линии, с експоненциално увеличаване на бонус за увеличаване на броя на едновременно завършено линии.
По този начин, стратегията за оптимизиране на резултата в такива варианти на Tetris включва създаването на възможности "за" получаване "на Tetris," Производни за използване на "I" форма за да получите четири едновременни линии и за достигането на много точки. ]
Ако имате празна дъска, и да оставите без "I" парче направи свободни попадат и земя, или вие веднага капка, която не е "I" парче, можете да се установи следната точка използването на диаграмата предприсъединителния търговски MS-DOS вариант на 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, които не са "I" фигури попадат общо 18 реда.
Това сметки за точка разликата между свободно падане и мигновени-капка случаи.
Чрез експериментиране с междинни случаи е лесно да infer следната точка формула:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Имайте предвид, че тази формула няма нищо общо с разстояние една бройка попада!
Тя е строго функция на реалното ниво, както и наказание за броя повторения на едно парче е позволено да падне свободно.
Това наказвам даден потребител се нуждаят от време за да мисля.
Също така имайте предвид, че една фигура, защото не могат да се завъртят в началото, когато първият spawns, играчът се санкционира с най-малко една свободна попадат итерация ротации, ако се изисква да поставите парче в пилотни.
Това най-вероятно никога не се отразява на човека играчи, освен ако те някак: признае фигура, натиснете клавишите за превод "(наляво" или "надясно)," натиснете клавиша "въртят" една или повече пъти, и натиснете клавиша "капка," всички в рамките на по-малко от секунда 0.5 ниво 1, или по-малко от секунда 0.05 ниво 10.
6. Стандартно Tetris стратегия
6.1 Въведение
Стратегия за игра на игра зависи от правилата на играта.
А стратегия зависи от параметър, който трябва да бъде оптимизирана.
В Стандартно Tetris, един надживява чрез попълване на редове, получава точки за кацане парчета, както и резултати от най-възможните точки за всяко парче от изпълняващата спад преди една или повече свободни попадат повторения transpire.
Една A.I. да оптимизирате точки, издадени за всяка фигура само с едно движение да вземе решение за бързо и "натискане на клавишите" за изпълнение на ход.
По-важно за една A.I. е оцеляването, тъй като неопределен оцеляване е произволно висок рейтинг може да бъде постигната. Защото Tetris фигури попадат в специален курс, на A.I. трябва да взема решения най-малко това бързо - и A.I. трябва да се движи, че пълни редове в размер, че средно най-малко 1 ред на 2,5 бройки. (Всяка част разполага с 4 клетки, както и всеки ред има 10 клетки.)
Разбира се могат да отложат решаването на редове от натрупване на парчета и изграждане на пилотни големи, но има само 200 клетки на целия борд, които по принцип могат да притежават само 50 бройки, така че всеки играч (като една A.I.), трябва да попълните линии, както основен приоритет.
В Стандартно Tetris, играта включва сегашното състояние борда на професията и на сегашните, попадащи парче (вид, състояние, както и ориентация). Играта държавни май избор включва "Напред парче".
6.2 Една променлив поредица от "S" и "Z" фигури
Heidi Burgiel, доктор, от Department of Mathematics, Statistics and Computer Science в University of Illinois at Chicago, се оказа, че един променлив поредица от "S" и "Z" парчета ще сила стандартен (10-колона, 20 реда) Tetris игра до края рамките на една предсказуема брой ходове.
Цитат от статията: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Асоцииран отпечатана статията: Mathematical Gazette, юли 1997 г., "How to Lose at Tetris"
Heidi Burgiel предлага Java applet, която работи в интернет браузъра, че се отличава с променен Tetris клонинг, че spawns променлив "S" и "Z" парчета.
[ "Обикновените Tetris" софтуер, свързани с документа, който четене също има режим, който spawns променлив "S" и "Z" парчета. ]
Heidi Burgiel заяви, че игра с променлив "S" и "Z" парчета (за стандартна Tetris съвет от 10 колони и 20 реда) трябва да се прекрати преди по-малко от 70000 бройки са паднали.
Стандартния софтуер, Tetris, включени в този документ дава възможност на дадено лице да играете игри с променлив "S" и "Z" парчета, както и промяна на борда на ширина.
Не е трудно да се види, че дъски, чиито цели са ширини кратните на четири колони (примери: 4 колони, 8 колони, 12 колони и т.н.) могат да бъдат възпроизвеждани завинаги, когато парчета заместник между "S" и "Z", с пилотни нараства не висока от 4 реда. I споменем това да стане ясно, че само оцеляване, описани в документ, научните изследвания, посочени по-горе е специално за случая на стандарт Tetris съвет (с 10 колони и 20 реда).
6.3 Unsolvable парче последователности в общите
Има цели категории патологични последователности, че не може да бъде преживяно.
Би било интересно да се изчисли общата вероятност от срещат игра-завършващо последователност, защото това би могло да постави горна обвързване на изпълнението на стратегията, дори и с пълно знание за всички бъдещи фигури във всеки даден момент в игра.
6.4 Всичко е възможно борда конфигурации
Като се има предвид, че на борда има 10 * 20 = 200 клетки, и предвид това, че всяка клетка може да съдържа само в една от двете държави (празен или заети), общият брой на борда конфигурации трябва да бъде по-малка или равна на: (2 ^ 200).
Като се има предвид, че всяка фигура добавя, 4 клетки на борда, както и всеки ред на проекта елиминира 10 клетки, от борда, броят на клетките, заети на борда винаги ще бъде дори. Така например, (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 и др Така, само половината от (2 ^ 200) борда на конфигурациите могат да бъдат достигнати чрез играе играта.
По този начин общият брой на борда на конфигурациите е приблизително: (2 ^ 199) = 8.03469... * 10^59.
Все пак, ние трябва да се изключат от нашето общо всяка конфигурация, която включва попълнили редовете, защото попълнили редовете са отстранени преди края на всеки ход. Всяка конфигурация с един или повече редове ще се попълва срив в друга конфигурация, която не съдържа никакви попълнили реда.
Също така, ние трябва да се изключи всякаква конфигурация, която включва не-празен ред над един или повече празни редове, защото не-празен ред над един празен ред винаги ще падне, както и на всички, включени спира преди края на всеки ход.
Всеки ред може да бъде по-2^10 = 1024-членки, една от които е "празна", една от които е "пълна", както и (1024 - 2) = 1022 от които са частично заети. Ние се изключат "пълното" случай от внимание.
Ако дъното ред е празен, тогава всички редове над дъното ред също трябва да бъде празен.
Ако дъното ред е частично заети, а после втория ред може да бъде празно или частично незаети.
Продължаване на този анализ, ние можем да изчислявате редица борда на конфигурациите, които се отчитат в пълна изолация на реда и ограниченията върху празни редове: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), което е приблизително ((1022 ^ 19) * (1023)).
По този начин, ние се намери по-точна оценка на общия брой на стабилна борда конфигурации: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199); т.е. около 3,74% по-малко от (2 ^ 199) прогноза.
Въпреки това, действителният брой на стабилно, достъпно борда членки вероятно ще се окаже по-ниска най-вече поради факта, че най-най-редове могат да бъдат запълнени в няколко посоки. Тъй като повечето от най-попълнят редовете, всекидневна с кухненски бокс, генерирани фигура не може да бъде преместен, или сменят много. Това ограничава броя на начините, по които най-най-редове могат да бъдат запълнени.
6.5 По принцип, най-добрият ход може да се намери за всяко парче борда и конфигурация
Защото ние можем да получите някое от седем възможни фигури за даден съвет-членка, общият брой на игра-членки е около 7 * (2 ^ 199) = 5.624... * 10^60.
Защото ние можем да, по принцип, не дълбоко търсенето на всички възможни фючърси за всички възможни ходове за дадена игра състояние, ние можем да имат една единствена "най-добрият" ход, свързани с всяка игра състояние.
Ние се предположи, че ние нямаме достъп до всяка информация, различна от сегашната съвет и текущото парче, така че "най-добър" е "в движение, която предлага най-голям шанс да отговаря на нашата дългосрочна цел на оцеляване".
Ход е само превод (до 10 опции) и въртене (до 4 опции), ние можем лесно да encode най-добрия ход в един бит.
Така че, по принцип, бихме могли да формират таблицата с 10^61 вписванията (байтове), които ни казват, най-добрият ход даде съвет държавните и сегашната бройка.
Разбира се това не е възможно, просто като enumerating всички "Go" дъски или "Chess" бордове е неприложима. Но точка е, че има едно вярно решение, и там е най-добрият ход за всяка дадена конфигурация. Там биха могли да бъдат еднакво добри ходове за дадена конфигурация, но не можем произволно избира един ход в този случай.
Много игра-игра алгоритми маси, които са изчерпателно изброяването на всички държавни игра ограничени възможности в рамките на контексти, като "отваряне на (първоначално) на свобода" или "края на играта (окончателно) на свобода" в шах. Статиите стол изчерпателно изброяване на Tetris Инструменти повърхности (приблизително (20 ^ 10) състояния) е осъществимо. Това е интересна идея.
Изчерпателно изброяване на всички държави от дъното два реда, умножена по седем възможни фигури, както и съхранение на най-добрия ход в един бит, би било доста лесно; се изисква само 7 MB на паметта. Може би за оптимизиране ефективността на тези седем милиона случаи би осигурил суровите данни за анализ, както и развитието на простите модели за данни; такива модели могат да се разглеждат като част от общата сигурност, Tetris игра-стратегия.
Имайте предвид, че най-доброто изпълнение на свобода все още не ни защитават срещу евентуални патологични игра-завършващо парче последователности. Това е само, че ние винаги ще се извършват движения, които ни предлага максимално потенциала за бъдещо оцеляване при положение, че всички бъдещи фигури са напълно случайни (и непознати към момента ние не трябва да решат как да се движат едно известно парче текущата).
6.6 В реално време изпълнението
Една пречка изправени някои алгоритми стратегия е необходимостта за реално време изпълнението - което означава, че алгоритъмът трябва да взема решение в рамките на определен период от време.
Когато човек играе Tetris, на парчета не спират, попадащи да даде на играча възможност да мислите. Това е част от предизвикателството на Tetris. Така, един A.I. система, която има за цел да симулират ролята на човека играч трябва също да взема решения в размер продиктувани от Tetris игра.
6.7 Ред и парче общите
Имайте предвид, че в дългосрочен план, броят на паднали парчета е много близо до 2.5 пъти броя на попълват редове - защото всеки ред има 10 клетки, както и всяка фигура е 4 клетки, и ние трябва да изпълним ред, средно, веднъж на всеки (10/4) = 2.5 парчета паднали.
Така че ние можем да използваме "попълват редовете" и "паднали фигури" почти заменимо с подходящи пропорционалност постоянно. Най-голямата грешка е, когато на борда е напълно изпълнен с изключение на една празнина във всеки ред (((10*20)-20)/4) = 45 парчета паднали, а дефицит на прогнозната (45/2.5) = 18 завършени редове.
6.8 Текущи-бройка (и борда) стратегия
Ако имаме само позволи на A.I. да имат познания по текущата съвет и текущото парче, и ние разглеждаме само се движат в резултат на текущото специално парче в начина, тогава това може да бъде наречена на "едно парче" анализ.
Това е груб чертеж на това как едно парче анализ може да вземе решение мести в Tetris:
Текущи бляскаво анализ на състоянието Tetris игра
Basically ние се опитваме всички възможни ходове и да изберат по преместването, че добивите най-добрия резултат.
Трудната част е на клиентите всеки резултат.
Ние трябва да курс един хипотетичен игра-членка в съответствие с колко добре такава държава подкрепя нашите краткосрочни и дългосрочни цели.
Нашата дългосрочна цел е оцеляването. Оцеляване зависи от предотвратяването на пилотни от Претоварената дъската. Ние можем да се намали Инструменти височина от които са пълни редове, които след това се елиминира от пилотни.
Да формират пълен ред, ние трябва да годни части от парчета в системата на всяка колона от този ред. По този начин, ние изискваме всички части на реда да бъдат изложени на парчета, включени, ако искаме да попълни в крайна сметка в целия ред.
Ако поради някаква причина ние покрива до части от празни реда с парчета на всеки висок ред, то сега сме в състояние да запълни в тези части на празен ред. Единственият начин (при не плъзгащи се) за достъп до тези "погребан дупки" е за отстраняване на горните редове, които имат части, действащи като препятствия.
Следните фактори са сред тези, които можете да използвате за курс, определен борда на състоянието:
Overall pile height
Колкото по-висока е Инструменти, на нашето лошо състояние, изглежда е, защото сме близо до Претоварената дъската.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
В rougher на пилотни, толкова по-вероятно е, че ще бъде трудно да попълни всички от вградените сложни контури, тъй като те стават изложени на площ.
Number of buried empty cells
Колкото повече дупки имаме погребан, в нашата ситуация е лошо, защото ние трябва да откриване погребан дупки, преди да можем да попълни съответните редове.
Можете да си представите други фактори, които обикновено се класира хипотетично съвет за това как и неговите Инструменти може да обработи всички от възможните бъдещи парчета, и как ситуацията изглежда добро за всички от тези възможни фигури.
Следващият въпрос е как да определя относителното значение на тези фактори.
Един общ подход е следният. Присвоите набор от "масите" (относителната значимост) за тези фактори, след което симулира много игри и записва резултата от тези игри (краен резултат, и т.н.). После, присвояване на нов набор от теглото и симулира нов набор от игри. Въз основа на това дали или не на нов набор от игри са по-добри резултати от предишните набор от игри, ние знаем, ако нов набор от теглото е по-добър от предишния пакет от тежестите.
В моя собствен опит аз се опитах системно търсене на случаен принцип и търсене на добри комбинации тегло, но аз не забележите други мащабни тенденции, които биха могли да преследват. Все пак, видях много изненадващо гладка bumps. Мислех, че е било интересно, че средната ефективност би могло да формират гладка крива, когато даден параметър е бавно се променя с други параметри, проведена в някои стойност комбинация.
Най-добрият в реално време, едно парче Tetris алгоритъм в света, създаден от Pierre Dellacherie (Франция) в 2003, дължи много на успеха си в стаята на измервания (или метрика). Намирането на теглото, когато е необходимо оптимизиране на стратегия, но тя също е много важно да започнем с вида на измерванията показват, че съответните характеристики на държавата.
Pierre Dellacherie's изобретението на нови начини за характеризират всяка борда му прави алгоритъм наистина отлична; борда характеристики за улавяне на важни стратегически измерения на борда на държавата.
Би могло да се развие един много различен набор от характеристики размери, че работи еднакво добре; Уверен съм, че е възможно да покриват съответните държавни борда на пространството в много различни начини, които могат да бъдат използвани да се определи стратегия функция. Ключът е да се намерят характеристиките на този проект държавната пространство чак до малък брой измерения, които могат да бъдат използвани за разработване на проста функция на клиентите (пример: на линейни претеглят комбинации от характеристики, използвани от Pierre's алгоритъм).
В една бройка алгоритъм, използван от "bot" в "xtris" софтуер (1996), написани от Roger Espel Llima използва тегла, определени от мащабно изследване на възможните комбинации на теглото с "генетични алгоритми". Симулирани annealing е друг възможен метод за проучване на много пространство на теглото комбинации.
Изглежда, че на основата на различни съображения, много функция на средната Tetris ефективност, като функция на тежести, например: F(w1,w2,w3,...), е "груб" (много от местните минимуми и максимуми), което означава, че просто много "хълм катерене" може да не работят.
6.9 Стратегията, когато сегашната бройка, следващото парче, както и борда са известни
Ако дадена стратегия алгоритъм се дава текущата парче, следващото парче, както и борда, тогава той може да взема решения, които да се възползват от комбинирането на парчета.
Познаване на следващата фигура може да се подобри успеха на една игра Tetris алгоритъм от няколко поръчки с магнитуд. Изключително лесно е да се знае как comprehend следващата фигура прави голяма разлика в стратегията.
Един може да направи "луд" ходове, като обхваща огромни дупки и т.н., защото те вече знаят, че на следващата фигура може да "определи" на ситуацията. Ако нямате познания на следващото парче, вие постоянно се опитват да играят на коефициентите, опитвайки се да задържи отворени възможности, в случай че следващото парче не е идеален.
Следната схема показва как на всички възможни ходове на текущото парче, са разгледани и за всеки такъв ход ще разгледа всички възможни ходове, включващи следващото парче.
Стратегия, включваща сегашните парче и следващото парче
Tetris стандартните софтуерни приложения в тази стратегия, когато "Следващо парче" е активирана от потребителя и се виждат на екрана, и когато две парче A.I. е включено (като, от една написана от мен, Colin Fahey). Ако "Следващо парче" не се вижда на екрана, моите две бройка попада обратно към едно парче A.I..
Моят една бройка A.I. е ужасна, когато в сравнение с други AIs в стандартните Tetris софтуер; така, това ви показва от полза повече информация (пример: на следващата фигура) може да бъде до A.I. система, е достатъчно да се подобри ефективността на моята собствена посредствен две A.I. парче от няколко поръчки с магнитуд - лесно surpassing изпълнението на най-добрите една бройка A.I. в света.
(Въпреки това, превръщането на най-добрите една бройка A.I. в света, да обмислят две парчета лесно ще се подобри, че от няколко поръчки с магнитуд, прекалено! Владеенето на следващата фигура е огромна!)
Моят първи тест игра с моите две парче A.I. продължило около 182 часа (7,6 дни), на 800 MHz PC, завършване 7216290 редове. Имам не е тестван на алгоритъм по-бърз компютър.
При записа на състоянието на Tetris игра (Shift-W) на текстов файл, ще можете да копирате и поставите на списъка с номера, от раздел "heightHistogram", с Excel електронна таблица.
Всяка бен в histogram се посочва броят на попълват се движи, че завърши с конкретен Инструменти височина (след пълно редове са отстранени). Както можете да си представите, като се мести, че напълно елиминира един Инструменти е рядко, така че общият брой на хода, че завършва с пилотни височината на нула, е относително ниска.
Междувременно, Вие бихте могли да очакваме, че като цяло fluctuates Инструменти височина около средната част, така кошчета, съответстващи на тези редове ще доминират histogram. И накрая, кошчета за най-най-редове (където са в опасност от Претоварената дъската) са много ниски суми.
В течение на много часове, с A.I. играе една игра с стратегия, включваща знания за "Напред парче", бях сигурна, случайни проби на играта състояние, копиране на пилотни височина histograms за електронни таблици, както е показано по-долу:
Купчина височина histograms, регистрирани в различни точки в една типична игра (с настоящите и най-ново парче стратегия)
Можете да мащаб всяка histogram от общия брой на фигури (общият брой на завършени хода), за да получите следните данни:
Мащабирани histograms, както и теорията
В забележително нещо е, че тези мащабирани histograms изглежда идентична, въпреки различните заповеди на размера на броя на фигури (попълва се движи), участващи.
Просто като се потърси по номера, който направих хипотезата, че опашката на кривата е изразител гниене. С изпитание и грешка да дойде с бурни теория, че опашката е бил описан от:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Следната диаграма показва мащабирани histogram през целия диапазон на реда.
Графика на мащабирани histograms
Имайте предвид, че кривата на 50000 парчета, както и за крива 2000000 парчета, както и кривата на опашката теория са почти отличават от този мащаб.
По-долу е по-отблизо начело на кривата.
Долната част на височина histogram
Следните е значително увеличено-гледна точка на екстремни опашката края на измерените и теоретични histogram криви.
Увеличените гледна точка на екстремни опашката края на мащабирани histograms
Както може би очаквате, че е много рядко за пилотни да се постигнат тези височини по-дълго, дори опити - но дори и с нашите ограничени доказателства в тази изключителна региона, на теория все още изглежда приемлива.
В пълен опис на теория изглежда се припокриват опашката на разпределението "точно", докато в увеличените структура на опашката на опашката, ще видите очевидната грешка. Струва ми се обаче, считат, че това се дължи на недостатъчни данни в тези пилотни екстремни височини. Ако се увеличи играта на борда, да речем, на височина от 25 реда, вместо от 20 реда, така че игрите не прекратява рязко, мисля, че теорията I представени над ще съвпадне удобно, с тенденция.
Моето усещане е, че това histogram е пряк резултат от комбинирания Tetris A.I. и правилата на Tetris. Така че, тази същата дистрибуция ще бъде наблюдавана по някаква случайност дългосрочна игра на Tetris използвайки моя специално A.I. стратегия за игра с "Следващо парче" познания.
Освен това, мисля, този тип histogram може да се използва за сравняване на AIs, които наемат на една и съща информация, докато играят. По този начин, не е необходимо да играе пълни игри (което може да трае с дни или години) за сравняване на дългосрочна стратегия за изпълнение на различни алгоритми.
Така например, въпреки привидно простия начин на моя модел, мисля, че могат да бъдат използвани за прогнозиране на средната продължителност игра! Ние просто да проумея колко бройки прави "ред 21" Инструменти височина на значителен брой, като разчитат на един.
Относителната честота на ред 21, в съответствие с моята проста теория, е:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Трябва да умножете тази цифра по (5.3 * 10^(7)), приблизително 50 милиона, за да получите стойността на една.
По този начин, аз приблизително предричат, че сегашната ми "Следващо парче" стратегия е само добро за по нареждане на приблизително 10 милиона завършени редове. Една от причините да направя тази консервативна прогноза е фактът, че дори и 18 редове могат да бъдат смъртоносни за моята A.I., защото аз не позволи ми да разгледа A.I. парчета докато не падна от поне един ред! (Това е така, аз не трябва да се тревожите за които не са в състояние да въртят бройки.)
Аз съм впечатлен от факта, че играе само 50000 бройки (и вероятно много по-малко бройки) може да ви даде много добра оценка на дългосрочни височина histogram, и по този начин, добра оценка от порядъка на размера на редове, преди да приключи играта приключва. Този подход е изключително ценен за бързо оценяване на фините промени в A.I., че вече се правят изключително добре.
6.10 Съвет за оценка метрика имитират спекулативни поглед напред
Ако един алгоритъм, като една I представени с този проект, просто се опитва парче на всички насоки и преводи за отпадане, както и курсове, всеки резултат борда на конфигурацията според някои мярка за заслугите на алгоритъм е по същество имитиране "поглед напред".
Когато един работят показатели като "Инструменти височина", "погребан дупки", "площ roughness" или "и дълбочина", един наистина се използва опростена форма на "поглед напред". Тези общи характеристики на борда даде някои посочване на дългосрочната жизнеспособност на борда.
Идеалният подход, като се има безкрайно количество на изчислителната мощност, ще бъде да се оцени една конфигурация на борда на даден всички възможни парче последователности, които могат да следват.
Въпреки че трябва да разгледа всички 7 парчета, както са с еднаква вероятност на всяко ниво от поглед напред, трябва да оптимизирате действителната преводи (до 10) и ориентации (до 4) за всяко парче по всички възможни поредица! Това е до (7*10*4) = 280 клонове на всички нива на борда на оценка! Така че, това е до ((280)^(LookAheadLevels)) борда конфигурации да се разгледа.
Защото ние трябва да се прекрати след анализ на ограничен брой нива, ние трябва да имат някои не-поглед напред метод за оценка на борда на състоянието - начин на МФ стойности на листните възли на нашето търсене на дърво. Така че, за тези листа възли, ние сме обратно към използване на формула, която олицетворява общия предиктори на бъдещи жизнеспособност на борда!
Този вид спекулации, може да се опита с едно парче и два-парче алгоритми на мястото на опростенческата борда на метрики за оценка. Поема всички последващи парчета са еднакво вероятно и обобщение на уменията на борда да се настаните бройки от всички видове в най-добрия възможен начин. Това може да се извършва с една, две или всеки брой на спекулативен ход дълбочина - с всички парчета са с еднаква вероятност (p=1/7).
Терминалът възли на това дърво все още могат да изискват от претеглените показатели за оценка, но спекулативни пластове по-точно за улавяне на същността на това, което искате да свършите: да определи колко добре даден съвет може да приеме всички възможни фигури, включително и положителни фактори, като например решаването на реда и отрицателни фактори, като нарастването на общото Инструменти височина и др
7. Tetris A.I. система демонстрация
7.1 Система за преглед
Това показва следната картина ми експериментални създаване.
Цялостната система за демонстрация
7.2 Оборудване
Ето кратко списък на оборудването, използвано в тази демонстрация:
[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)
Разбира се можете да използвате подобни съоръжения да изпълни същите резултати. Повече подробности по отношение на оборудването са описани в съответните раздели на тази статия.
Ето кратко описание на персонални компютри, използвани в тази демонстрация:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Тази демонстрация могат лесно да се възпроизведе с други операционни системи, като Linux. Тя е по-важно да има CPU скорост от порядъка на 800 MHz или по-бърз за компютър, е да стартирате A.I. софтуер, защото този компютър ще се правят в реално време обработката на видео.
7.3 Видео улавяне на хардуер
I използват обща USB видео камера за видео устройство за улавяне на моя A.I. система. В частност, I, използвани за Creative "WebCam Pro", един USB видео камера с 640 * 480 резолюция.
Creative(TM) USB видео камера описание
USB видео камера (в ъгъла)
USB видео камера (отпред)
USB видео камера (с борда CCD)
USB видео камера (основните чипове)
OV511 основни групи (забележка: USB видео камера е OV511+)
7.4 OV511 информационен лист
ov511ds.pdf
OV511 информационни листове
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "Плюс") функция разлики
ov511plus_101.pdf
OV511+ функцията разлики
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Видео улавяне на софтуер
Microsoft има много стари API име "Video for Windows" (VFW), че използва успешно за този проект. (Може линк към "vfw32.lib" в своя C++ страници, или правите DllImport на "vfw32.dll" в своя C# код.) Примери за използване на VFW API са широко достъпни.
Възможна алтернатива е да използвате Microsoft's "DirectShow" API да правите видео плен.
Защото VFW бяха само десетина реда код, за да използвате, както и извършени acceptably на моя 800 MHz машина, аз не се мъчите проучване на алтернативни APIs. Но DirectShow е най-съвременната API за Windows видео улавяне, както и потенциално много по-високи добиви рамка ставка за същия хардуер.
Потърсете в "CPF.StandardTetris.STVideoCapture" изходния код файлове в стандартния Tetris софтуер, за да видите колко лесно е да получите видеоклип в плен на собствения си проекти.
7.7 Компютърен интерфейс за релета (чрез RS232)
За да има право на един компютър "натиснете клавиши" на клавиатурата на друг компютър, да използват един "реле борда на" контролирано от текста команди, изпратени от един сериен порт комуникация (например: "COM1") чрез RS-232 кабел. I използва всяка реле за свързване на два проводника на специална клавиатура от ключово значение за симулира ключов преса.
Това изисква отваряне на клавиатурата и създаване на връзки. Има много лесни методи за симулира натискане на клавиша на компютъра, но аз исках да направя нещо, което изглеждаше възможно най-близко до човек наистина да пишете на клавиатурата.
Един много гъвкави и добре направени реле борда е ADR2200, направени от Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Можете да погледнете в "CPF.StandardTetris.STRS232" изходния код файлове, за да видите колко лесно е да изпращате байта чрез сериен порт, който може да се използва за контрол на устройства, като например ADR2200 борда е показано по-горе.
8. Стандартно Tetris софтуер
8.1 Изтегли софтуер
Към началото на тази статия, за да откриете линк за изтегляне на изходния код (C# и C++ версии) и вграден софтуер (*.exe).
8.2 Обобщение на функции
Софтуер характеристики:
Инструкция екрани и кредити
Монохромен режим
Сянка режим
Съвет режим
Нежелана редове
Честота на контрола
Следваща част
Размер съвет
S/Z фигури
Калибриране режим
Видео улавяне и признаване
Debugging конзола
Запазване на игра
Зареждане на игра
8.3 Започва появата
Изяви, когато софтуерът е започнала:
Изяви, когато софтуерът е започнало
8.4 Монохромен режим
По подразбиране на борда се появява в цвят:
По подразбиране се появява на борда на цвят.
Цвета режим може да бъде променено на монохромна (Shift + K):
Цвета режим може да бъде променено на монохромна.
8.5 Сянка режим
Сянка режим показва, когато една бройка ще се земя. Това е много полезно за много големи табла, защото е трудно да преценят, когато ще парче земя.
Сянка режим показва, когато една бройка ще се земя.
8.6 Съвет режим
Съвет за начина ви показва, където в момента-разглеждане AI ще се движат като се има предвид сегашната ситуация. (Shift + H)
Съвет режим показва, където в момента-разглеждане на AI ще се движат.
8.7 Нежелана редове
Поставете "смет" редове в дъното на пилотни, една по една ръчно. (Shift + J)
Поставете "смет" редове в дъното на пилотни.
8.8 Честота на контрола
В '+' (плюс) и '-' (минус) клавиши за контрол на скоростта на играта.
По подразбиране, играта е на стандартна скорост, съгласно правилата на Стандарт Tetris (скорост на базата на ниво).
Това е таблица на значения на скоростта пристрастие:
-3,-4,...: забавяне, пропорционално пристрастие
-2: бавен от ниво 1
-1: нормална, но ограничен до ниво 6 (0,2 сек) скорост;
0: нормални; Стандарт Tetris скорости;
+1: малко по-бързо, отколкото ниво 9 (0.05 sec закъснения);
+2: ограничена от превръщането курс (пример: 75 Hz);
+3,+4,...: многократни повторения на извършените рамка;
Харесва ми да тече от A.I. при определянето на "+2" (натиснете два пъти клавиша '+' пристрастие, ако започва от нула).
Speed пристрастие променя скоростта на играта.
8.9 Показване на следващото парче
Натиснете "N", за да включите "Следващо парче" дисплей. В A.I. ще използваме "Следващо парче" информация, само ако "Следващо парче" се появява на екрана.
Можете да бъдете уверени, че AI не ползва "Следващо парче" информация, когато не можете да видите "Следващо парче" на екрана.
Показване на следващото парче
8.10 Размер съвет
При натискане Ctrl + (вляво, вдясно, установени, създаден), може да настроите големината на борда на произволни размери от 4 * 4 до 200 * 400.
Размер на Борда: 4 * 8
Съвет размер: 20 * 40
Съвет размер: 40 * 80
Съвет размер: 20 * 5
Размер на Борда: 4 * 100
8.11 S/Z бройки само
Проучване на интересни променлив S/Z модел.
Този модел не може да бъде решен за 10 * 20 съвет (ширина * височина).
Въпреки това, плоскости, които са ширини, които са кратните на 4 са показани trivially да позволи безкрайно оцеляване.
В AIs оцелее неопределено време в тези случаи, въпреки че те не са изрично мелодия да боравят с това патологично състояние.
S/Z бройки само
8.12 Видео калибриране режим
Хит "C" да влезе "Калибриране режим". Когато в режим на калибриране, можете да натиснете клавишите на броя: {1,2,3,4,5,6,7} да изберете парче {O,I,S,Z,L,J,T} в началото на борда на игра.
Това е полезно за позоваване на изображението за видео улавяне на втори стандарт Tetris софтуер.
Ако натиснете бутона 0 (нула) ключ, той ще направи борда на празно.
Може да се твърди, за да spawn бройки, като изберете парче (1..7), а след това изберете празно (0), а вторият компютър прави видео часовници за улавяне на парчета.
Можете да стартирате A.I. на втория компютър и да видите как тя се занимава с ръчно да влезе патологични Tetris сценарии!
Калибриране Mode е единственият път, когато могат да манипулират видео обработка шаблон за улавяне на изображението (4 * 2 решетка). Можете да използвате мишката, за да привлекат правоъгълник, но след това можете да ползвате клавишите курсора на мишката ( "нагоре", "установяване", "ляво", "право"), за да има глоба за контрол на границите - използва Shift клавиша, за да изберете противоположните граници на правоъгълник (например: "Shift-ляво" комбинация е различен от "ляво").
Видео калибриране режим
8.13 Видео улавяне и признаване
При натискане "V" Включва видео улавяне режим. Ако правилно калибрирана (виж "видео калибриране" в предишния раздел), на броя на отдалечените видео екран ще бъде заловен от видео камера и класифицирани - и на парчета ще се зареди в местната игра за A.I. да разгледа и да реагираме .
В A.I. изход трябва да се предават (чрез RS-232 интерфейс в демонстрация, описани в тази статия) с дистанционно играта вход (пример: клавиатура) за A.I. успешно да играе на отдалечените игра.
Ако във всеки един момент този затворен цикъл е нарушена (пример: видео за улавяне на неизправност, или изходния сигнал неизправност), тогава A.I. ще разработи грешно впечатление за статута на отдалечени от дивеч, както и A.I. ще направи неуместни решения, които бързо да изгубите играта .
(Забележка: Този проблем може да бъде преодоляна със скромен размер на усилие: The A.I. система трябва само разглежда цялата дистанционно Tetris екран за продължаване на "проверка на действителността" на целия борд, и A.I. система трябва да бъде подготвен за някои команди към изхода не успее в някои забавление.)
Видео улавяне и признаване
9. Оригинална Tetris AI експеримент (2003)
Следните показва първия работен вариант на Tetris A.I. система през 2003 година.
Видео камера, изправени пред компютъра # 1 се изпълняват всеки обикновен Tetris игра
Компютърни # 2 текат Стандарт Tetris софтуер в A.I. режим
Вляво: Рисунка мрежа да коригира видео изображение признаване;
Право: Tetris парче признаване случаи.
Кадър от клипа на Tetris A.I. експеримент през 2003 г.
10. Награда за една бройка Tetris-алгоритъм игра в света
10.1 Pierre Dellacherie (2003; Франция)
Pierre Dellacherie (2003; Франция), разработчик на най-добрите една бройка Tetris-алгоритъм игра в света
Най-добрият една фигура, в реално време Tetris алгоритъм да ми е известно е създадена от Pierre Dellacherie на Франция.
Неговата удивителните алгоритъм понякога се запълва повече от 2 милиона редове!
Средната ефективност е по нареждане на 650000 редове.
В алгоритъм отнема много малко памет, и работи на висока скорост (около 160 реда в секунда на моя 800 MHz компютъра).
Извършване на Pierre Dellacherie's алгоритъм:
Текущата ми модел за изпълнение на Tetris ПИ е, че за всяка дадена фигура има предвид, че е постоянна вероятността, че играта ще се прекрати, p.
По този начин, вероятността, че парче няма да се прекрати играта е q=(1-p).
Вероятността от играта се прекратява след k хода е просто продукт на вероятността от преживял (k-1) ходове, а именно q^(k-1), както и вероятността за прекратяване на следващия ход, а именно p.
Това съответства на "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 )
За малките p, ln(q) е приблизително (-p), и ние имаме следното:
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 )
Очакваме частта от общия брой изиграни игри да прекрати с редица завършени редове в интервала [k1, k2] да бъдат:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
След завършване на 36 игри на компютъра си, в продължение на два дни, намерих една средно 674827 завършени редове.
Според общата теория по-горе, бих се очаква следващата относителна част от игрите да приключи в следните диапазони попълнен ред:
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
Ето една диаграма, че сравнява Exponential Distribution теория с наблюдават разпределението на игри.
Извършване на Pierre's алгоритъм над 36 завършени игри
Въпреки че съществуват много малко игри в този набор от данни, като е очевидно, че моделът е относително добър в който наблюдаваното разпределение.
Pierre's въвеждането на неговия алгоритъм:
Pierre започнаха работа в тази една бройка алгоритъм в 2003,1.
Pierre ми изпрати по електронната поща и за неговия алгоритъм за 2003.4.9, отчитане на следните ефективността на повече от 20 последователни игри:
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.
"The алгоритъм се изпълнява в Turbo Pascal и приключва 7000 редове / мин. С Athlon 1600+."
I преобразува Pierre's алгоритъм за C++ в 2003,6, след няколко пощата обмен с Pierre. Ние потвърдили, че A.I. в C++ версия направи същото решенията на Pascal версия.
I наблюдавани подобни изпълнение на първоначалната си доклад; завършено средно около 650000 реда, а някои игри завършване 2 милиона реда.
Невероятно!
10.2 Разговор с Pierre Dellacherie
[1] Кога бе първоначалното създаване на този код?
I са работили по алгоритъм от края на януари 2003 г. до сега.
[2] От колко време сте работили по нея?
I работил върху нея почти всяка седмица ... но не и всекидневието дълго, защото имам други дейности: За съжаление трябва да печелят пари като никой друг!
[3] Какво вдъхнови създаването на кодекс?
I изигра Tetris 10 или 15 години, но не играе отново за дълго време. Бих казал, че съм един "среден" играч които знаят правилата и някои трикове.
Въпреки това, когато започнах да работят върху алгоритъма не играят толкова много, защото открих, беше доста по-ефективно да гледате на компютъра играе и анализира слабостите си.
[4] Знаете ли, използвайте каквато и да "обучава" своя автоматизация код, за да представят по-добре? Дали имате някакви отзиви за подобряване на алгоритъм?
Или не можете просто да гледат резултатите и да реши да направи промени?
Аз съм от "старата школа:" Аз просто гледани резултатите от него и реши да направи промени.
"Автоматично обучение" е вид мета-алгоритъм, така че не съм сигурни, че това, че по този начин ще се улесни, тъй като това мета-алгоритъм би трябвало да се построи прекалено и това не е толкова лесно!
Нещо повече, аз правя съгласни с Roger Penrose, когато той казва (в книгата си "Shadows of the mind"), че хората на разбиране и интуиция не може да бъде algorithmic (пример: computable).
[5] Кога бе първото стартиране игра Tetris, и кога ли е идеята за решаване на Tetris с A.I.?
I преподават algorithmic и компютърни програми (Turbo Pascal и Scilab) за студенти, които обучават за проверка на входа завършил инженер на училищата.
На първо място, "Компютърни играе Tetris" е една идея ми се искаше да разработи за моите студенти през следващата година.
Не бях наясно от уеб страницата си, когато започва да работи по алгоритъм.
Наистина имах щастието да бъдат запознати с вашата уеб страница, само няколко седмици, защото аз смятам, че би било възпират от вашите резултати (както бихте могли да познаят, ранните версии на моите алгоритъм не играе толкова добре!).
[6] Каква е вашата текущото състояние?
Аз съм почти 30 [преди 2003 април 27]. Имам няколко дейности: Аз съм cellist, аз съставяне на музиката и аз преподавам компютърна програма.
Имам магистърска степен по музикознание (1994) и "Artificial Intelligence and Algorithmic" диплома (1998).
Във Франция тази диплома съответства на 5-та година на следването в университета (4-та година е капитанът степен и 6 години е тезата).
Pierre's композиции:
[7] Къде живеете?
Аз съм френски и живея в Руан (Нормандия).
[8] други коментари:
В крайна сметка не съм всяка нова идея е да я подобрим.
Имам опитвали толкова безполезен (и глупав) неща, които несъмнено би могъл да бъде подобрен.
От друга страна, мисля, че там може да съществува напълно различни алгоритми, които биха могли да имат по-добри изпълнения.
Между другото, един бърз тест се състои в началото на парчета по половин кутия (10 реда х 10 колони): по половин кутия, ми алгоритъм прави средно по 280 попълват редове.
Още нещо: на алгоритъм може лесно да бъде променен по двоен слой алгоритъм ([Ще направя] тестовете скоро).
Обичам музиката филма: станете филм композитор е част от основните ми мечти (но това е само мечта!).
11. Най-добър играч на човека в света
11.1 Японски Tetris Master (2001 януари 27) видео
Tetris Капитанът (2001; Япония) видео
Arika представя японски Tetris финалите Капитанът (2001 януари 27). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Обратна връзка
12.1 Разсичам конец (2003)
През 2003 г. ми Tetris A.I. Проектът беше обсъден на Slashdot интернет форум (
http://slashdot.org).
Slashdot (http://slashdot.org) заглавие интернет форум за обсъждане на моя Tetris A.I. страници
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 ]
Комикс вдъхновени от моите Tetris A.I. страници (2003) (първи път съм вдъхновена един комично!)
Комикс вдъхновени от моите Tetris A.I. страници (2003) (втори път съм вдъхновена един комично!)
13. История на Tetris A.I. страници
През пролетта на 1989 бях зает отпадне (и при липса) второ полугодие Нов класове в University of Pennsylvania.
Една от моите roommates, Bill Matthews, имаше Mac Classic, а понякога и играят видео игри.
Хората които се допускат за Ivy League училища обикновено са склонни да се конкурира с други хора по всяко време - така че, когато Bill получи играта Tetris за неговата Mac, ние веднага започна дългосрочна борба за висока рейтинг.
Тъй като резултатите се изкачи, времето инвестиция, необходима, за да направим малък печалба се увеличи драстично.
За да направите разсея съмненията, Bill supposedly притежава висок рейтинг между нас, но аз подозирам го използвате ResEdit и сух резултат на файла!
Bill са класовете в училище Wharton на бизнеса, на alma mater на Michael Milken и Donald Trump, така че не е немислимо, че някой rigged един impossibly висок рейтинг ...
През лятото на 1990 I привлечени един 30 MHz Intel 80386 IBM PC от моя съквартирант, Alex Haidas.
I купи Mac клавиатура в Синоними пазар за $ 1.
I построена паралелен порт движение да позволи на PC за контрол на Mac клавиатура.
(I използва един чип CMOS 4040 да действа като един вид на твърда-реле да се присъединят към клавиатурата контакти в рамките на Mac клавиатура.)
Написах компютърна програма, която използва едно решение, дърво, както неговата стратегия за игра на играта Tetris. Само за няколко седмици имах един PC играят на Tetris игра вървят по Mac.
Струва ми се обаче, е необходимо да използвате клавиатурата PC да си кажем A.I. за всяка фигура, попадаща върху екрана.
Започнах работа по схема, използвайки CdS (Cadmium Sulfide) светлината детектори, които биха постно срещу Mac екран и "виж" падането парчета, но CdS сензори реагира твърде бавно да се промени в яркостта и контраста между Tetris парчета и на фона на екрана Mac Classic е твърде ниска за надеждно дискриминация.
През тези дни не са много пари, така че е твърде рисковано да се купи $ 2 Radio Shack phototransistor, че може да не направи това, което исках.
Също така, като се има предвид контраст проблем, аз бях песимистично за целия подход.
При първото ми, закупени персонални компютри през 1996 г., не можех да получавате софтуер под Windows 95 по 100 MHz CPU да правите видео обработка достатъчно бързо да се направи проста система визия работа.
Написах за обработка на изображения код в сглобяването език, но имаше толкова много режийни, преди да ми код, действително получените данни, видео, че изглеждаше невъзможно да правите каквото и да било полезно.
През 2003, технологията, особено CPU скорост, са достигнали ниво, което прави завършването на проекта почти незначителен.
I dug до моите стари лични страници и накрая да го завърши, чувството за получаване на някои закриване.
Беше много вълнуващо да видите една компютърна игра друг компютър чрез USB видео камера и релета.
Звука на релета кликване, и гледат на парчета Сервиз и спад в смешен, superhuman скорости, направил опит много, отговарящ по multisensory начин.
През 2003 г., работата ми бе признато от Slashdot (
http://slashdot.org), и получих много полезна обратна връзка.
Бях поканен да се яви на "Screen Savers" показват по телевизията TechTV цифрови телевизионни мрежи.
Отидох до Сан Франциско и се появява на концерта, както и опит беше страхотно.
По-късно през 2003, Получих съобщение от Henk Rogers, кани ме да Хавай да отговарят на него и Alexey Pajitnov да говорим за създаване на някаква стандарт за Tetris, за целите на Tetris като турнири.
Един особен интерес бе играчи, позволяващи да се използват мобилни телефони да се "конкурират една с друга," косвено, чрез A.I., че имитира играчи (от преди анализ на действията на всеки играч), като по този начин се избягва ефекта на мобилни телефони достъп до Интернет латентност, и позволява играчи да се "състезават срещу" * До най-добрите играчи на човека в света (*..., или скоро, A.I. имитиране на най-добрите играчи на човека по света).
Бях thrilled от перспективата на срещата на създателя на Tetris. За съжаление, ме прави под Загрижена, и аз отказа поканата.
През 2006 г. преобразува ми "Стандарт Tetris" софтуер от C++ да C# да направят софтуера по-достъпни и полезни за съвременните програмисти.
