Тетрис
Colin Fahey
1. Программное обеспечение
2. Введение
Эта статья описывает, как компьютер может играть классический видео игры Tetris на получение информации о борту, определяющих хорошие действия, и выполняют эти действия.
Эта статья включает в себя программное обеспечение, способных играть Тетрис в режиме реального времени.
Программное обеспечение включает в себя лучшие в режиме реального времени Тетрис алгоритм игры в общественное достояние.
Данная статья определяет правила для «стандартных Тетрис,» спецификация основывается на первоначальной 1986 до коммерческой версии Tetris для персональных компьютеров (PC).
В 2003, программное обеспечение, включенных в настоящей статье, была использована для того, чтобы играть в компьютерные Тетрис работает на отдельном компьютере.
Обыкновенных USB видеокамера была использована для того, чтобы компьютер «видеть» экран другой компьютер.
Реле борту, который контролируется через RS-232 интерфейс к компьютеру, чтобы «нажать клавиши» на клавиатуре другой компьютер.
Таким образом, первый компьютер имеет отношения к второй компьютер, который похож на типичного игрока человеческого отношения к компьютеру при игре в Tetris; игру состоянии известен только взглянуть на экран, и игрок действия могут быть начата только с помощью клавиатуры .
Конфигурация в этой демонстрации установлено, что компьютер может сыграть Тетрис лучше, чем права, в соответствии с обычной в режиме реального времени игры Tetris условиях.
3. История Тетрис
В 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 которые работали в академии осуществляется на Тетрис IBM PC работает MS-DOS операционной системы.
(Vadim Gerasimov позже сделал исследований на MIT Media Laboratory, от 1994 до 2003, получив степень доктора философии по окончании много интересных проектов:
http://vadim.www.media.mit.edu)
Введение экране 1987-1988 до коммерческого выпуска Тетрис для PC
Игру экране 1987-1988 до коммерческого выпуска Тетрис для PC
После 1987, Тетрис распространились по всему миру.
The Tetris Company, LLC, владеющей торговой маркой Тетрис.
4. Проекты вдохновили на Тетрис
4.1 0-мерное Тетрис
Еще не разработаны.
4.2 1-мерное Тетрис
Ziga Hajdukovic разработал 1-мерной Тетрис программное обеспечение, которое можно играть в Интернет-браузере.
Ziga Hajdukovic также разработал 1-мерной Тетрис программного обеспечения для мобильных телефонов, используя Java J2ME платформы.
4.3 2-мерном Тетрис
Все обычные Тетрис варианты в этой категории.
Данный раздел включает в себя интересные варианты.
4.3.1 Самый большой когда-либо игру Тетрис: Delft University of Technology (1995)
Тетрис играл на строительство; 2000 m^2 площадь поверхности; Delft University of Technology (1995)
Тетрис играл на строительство; 2000 m^2 площадь поверхности; Delft University of Technology (1995)
4.3.2 Еще одна игра Тетрис играл на здании: Brown University (2000)
Тетрис игра отображается, используя огни в окнах здания на Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
«Я считаю, что это было лишь самые невероятные один день, что я могу представить себе в моей жизни. Как и Стив Работа всегда говорили, перевозки вознаграждение.»
«Он сделал мне кажется проектов, мы сделали еще в колледже. Вещи, которые были почти undoable, что другие люди не будут думать о занимаемся.»
Steve Wozniak (2000)
4.3.3 Интернет-браузер, игры с MIT «Green построение» изображений
Vadim Gerisimov's Интернет-браузера Тетрис
Этот Интернет-браузер Тетрис вариант был создан Vadim Gerasimov.
Этот Интернет-браузер Тетрис черты «Green» здание на кампусе MIT.
Тетрис Этот вариант имеет только девять колонок вместо стандартных десять колонн.
Это Тетрис вариант представляет новые куски со случайной ориентации.
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» осциллографа тетрис на Lars Pontoppidan (2007.8)
«Scopetris» осциллографа тетрис на Lars Pontoppidan (2007.8)
Lars Pontoppidan писал код для AtMega32 микроконтроллеров, и добавил, простых аналоговых схем, создавать Тетрис версия, которую могли бы играть по осциллографа.
Некоторые регистры AtMega32 микроконтроллерным контроля 8-битных выходных сигналов, и, когда проходили через «R-2R» электрического сопротивления контура для цифрового сигнала в аналоговый (D/A) преобразования, в результате аналоговые сигналы могут контролировать (x,y) координаты луча осциллографа (когда это осциллографа набор для «X-Y режиме).»
YouTube видео:
FLV видео:
4.3.6 Obfuscated код Тетрис: 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 код Тетрис: Perl код
Ниже приводится Тетрис для 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 Тетрис
Scalable Vector Graphics (SVG) является стандартом для описания графических объектов, используя XML.
Mozilla SVG Тетрис: Tetris осуществляться с использованием Scalable Vector Graphics (SVG) описание
4.3.9 Google «widget» Тетрис
Google, Yahoo! и Microsoft, а также других компаний, способствовали миниатюрный интернет-программное обеспечение с именем «widgets», которые обычно характерны некоторые использования динамических данных, имеющихся на Интернете.
Одним из таких widget через Google является Тетрис игры.
Следующий пример является cute, но формы вращаются в раздражает способами:
Google «widget» Тетрис
Другие Google widgets:
4.3.10 MIT исследования: «Tetris is Hard, Even to Approximate» (2002)
Следующие исследования документе содержатся доказательства того, что некоторые виды Тетрис вариант «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 на Computer Science отдела Rhodes University, Южной Африки, представляет применение «обучения с подкреплением» к Тетрис.
4.3.12 Тетрис юбку (2007.11)
Тетрис юбку (2007.11)
Тетрис юбка была создана «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."
Форум комментарии относительно этой юбки:
«Человек, что юбка sucks на Тетрис»
«Ahahahaha, я думал, одно и то же.»
«Там в полное соответствие вниз на дно ... завершен линий исчезнет.» «СДЕЛАТЬ БОЛЕЕ» «.»
«Там должно быть места в задней или передней, где давно куска будет вполне соответствуют ...»
«Это действительно отвратительный, хотя юбку. Мой парень не может купить мне достаточно шоколад и цветы, чтобы убедить меня надеть что вещь.»
4.3.13 Тетрис этапе действовать (2007.4)
Тетрис этапе действовать (2007.4)
«Из тех, кто вывел вас Triforce в 2006 ... Comes следующего поколения неодушевленных объектов скит ... Тетрис.»
Локально-кэше Flash видео в формате видео (FLV) (использование VLC играть):
4.3.14 Забавного Тетрис вариации на японские телевизионные шоу
Тетрис вариации на японские телевизионные шоу
Это видео сегмент от японской телевизионных шоу включает в себя забавного вариаций Тетрис, в том числе:
штук, которые исчезают после посадки, кусок, что наполняет всю строку (завершив тем самым подряд после посадки), несколько единиц, входящих одновременно, неправильной формы куски, долго кусок, что немного слишком большим для того, чтобы он поместился в разрыв (предотвращение 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 во Дворце Rumine (Лозанна, Швейцария) на November 24th 2007.
Локально-кэше Flash видео в формате видео (FLV) (использование VLC играть):
4.3.16 2.5-мерное Тетрис
Термин «2.5-мерной» используется здесь в виду не являющихся ортогональных мнению двумерного версию Tetris, причем некоторые толщиной в третье измерение.
(Узнать ссылку «tetris3d» в «F7: GAMES».)
4.4 3-мерные Тетрис
Linux / GTK версия
Трехмерная Tetris в виде Java апплет для Интернет-браузеры:
Трехмерная Tetris для Windows операционной системы:
4.5 4-мерной Тетрис
Greg Kaiser's «HyperTetris» (1996): 4-мерной Тетрис
В [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.
Она занимает некоторое время привыкнуть к, мягко говоря.
Если некоторые чудо терпения или изменения параметров игры, один делает полный куб, она исчезнет, как завершены линий сделать в первоначальном Тетрис, хотя и не показатель находится в HyperTetris.
Benjamin Bernard (2000)
4.6 N-мерной Тетрис
Polytope Tetris (2003): N-мерной вариант игры Tetris
Polytope Tetris является n-dimensionally Тетрис.
Воодушевленная HyperTetris программа, Polytope Tetris позволяет тонн играть в любом Тетрис ЧИСЛО измерение.
Играйте в Тетрис 3D, 4D, 5D, или даже больше.
HyperTetris является гораздо catchier название, чем Polytope (Ок) Тетрис, но я не могу украсть название.
5. «Стандартные» спецификации «Тетрис»
5.1 Введение
Определение «стандарта Тетрис» является моделью идеального наиболее важных характеристик и поведения первого IBM-PC осуществления игру Тетрис (ок. 1986-1988).
Идеализированных модель основана на inferring явного намерения создателей первого IBM-PC осуществления Тетрис игры.
Например, представляется разумным сделать вывод о том, что разработчики первых IBM-PC осуществления Тетрис игры предназначены для выбора формы каждого нового падения куска «случайно,» и что использование Borland C осуществления rand() функция заключается лишь практические приближении намерение.
Определение «стандарта Тетрис» указывается, что форма каждого нового падения куска должен быть выбраны «произвольно.»
Этот идеал поведения не может быть достигнуто за счет каких-либо реализации, однако реализация может приблизительное идеального поведения.
Хотя никаких осуществление может прекрасно выполнять определение «стандарта Тетрис,» идеалы «Стандартный Тетрис» включать объективные характеристики, и реализациях могут быть сопоставлены с учетом их относительной близости к идеалам «Стандартный Тетрис.»
Этот раздел описывает набор элементов, модели поведения и правил, которые в совокупности определяют «стандарт Тетрис.»
5.2 Стандартный Тетрис борту
Совет сетку из клеток, имеющих 10 столбцов и 20 строк, в общей сложности 10 * 20 = 200 клеток.
Стандартный Тетрис борту (10 колонок, 20 строк)
Каждый элемент может быть либо незанятых (пусто) или занятые (полный).
5.3 Стандартный Тетрис штук
Есть семь (7) стандарта Тетрис штук, причем имена следующее письмо:
{ O, I, S, Z, L, J, T }
Письмо имена вдохновляет формы штук.
Стандартный Тетрис семь штук, и их «ориентации»
Точку в (0,0) совпадает с позиции (6,20) борту, когда кусок первый взгляд.
Первая колонка показывает первоначальных «ориентиров.»
В следующие слова «ориентация» используется для обозначения любого состояния куска, в рамках комплекса позволяет государствам, которые могут возникнуть в результате против ротации событие.
Смена «ориентации» с указанной «ориентации I, S» или «Z» кусок, требует сочетания ротации и перевод.
Таким образом, слово «ориентация» используется здесь означает нечто большее, чем вращение в одиночку.
Однако, «ориентация» может изменить лишь в ответ на мероприятие против ротации, а также цикл различных «направлений» для каждого куска приближается, или спички, цикл результате чистая замен.
Специальное использование слова «ориентацию» в данном контексте это почти эквивалентно смыслу слова «ротации» или «угол,» но слово «ориентация» используется вместо «ротации» пытаться привлечь внимание к тому факту, что некоторые куски требуют больше, чем производить ротацию набор разрешенных состояний в результате против «ротации» событий.
Кусочки могут лишь переключатель направления (или пройти конкретные горизонтальной или вертикальной перевод), если в результате состояние куска не будет иметь никаких оккупированных (полное) клетки вне области борту и не будет иметь никаких оккупированных клеток, которые в настоящее время каких-либо накладок, оккупированных клеток от борту.
(В этом правиле, оккупированных (полное) клеток кусок, не рассматриваются как часть «в настоящее время занимают клетки борту»
В следующие замечания, любая ссылка на результат против ротации случае производится с предположением, что такая ротация может фактически быть выполнены с учетом существующих условий и кусок борту.
«O» (вставка) фрагмент только одного ориентации, и не меняет места какого-либо из своих оккупированных (полное) клетки в ответ на любые мероприятия против ротации.
«I» (линии) кусок имеет два возможных направления, первоначально появляются в горизонтальной ориентации.
«I» кусок между заместителями два направления в ответ на сменявшие друг против ротации событий.
«S» и «Z» штук каждой из двух возможных ориентаций.
Эти кусочки каждого поочередно два направления в ответ на сменявшие друг против ротации событий.
«L», «J» и «T» штук каждого из четырех возможных направлений, и эти направления являются результаты простого вращения около центра точек формы.
Когда кусок первого появления на борту, часть имеет свои «основные оси» в горизонтальной ориентации, и кусок находится в верхней части поля.
Таким образом, нет фигуры, способной изначально располагать их ориентиры изменились. Куска должны спуститься на одну строку иметь возможность иметь свою направленность изменилась.
После того, как кусок упал на одну строку на борту, все кусок ориентаций может быть достигнуто (если кусок не слишком близко к боковые стенки или на текущий куча штук).
5.4 Стандартные схемы Tetris
Ниже приводится приблизительная блок-схема Стандарт Tetris игры.
Примерная блок-схема Стандарт Tetris игры
Примерная блок-схема Стандарт Tetris игры
5.5 Стандарт Tetris кусок создания
Следующая диаграмма показывает (4 * 2 клетки клетке) региона на борту, где все фигуры появляются, когда созданы.
Регион, где штук появляются, когда созданные в стандартной Tetris
Когда новый кусок первого появления на борту, его происхождение совпадает с точкой на этой диаграмме, и кусок будет полностью содержащиеся в затемненной области на этой диаграмме.
Когда новая игра началась, полностью свободного падения задержки, прошедшее, и на первом свободного падения итерации образца не вызвала в верхней части поля.
В ходе нормальной игры играть, когда конкретные свободного падения итерации кусок «земли,» полностью свободного падения задержки, прошедшее и на следующей свободного падения итерации образца не вызвала в верхней части поля.
Когда образца не вызвала, типа куска выбирается с помощью алгоритма следующие:
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 Стандартный Тетрис контроля
За игру, следующие материалы доступны:
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
Все материалы в действие на рост-кромка позитивный вклад (на нажатие кнопок, в отличие от кнопки-релиз).
Когда происходит нажатие кнопок, это засчитывается как просьбу.
Холдинг кнопку спуска за определенное время, возможно, приведет к «автоматической повторять» особенность клавиатуры, создавая новые кнопки и прессы, - но эта функция вне игры двигателя.
Материалов, указанных выше, соответствуют первоначальным Тетрис игры.
Повернуть запросы могут быть выполнены, если нет совпадения между желаемой ориентации и набор клеток на текущий пансион (за исключением входящих шт), и если желаемый ориентация не имеет набор клеток вне борту области.
Перевести запросы могут быть выполнены, если нет совпадения желаемого переведены конфигурации и набора клеток на текущий пансион (за исключением входящих шт), и, если требуемый перевод конфигурации не имеет набор клеток вне борту области.
Введите запросы обрабатываются с латентностью, которая зависит от кадров из игры (например: 75 Hz), и просит в силу (в случае действительной) мгновенно.
Кусок может быть отброшен без каких-либо шагов, входящих линии происходит.
Кусок может быть переведены несколько раз влево или вправо, а затем сбросили, которые испытывают все без официальной линией падения шаг.
Потому что недавно вызвал фрагмент не могут быть повернуты (потому что он застрял в отношении верхней кромки доска), игрок должен согласиться, по крайней мере один фрагмент, входящих шаг, если циклы подвергаются желаемого или требуемого.
Влияние на оценку является незначительным.
5.7 Стандартный Тетрис кусок «посадки»
Если это просто кусок падает, он падает на одной строке на каждый кусок, входящих итерации.
Там будет итерации, что она движется с места без каких-либо контактов с горизонтальной поверхности на месте, которое имеет контакт с горизонтальной поверхности. Как только это произойдет итераций, фигуры покоится в контакт.
Если итерации начинается с куска отдыха в контакт с горизонтальной поверхности, кусок «земли,» и становится частью статический стопку.
5.8 Стандартный Тетрис «линий завершена»
Завершена строка строка стопку, в которой все ячейки заняты. Когда завершен ряд исключен из стопки, и рядами выше ликвидированы подряд являются сместился вниз на одну строку ликвидировать разрыв, это засчитывается как завершил «линию.»
Когда кусок земли она становится частью стопки.
Сразу же после кусок земли, куча проверяется завершен рядами, и все строки будут завершены ликвидирован.
До четырех строк может быть завершена одновременно.
Следующая таблица дает верхний предел на линиях завершена одновременно одного куска:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Стандартный Тетрис «уровнях»
Стандартный Тетрис имеет 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 Стандартный Тетрис, входящих итерации задержки
Стандартный Тетрис имеет реальном времени задержки между последовательными линия свободного падения итераций, что является функцией от текущего уровня сложности.
Следующие взаимосвязи между уровнем индекса и падение итерации задержки основана на неоднократные секундомер измерений на всех уровнях до коммерческого 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,» жаргон для использования «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 строк.
Этим объясняется разница между точкой свободного падения и мгновенной-снижение случаев.
К экспериментируют с промежуточными случаев очень легко вывести из следующих точек формуле:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Заметим, что эта формула не имеет ничего общего с расстояния кусок падает!
Она строго функцию фактического уровня, и наказание за количество итераций фрагмент является свободно падать.
Это наказание для пользователей, нуждающихся время подумать.
Имейте также в виду, потому что кусок может первоначально не поворачивается, когда она впервые нерестится, игрок наказан по меньшей мере, один свободного падения, если итерация замен требуется поставить кусок в стопку.
Это, вероятно, никогда не затрагивает права игроков, если они каким-то: признать фрагмент, нажмите клавиши перевода «(слева» или «справа), пресс-повернуть» ключ один или несколько раз, и «пресс-падение» ключ, все меньше чем 0.5 секунд на уровне 1, или меньше, чем 0.05 секунд на уровне 10.
6. Стандартный Тетрис стратегии
6.1 Введение
Стратегия игры игры зависит от правил игры.
Стратегии зависит от того, какие параметр должен быть оптимизирован.
В стандартной Тетрис, один выживает, завершив строки, получает центров для посадки штук, и десятки наиболее возможных точек на каждый кусок, выполнив падение до одного или более свободного падения итераций transpire.
A.I. может оптимизировать точек присуждается за каждый кусок просто приняв решение о быстро и «нажмите клавиши» для выполнения переезда.
Более важным является A.I. выживания, потому что бессрочное выживание означает произвольно высоких баллов, могут быть достигнуты. Потому что Тетрис штук падения на конкретные ставки, A.I. должны принимать решения, по крайней мере, это быстро - и A.I. должны предпринять шаги, что полные ряды в том, что в среднем ставка по меньшей мере на 1 строку за 2,5 штук. (Каждый фрагмент имеет 4 клетки, и каждая строка состоит из 10 клеток.)
Конечно, можно отложить завершение строк по накапливают кусочки и строительство крупных куча, но есть только 200 ячеек по всему борту, которые в принципе можно провести только 50 штук, так что любой игрок (как, например, A.I.) должен иметь заполнении строки основных приоритетов.
В стандартной Тетрис, игра государства включает в себя текущий борту оккупации и нынешнего падения куска (тип, расположение и ориентация). Игра государство может дополнительно включить "След произведения".
6.2 Чередующихся последовательности "S" и "Z" куски
Heidi Burgiel, к.т.н., из Department of Mathematics, Statistics and Computer Science на University of Illinois at Chicago, оказалось, что чередующихся последовательности "S" и "Z" штук заставит стандарта (10-колонка, 20 строка) Тетрис игру в конце предсказуемый номер ходов.
Цитата из статьи: "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, что работает в Интернет-браузер, что возможности изменения Тетрис клона, что порождает чередующихся "S" и "Z" куски.
[В "Стандарт Тетрис", связанные с программным обеспечением Документ, который вы читаете также имеет режим которых нерестится чередующихся "S" и "Z" куски. ]
Heidi Burgiel утверждали, что игры с участием переменных "S" и "Z" штук (для стандартного Тетрис борту 10 столбцов и 20 строк) должны заканчиваться до менее чем 70000 штук упали.
Стандартный Тетрис программного обеспечения, включенные в настоящий документ позволяет лицу играть в игры с чередующимися "S" и "Z" куски, и изменение ширины борту.
Легко видеть, что ширина доски которого являются целыми кратными четыре колонки (примеры: 4 колонки, 8 колонок, 12 колонн и т. д.) можно играть вечно, когда поочередно кусочки "S" и "Z", причем не куча растет выше, чем на 4 строки. Я говорю об этом, чтобы было ясно, что ограниченный живучести, описанных в научно-исследовательских документ, упоминаемый выше, специально для случае стандартного Тетрис борту (с 10 столбцов и 20 строк).
6.3 Неразрешимой фрагмент последовательности в целом
Есть целых категорий патологических последовательностей, которые не могут быть живы.
Интересно было бы вычислить вероятность общей сложности возникают игры, заканчивающийся последовательность, потому что это будет положить сверху на выполнение каких-либо стратегии, даже с полным знанием всех будущих единиц в любой данный момент в игре.
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 вариантов), мы можем легко кодировать лучше двигаться в одном байтом.
Так что, в принципе, мы могли бы составить таблицу с 10^61 рубрик (байт), который рассказал нам лучше двигаться с учетом любого государственного совета и нынешнего образца.
Конечно, это непрактично, равно как и перечисление всех "Go" советов или "Chess" доски является нецелесообразным. Но то, что Существует один истинное решение, и есть лучший шаг для любой конфигурации. Там могут быть одинаково хорошие шаги для данной конфигурации, но мы можем произвольно выбрать один шаг в этом случае.
Многие игры играют алгоритмы имеют таблицы, подробно перечислять все возможности игры состояние в рамках ограниченных контекстах, таких как "открытие (первоначальный) движется" или "в конце игры (заключительная) движется" в шахматах. Возможно, исчерпывающий перечень Тетрис куча поверхностей (примерно (20 ^ 10) штатах) является возможным. Это интересная идея.
Исчерпывающий перечень всех штатах снизу в два ряда, умноженных на семь возможных мест, и хранить лучше двигаться в одном байт, было бы достаточно легко; требующих лишь 7 MB памяти. Возможно, оптимизировать производительность для этих семи миллионов случаев предоставит исходные данные для анализа и разработки простой модели данных, такие модели можно рассматривать как часть общего идеала Тетрис игры стратегии.
Заметим, что лучшие исполнители движется еще не защищает нас от возможных патологических игры, заканчивающийся кусок последовательностей. Это просто, что мы всегда будем осуществлять шаги, которые предлагает нам максимальный потенциал для выживания в будущем с учетом того, что все будущие куски совершенно случайных (и неизвестных на момент мы должны решить, каким образом двигаться единый текущий известный фрагмент).
6.6 В реальном времени исполнения
Один из препятствий, стоящих некоторые стратегии, алгоритмы является потребность в режиме реального времени исполнения - это значит, что должны сделать алгоритм решения в рамках конкретного времени.
Когда человека играет Тетрис, куски не остановить падение дать игроку возможность думать. Это часть проблемы Тетрис. Таким образом, A.I. системы, которая предназначена для моделирования роли человеческого игрок должен также принимать решения по ставке продиктовано Тетрис игры.
6.7 Роу и кусок итоговые
Заметим, что в долгосрочной перспективе, число сократилось штук очень близок к 2.5 раза количество заполненных строк - потому что каждая строка состоит из 10 клеток, и каждый кусок в 4 клетки, и мы должны завершить подряд, в среднем, один раз в (10/4) = 2.5 куски сняты.
Таким образом, мы можем использовать "завершен рядами" и "сбросил штук" почти взаимозаменяемы с соответствующим пропорциональности постоянной. Крупнейшая ошибка, когда плата будет полностью заполнены, за исключением одного пробела в каждой строке (((10*20)-20)/4) = 45 штук снизилась, но дефицит предсказывали (45/2.5) = 18 завершен рядами.
6.8 Текущая убор (и питание) стратегии
Если бы мы только позволит A.I. иметь знания о текущих борту и текущий фрагмент, и мы рассматривать только результат перехода нынешних кусок, в частности, пути, то это можно назвать "один кусок" анализ.
Вот грубый набросок того, как один кусок-анализ может принять решение относительно перехода в Тетрис:
Текущая куска анализ состояния игры Tetris
В основном мы стараемся все возможные шаги, а выбрать шаг, который дает лучший результат.
Трудной частью является оценка каждого результата.
Мы должны ставка гипотетической игре государственной соответствии с тем, как хорошо такое государство поддерживает наши краткосрочные и долгосрочные цели.
Наша долгосрочная цель состоит выживания. Выживание зависит от предотвращения перелива стопку борту. Мы можем снизить высоту стопки за счет формирования полной строки, которые затем исключены из кучи.
Для формирования полной строки, то мы должны соответствовать частей штук в каждом столбце этой строки. Таким образом, мы требуем, чтобы все части подряд подвергаться входящих штук, если мы хотим в конечном итоге, заполните все подряд.
Если по какой-либо причине мы замаскировать пустой части подряд на кусочки по любому выше подряд, то сейчас мы не можем заполнить эти пустые части подряд. Единственный способ (если нет скольжения) для доступа к этим "похоронили дыры" состоит в том, чтобы ликвидировать рядами выше, которые частей действующей в качестве препятствия.
Следующие факторы относятся к числу тех, которые мы можем использовать для определения рейтинга с учетом борту состоянии:
Overall pile height
Высшее стопке, наша ситуация хуже, как представляется, потому что мы ближе к течению борту.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
Шероховатой стопке, более вероятно, что это будет сложно заполнить все встроенные сложных контуров, как они стали подвергаться поверхность.
Number of buried empty cells
Больше дыр мы похоронили, наша ситуация хуже, есть, потому что мы должны раскрыть похоронен дыры, прежде чем мы сможем завершить соответствующие строки.
Можно представить себе и другие факторы, как уровень гипотетического совета от того, насколько хорошо ее кучи может вместить всех возможных будущих произведений, и, насколько хорошо выглядит ситуация для всех этих возможных штук.
Следующий вопрос заключается в том, чтобы определить относительную важность этих факторов.
Один общий подход заключается в следующем. Назначить набор "веса" (относительное значение) на эти факторы, а потом имитировать многочисленные игры и записывать результаты этих игр (окончательный балл, и т.д.). Затем, назначить нового набора веса и имитации новых игр. На основе или нет новый набор игр были лучшие результаты, чем предыдущий набор игр, мы знаем, если новый набор весов была лучше, чем предыдущий набор веса.
В моих собственных экспериментов, я попытался систематического поиска и случайной ищут добрых вес комбинаций, но я не заметил каких-либо крупномасштабных тенденций, которые я мог бы стремиться. Тем не менее, я видел много удивительно гладкой ударах. Я думал, он был интересен, что в среднем производительность может стать гладкой кривой, когда параметр постепенно регулироваться по другим параметрам, состоявшейся в определенную ценность комбинации.
Лучший в режиме реального времени, одного куска Тетрис алгоритм в мире, созданная Pierre Dellacherie (Франция) в 2003, во многом его успех его набор измерений (или показатели). Поиск весов, когда необходимо оптимизировать стратегию, но это также важно, чтобы начать с видами измерений показывают, что соответствующие характеристики государства.
Pierre Dellacherie's изобретение новых способов для характеристики каждого борту делает его алгоритм действительно отлично; борту характеристики захвата важных стратегических аспектов государственного совета.
Можно было бы развивать совершенно иной набор характеристик аспекты, которые работали одинаково хорошо, и я уверен, что это возможно, охватывающих соответствующие борту пространстве состояний по-разному, что может быть использовано для задания стратегии функции. Ключ заключается в том, чтобы найти характеристики этого проекта пространстве состояний вплоть до малого числа измерений, которые могут быть использованы для разработки простых рейтинг функцию (например: линейные комбинации весовых характеристик, используемых Pierre's алгоритм).
Произведение-один алгоритм используется "bot" в "xtris" программное обеспечение (1996), написанные Roger Espel Llima использует весов определяется крупномасштабного исследования возможных комбинаций по весу "генетические алгоритмы". Имитация отжига является еще одним возможным методом изучения многомерном пространстве весовых комбинаций.
Кажется, что, основываясь на различные замечания, многомерной функция Тетрис средняя производительность функцией весов, например: F(w1,w2,w3,...), является "грубым" (множество локальных минимумов и максимумов), что означает, что простые многомерные "лазания на холме" может не сработать.
6.9 Стратегия, когда текущий фрагмент, следующий фрагмент, и питание, как известно
Если алгоритм стратегии уделяется текущий фрагмент, следующий фрагмент, и питание, то он может принимать решения о том, что воспользоваться сочетанием штук.
Знание следующий кусок может повысить успех игры Tetris алгоритма на несколько порядков. Можно легко понять, насколько известно, следующий кусок делает большие различия в стратегии.
Можно делать "сумасшедшие" движется, как, например, охватывающие огромные дыры, и т.д., потому что они уже знают, что следующий кусок может быть использован для "исправить" ситуацию. Если у вас нет знаний о следующем кусок, вы постоянно пытаетесь играть трудности, пытаясь держать свой выбор открытым в случае следующий фрагмент не является идеальным.
Следующий рисунок показывает, насколько все возможные ходы текущего куска считаются, и за каждый такой шаг мы рассматриваем все возможные шаги с участием следующего куска.
Стратегии, связанных с текущей и следующей кусок куска
Стандартный Тетрис программа использует эту стратегию, когда "Литературная След" возможен только с пользователем и отображается на экране, и когда два куска A.I. включен (как, например, одна написана мною, Colin Fahey). Если "След Произведение" не видимые на экране, мои два куска падает обратно на один-кусок A.I..
Мой один кусок A.I. является страшной по сравнению с другими AIs в стандартной Тетрис программного обеспечения, так что это показывает вам пользу более подробной информации (например, следующий фрагмент) может быть A.I. системы, это достаточно, чтобы повысить эффективность моей посредственных два куска A.I. на несколько порядков - легко превысив исполнении лучших один кусок A.I. в мире.
(Однако, преобразование лучше один кусок A.I. в мире рассмотреть две штуки будет легко улучшить ее на несколько порядков, тоже! Зная следующий кусок огромен!)
Мой первый тест игры с моим два куска A.I. длилась примерно 182 часов (7,6 суток) на 800 MHz PC, завершив 7216290 строк. Я не проверял алгоритм по быстрее компьютера.
Когда вы сохраните состояние игры Tetris (Shift-W) в текстовый файл, можно скопировать и вставить список номеров, из раздела "heightHistogram", для электронных таблиц Excel.
Каждый бин в Гистограмма показывает количество завершенных движется, что закончился частности куча высоте (после завершения строки будут ликвидированы). Как вы можете себе представить, что делает шаг, который полностью устраняет кучу редко, так что общее число ходов, что концы с высоты стопки нуля является сравнительно низким.
Между тем, можно ожидать, что высота стопки в целом колеблется вокруг некоторых среднем, так лотков соответствии с данными строк будет доминировать гистограммы. Наконец, лотков для топ-большинство строк (там, где мы находимся в опасности перелива совета) имеют очень низкие итоговые показатели.
На протяжении многих часов, играя A.I. одной игры с использованием стратегии, знание "След произведения", я взял случайных выборок из игры государства, копирование стопку высотой гистограмм в таблицу, как показано ниже:
Стопка высоты гистограммы зарегистрированных в различных точках типичные игры (с текущего и следующего куска стратегия)
Вы можете масштабе каждой гистограммы в общей сложности штук (общее число завершенных движется), чтобы получить следующие данные:
Масштабируется гистограммы, и теория
Замечательную вещь заключается в том, что масштабы этих гистограмм с нетерпением идентичными, несмотря на разных порядков от количества штук (завершено движется), участвующего.
Просто, посмотрев на цифры я высказал гипотезу о том, что хвост кривой экспоненциального распада. Путем проб и ошибок я пришел с грубая теория, что хвост был описан:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Ниже диаграмме показано масштабируется гистограммы в течение всего диапазона строк.
График масштабируется гистограмм
Заметим, что кривая 50000 штук, и кривая 2000000 штук, и кривой хвост теории практически неразличимы на этой шкале.
Ниже приводится пристальный взгляд на руководителя кривой.
Нижняя часть высоты гистограммы
Ниже приводится в значительной степени-величались ввиду крайней конце хвоста измеряется и теоретические гистограммы кривых.
Величались ввиду крайней хвост конце масштабируется гистограмм
Как вы могли ожидать, очень редко куча достичь этих высот в течение долгого времени эксперименты, - но даже при наших ограниченных доказательств в этой крайней регионе, теоретически все еще кажется приемлемым.
В полную схему теории, как перекрываются хвост распределения "точно", в то время как в величались схему хвост хвост, мы видим, явно ошибка. Тем не менее, я утверждать, что это вызвано тем, недостаточность данных в этих экстремальных высоты стопки. Если я увеличилось игровое поле, скажем, высота 25 строк вместо 20 строк, так что игр не прекращается внезапно, я думаю, теоретически я изложил выше, вполне совпадают с тенденцией.
Мое мнение заключается в том, что этой гистограмме является прямым результатом сочетании Тетрис A.I. и правил Тетрис. Так что, это же распределение будет отмечаться в любой случайной долгосрочную игру Тетрис, используя свою особую A.I. стратегию игры с "След Произведение" знания.
Кроме того, я думаю, этот тип гистограммы можно использовать для сравнения 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 штук (и, возможно, гораздо меньше штук), может дать вам очень хорошую оценку долгосрочных высоты гистограммы, а следовательно, хорошую оценку порядка строк до завершения игры заканчивается. Такой подход является чрезвычайно полезной для оценки быстро тонкие изменения в A.I., что это уже делается очень хорошо.
6.10 Совет оценки показателей подражать спекулятивный-смотреть вперед
Если алгоритм, как, например, один я изложил в этом проекте, просто старается все куска ориентаций и переводы для снижается, и цены в результате борту каждой конфигурации в соответствии с какой-то степени заслуг, алгоритм в основном подражая "-смотреть вперед".
Когда кто-то использует такие показатели, как "высота стопки", "похоронили дыр", "шероховатость поверхности" или "хорошо глубин", одна действительно с использованием упрощенной форме "смотреть в будущее". Эти общие характеристики борту дают некоторое представление о долгосрочной жизнеспособности борту.
Идеальный подход, учитывая бесконечное количество вычислительной мощности, будут оценивать борту конфигурации с учетом всех возможных кусок последовательностей, которые могут следовать.
Хотя вы должны рассмотреть все 7 штук как в равной степени вероятно, на каждом уровне-смотреть в будущее, нужно оптимизировать фактический перевод (до 10) и направлениях (до 4) за каждую единицу в каждой возможной последовательности! Вот до (7*10*4) = 280 ветвей на каждом уровне борту оценку! Итак, вот до ((280)^(LookAheadLevels)) борту конфигураций, которые необходимо учитывать.
Потому что мы должны прекратить анализ после конечного числа уровней, мы должны иметь некоторые-смотреть вперед-метод оценки состояния борту - способ придания значения узлами лист нашей поисковой дерева. Так, для этих листьев узлы, мы опять использовать формулу, которая воплощает в себе общую предсказатели будущего жизнеспособности борт!
Такого рода спекуляции может быть судим с Один-два произведения и произведения-алгоритмы вместо упрощенного борту оценка показателей. Допустим, что все последующие куски одинаково вероятных и подытожит способностей борту для размещения единиц всех видов в наилучших возможных способов. Это могут быть осуществлены с одно-, двух-, или любое количество спекулятивных двигаться глубинах - все куски имеют одинаковую вероятность (p=1/7).
Терминал узлах этого дерева, возможно, все еще нуждаются в весовых показателей для оценки, но и спекулятивный слоев точнее захвата суть того, что мы хотим сделать: определить, насколько хорошо учитывая совет может принять все возможные штук, в том числе позитивных факторов, таких, как завершение строки и негативные факторы, такие как увеличение общей высоты стопки и т.д.
7. Тетрис 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 Видео захват аппаратных
Я использовал общий USB видеокамеру, как видео устройство для захвата моей A.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 занимает лишь десяток строк кода для использования, а также осуществляется приемлемо в моем 800 MHz машина, я не смущает изучает альтернативные APIs. Но DirectShow является более современный API для Windows видео захвата, и, возможно, дает гораздо больше кадров за одно и то же оборудование.
Посмотрите на "CPF.StandardTetris.STVideoCapture" исходного кода в файлы стандартных программных Тетрис видеть, насколько легко получить видео захвата в свои собственные проекты.
7.7 Компьютерный интерфейс для реле (через RS232)
Чтобы иметь один компьютер ", нажмите клавиши" на клавиатуре другой компьютер, я использовал "реле борту", контролируемой текст команды из серийного коммуникационного порта (например: "COM1") через RS-232 кабеля. Я использовал каждый реле подключить два провода от конкретных клавиатуре ключ для имитации нажатия клавиши.
Это требует открытия клавиатуры и подсоединений. Есть много проще методы для имитации основных насущных на компьютером, но я хотел бы сделать то, что казалось как можно ближе к лицу действительно ввода с клавиатуры.
Один очень универсален и хорошо сделал реле плата 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. Стандартный Тетрис программного обеспечения
8.1 Загрузить программное обеспечение
Перейти в начале этой статьи, найти ссылку, чтобы загрузить исходный код (C# и C++ версии) и построил программного обеспечения (*.exe).
8.2 Сводные характеристики
Программное обеспечение возможности:
Инструкция экранов и кредиты
Монохромный режим
Тень режиме
Подсказка режиме
Нежелательная строк
Оценить контроль
Следующий фрагмент
Совет размер
S/Z штук
Калибровочный режим
Видео захват и признания
Отладка консоли
Сохранить игру
Загрузите игру
8.3 Начиная внешний вид
Внешний вид программного обеспечения при запуске:
Внешний вид, когда программное обеспечение запускается
8.4 Монохромный режим
По умолчанию борту появляется в цвет:
По умолчанию борту появляется в цвете.
Цветовой режим может быть изменен на монохромные (Shift + K):
Цветовой режим может быть изменен на монохромные.
8.5 Тень режиме
Тень режиме показано, где будет кусок земли. Это очень полезно для очень больших щитов, потому, что трудно судить, где будет кусок земли.
Тень режиме показано, где будет кусок земли.
8.6 Подсказка режиме
Подсказка режиме покажет, где в настоящее время выбраны МА будет двигаться с учетом текущей ситуации. (Shift + H)
Подсказка режиме показывает, где в настоящее время выбраны МА будет двигаться.
8.7 Нежелательная строк
Включить "мусор" строк в нижней части стопки, одну за другой, вручную. (Shift + J)
Включить "мусор" строк в нижней части стопки.
8.8 Оценить контроль
'+' (плюс) и '-' (минус) ключи контроля скорости игры.
По умолчанию, игра запускается на стандартной скорости, в соответствии с правилами стандарта Тетрис (скорость по уровню).
Вот таблица значений скорости предвзятости:
-3,-4,...: медлительность, пропорциональной предвзятости
-2: медленнее, чем уровень 1
-1: нормальный, но ограниченные к уровню 6 (0,2 сек) скорости;
0: нормальный; Стандартный Тетрис контроля скорости;
+1: слегка быстрее, чем уровень 9 (0.05 sec задержки);
+2: ограниченная делает ставки (пример: 75 Hz);
+3,+4,...: несколько итераций за оказанные рамы;
Мне нравится запускать A.I. на установление "+2" (хит '+' ключ два раза, если отклонения начинается с нуля).
Скорость отклонения изменяет скорость игры.
8.9 Показать Следующий фрагмент
Хит "N", чтобы переключиться "След Произведение" дисплей. A.I. будет использовать "След Произведение" информацию только в том случае, если "Литературная Далее" появляется на экране.
Вы можете быть уверены в том, что ИИ не используете "След Произведение" информацию, когда вы не видите "След произведения" на экране.
Показать Следующий фрагмент
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, тривиально показано разрешать бесконечное выживание.
AIs выжить на неопределенный срок в этих случаях, даже если они не были специально настроенное для обработки данного патологической ситуации.
S/Z штук только
8.12 Видео режим калибровки
Хит "C", чтобы ввести "Калибровка Mode". Когда в режиме калибровки, вы можете нажать клавишу количество клавиш: {1,2,3,4,5,6,7} выбрать фрагмент {O,I,S,Z,L,J,T} в верхней части играя борту.
Это полезно как для передачи изображения видео захвата на второй Стандарт Tetris программного обеспечения.
Если вы нажмете 0 (ноль) ключом, она будет делать борту пустым.
Вы можете претендовать на нерест штук, выбрав кусок (1..7), а затем выбрав (0) пустым, в то время как второй компьютер делать захват видео-часы для штук.
Вы можете запустить A.I. на второй компьютер и посмотреть, каким образом он связан с вашим вручную вступил патологических Тетрис сценариев!
Калибровочный режим единственный раз, вы можете манипулировать видео захвата обработки изображения шаблона (4 * 2 сетки). Вы можете использовать мышь, чтобы нарисовать прямоугольник, но потом вы можете использовать клавиши курсора ( "вверх", "вниз", "влево", "Право") иметь штраф контроль границ - с использованием ключевых Shift выбрать противоположной границы прямоугольника (пример: "Shift налево" комбо показатель отличается от "левой").
Видео режим калибровки
8.13 Видео захват и признания
Нажатие 'V "toggles видео захвата режиме. Если правильно калибровать (см. "видео калибровки" в предыдущем разделе), кусочки удаленного экран будет захвачен видеокамеру и классифицируются - и куски будут вызвал в местных игры для A.I. рассмотреть и отреагировать .
A.I. выход должен быть затем передается (через интерфейс RS-232 в демонстрации, описанных в этой статье) для дистанционного игры ввода (например, клавиатура) для A.I. успешно играть дистанционного игры.
Если в любое время в этом замкнутом цикле с тревогой (пример: видео захвата неисправности или выходной сигнал неисправности), а затем A.I. будет развиваться ложное впечатление о состоянии удаленных игру и A.I. будет делать нецелесообразно решений, которые быстро теряют игры .
(Примечание: Эту проблему можно преодолеть с скромную сумму усилий: В A.I. системы нужно только изучить весь экран удаленного Тетрис для постоянного "проверять реальность" в целом борту, а также A.I. система должна быть подготовлена для некоторых вывод команды неудачу в определенным образом.)
Видео захват и признания
9. Оригинал Тетрис МА эксперимент (2003)
Следующие первую рабочую версию Tetris A.I. системы в 2003 году.
Видеокамера, стоящих перед компьютером # 1 работает любой простой игры Tetris
Компьютерные # 2 работает Стандарт Тетрис программного обеспечения в режиме A.I.
Слева: рисунок сетки для калибровки видеоизображения признания;
Справа: Tetris кусок признание случаев.
Рамка с видео Тетрис A.I. эксперимента в 2003 году
10. Лучшие один кусок Тетрис алгоритм игры в мире
10.1 Pierre Dellacherie (2003, Франция)
Pierre Dellacherie (2003, Франция), разработчик из лучших один кусок Тетрис алгоритм игры в мире
Лучше один кусок в реальном масштабе времени, Tetris алгоритм насколько мне известно, была создана Pierre Dellacherie Франции.
Его удивительный алгоритм заполняет порой более чем 2 млн. строк!
Средняя производительность на порядок 650000 строк.
Алгоритм занимает очень мало памяти и работает на высокой скорости (около 160 строк в секунду в моем 800 MHz компьютера).
Исполнение Pierre Dellacherie's алгоритм:
Мои нынешние модели для выполнения Тетрис АИС состоит в том, что для выполнения того или иного куска существует вероятность того, что постоянная игра прекращается, 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.
"Алгоритм реализован в Turbo Pascal и завершит 7000 строк / мин. С Athlon 1600+".
Я преобразованы Pierre's алгоритм C++ в 2003,6, после нескольких электронной почте обмены с Pierre. Мы убедились в том, что в A.I. C++ версия сделал же решения Pascal версия.
Я наблюдаю аналогичные показатели для его первоначального доклада; среднем около 650000 строк завершен, и некоторые игры завершения 2 миллиона строк.
Incredible!
10.2 Разговор с Pierre Dellacherie
[1] Когда вы впервые создать этот код?
Я работал над алгоритмом с конца января 2003 года до сих пор.
[2] Как долго вы работали на него?
Я работала на него почти каждую неделю ... но не каждый день долго, потому что я есть другие виды деятельности: к сожалению, я вынужден зарабатывать деньги как никто другой!
[3] Что вдохновили дизайн-код?
Я играл Тетрис 10 или 15 лет назад, но я не раз играл за долгое время. Я хотел бы сказать, что я "среднего" игрока которые знают правила и некоторые хитрости.
Однако, когда я начал работать над алгоритмом я не играл столько потому, что я обнаружил, было более эффективным, а смотреть компьютерные игры и анализировать его слабые стороны.
[4] ли Вы использовать какие-либо автоматизации «подготовки» кода для выполнения лучше? Было ли у вас какие-либо отзывы по улучшению алгоритма?
Или же вы просто наблюдать результаты и решить, вносить изменения?
Я из «старой школы:» Я просто наблюдал за результатами и решили внести изменения.
"Автоматическое обучения" является тип мета-алгоритм с тем я не уверены в том, что делают это таким образом будет легче получить, поскольку это мета-алгоритм должен быть построен также и о том, что это не так просто!
Более того, я согласен с Roger Penrose когда он говорит (в своей книге "Shadows of the mind"), что понимание человеческой интуиции и не может быть алгоритмическим (пример: вычислимого).
[5] Когда Вы впервые начать игру Тетрис, и когда у вас есть идеи по решению Тетрис с A.I.?
Я преподаю алгоритмические и компьютерное программирование (Turbo Pascal и Scilab) для студентов, которые поезд на вступительных экзаменах на инженера выпускник школы.
Во-первых, "Компьютерные играет Tetris" была идея Я хотел бы разработать для моих студентов в следующем году.
Я ничего не известно о вашей веб-странице, когда я начал работать по алгоритму.
Действительно я посчастливилось быть в курсе вашей веб-странице только несколько недель назад, потому что мне кажется, я была бы разочарована своими результатами (как вы уже могли догадаться, ранних версий моего алгоритма не играл так хорошо!).
[6] Каково ваше нынешнее состояние?
Мне почти 30 [до 2003 27 апреля]. Я несколько мероприятий: "Я виолончелист, я сочинять музыку, и я преподаю компьютерное программирование.
Я имею степень магистра в музыковедение (1994) и "Artificial Intelligence and Algorithmic" диплом (1998).
Во Франции этот диплом соответствует 5 год учебы в университете (4 года магистров и 6 год является тезис).
Pierre's композиций:
[7] Где вы живете?
Я французском и я живу в Руане (Нормандия).
[8] Другие комментарии:
В конце концов я не какие-либо новые идеи по его улучшению.
Я попытался столько бесполезных (и глупо) то, что я сомневаюсь, он мог бы быть улучшен.
С другой стороны, я думаю, там могут существовать абсолютно различные алгоритмы, которые могли бы иметь более исполнений.
Кстати, быстрее испытания состоит в запуске штук в коробке половина (10 строк х 10 столбцов): в половине ящика, мой алгоритм составляет в среднем 280 строк завершен.
И еще один момент: алгоритм может быть легко изменена в двойной слой алгоритм ([я сделаю] испытания в скором времени).
Люблю кино музыка: стать композитором фильма является частью моей главной мечты (но это просто мечта!).
11. Лучший игрок человека в мире
11.1 Японский Тетрис Master (2001 27 января) видео
Тетрис мастер (2001; Япония) видео
Arika представлена японская Тетрис Finals мастер (2001 27 января). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Обратная связь
12.1 Slashdot нить (2003)
В 2003 году моя A.I. проекту Tetris был обсужден на Slashdot Интернет-форум (
http://slashdot.org).
Slashdot (http://slashdot.org) Интернет-форум заголовок для обсуждения моего A.I. проекту Tetris
Benefactor of mankind--thank you! (Score:4, Funny)
by EnlightenmentFan (617608) on Tuesday January 28, @02:29PM
(#5176294)
(http://betsydevine.weblogger.com/ | Last Journal: Tuesday
January 21, @01:55PM)
Now I can set up computer #1 to play an infinite, obsessive
game of Tetris on computer #2, leaving me free at last to sit
down at computer #3 and get some work done. The $200 for
webcam and other hardware is cheap for an invention like this,
with the revolutionary potential of the wheel, or fire, or
even pizza delivery.
Thank you! Thank you! Thank you!
[ Reply to This ]
The New 4th law... (Score:5, Funny)
by gokubi (413425) on Tuesday January 28, @02:09PM (#5176135)
(http://www.gokubi.com/kinggeorge)
1. A robot may not injure a human being, or, through inaction,
allow a human being to come to harm.
2. A robot must obey the orders given it by human beings
except where such orders would conflict with the First Law.
3. A robot must protect its own existence as long as such
protection does not conflict with the First or Second Law.
4. A robot must never place the long skinny ones horizontally,
unless it leads to a long skinny vertical hole so 4 rows can
be cleared at once the next time a long skinny one comes
around.
[ Reply to This ]
Re:The New 4th law... (Score:5, Funny)
by GuyMannDude (574364) on Tuesday January 28,
@02:14PM (#5176179)
I thought Directive 4 was that any attempt to arrest a
senior officer of OCP Corporation would result in
immediate shutdown!
GMD
[ Reply to This | Parent ]
Comic вдохновили моим A.I. проекту Tetris (2003) (первый раз я когда-либо вдохновили комиксов!)
Comic вдохновили моим A.I. проекту Tetris (2003) (второй раз я когда-либо вдохновили комиксов!)
13. История A.I. проекту Tetris
В весной 1989 года я был занят пропускается (и отсутствие) второго семестра freshman классов в University of Pennsylvania.
Один из моих соседями по комнате, Bill Matthews года Mac Classic, а иногда и играли видеоигры.
Люди которые получают допущены к Ivy League школах, как правило, склонны к конкуренции с другими людьми во все времена - это, когда Bill получили игру Тетрис за его Mac, мы сразу же начали долгосрочную борьбу за высокий балл.
Как и десятки забрались, время инвестиций, необходимых чтобы добиться малых резко возросло.
Чтобы долго короткий рассказ, Bill якобы имеет высокий балл между нами, но я подозреваю его использования ResEdit и хакерство, забитые файл!
Bill были занятия в школе Wharton бизнеса, alma mater из Michael Milken и Donald Trump, поэтому он не себе, чтобы кто-то подтасованы нереально высокий балл ...
В летом 1990 года я 30 MHz Intel 80386 IBM PC заимствованные из моих соседей, Alex Haidas.
Я купил Mac клавиатуры на блошиный рынок за $ 1.
Я построен параллельный порт схема разрешить PC контролировать Mac клавиатуры.
(Я использовал CMOS 4040 чип в качестве вида твердого состояния реле, чтобы присоединиться к клавиатуре контакты внутри Mac клавиатуры.)
Я написал компьютерную программу, которые используют дерева решений, как свою стратегию игры Tetris. Всего лишь несколько недель я имел PC игры Tetris игры, работающие на Mac.
Однако я был обязан использовать PC клавиатуре, чтобы рассказать о каждом A.I. падения куска на экране.
Я начал работать по схеме, используя CdS (Cadmium Sulfide) свете детекторов, которые будут опираться в отношении Mac экрана и "увидеть" падающие куски, но CdS датчики слишком медленно реагируют на изменения в яркости и контраста между Тетрис кусочки и фона на экране Mac Classic является слишком низким для надежного дискриминации.
В те дни у меня не было много денег, это было слишком рискованно покупать $ 2 Radio Shack phototransistor, которые не могут делать то, что я хотел.
Кроме того, учитывая отличие от проблемы, то я был пессимистично по поводу всего подхода.
Когда я купил мой первый персональный компьютер в 1996 году, я не мог получить программное обеспечение в соответствии с Windows 95 по 100 MHz CPU делать обработки видео достаточно быстро сделать простой видение системы работы.
Я написал для обработки изображений код на ассемблере языка, но там было так много накладных до моего кода, фактически полученных видеоданных, что, казалось, невозможно сделать что-либо полезным.
В 2003 году технологии, в частности CPU скорость, достигла уровня, который сделал отделочные проекта почти тривиальным.
Я копался в моей личной старого проекта, и, наконец, закончил его, или ином смысле закрытия.
Было очень интересно увидеть один компьютер играет другой компьютер через USB видеокамеру и реле.
Звук нажатия реле, и смотреть куски спина и падение на смешно, superhuman скорости, достигнутый опыт очень удовлетворения в multisensory способом.
В 2003 году моя работа была признана Slashdot (
http://slashdot.org), и я получил очень много отзывов.
Я был приглашен для показа на "Screen Savers" теле-шоу на TechTV цифровой телевизионной сети.
Я отправился в Сан-Франциско и появился на шоу, и опыт был велик.
Позже в 2003, я получил сообщение от Henk Rogers, пригласили меня на Гавайи встретиться с ним и Alexey Pajitnov говорить о создании своего рода стандарт на Тетрис, для целей проведения турниров Тетрис.
Один Особый интерес игроков позволяет использовать мобильные телефоны «конкурировать друг с другом,» опосредованно, через A.I., что имитирует игроков (по предварительному анализу каждого игрока, действия), что позволяет избежать воздействия мобильного телефона латентность доступа в Интернет, а также позволит игрокам «конкурировать с» * Самые лучшие игроки человека в мире (*... или, наоборот, подражая A.I. самого лучшего человека игроков в мире).
Я был взволнован на перспективу встречи создатель Тетрис. К сожалению, приводит меня в полет стремится, и я снизился приглашение.
В 2006 году я преобразованы моя "Стандарт Тетрис" программное обеспечение с C++ к C# сделать программное обеспечение более доступным и полезным для современных программистов.
