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있는 퍼즐 조각 만들어진 5 개의 사각형 참여 준비합니다.
Alexey 생각을하게 떨어진 그들의 생각이 작품을 준비 Pentamino 직사각형 컵, 그러나 실현하는 12 개의 서로 다른 다섯 - 스퀘어 모양의 비디오 게임은 너무 복잡합니다.
7 Alexey로 전환 "tetramino"를 사용하여 조각, 각각 4 개의 사각형 만들어진합니다.
이 1985.6, Alexey Pajitnov 프로그램에서 첫 번째 버전의 tetris Electronica 60합니다.
Dmitry Pavlovsky, Alexey Pajitnov, 그리고 tetris합니다.
이 1985-1986, Vadim Gerasimov, 컴퓨터 천재 16 - 세의 하이 - 학교에서 일한 아카데미, 구현 tetris MS-DOS 운영 체제를 실행하는 PC을 IBM합니다.
- 1987-1988 사전을 도입 화면에서 PC의 상업적인 릴리스의 tetris
게임 플레이 화면을 1987-1988 - 상업적인 릴리스의 이전을 PC tetris
1987 후, 전 세계의 확산 tetris합니다.
The Tetris Company, LLC, tetris 상표권을 소유하고있습니다.
4. 프로젝트를 영감을 tetris
4.1 0 - 차원 tetris
아직 개발합니다.
4.2 1 - 차원 tetris
1 - 차원 tetris Ziga Hajdukovic을 개발하는 소프트웨어를 인터넷 브라우저에서 재생할 수있습니다.
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
"대부분의 믿을 수 있었던 것 같아 한 - 일 단지 내 인생에서 내가 할 수있는 상상합니다. 스티브처럼 일자리가 항상 말씀 하시길, 그 여정은 보상합니다."
"그것은 우리가 위로는 대학의 프로젝트 나를 생각합니다. 과거의 일들과 거의 취소할 수가 아닌 다른 사람들이하는 생각을합니다."
Steve Wozniak (2000)
4.3.3 인터넷 브라우저의 게임을 "그린 건물" 이미지를 MIT
인터넷 브라우저를 Vadim Gerisimov's tetris
변형 만든이 인터넷 브라우저를 tetris Vadim Gerasimov합니다.
인터넷 브라우저를 tetris 기능이 "Green" 건물의 캠퍼스 MIT합니다.
9 개 열을뿐만 아니라 변형이 tetris의 표준 10 열합니다.
임의의 방향으로 새로운 작품이 tetris 선물을 변형합니다.
Vadim Gerasimov은 컴퓨터에 코드를 쓴 사람 PC 버전의 tetris에 1986합니다.
Vadim Gerasimov 한 박사 학위 MIT Media Laboratory하는 동안의 연구 1994-2003, 노동, 많은 흥미있는 프로젝트.
4.3.4 마이크로 컨트롤러 - 기반 PIC16F84 12 MHz tetris NTSC / PAL 비디오 게임
마이크로 컨트롤러 - 기반 PIC16F84 12 MHz tetris NTSC / PAL 비디오 게임
위의 이미지를 보여주는 NTSC / PAL 비디오 출력 PIC16F84 12 MHz 마이크로 컨트롤러에 의해 생산 Rickard Gunee를 실행하는 소프트웨어를 작성한 1998합니다.
비디오 신호의 디지털 출력을 제어하는 소프트웨어가 발생합니다.
4.3.5 오실로 스코프 Lars Pontoppidan (2007.8) 의해 "scopetris" tetris
오실로 스코프 Lars Pontoppidan (2007.8) 의해 "scopetris" tetris
마이크로 Lars Pontoppidan 쓴 코드를 AtMega32, 그리고 추가 단순한 아날로그 회로, tetris 버전을 만들 오실로 스코프에서 재생할 수있습니다.
레지스터의 특정 AtMega32 마이크로 컨트롤 8 - 비트 출력 신호, 그리고 때, 전기 저항을 통과 "R-2R"을 통해 아날로그 회로를 디지털 -이 - (D/A) 변환, 그 결과 아날로그 신호를 오실로 스코프의 좌표를 (x,y)가 제어할 수있는 빔 (오실로 스코프는 때 "X-Y 모드로" 설정).
YouTube 비디오 :
FLV 비디오 :
4.3.6 판단이 흐려지게 코드를 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 판단이 흐려지게 코드를 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 tetris Mozilla SVG
를 사용하여 그래픽 개체를 설명하기위한 Scalable Vector Graphics (SVG)가 표준 XML합니다.
Mozilla SVG tetris : tetris Scalable Vector Graphics (SVG) 설명을 사용하여 구현
4.3.9 tetris Google "widget"
Google, Yahoo!, 그리고 Microsoft, 기타 회사의 이름을 추진 "widgets" 소형 인터넷 - 기반 소프트웨어를 사용하는 일부 특징으로하는 동적 데이터는 대개 인터넷에서 사용할 수있습니다.
그런 Google가 tetris 경기를 통해 액세스할 수있습니다 widget합니다.
다음 예제는 귀엽지만, 성가신 방법으로 회전의 형태 :
tetris Google "widget"
다른 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 치마를 (2007.11) tetris
치마를 (2007.11) tetris
치마를 만든 the 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 크리에이 티브기구).
- Flash 비디오 영상을 로컬 캐시 (FLV) 형식 (VLC을 재생을 사용) :
4.3.16 2.5 - 차원 tetris
여기에 "2.5 - 차원이라는" 용어가 사용됩니다 - 직교이 문서가 적용되는 의미가 아닌, 2 - 차원 버전의 tetris의 일부 두께의 3 차원을합니다.
("tetris3d"의 링크를 찾을 "F7: GAMES"합니다.)
4.4 3 - 차원 tetris
Linux / GTK 버전
3 - 차원 tetris의 형태로 애플릿을 Java 인터넷 브라우저 :
3 - 차원 tetris의 Windows 운영 체제 :
4.5 4 - 차원 tetris
Greg Kaiser's "hypertetris" (1996) : 4 - 차원 tetris
이 [1996], [...], 4 - 차원 변형들을 하나로 결집하고 Greg Kaiser 고전 게임을합니다.
IrisGL (a.k.a. igl)를 사용하여 만든 그는 작업, 만약 하드를 재생, 게임 묘사를 사용하여 서로 다른 4 개의 서브 - 스크린을 3 개 - 치수 측면의 전체 게임 - 공간을합니다.
[왜냐면] 쉬운 없다 [이해할 수] 4 - 패 개체를 그리는 방법을, 2 - 패 스크린, 4 개의 서브 -보기는 실용적인 방법을 조작하고 회전 및 번역 조각을 시각화를 통해 4 개의 치수 ( 게임에 전화 x,y,z,w).
같이 라인의 블록을 완료보다는 원래의 목표는이 사건은 완전한 정육면체를 x,y,z을 채우는 subview (일반적으로 4 - 4 - 4).
"w" 포함하는 다른 차원은 배열의 subviews에서 4 - 4 - 10 블록에 대한 기본 협정을 체결 "w"가 긴, "vertical" 3 차원의 경우, 서로 다른 기지와 (x,y), (x,z), (y,z)합니다.
사도 행전에 "-w" 중력 방향으로, 그래서 작품에서 "떨어질" subviews를 포함하는 3 개의 긴 "w", 그리고 플레이어 컨트롤에 의해 움직이 지마의 마지막 (x,y,z)하지 않는 한 subview합니다.
그것에 익숙해질 데는 시간이 많이 소요를 최소한에 따르면합니다.
기적의 경우 일부 게임의 인내심을하거나 매개 변수를 변경하여, 하나는 완료하는 큐브, 그것은 사라질 것이다 라인을 완성하지의 기존 tetris지만 점수는 보관 HyperTetris없습니다.
Benjamin Bernard (2000)
4.6 N - 차원 tetris
Polytope Tetris (2003) : an N - 차원 tetris 게임 기타
Polytope Tetris는 n - 치수 tetris합니다.
HyperTetris에 의해 영감을받은 프로그램, Polytope Tetris tetris 어떠한 플레이하실 수있습니다 톤 개수 치수합니다.
tetris에서 플레이 3D, 4D, 5D, 또는 좀 더합니다.
catchier 이름을 HyperTetris은 훨씬 더 Polytope (def) tetris했지만 그렇게 할 수 없어 이름을 도용합니다.
5. "표준 tetris" 사양
5.1 소개
"tetris는" 이상적인 모델에 대한 정의를 "기준의" 가장 중요한 특성과 동작의 구현의 첫번째 IBM-PC tetris 게임 (대진 1986-1988).
이상적인 모델을 기반으로 the inferring the 명백한 의도를 IBM-PC의 개발자의 첫번째 tetris 게임의 구현합니다.
예를 들어, 합리적으로 추론하는 것 IBM-PC의 개발자의 첫번째 게임의 구현하기위한 tetris 각각의 새 떨어지는 모양의 작품을 선택하여 "무작위로," 그리고 Borland C의 구현을 사용하는 기능은 단순히 실용적인 접근 rand() 의도합니다.
"tetris" 지정하는 "표준에" 대한 정의를 각각의 새 하락의 모양을 선택한이 작품은 "무작위로합니다."
이 이상 문제가되지 않습니다 다습에 의한 모든 구현, 그러나 대략적인 가장 이상적인 동작 구현을 수있습니다.
완벽하게 구현하는 지역에 대한 정의를 구현하는 것이지만 "표준 tetris," 객관적 특성을 이념 "표준 tetris" 참여, 그리고 그들의 상대적인 구현을 비유할 수있다 친밀감을 이념에 따라 "표준 tetris합니다."
이 섹션에 대해 설명 일련의 요소, 동작, 그리고 규칙, 어떤, 총칭를 정의 "표준 tetris합니다."
5.2 표준 tetris 보드
그리드의 세포 보드는 애를 10 열, 그리고 20 행, 기간이 총 10 * 20 = 200 세포를합니다.
표준 tetris 보드 (10 컬럼, 20 행)
각각의 세포 중 하나는 빈 (빈) 또는 점령 (전체).
5.3 표준 tetris 조각
tetris (7) 기준에 해당하는 이미 7 개 조각, 다음과 같은 편지 이름 :
{ O, I, S, Z, L, J, T }
그 편지의 이름은 작품의 형태에 의해 영감을받은합니다.
7 표준 tetris 조각과 그 "오리 엔테이션"
보드 입장과 일치한다 (0,0) 도트를 (6,20)로 조각을 때 첫 번째가 나타납니다.
첫 번째 열에는의 초기 "오리 엔테이션합니다."
다음과 같은, 그 단어 "오리 엔테이션은" 모든 상황을 설명하는 데 사용 한 조각 세트를 허용 상태로, 그 시계 회전 행사에서 발생할 수있습니다.
"오리 엔테이션에서 오리 엔테이션을" 변경하지 않는 "I, S," 또는 "Z 작품의" 회전과 번역의 조합이 필요합니다.
따라서, "오리 엔테이션이라는" 단어가 사용됩니다 혼자 여기를 회전 이상의 의미가있습니다.
그러나, 시계 반대 "방향으로" 회전을 변경할 수있습니다 이벤트에 대한 응답만을, 그리고 별개의 순환 과정에서 각각의 작품에 대한 "오리 엔테이션" 근사, 또는 성냥, 순수의 사이클에 따른 회전합니다.
"오리 엔테이션의" 특별라는 단어의 사용이 문맥이라는 단어의 의미는 거의 동일합니다 "회전하거나 각도," 그러나 "혁명이라는" 단어 대신에 "오리 엔테이션을" 사용하려고 할 사실에 대한 관심을 가지고이 필요 이상의 회전을 생산하면 몇 조각 시계 "회전" 행사를 통해 발생한 상태 세트를 허용합니다.
작품은 유일한 스위치를 오리 엔테이션 (또는받는 특정 수평 또는 수직 번역)로 조각을 경우에는 결과가없는 상태를 점령 (전체) 세포를 넘어 영역을 보드와 겹치는 어떠한 않았을 현재 차지하고있는 모든 세포를 세포를 점령 이사회합니다.
(이 규칙에 점령 (전체) 세포의 작품의 일부로 간주되지 않습니다 "세포를 점령은 현재 이사회"
다음과 같은 의견, 로테이션에 대한 언급은 시계 반대의 결과를 만들어 이벤트는 회전이 같은 추측을 수행할 수 사실을 고려할 때 기존의 조건에 조각 및 이사회합니다.
the "O" (상자) 작품에는 하나의 오리 엔테이션, 그리고 그 중 하나의 위치는 변경되지 않습니다 점령 (전체) 세포에 대한 응답으로 어떤 시계 회전 행사합니다.
the "I" (행) 작품에는 두 개의 가능한 오리 엔테이션, 초기에 나타나는 수평 오리 엔테이션합니다.
둘 사이에 대체 the "I" 작품 연속적인 시계 반대 방향으로 회전 이벤트에 대한 응답합니다.
각각의 작품 수가 두 "Z" the "S" 및 오리 엔테이션합니다.
이들 각각의 다른 작품 사이에 두 개의 연속적인 시계 반대 방향으로 회전 이벤트에 대한 응답합니다.
the "L", "J", 그리고 각각의 작품이 4 수있습니다 "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 일 (7) 작품 무작위로, 구체적인 작품은 p=(1/7) 확률이되고있다.
만일 우리가 이렇게 n=70 시간, 예를 들면, 정확하게 확률은 점점 k 조각 (0을 k 범위에서 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와 조각, 그리고 모든 위치에서 최적의 의사 결정의 순서를 찾을 수있습니다.
(충분한 기회가되는 것 같아 보드를 완전히 빈 기판 주, 우리가 동기화할 수 있도록 최적의 솔루션과 경로를 예측합니다.)
간단한 난수 생성기를 사용의 위험을 의도에서 시뮬레이션을 발견하면 문제는 최적의 솔루션을 최적의 솔루션은이 문제에 대해서만 공간의 특정 경로를 통해 간단한 난수 생성기를 선택합니다. ]
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 "라인 완성"
행의 더미를 완료 행이있는 모든 세포가 차지하고있습니다. 더미에서 제거를 완료하면 행이, 그리고 위에있는 행이 삭제 행은 행 하나를 아래로 이동 간격을 제거하기 위해,이 완료된 "라인을" 계산합니다.
한 조각의 일부가 토지를 쌓기이된다.
그 조각이 땅에 후 즉시의 더미를 검사 완료 행, 및 모든 완료된 행이 삭제합니다.
동시에 최대 4 개의 행을 완료할 수있습니다.
위 제한이 줄을 다음과 같은 테이블을 제공하여 하나의 작품을 동시에 완료 :
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 (1) ~ 10 (10), 1과 수준이 "최소 어려운합니다."
의 수준 인덱스는 최대 두 개의 값 :
actualLevel = max( initialLevel, earnedLevel );
the 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는 실제 - 시간 지연 자유 - 가을 반복하는 사이에 연속적인 라인이 기능을 현재의 난이도합니다.
다음과 같은 관계를 수준의 색인을 생성하고 지연을 기반으로 반복 반복적으로 하락은 모든 수준의 측정을 기초 시계 - 상업적인 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]
이 보드는 빈, 그리고 사용자의 입력 없다는 조각을 실제 수준 시키려 10 초 약 1 토지와 토지를 약 10 시키려 작품을 실제 수준 1 두 번째합니다.
5.11 표준 tetris "점수"
보너스 포인트만을 기준 tetris 한 조각의 행위를 방문합니다.
포인트가없습니다 수상의 행위를 한 줄로을 완료, 또는 완료 2, 3, 또는 4 개의 회선을 동시에합니다.
[참고 : 일부 변화, 여성의 행위를 완료한 tetris 보너스 포인트 라인, 상여를 확대로 급격히 늘고있다 라인을 동시에 완성합니다.
이에 따라 평가 점수를 최대화하기위한 전략을 설정하는 그러한 변화에는 기회를 "좀" tetris "Tetris," 속어를 사용하기위한 4 개의 동시 모양 "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. 표준 tetris 전략을
6.1 소개
게임을 재생하는 전략 게임의 규칙을 따라 달라집니다.
어떤 매개 변수가이의 전략에 따라 달라집니다 최적화된합니다.
표준 tetris, 하나 생존을 완료하여 행, 제 점수를 방문 조각, 그리고 각각의 점수가 올라갑니다을 실행하여 가능 한 방울 발생하기 전에 하나 이상의 자유 - 가을 반복합니다.
an 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, 7 월 1997, "How to Lose at Tetris"
Heidi Burgiel는 인터넷 브라우저를 실행하는 Java applet 조작을 감상할 수있습니다 교류를 생성하는 tetris 클론 "S"및 "Z"조각합니다.
[ "표준 tetris"소프트웨어와 관련된 문서를 읽는 당신은 어떤을 생성하는 모드도 교체 "S"및 "Z"조각합니다. ]
게임 관련 Heidi Burgiel 번갈아 주장했다 "S"및 "Z"장 (10 컬럼을 기준 tetris위원회와 20 행) 70000 미만의 작품들이 추락하기 전에 끝나야합니다.
이 문서에 포함된 tetris 소프트웨어의 표준을 사용하면 게임을하기 위해서는 사람과 교류 "S"및 "Z"조각, 그리고 보드 너비를 변경합니다.
그것은 누구의 너비가 정수를 쉽게 확인할 수의 배수가 보드 4 열 (예 : 4 열, 8 열, 12 열 등)을 영원히 재생할 수있는 대체하면 작품 사이 "S"및 "Z", 상승 지역을 쌓기 이상의 4 개 열로 구성된합니다. 나는 이것을 분명히 언급에 설명되어있는 연구가 제한된 생존에 대한 문서를 상기의 경우는 특히 표준 tetris 보드 (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); 즉, 약 (2 ^ 199) 예상보다 적습니다 3.74퍼센트합니다.
그러나, 실제 수를 안정적인 접근 보드 상태가 현저히 낮은 것으로 보인다는 사실을 최고로 인해 - 대부분의 행 수있는 몇 가지로만 입력합니다. - 대부분의 행으로 최고 채우기, 새로 생성 조각 회전 이동하거나 매우 수없습니다. 이 방법으로 수를 제한하는 방법 - 대부분의 행을 최고 채워진 수있습니다.
6.5 원칙적으로 최고의 이동에 대한 모든 보드 및 작품 구성을 찾을 수있습니다
왜냐하면 우리는 조각을 얻지는 특정 보드의 7 수있습니다 주, 게임 상태의 총 수입은 약 7 * (2 ^ 199) = 5.624... * 10^60합니다.
왜냐하면 우리는 원칙적으로 모든 가능한 미래에 대한 검색을 깊이 할 수있습니다 움직임에 대한 특정 게임의 모든 주, 우리는 하나 "최고"각 게임과 연관된 상태 이동합니다.
우리가하지 않는 우리가 추측 이외의 어떠한 정보에 액세스할 수 현재의 보드와 현재 작품, 그래서 "최고"라함은 "최고의 이동 기회를 제공하는 우리의 기나긴 - 임기 목표의 생존을 충족"합니다.
움직임은 단지 변환 (최대 10 개의 옵션)과 회전 (최대 4 개의 옵션)을, 우리가 쉽게 인코딩을 최고의 이동을 단일 바이트합니다.
그래서, 원칙적으로 우리가 형성하는 테이블을 10^61 항목 (바이트)가 최고의 이동이 말씀 주어진 모든 보드 상태 및 현재 작품합니다.
물론, 이것은 실제와 마찬가지로 열거 모든 "Go"보드 또는 "Chess"보드는 실제합니다. 그러나 중요한 점은이 진정한 솔루션을, 그리고이 특정 구성을위한 최고의 이동합니다. 동등하게 좋은 움직임이있을 수있습니다 특정 구성, 그러나 우리는이 경우 임의로 이동을 하나 선택합니다.
많은 게임 - 게임 알고리즘은 모든 게임 테이블을 철저 상태 가능성이 시간 제한을 열거 문맥과 같은 "오프닝 (초기) 이동"또는 "엔드 - 게임 (결승) 움직임"체스합니다. 아마도 철저한 열거 tetris 더미 표면 (약 (20 ^ 10) 상태)가 가능합니다. 그것은 재미있는 아이디어.
맨 아래에 열거 두 개의 완전한 상태의 모든 행, 7 수있습니다 곱한 조각, 그리고 최고의 움직임을 저장을 단일 바이트,이 매우 간단; 7 MB 전용의 메모리를 필요로합니다. 아마도 이들의 성능을 최적화하는 원시 데이터를 제공 7백만가지 경우는 두 모델을 분석하고 데이터의 개발을 단순 있으며, 그러한 모델의 일부로 간주 수 이상의 전체 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 게임 - 작품 분석을 현재 상태
실제적으로 우리는 가능한 모든 움직임을 시도 결과로 이동해서 최상의 결과를 선택하십시오.
각각의 결과의 어려운 부분은 평가합니다.
가상의 게임 상황에 따라 등급을해야합니다 이러한 상황을 지원 얼마나 호응을 얻고 있는지 우리의 짧은 - 계약 기간 및 긴 - 임기의 목표합니다.
우리의 기나긴 - 임기의 목표는 생존합니다. 더미를 방지하는 생존에 범람하고 이사회에 따라 달라집니다. 우리가 더미 높이를 줄일 수있습니다 결성하여 제거를 완료 행하는 더미를합니다.
을 형성하는 완전한 행, 우리가 필요에 맞게 모든 칼럼의 일부 작품의 행. 그러므로, 우리의 모든 부분이 필요 연속 하락에 노출이 작품 전체를 채우 만약 우리가 결국 행합니다.
만약 어떤 이유로 빈 부분을 은폐 연속으로 우리가 작품을 더 높이 행, 그리고 우리는 이제 그 빈 부분을 채우는 수없습니다의 행. 유일한 방법은 (추측 아니오 슬라이딩)에 액세스 그 "매장 홀"은 부품을 제거하기 위해 행 위의 역할은 장애물을합니다.
다음과 같은 요인이 중 우리가 주어진 데 사용할 수있는 비율 보드 상태 :
Overall pile height
이 높을수록 더미, 우리 상황이 더 나쁜 것 같습니다, 왜냐하면 우리는 범람하고 이사회에 가까이합니다.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
the 거칠어 아래에 있던 게 확률이 더 높아 그것은 그것을 채우기는 어려울 임베디드 복잡한 등고선의 모든 표면에 노출되기로합니다.
Number of buried empty cells
더 홀에 묻혀 우리는, 우리가 처한 상황 악화는, 우리가 발견해야합니다 묻혀 구멍에 해당하기 전에 행을 완성할 수있습니다.
당신이 상상할 수있는 다른 요인은 일반적으로 속도는 얼마나 호응을 얻고 있는지 추측 보드를 수용할 수있는 모든 가능한 미래의 조각 쌓기, 그리고 얼마나 잘들을 수있습니다의 모든 작품의 상황을 찾습니다.
다음 문제는 이러한 요인의 중요성을 확인하는 방법에 대한 상대합니다.
한 일반적인 접근 방식은 다음과 같습니다. 할당하는 일련의 "무게"(상대적인 중요성을)에 이러한 요소를 입력한 다음 수많은 게임과 시뮬레이션이 게임의 결과를 기록합니다 (최종 점수 등)을합니다. 그리고, 할당하는 새로운 일련의 무게와 시뮬레이션 게임의 새로운 설정합니다. 할지 여부를 기반으로 새로운 일련의 게임은 이전보다 더 나은 결과를 일련의 게임, 우리가 알고 새로운 일련의 무게 경우에는 일련의 무게는 이전보다 더 나은합니다.
내 자신이 검색하는 임의의 검색 및 체계적인 실험을했는데 좋은 제품 무게의 조합,하지만 난 어떤 대형 - 스케일 동향을 않썼는데 추구 할 수있습니다. 그러나, 놀랍게도 원활 많은 범프 봤다. 흥미로운 사실 줄 알았는데 부드러운 곡선의 평균 실적이 양식을 느리게하면 매개 변수는 어떤 값을에서 열린 기타 매개 변수에 따라 차이가 조합을합니다.
최고의 실제 - 시간, 1 - 조각 tetris 알고리즘을 세계에서 만든 Pierre Dellacherie (프랑스)에서 2003, 빚을지고있다는 정도의 성공을 측정 집합 (또는 통계). 중량을 최적화하는 전략을 찾을 필요가 있지만이있는 종류의 측정을하여 작업을 시작하는 것도 중요 흐루시초프의 관련성이 높은 특성을 그 상태합니다.
각각의 성격을 나타내는 새로운 방법을 발명 Pierre Dellacherie's 보드가 그의 알고리즘을 정말 우수한;위원회 characterizations을 캡처하여 중요한 전략적인 차원의 보드 상태.
하나 매우 다른 일련의 특성을 개발할 수 치수가 동일하게 근무; 나는 확신하는 것이 가능 보드 상태의 관련에 확장하는 데 사용할 수있는 공간이 다양한 방법을 지정하는 전략 기능을합니다. 열쇠는이 프로젝트를 찾을 재산의 상태 공간의 범위를 작은 수의 규격을 개발하는 데 사용할 수있는 간단한 평가 함수 (예 : Pierre's 알고리즘을 사용하는 특성을 조합의 선형 가중).
the 1 - 조각 알고리즘을 사용하여 "bot"에서 "xtris"소프트웨어 (1996 년) 작성한 Roger Espel Llima 무게에 의해 결정됩니다 대형 - 규모 무한대로 사용이 가능한 제품 무게의 조합을 "유전자 알고리즘을"합니다. 단련은 다른 가능한 방법을 모의 탐험이 다차원 공간의 무게 조합을합니다.
것으로 보인다에 따라 다양한 관측, tetris의 성능에 관한 다차원의 기능을 기능을 무게, 예 : F(w1,w2,w3,...),이 "러프"(많은 로컬 최소 및 맥시마), 즉, 단순한 다차원 "언덕 오르기" 작동하지 않을 수있습니다.
6.9 현재 작품 전략을 때, 다음 조각, 그리고 보드는 알려진
전략적인 알고리즘이 주어진 경우에는 현재의 작품, 다음 작품, 그리고 보드, 그리고 의사 결정에 활용할 수있습니다 조각의 결합으로합니다.
다음 작품의 성공에 대한 지식을 향상시킬 수있습니다 tetris 여러 자릿수로 알고리즘을 연주합니다. 쉽게 이해하는 방법의 다음 작품이 커다란 차이를 알고 전략을합니다.
하나는 할 일 "미친"움직임과 같은 커버 거대한 구멍, 기타, 왜냐하면 그들은 이미 알고있습니다 다음 작품을 사용할 수있습니다을 "수정"이 상황. 에 대한 지식이 없다면 다음 조각, 당신은 지속적으로 노력을 재생하는 확률, 당신의 옵션을 열어 놓으려고 한 경우에는 다음 작품은 이상합니다.
다음과 같은 스케치를 보여줍 수있는 모든 움직임은 현재 작품은 고려, 그리고 각 같은 이동 가능한 모든 움직임 관련된 우리의 다음 작품을 고려합니다.
현재 작품과 다음 작품 전략적인 관계
이 전략의 표준 tetris 소프트웨어를 사용하면 "다음 작품"는 사용자에 의해 활성화되어 화면에 표시하고, 2 - 조각 A.I.이 활성화된 경우 (예 : 1 작성한 날 Colin Fahey). 경우에 "다음 작품"는 화면에 보이지 않는다, 내 두 개의 - 조각 폭포 위로 한 - 조각 A.I.합니다.
내 하나 - 작품과 비교할 때이 엉망 A.I.은 표준 tetris 소프트웨어를 다른 AIs 때문에 이익이 더 많은 정보를 보여줍니다 (예 : 다음 작품)는 A.I.으로 시스템의 성능을 향상시키기 위해 그것은 충분히 나의 자신의 - 작품을 여러 A.I. 평범한 두 자릿수 - 최고의 성능을 쉽게 제치고 세계에서 한 - 조각 A.I.합니다.
(단, 전환 률을 세계에서 최고의 하나 - 조각 A.I. 두 조각을 고려하여 개선이 쉽게 여러 자릿수로 해요! 아는 다음 작품은 거대한!)
첫 번째 테스트 게임을 내 두 - 작품 약 A.I. 지속 1백82시간 (7.6 일)에 800 MHz PC, 7,216,290 행을 완료합니다. 아직 테스트를 위해보다 빠른 컴퓨터 알고리즘을합니다.
tetris 게임을 저장할 때의 상태를 (Shift-W)를 텍스트 파일에, 당신의 목록은 다음의 숫자 복사 및 붙여넣기에서 섹션 "heightHistogram", 엑셀 스프레드 시트를합니다.
각각의 빈이 완료된의 개수를 나타냅니다 움직임이 끝난 히스토그램의 특정 더미 높이 (후에 완전한 행이 제외). 당신이 상상할 수있는로를 만들고 더미로 이동해서 완전히 제거하는 드문, 그래서 움직임의 총 수입니다 산의 높이가 제로로 끝나는은 상대적으로 낮은합니다.
한편, 일반적으로 변화가 심합니다 만끽할 수있을 것입니다 주변의 일부 더미 높이 평균, 그래서 쓰레기통에 해당하는 이러한 행은 히스토그램을 지배합니다. 마지막으로, 쓰레기통에있는 최상위 - 대부분의 행 (여기서 우리는 위험이 범람하고 이사회)가 매우 낮은 합계합니다.
이 과정은 많은 시간 이상으로 A.I. 하나의 게임 플레이에 대한 지식을 사용하여 전략적인 관계 "다음 작품", 그 샘플을 무작위 게임 주, 히스토그램을 스프레드 시트를 복사하여 아래 그림처럼 높이 쌓기 :
각종 포인트를 쌓기 높이 히스토그램 기록 전형적인 게임 (현재 -과 - 다음 - 조각 전략)
각각의 히스토그램을하실 수있습니다의 총 수입 규모 장 (총 개수 완료 움직임)에 다음과 같은 에러가 데이터 :
크기 조정 히스토그램, 그리고 하나의 이론
히스토그램 the 놀라운 것은 이러한 크기를 조정 명령을 봐 서로 다른 크기와 동일에도 불구하고 작품의 개수 (완료 이동) 참여합니다.
보고있는 것만으로 가설의 숫자를 만들었어요 곡선의 꼬리는 부패 지수합니다. 하여 시행 착오를 온의 대략적인 이론에 의해 설명이 꼬리는 :
relative_frequency = ((0.122) * ((0.375)^(row-5)))
다음의 그래프는 전체 범위의 크기를 조정 히스토그램 행합니다.
막대 그래프의 그래프 크기 조정
참고 : 50000 작품은 곡선을, 그리고 커브를 2000000 조각, 그리고 곡선의 꼬리 부분은 이론이 거의 구별할 수없는 정도라 생각합니다.
다음은 곡선의 수장을 더 자세히 조사합니다.
아래 부분 높이 히스토그램
- 확대 사진을 크게 다음은 꼬리 끝에 볼 수있는 극단적인 측정 및 이론적인 막대 그래프 곡선을합니다.
히스토그램의 극단적인 꼬리 끝이 문서가 적용되는 확대 축소
을 만끽할 수있을 것입니다, 그것은 매우 드문 하이츠에서도 이들은 오랫동안 실험을 쌓기에 도달 -하지만이 극단적인 지역에 증거 자료로 자사의 제한에도 불구하고, 그 이론이 여전히 허용 보인다.
중복의 전체 차트의 이론에 꼬리의 분포를 보인다 "를 정확하게", 반면에 꼬리에 꼬리를 차트를 확대, 우리가 보는 명백한 오류가있습니다. 그러나 그 주장이 이런 극단적인 더미로 인해 데이터의 불충 분한 하이츠합니다. 게임 보드를 상승면, 예를 들면 고도에의 25 행 대신에 20 행, 그래서 급격하게 게임을 종료할 않았 것 이상의 이론 발표 전의 흐름을 완벽하게 일치합니다.
제 느낌은이 막대 그래프는 tetris A.I.의 결과에 직접적인 결합과 규칙을 tetris합니다. 그래서,이 같은 분포는 임의의 관측의 모든 게임을 오랜 기간 tetris - A.I. 전략을 사용하여 특정 놀고 "다음 작품"지식합니다.
또한, 이러한 유형의 생각을 비교 히스토그램 AIs 사용할 수있습니다 연주하는 동안 그 같은 정보를 고용합니다. 따라서, 전체의 게임을 재생하지 않아도됩니다 (이것이 지난 며칠 동안이나 년)의 성능을 비교하여 서로 다른 전략을 알고리즘을 오래 - 용어합니다.
예를 들어, 나의 모델을 단순화에도 불구하고, 제 생각 게임의 평균 소요 시간을 예측할 수있습니다! 우리가 얼마나 많은 작품을 간단하게 알아낼에서 "행 21"더미 키 큰 숫자와 같은 개수를 한합니다.
에 대한 상대 주파수를 연속 21 일 내 간단한 이론에 따르면이 :
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
이 번호로 여러 (5.3 * 10^(7))하셔야합니다, 약 50 만, 값 중 하나를합니다.
따라서, 나는 나의 현재의 대략 것으로 예측하고 "다음 작품인"의 순서를 위해 유일하게 좋은 전략은 대략 1000 만 완료 행합니다. 이유 중 하나는 사실을 나는이 보수적인 견적은 치명적인 나의 A.I.도 18 행 수있습니다 허용하지 않는 나는 내 A.I. 때문에 작품을 고려하여 겪어 때까지는 적어도 하나의 행을! (이것은 그래서 볼 수 없다는 사실에 대해 걱정할 필요는 없어 조각을 회전합니다.)
연주는 사실을 감명을 나는 작품에만 50000 (그리고 어쩌면 훨씬 더 적은 조각)는 견적을 줄 수있는 매우 좋은 긴 - 임기 신장 히스토그램, 그리고 그러므로, 좋은 견적을 완료 리히터 규모의 순서를 게임하기 전에 행 종료합니다. 이 접근법은 매우 귀중한에서 변경 사항을 신속하게 평가하는 미묘한 A.I. 그것은 이미 아주 잘하고있습니다.
6.10 보드 평가 통계를 흉내 - 앞두고 투기보세요
만일하는 알고리즘과 같은 하나 나는이 프로젝트를 제시하기만하면됩니다 하락 시도의 모든 작품에 대한 오리 엔테이션과 번역, 그리고 등급위원회 구성에 따라 각각의 결과를 측정하는 기준입니다 일부 장점으로,이 알고리즘은 본질적으로 모방 "봐 - 앞두고"합니다.
고용 통계와 같은 하나가 "더미 신장", "매장 홀", "표면 거칠기"또는 "잘 깊이"를 사용하여 간단한 형태의 하나는 정말로 "찾는 앞두고"합니다. 이러한 일반적인 characterizations 대표 이사 - 용어 긴 생명력을 보여주고 이사회합니다.
가장 이상적인 방법은 주어진 무한한 양의 컴퓨팅 파워,이 보드 구성을 주어진을 평가할 수있는 모든 가능한 조각 시퀀스를 다음과합니다.
비록 당신이 동등하게 고려해야합니다 총 7 작품으로 추정에서 각 레벨을 봐 -을 앞두고을 보완하는 데 필요한 실제적인 번역 (최대 10) 및 오리 엔테이션 (최대 4)의 각 조각을 모든 가능한 순서! 그것은 모든 수준에서 최대의 보드 평가 (7*10*4) = 280 점포! 그래서, 저 여자에게 ((280)^(LookAheadLevels)) 보드 구성을 고려해야합니다.
왜냐하면 우리의 분석 후에 종료해야합니다 유한 수의 수준, 우리가 필요합니다 - 봐 - 앞두고 방법을 일부 아닌 평가를 보드 상태 -하는 방법 중 하나 잎 노드를주고 우리의 검색 트리에 값을합니다. 그래서, 이러한 잎 노드를, 우리는 위로를 사용하는 수식을 실현할 미래의 일반적인 원근법의 생존 능력은 보드!
이러한 유형의 합작을 시도 수있습니다 - 조각, 2 - 조각 알고리즘을 하나의 단순한 보드 평가 통계에 위치합니다. 이후의 모든 작품은 동등하게 추측을 추정하고 있 보드의 능력과 모든 종류의 조각을 수용하기 위해 최선의 방법으로합니다. 이것은 집행될와 1, 2, 또는 임의의 숫자 합작 이동 깊이 - 모든 작품이 동등하게 추정 (p=1/7).
이 나무의 터미널 노드를 가중 통계에 대한 평가가 여전히 필요합니다,하지만 레이어를보다 정확하게 포착 투기의 본질을 우리가하고 싶은 : 특정 보드 얼마나 호응을 얻고 있는지 확인할 수있습니다 수락하실 수있습니다의 모든 작품을 포함한 라인을 완료와 같은 긍정적인 요인 과 같은 부정적인 요인을 확대하고 전반적인 더미 높이, 등등
7. A.I. 시스템 시위를 tetris
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+ ( "더하기") 기능의 차이
7.6 비디오 캡처 소프트웨어
Microsoft는 매우 오래된 API 이름은 "Video for Windows"(VFW)가 나는이 프로젝트에 대해 성공적으로 사용합니다. (이 링크를 "vfw32.lib"를 C++ 프로젝트, 또는 a DllImport "vfw32.dll"를 C# 코드를합니다.) 예제를 사용하여 VFW API은 광범위하게 사용할 수있습니다.
을 사용 Microsoft's의 대안은 "DirectShow"API을 비디오 캡처합니다.
때문에 불과 12 줄의 코드를 데려 VFW 사용하고, 수행 만족시키기 제 800 MHz 기계, 나는 다른 대안을 탐구 APIs 성가시게하지 않았다. 하지만 API에 대한 DirectShow은보다 현대적인 Windows 비디오 캡처, 그리고 잠재적인 결과는 훨씬 더 높은 프레임 속도를 동일한 하드웨어합니다.
보고에서 "CPF.StandardTetris.STVideoCapture"소스 코드를 파일에 대한 표준 tetris 소프트웨어를 참조하는 것이 얼마나 쉬운를 사용하여 자신의 프로젝트에서 비디오 캡처를합니다.
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. 표준 tetris 소프트웨어를
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 속도 제어
the '+' (플러스)과 '-' (마이너스) 키를 게임의 속도를 제어합니다.
기본적으로, 게임을 실행에 표준 속도, 표준의 규칙에 따르면 tetris (속도에 따라 수준).
여기에 편견이 테이블에있는 속도의 의미 :
-3,-4,... : 느림 편견에 비례
-2 : 느린 것보다 레벨 1
-1 : 보통,하지만 국한 레벨 6 (0.2 초) 속도;
0 : 기본적인; 표준 tetris 속도 제어;
+1 : 약간 빠른 레벨 9 일 (0.05 sec 지연);
+2 : 경계로 렌더링 속도 (예 : 75 Hz);
+3,+4,... : 여러 반복 1 렌더링 프레임;
맘에를 실행하는 A.I.에서 설정을 "+2"(조회수 '+' 키를 두 번 편견에서 시작하면 영)으로합니다.
스피드 편견 게임의 속도를 변경합니다.
8.9 다음 작품보기
'을 누르 N'를 토글 "다음 작품"표시합니다. the 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아르 자명 너비를 표시하는 무한 생존을 허용합니다.
the AIs 생존 무기한으로 다음과 같은 경우에, 비록 그들이 이것을 처리하는 명확하게는 아니 병적인 상황을 지켜봐 주시기 바랍니다.
조각에만 S/Z
8.12 영상 보정 모드로
'을 누르 C'를 입력하십시오 "보정 모드". 때 보정 모드를 사용하면 전화 번호를 누르십시오 키 : {1,2,3,4,5,6,7}를 선택하실 수있습니다 연주 보드의 상단에 조각 {O,I,S,Z,L,J,T}합니다.
이것은 유용한 이미지를위한 레퍼런스로서, 비디오 캡처에서 두 번째 기준 Tetris 소프트웨어를합니다.
0 테러로하는 경우 (영)으로 키,이 보드 공백을합니다.
흉내를 시작하실 수있습니다 한 조각 작품을 선택하여 (1..7)를 입력한 다음 공백을 선택 (0), 시계에 대한 비디오 캡처하는 동안 컴퓨터에 두 번째 작품.
두 번째 컴퓨터를 실행할 수있습니다 A.I.을보고 거래를 수동으로 입력하는 방법 진단 tetris 시나리오를!
보정 모드를 조작할 수있는 유일한 시간의 비디오 캡쳐 이미지 프로세싱 템플릿 (4 * 2 그리드). 마우스를 사용하여 사각형 그리기하실 수있습니다,하지만 그때는 커서 키를 사용할 수있습니다 ( "을", "아래", "왼쪽", "오른쪽")을 사용하여 국경을 세밀하게 조정할 수가 - Shift 키를 선택을 사용하여 반대로 테두리를 직사각형 (예 : "Shift - 왼쪽"콤보가 다르게 "왼쪽").
영상 보정 모드로
8.13 비디오 캡처 및 포상
누르면 'V'의 비디오 캡쳐 모드로 전환합니다. 만약 적절하게 보정 (아래의 "영상 보정"에 이전 섹션), 그 조각들은 원격 비디오 화면을 캡처하여 비디오 카메라로 분류된다 - 그리고, 그 조각은 시키려의 로컬 게임을 실행하고 반응을 고려 A.I. 합니다.
the A.I. 출력을 전송해야합니다 (RS-232 인터페이스를 통해이 문서에서 설명하는 시위에)를 원격 게임 입력 (예 : 키보드)를 A.I.의 원격 게임을 성공적으로 재생합니다.
만약이 폐쇄 루프는 언제든지 방해합니다 (예 : 비디오 캡처 기능 장애, 또는 출력 신호 오작동), 다음 A.I.는 인상을 개발하는 허위의 상태를 원격 게임, 그리고 부적 절한 의사 결정을 신속하게하면 잃을 A.I. 게임 합니다.
(참고 사항 :이 문제는 겸손한 금액의 노력으로 극복할 수있습니다 : A.I. 시스템 전체를 원격 tetris 화면이 필요하는 유일한 검토하여 지속적인 "현실"확인란을 선택하십시오의 전체 보드, 그리고 일부 출력 A.I. 시스템에 명령을 준비를해야합니다 어떤 방법으로 실패합니다.)
비디오 캡처 및 포상
9. 기존 tetris 또는 실험을 (2003 년)
첫 번째 작업은 다음 버전을 보여주는 2003 년 tetris A.I. 시스템합니다.
비디오 카메라를 컴퓨터에 # 1을 실행하고있는 일반 tetris 게임에 직면
표준 tetris 소프트웨어를 실행하는 컴퓨터를 A.I. 모드 # 2
왼쪽 : 그림 그리드 비디오 이미지를 보정하는 데 인식;
오른쪽 : tetris 작품의 경우 인식합니다.
2003 년 실험을 A.I. 프레임에서 비디오를 tetris
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 게임을 완료한 후 내 컴퓨터, 2 일 이상의 기간을 발견 했어 행 평균 674,827 완료합니다.
상기의 일반 이론에 따르면, 전 다음과 같은 상대적인 분수의 게임을 기대하고 다음과 같은 완료를 완료 행 범위 :
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을 보여주는 그래프를 비교합니다 유통의 게임 이론을 관찰합니다.
36 완성의 게임 이상의 성능 알고리즘을 Pierre's
있지만 소수의 게임을이 데이터를 설정하는 것은 명백한 관찰된 분포와 일치하는이 모델은 매우 능숙합니다.
자기 소개 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+을합니다."
C++에서 2003.6로 변환 알고리즘을 Pierre's 나는 후 이메일 - 메일 교류를 여러 Pierre합니다. C++ 버전을 확인하는 A.I.에서 우리가 예전에 같은 Pascal 버전의 의사 결정합니다.
나는 그의 원본 보고서를 유사한 성능을 관찰; 평균 650,000 완료 주위 행, 일부의 게임을 완료 2 백만 행이합니다.
굉장합니다!
10.2 Pierre Dellacherie과 대화하기
[1]이 코드를 처음 만들 언제?
이 알고리즘 하순에서 일하고 나는 지금까지 2003년 1월합니다.
[2] 얼마나 오래 일하 셨나요 들어 있나?
나는 거의 매주 효과가 ... 하지만 일상 긴 것이 없어서 다른 활동 : 불행히도 나는 다른 사람이 같은 수익을 올리십시오!
[3] 어떤 영감의 디자인의 코드?
tetris 10 개 또는 15 년 전에 뛰었는데하지만 오랜 시간이 다시 한 번 재생되지 않는다. 나는 생각을하는가하는 말은 "일반적인"선수 잘 알고있는 규칙과 일부 트릭을합니다.
그러나 나는이 작업을 시작했다 알고리즘을 안 찾았 때문에 많이 플레이는 컴퓨터를보고 오히려 더 효과적인 재생 및 그의 약점을 분석합니다.
[4] 당신의 코드를 사용하여 더 나은 실적을 자동화를 "기차." 알고리즘을 개선하기 위해 2595 셨나요?
아니면을 결정하기만하면 그 결과를보고 수정?
나는 "오래된 학교로부터" : 나는 간단하게 지켜 보면서 결과를 수정하기로 결심합니다.
"자동 학습"은 일종의 메타 - 알고리즘을 안심하고 있어요 없다 그래서 난이 방법으로 돈을 벌게이 메타 - 알고리즘을 쉽게 구축이가 너무 그것이 그리 간단합니다!
하지만 무엇보다, 나는 그가 말한다 Roger Penrose에 동의 (그의 책 "Shadows of the mind")가 인간의 이해와 직관 알고리즘 수없습니다 (예 : 계산).
[5] 언제 연주를 처음 시작 tetris, 그리고 언제부터 tetris를 해결하는 생각을 A.I.가?
가르치는 알고리즘과 컴퓨터 프로그래밍 (Turbo Pascal 및 Scilab) 대학원 학생들을 위해 훈련을 위해 엔지니어의 학교에 입학 시험합니다.
처음에, "컴퓨터 재생 Tetris"는 개발에 대한 아이디어가 나의 다음 학년 학생 싶었어요.
귀하의 웹 페이지를 인식하지 못합니다 전에 작업을 시작했다 알고리즘을 때.
운이 좋았어요 알고있는 사실을 귀하의 웹 페이지를 불과 몇 주전에 의해 낙담했을 것 때문에 귀하의 검색 결과 (당신이 추측 초기 버전의 내 알고리즘을 너무 잘 못 플레이!).
[6] 당신의 현재 상태를 무엇입니까?
저는 거의 30 [전 2003 년 4 월 27]. 나는 여러 활동 : 나는 첼로, 작곡 음악과 가르치는 컴퓨터 프로그래밍합니다.
나는이 음악이 석사 학위를 취득 (1994 년)과 "Artificial Intelligence and Algorithmic"졸업장 (1998).
이 졸업장에 해당하는 프랑스에서 5 년간 공부 대학교 (4 학년은 6 년 석사 학위를 취득하고 논문은).
Pierre's 작곡 :
[7] 어디에 계십니까?
나는 프랑스와 내가 살고 후앙 (노르망디).
[8] 기타 의견 :
결국 나는 어떤 새로운 아이디어를 개선하지 않은합니다.
나는 너무 많은 쓸모없는 시도 (그리고 어리석은) 것들을 그럴 것 같지를 개선해야합니다.
반면에, 나는 존재하는 것 같다는 생각이 더 나은 공연 수있는 완전히 다른 알고리즘을합니다.
그런데, 더 빠른 구성에서 발사 시험에, 그 조각들은 반 - 박스 (10 행 × 10 열) : 30 - 상자, 내 알고리즘을 완료하게되면 평균 280 행합니다.
하나 더 :이 알고리즘을 변경할 수있습니다 쉽게 알고리즘을 더블 - 플라이 ([해야할지]의 시험 예정).
나는 영화를 사랑하는 음악 :되는 영화 작곡자의 일부인 내 메인 꿈이 (그러나 이건 그냥 꿈을!).
11. 세계에서 최고의 인간의 선수
11.1 일본어 tetris 마스터 (2001 년 1 월 27) 비디오
tetris 마스터 (2001; 일본) 비디오
일본의 선물을 Arika tetris 결승 마스터 (2001 년 1 월 27). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. 피드백
12.1 / Slashdot 스레드 (2003 년)
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 년 봄에 건너뛰는 바빠서 (그리고 실패) 제 2 학기 1 학년 교실에서 - University of Pennsylvania합니다.
내 룸메이트 중 하나, Bill Matthews, Mac Classic 있었을, 그리고 때로는 경기 비디오 게임.
학교는 일반적으로 사람들을 Ivy League get 성향을 인정하고 다른 사람들이 언제든지 경쟁할 - 그래서 tetris을 때 그의 Bill 게임이 Mac, 우리를 즉시 긴 - 임기 전투를 시작 최고 점수를합니다.
로 점수를 기어, 시간 투자 필요로 소정의 이익을 크게 향상합니다.
길고도 짧은 이야기를 만들어, 우리 사이에 최고 점수를 보유하고 기발한 Bill,하지만 난 그를 의심의 ResEdit 및 해킹의 점수를 사용하여 파일을!
Wharton 학교는 수업의 사업에 Bill, Michael Milken 및 alma mater의 Donald Trump, 그래서 누군가가 조작되고 an 매우 높은 점수 생각할 수도없습니다 ...
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 밝기를 센서, 그리고 tetris 조각과 배경 사이의 대비 Mac Classic 화면에서 를 안정적으로 차별이 너무 낮습니다.
그 당시에는 돈 게별로 없었어요, 그래서 그것은 너무 위험을 구매하기 위해 $ 2 Radio Shack하고 싶은 걸하지 phototransistor이 될 수도있습니다.
또한, 주어진 문제를 대비, 나는 전체적인 접근에 대해 비관적인합니다.
내 첫 개인용 컴퓨터 구입시 1996 년, 나는 소프트웨어를 가져올 수없습니다 Windows 95에 비디오 프로세싱 속도가 충분 할 100 MHz CPU 간단한 비전 시스템을 작동합니다.
나는 이미지 프로세싱 코드를 어셈블리 언어를 쓴 사람은했지만 거기는 너무 많은 오버헤드가 비디오 데이터를 수신하기 전에는 이런 코드를 실제로 아무 일도 할 수있는 것 같았습니다 가치가 불가능하다.
2003 년, 기술, 특히 CPU 속도는 일정 수준에 도달하게 만든이 프로젝트를 거의 능률을 마무리하고있습니다.
나는 내 아버지는 개인 프로젝트를 파낸 그리고 마지막으로 완성, 이제 일부 감각을 폐쇄합니다.
그것은 매우 흥미로운 게임을 다른 컴퓨터에 하나의 컴퓨터를 통해 볼 USB 비디오 카메라와 릴레이를합니다.
릴레이를 클릭의 소리를, 그리고 스핀 앤 드롭을 말도 안되는 작품을 보며, 초인적인 속도를 만들어 multisensory 방식의 경험에 아주 만족합니다.
나는 초대에 게재될 수있는가 "Screen Savers"텔레비전 TechTV 디지털 텔레비전 네트워크에 게재합니다.
샌프란 시스코 및 출연에 갔었 쇼, 그리고 경험을 대단합니다.
나중에 2003, 나 Henk Rogers에서 메시지를 수신, 하와이에 초대해 얘기 Alexey Pajitnov을 만나고, 어떤 종류의 표준을 확립 tetris, 경기 대회의 목적을 위해 tetris 데합니다.
하나의 특별한 관심은 휴대 전화를 사용 활성화 "선수와 경쟁이 서로를" 간접적으로, A.I. 그 모방을 통해 플레이어 (하여 분석을하기 전에 각 선수의 행동), 따라서 휴대 전화의 효과를 피하는 인터넷 접속 대기 시간, 그리고 선수들에게 "경쟁" 활성화 * 인간의 플레이어 세계 (*... 최고 또는, 오히려, A.I. 인간의 선수가 세계 최고 모방).
전 감격의 전망 tetris 회의를 창조합니다. 불행히도, 비행 나를 불안, 그리고 나는 초대를 거부합니다.
2006 년에 나는 내로 변환 "표준 tetris"소프트웨어에서 C++에 액세스할 수 있으며 다른 사람이 소프트웨어를 C# 현대적인 프로그래머에게 유용합니다.
