Tetris
Colin Fahey
1. Software
2. Introdução
Este artigo descreve como um computador pode jogar o clássico vídeo game Tetris em obter as informações sobre o conselho de administração, determinação boas ações, bem como a realização dessas acções.
Este artigo inclui software capaz de jogar Tetris em tempo real.
O software inclui o melhor tempo real Tetris-playing algoritmo de domínio público.
Este artigo define regras para “Standard Tetris,” uma especificação baseada no original 1986 pré-comerciais para a versão de Tetris Personal Computer (PC).
Em 2003, o software incluído neste artigo foi usado para permitir que um computador para jogar Tetris rodando em um computador separado.
Ordinária USB câmaras vídeo foi usado para permitir que o computador para “ver” a tela do outro computador.
Um relé bordo RS-232 foi controlada através de uma interface para permitir que o computador para “pressionar as teclas” no teclado do outro computador.
Assim, o primeiro computador tem uma relação com o segundo computador que é semelhante a um típico jogador do relacionamento humano a um computador quando jogando Tetris, o jogo só é conhecida pelo estado a olhar para o ecrã, eo jogador acções só pode ser iniciado através de um teclado .
A configuração neste demonstração estabelecido que um computador pode jogar Tetris melhor do que um ser humano, em condições normais de tempo real jogando Tetris condições.
3. História do Tetris
Em 1985, Alexey Pajitnov e Dmitry Pavlovsky eram engenheiros informáticos no Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre do Russian Academy of Sciences
Alexey e Dmitry estavam interessados em desenvolver e vender computador viciantes jogos.
Eles experimentam as diferentes jogos.
Alexey foi inspirado no grego antigo puzzles, Pentaminos, que envolveu enigma arranjar peças feitas de cinco quadrados.
Alexey pensamento da ideia de organizar Pentamino peças como eles caíram em uma rectangular a taça, mas percebeu que a doze de cinco diferentes formas quadradas eram demasiado complexas para um jogo de vídeo.
Alexey comutada para “tetramino” utilizando sete peças, cada um constituído por quatro quadrados.
Em 1985.6, Alexey Pajitnov programada a primeira versão de Tetris em um Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov, e Tetris.
Em 1985-1986, Vadim Gerasimov, uma alta de 16-year old-escolar computador prodígio que trabalhou na Academia, implementado Tetris para o IBM PC correr o MS-DOS sistema operacional.
(Vadim Gerasimov mais tarde fez a investigação ao MIT Media Laboratory, a partir de 1994 até 2003, recebendo um Ph.D. após completar muitos projetos interessantes:
http://vadim.www.media.mit.edu)
A introdução da tela 1987-1988 pré-comerciais para a libertação de Tetris PC
A tela do jogo 1987-1988 pré-comerciais para a libertação de Tetris PC
Após 1987, Tetris espalhados ao redor do globo.
The Tetris Company, LLC, é proprietária da marca Tetris.
4. Projetos inspirado pelo Tetris
4.1 0-dimensional Tetris
Ainda não desenvolvido.
4.2 1-dimensional Tetris
Ziga Hajdukovic tem desenvolvido 1-dimensional Tetris software que pode ser jogado em um browser da Internet.
Ziga Hajdukovic também desenvolveu 1-dimensional Tetris software para telefones celulares usando a plataforma Java J2ME.
4.3 2-dimensional Tetris
Todas as variantes Tetris convencionais estão nesta categoria.
Esta seção inclui interessantes variantes.
4.3.1 Cada vez maior jogo Tetris: Delft University of Technology (1995)
Tetris jogado em um edifício; 2000 m^2 superfície; Delft University of Technology (1995)
Tetris jogado em um edifício; 2000 m^2 superfície; Delft University of Technology (1995)
4.3.2 Outro jogo Tetris jogado em um edifício: Brown University (2000)
Tetris jogo exibido usando luzes nas janelas de um edifício em Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
“Acho que foi apenas um dos mais incríveis do dia-coisa que eu podia imaginar na minha vida. Tal como sempre disse Steve Jobs, a viagem é a recompensa.”
“Ele me fez pensar em projectos de volta fizemos na faculdade. Coisas que eram quase reversível que as outras pessoas que não pensam em fazer.”
Steve Wozniak (2000)
4.3.3 Internet browser jogo com MIT “Green Building” imagem
Vadim Gerisimov's navegador Internet Tetris
Este navegador Internet Tetris variante foi criada por Vadim Gerasimov.
Este navegador Internet Tetris as características “Green” a construção do campus da MIT.
Tetris Esta variante tem apenas nove colunas em vez de a norma dez colunas.
Esta variante apresenta Tetris com peças novas orientações aleatórias.
Vadim Gerasimov é a pessoa que escreveu o código para o computador PC versão de Tetris em 1986.
Vadim Gerasimov fez doutorado a investigação ao MIT Media Laboratory durante 1994-2003, trabalhando em vários projetos interessantes.
4.3.4 PIC16F84 12 MHz microcontrolador à base de NTSC / PAL video jogo Tetris
PIC16F84 12 MHz microcontrolador à base de NTSC / PAL video jogo Tetris
A imagem acima mostra o NTSC / PAL video output produzido por um microcontrolador PIC16F84 12 MHz rodar o software escrito por Rickard Gunee em 1998.
O sinal de vídeo é gerado pelo software de controlo das saídas digitais.
4.3.5 “Scopetris” osciloscópio Tetris por Lars Pontoppidan (2007.8)
“Scopetris” osciloscópio Tetris por Lars Pontoppidan (2007.8)
Lars Pontoppidan escreveu código para o microcontrolador AtMega32, e acrescentou circuitos analógicos simples, para criar uma versão Tetris que pode ser desempenhado por um osciloscópio.
Certos registos de controlo do AtMega32 microcontrolador 8-bit sinais de saída, e, quando passaram por uma “R-2R” resistor circuito elétrico para a digital para o analógico (D/A) conversão, o resultado pode controlar os sinais analógicos (x,y) coordenadas de um osciloscópio vara (quando for o osciloscópio “X-Y modo” a definir).
YouTube vídeo:
FLV vídeo:
4.3.6 Obfuscated código Tetris: C / Unix
O seguinte foi atribuído “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 código Tetris: Perl código
O que se segue é Tetris para o Perl intérprete: Perltris (versão 20050717) por Sean Adams.
#!/usr/bin/perl
$_='A=15; B=30; select(stdin); $|=1; select(stdout);$|=1; system
"stty -echo -icanon eol \001"; for C(split(/\s/,"010.010.010.010
77.77 022.020.020 330.030.030 440.044.000 055.550.000 666.060.".
"000")){D=0;for E(split(/\./,C)){F=0;for G(split("",E)){C[P][F++
][D]=G} D++}J[P]=F; I[P++] =D}%L=split(/ /,"m _".chr(72)." c 2".
chr(74)." a _m");sub a{for K(split(/ /,shift)){(K,L)=split(/=/,K
);K=L{K};K=~s/_/L/; printf "%c[K",27}}sub u{a("a=40");for D(0..B
-1){for F(0..A-1){M=G[F][D];if(R[F][D]!=M) {R[F][D]=M;a("m"."=".
(5+D).";".(F*2+5)); a("a=".(40+M).";" .(30+M));print " "x2}}}a(
"m=0;0 a=37;40")}sub r{(N)=@_;while(N--) {Q=W;W=O=H;H=Q;for F( 0
..Q-1){for D(0..O-1) {Q[F][D]=K[F][D]}}for F(0..O-1){for D(0..Q-
1){K[F][D]= Q[Q-D-1][F]}}}}sub l{for F(0..W-1){for D(0..H-1){(K[
F][D]&& ((G[X+F][Y+D])|| (X+F<0)||(X+F>=A)|| (Y+D>=B)))&& return
0}}1}sub p{for F(0..W-1){for D(0..H-1){(K[F][D]>0)&&(G[X+F][Y+D]
=K[F][D]) }}1}sub o{for F(0..W-1){for D(0..H-1){(K[F][D]>0)&&(G[
X+F][ Y+D]=0)}}}sub n{C=int(rand(P)) ;W=J[C];H=I[C];X=int(A/2)-1
;Y=0;for F(0..W-1){for D(0..H-1){K[F][D]= C[C][F][D]}}r(int(rand
(4)));l&&p}sub c{d:for(D=B;D>=0;D--){for F(0..A-1){G[F][D]||next
d}for(D2=D;D2>=0; D2--){for F(0..A-1){G[F][D2]= (D2>1)?G[F][D2-1
]:0; }}u;}}a ("m=0;0 a=0;37;40 c");print "\n\n".4x" "." "x(A-4).
"perltris\n".(" "x4)."--"xA."\n".((" "x3)."|"." "x(A*2)."|\n")xB
.(" "x4). "--"xA."\n";n;for(;;) {u;R=chr(1); (S,T)=select(R,U,V,
0.01);if(S) {Z=getc;}else {if($e++>20){Z=" ";$e=0;}else{next;} }
if(Z eq "k"){o;r(1);l||r(3);p}; if(Z eq "j"){o;X--;l||X++;p}; if
(Z eq "l"){o;X++;l||X--;p};if(Z eq " "){o;Y++;(E=l)||Y--;p;E|| c
|c|c|c|c|n||goto g;};if(Z eq "q"){last;}}g: a("a=0 m=".(B+8).";0
" ); system "stty sane"; '; s/([A-Z])/\$$1/g; s/\%\$/\%/g; eval;
4.3.8 Mozilla SVG Tetris
Scalable Vector Graphics (SVG) é um padrão para a descrição de objectos gráficos usando XML.
Mozilla SVG Tetris: Tetris implementado utilizando uma descrição Scalable Vector Graphics (SVG)
4.3.9 Google “widget” Tetris
Google, Yahoo!, e Microsoft, e de outras empresas, têm promovido miniatura baseados na Internet, software chamado “widgets” que normalmente são caracterizadas por alguns utilização de dados dinâmicos disponíveis na Internet.
Um desses widget disponíveis através Google é um jogo Tetris.
O exemplo a seguir é cute, mas molda a girar em irritar maneiras:
Google “widget” Tetris
Outros Google widgets:
4.3.10 MIT investigação papel: “Tetris is Hard, Even to Approximate” (2002)
O documento contém uma investigação após a prova de que um certo tipo de Tetris variante é “NP-completa.”
Erik D. Demaine, Susan Hohenberger, e David Liben-Nowell, “Tetris is Hard, Even to Approximate”, Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
“NP completa-se” uma classificação do custo do tempo e do espaço custo de um algoritmo.
Outras classificações incluem “P” e “NP”.
A classificação de “NP-completo” implica que, para os problemas maiores do que alguma pequena dimensão, é pouco provável o algoritmo para encontrar uma solução desejada em prática uma quantidade de tempo ou de espaço.
4.3.11 Investigação documento: “Applying reinforcement learning to Tetris”
O seguinte documento, publicado 2005.5.30, por Donald Carr no departamento de Ciência da Computação Rhodes University, África do Sul, apresenta o pedido de “reforço da aprendizagem” ao Tetris.
4.3.12 Tetris saia (2007.11)
Tetris saia (2007.11)
O Tetris saia foi criado por “Lucy” (“hissyfitoly” em etsy.com) antes 2007.11.
Desde o criador da descrição da saia (colocados à venda em etsy.com):
"Okay, so I was a secret, closet Tetris fanatic from about, oh, 1993 to 1996. It was a bitter-sweet obsession. My life wasn't so great, but I could control the stacking of a few measly blocks, [damn it]! Or could I? Video games have been coming back to haunt my dreams as of late, and I find myself stacking blocks, jumping away from a frighteningly-large Q*Bert, and slipping off of logs next to a pixellated frog. This skirt is the result of those nightmares."
Fórum comentários sobre este saia:
“O homem que saia suga a Tetris”
“Ahahahaha, pensei a mesma coisa.”
“Existe uma linha completa para baixo no fundo ... concluídas linhas desaparecem.” “FAZER MAIS” “.”
“Não deveria haver um espaço na parte traseira ou dianteira longa peça onde se enquadraria perfeitamente ...”
“Isso é realmente uma saia embora feio. O meu namorado não podia comprar flores e chocolate-me suficiente para convencer-me ao desgaste que a coisa.”
4.3.13 Tetris fase acto (2007.4)
Tetris fase acto (2007.4)
“Desde aqueles que lhe trouxe a Triforce em 2006 ... Vem a próxima geração de objeto inanimado skit ... Tetris.”
Localmente-cache Flash vídeo (FLV) vídeo em formato (utilize a desempenhar VLC):
4.3.14 Hilariante Tetris variações sobre um japonês de televisão mostram
Tetris variações em japonês de televisão mostram
Este vídeo segmento de televisão mostram um japonês inclui hilariante variações de Tetris, incluindo:
peças que desaparecem após a aterragem, uma peça que preenche toda uma fila (completando assim uma fila após a aterragem), várias peças caindo em simultâneo, irregularmente peças moldadas, uma longa peça que está ligeiramente demasiado grande para caber em um fosso (impedindo uma linha 4 - conclusão!), Mario acertando um cogumelo e se tornando enorme e morrer! de pequeno pedaço detritos remanescentes após filas são destruídos, fazendo peças flutuar para cima gravidade para o topo, etc
Localmente-cache Flash vídeo (FLV) vídeo em formato (utilize a desempenhar VLC):
4.3.15 “The Original Human TETRIS Performance by Guillaume Reymond” (2007.11)
“The Original Human TETRIS Performance by Guillaume Reymond” (2007.11)
A partir da descrição sobre YouTube:
“TETRIS desempenhado pelos verdadeiros seres humanos-sentado em um auditório:”
TETRIS é o 4o vídeo desempenho do GAME OVER Project, dirigida pelo artista suíço Guillaume REYMOND (NOTsoNOISY criativo da agência).
Este stop-motion video foi baleado e jogado para “LES URBAINES” festival
http://www.urbaines.ch no Palais de Rumine (Lausanne, Suíça) em November 24th 2007.
Localmente-cache Flash vídeo (FLV) vídeo em formato (utilize a desempenhar VLC):
4.3.16 2.5-dimensional Tetris
“2.5-dimensional” O termo é usado aqui para significar um não-ortogonais vista de uma bidimensional versão de Tetris, com cerca de espessura na terceira dimensão.
(Encontre o link “tetris3d” em “F7: GAMES”.)
4.4 3-dimensional Tetris
Linux / GTK versão
Tetris tridimensional, sob a forma de uma applet Java para navegadores Internet:
Tridimensional Tetris Windows para o sistema operacional:
4.5 4-dimensional Tetris
Greg Kaiser's “HyperTetris” (1996): a 4-dimensional Tetris
Em [1996], [...], Greg Kaiser juntos um quatro-dimensional variante sobre o clássico jogo.
Usando IrisGL (a.k.a. igl) ele criou um grupo de trabalho, se for difícil de jogar, jogo com quatro sub-telas retratam a três dimensões diferentes aspectos do jogo-a totalidade do espaço.
[Porque] não existe uma facilidade [compreensível] maneira de chamar a quatro-D dois objetos em uma tela-D, as quatro sub-pontos de vista são um método prático de manipular e visualizar a rotação e tradução das peças, através das quatro dimensões ( no jogo chamado x,y,z,w).
Ao invés de completar linhas de blocos, como no original, o objetivo neste caso é a de preencher um cubo completo no x,y,z subview (geralmente 4 a 4 em 4).
Os outros subviews que contêm as “w” dimensão são dispostos em um padrão 4 a 4 por 10 blocos acordo com “w” sendo o longa, “vertical” dimensão em todos os três casos, com diferentes bases de (x,y), (x,z), (y,z).
Gravidade atua no “-w” direcção, de modo “caio” em pedaços os três longos subviews que incluem “w”, e não se desloquem a menos que o último jogador no controle (x,y,z) subview.
Demora algum tempo a habituar-, para dizer o mínimo.
Se por algum milagre de paciência ou alterando os parâmetros do jogo, faz uma completa um cubo, ele irá desaparecer, as linhas concluída em fazer o Tetris original, embora não seja mantido na pontuação HyperTetris.
Benjamin Bernard (2000)
4.6 N-dimensional Tetris
Polytope Tetris (2003): um N-dimensional jogo Tetris variante
Polytope Tetris é n-dimensionalmente Tetris.
Inspirado no programa HyperTetris, Polytope Tetris toneladas permite que você joga em qualquer Tetris NÚMERO DE dimensão.
Jogue Tetris em 3D, 4D, 5D, ou mais.
HyperTetris é um nome muito catchier do que Polytope (def) Tetris, mas eu não posso roubar o nome.
5. “Standard Tetris” especificação
5.1 Introdução
A definição do “padrão Tetris” é um modelo idealizado das mais importantes características e comportamentos dos primeiros IBM-PC implementação do jogo Tetris (circa 1986-1988).
O modelo idealizado baseia-se em deduzir as aparentes intenções dos promotores do primeiro IBM-PC implementação do jogo Tetris.
Por exemplo, parece razoável inferir que os desenvolvedores do primeiro IBM-PC implementação do jogo Tetris destinado a selecionar a forma de cada nova queda peça “ao acaso,” e que a utilização do Borland C execução do rand() função era apenas uma aproximação das práticas a intenção.
A definição do “padrão Tetris” especifica que a forma de cada peça nova queda, deve ser seleccionados “aleatoriamente.”
Este comportamento ideal não pode ser alcançada por qualquer aplicação, mas implementações podem aproximar o comportamento ideal.
Apesar de não aplicação pode perfeitamente aplicar a definição da “norma Tetris,” os ideais de “Tetris Standard” envolvem características objectivas, e implementações podem ser comparados de acordo com a sua relativa proximidade com os ideais da “Standard Tetris.”
Esta seção descreve um conjunto de elementos, comportamentos, regras e que, coletivamente, definem “Standard Tetris.”
5.2 Standard Tetris bordo
O conselho de administração é uma grade de células, com 10 colunas, e de 20 linhas, para um total de 10 * 20 = 200 células.
Standard Tetris bordo (10 colunas, 20 linhas)
Cada célula pode ser desocupados (vazio) ou ocupados (completo).
5.3 Standard peças Tetris
Há sete (7) padrão Tetris pedaços, com os seguintes nomes carta:
{ O, I, S, Z, L, J, T }
Os nomes são inspirados por carta as formas das peças.
Os sete Standard peças e suas “orientações” Tetris
O dot (0,0) coincide com a posição (6,20) bordo quando a peça apareceu pela primeira vez.
A primeira coluna mostra as “orientações” iniciais.
Nos seguintes, o termo “orientação” é usado para descrever qualquer estado de uma peça, dentro de um conjunto de estados permitidos, que podem resultar de uma rotação counterclockwise evento.
Mudar de “orientação” a partir de uma determinada “orientação” de um “I, S,” ou “Z” peça, requer a combinação de uma rotação e uma tradução.
Portanto, a “orientação” palavra é usada aqui para significar algo mais do que rotação sozinho.
No entanto, a “orientação” pode mudar apenas em resposta a uma rotação counterclockwise evento, bem como o ciclo de distintas “orientações” para cada peça aproxima, ou jogos, o ciclo resultantes da pura rotações.
O uso da palavra especial “orientação,” neste contexto, é quase equivalente ao significado da palavra “rotação” ou “ângulo,” mas a “orientação” palavra é usada em vez de “rotação” a tentativa de aproximar a atenção para o facto de algumas peças exigem mais do que a rotação de produzir conjunto de estados permitidos resultante de acontecimentos counterclockwise “rotação.”
As peças só podem mudar de orientações (ou submetidos a um específico horizontal ou vertical tradução) se o estado resultante da peça não teria qualquer ocupados (completo) células além da área da administração e não teria qualquer ocupados células que qualquer sobreposição actualmente ocupados células do conselho de administração.
(Em esta regra, os ocupados (completo) células da peça, não são consideradas como parte das “células actualmente ocupados do conselho de administração”
Nos seguintes observações, qualquer referência a um resultado de um acontecimento counterclockwise rotação é feita com o pressuposto de que uma tal rotação pode realmente ser executada, tendo em conta as actuais condições da peça e do conselho de administração.
O “O” (casa) só tem uma peça única orientação, e não alterar os locais de qualquer um dos seus ocupados (completo) células em resposta a qualquer rotação counterclockwise evento.
O “I” (linha) peça tem duas possíveis orientações, inicialmente, aparecendo em uma orientação horizontal.
A peça “I” alterna entre as duas orientações em resposta a sucessivos counterclockwise rotação eventos.
O “S” e “Z” peças cada uma, duas possíveis orientações.
Estas peças cada alternam entre duas orientações em resposta a sucessivos counterclockwise rotação eventos.
O “L”, “J”, e “T” peças têm cada quatro orientações possíveis, e estas orientações são os resultados de cerca de rotações simples center pontos sobre as formas.
Quando uma peça primeira vez em que o conselho de administração, a peça tem o seu “eixo principal” de uma orientação horizontal, bem como a peça está no topo do tabuleiro.
Por isso, não peças são inicialmente capaz de ter mudado as suas orientações. A peça tem de descer por uma fila de ter a possibilidade de ter mudado a sua orientação.
Uma vez que um pedaço caiu em uma fila no conselho de administração, peça todas as orientações podem ser atingidos (assumindo que a peça não é demasiado próximo da paredes laterais ou para o atual pilha de peças).
5.4 Standard Tetris fluxograma
O que se segue é um fluxograma para aproximar um padrão Tetris jogo.
Aproximado de um fluxograma simples jogo Tetris
Aproximado de um fluxograma simples jogo Tetris
5.5 Standard Tetris peça criação
O diagrama a seguir mostra a (4 * 2 celular de células) no conselho de administração região onde aparecem quando todas as peças criadas.
Região onde aparecem quando criado em pedaços Standard Tetris
Quando uma nova peça primeira vez em que o conselho de administração, a sua origem coincide com o ponto sobre este esquema, e a peça será totalmente contida pela área sombreada sobre este esquema.
Quando um novo jogo é iniciado, uma plena queda livre demora decorre, e sobre a primeira iteração a queda-livre é uma peça desovado no topo do tabuleiro.
Durante o jogo normal, quando uma determinada queda livre iteração “terras” uma peça, uma plena queda livre e demora decorre na próxima iteração queda livre é uma peça desovado no topo do tabuleiro.
Quando uma peça é desovado, o tipo de peça é selecionada usando o seguinte algoritmo:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Porque há uma constante p (= 1/7) chance de seleção de um determinado tipo de peça, e todas as peças do mesmo tipo são indistinguíveis, a probabilidade de se ter exatamente k pedaços de um tipo específico após julgamentos n segue uma distribuição binomial:
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 )
Quando temos de escolher entre as 7 (sete) peças ao acaso, a probabilidade de obter uma determinada peça é p=(1/7).
Se o fizermos n=70 vezes, por exemplo, a probabilidade de obter exactamente k peças (com k na faixa 0 a n) é dada pela distribuição binomial, como mostrado na imagem seguinte.
Distribuição binomial para n=70, p=(1/7)
Assim, é possível prever a média total de peças de um único tipo de dado um número total de peças aleatória, e um também pode calcular o desvio padrão esperado e variância (raiz quadrada da variância):
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
Quando nos converter um valor aleatório para uma peça índice, nós interpretá-lo como se segue:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[O pré-comercial MS-DOS versão do Tetris utilizado o número aleatório funções oferecidas pela Borland Pascal compilador.
Essa função utilizada uma variável de 32 bits estado.
Por isso, a seqüência de números aleatórios foi limitada a 2^32 valores distintos.
Por isso, em princípio, um jogador poderá descobrir, depois de cair talvez 10 peças, o local exato, no conjunto de 2^32 números correspondentes ao actual estado do jogo.
Se Tetris simulações são executadas com o fixo seqüência de 2^32 pedaços e, em seguida, ideal decisões podem ser encontrados para cada lugar na seqüência.
(Parece haver oportunidades suficientes para estar a bordo de um Estado totalmente vazio bordo, permitindo-nos ter sincronizado com o pré solução óptima caminho.)
O risco de usar um simples gerador de números aleatórios, em uma simulação destinada a encontrar uma solução ideal para um problema que é a solução ideal será apenas para o caminho através do problema particular espaço seleccionados pelo simples gerador de números aleatórios. ]
5.6 Standard Tetris controles
Durante o jogo, estão disponíveis os seguintes factores:
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
Todos os insumos ter efeito sobre a subida de ponta do contributo positivo (a tecla imprensa, em oposição à libertação botão).
Ao pressionar um botão ocorre, esta conta como um pedido.
Segurando um botão para baixo além de um certo tempo pode resultar em “auto-repetir” a funcionalidade de um teclado, gerando novas prensas botão - mas esse recurso é externa para o jogo motor.
As entradas acima especificados conformes com o original jogo Tetris.
Rodar os pedidos podem ser executados se não houver uma sobreposição entre a orientação desejada e células conjunto sobre a actual administração (excluindo a queda peça) e, se a orientação desejada não tem qualquer conjunto células fora da área bordo.
Traduzir os pedidos podem ser executados se não houver uma sobreposição entre a configuração desejada traduzidos e células conjunto sobre a actual administração (excluindo a queda peça) e, se a configuração desejada traduzido não tem qualquer conjunto células fora da área bordo.
Entrada de pedidos são tratados com uma latência que depende da taxa de quadros de o jogo (exemplo: 75 Hz), e dos pedidos ter efeito (se válidos) instantaneamente.
A peça pode ser eliminados sem qualquer linha queda etapas ocorrendo.
A peça pode ser traduzida por diversas vezes à esquerda ou à direita, e, posteriormente retirada, todas sem experimentar uma linha oficial queda etapa.
Uma vez que um recém-desovado peça não pode ser girado (porque é furado contra a borda superior da placa), o jogador tem que aceitar, pelo menos, um pedaço queda passo se rotações são desejadas ou necessárias.
O efeito sobre a pontuação é insignificante.
5.7 Standard Tetris peça “aterragem”
Se uma peça é simplesmente cair, cai em uma única linha durante cada peça queda iteração.
Haverá uma iteração que move-lo a partir de um local sem nenhum contato com superfícies horizontais para um local que tenha contato com superfícies horizontais. Uma vez que isso ocorre iterações, as peças estão em contacto descansando.
Se uma iteração começa com uma peça em repouso contacto com uma superfície horizontal, a peça “terras,” e se torna parte da pilha estática.
5.8 Standard Tetris “linhas concluída”
Uma fila é preenchido um fila do monte em que todas as células são ocupadas. Quando concluída uma fila é eliminada a partir do monte, e as linhas acima da linha são eliminados deslocada para baixo em uma fila para eliminar o fosso, este conta como uma “linha” concluída.
Quando uma peça terras torna-se parte do baralho.
Imediatamente após a peça terras, a pilha está marcada para concluídas fileiras, e todas as linhas estão concluídas eliminados.
Até quatro linhas podem ser preenchidos simultaneamente.
A tabela a seguir apresenta o limite superior concluído em linhas simultaneamente por uma única peça:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Standard “níveis” Tetris
Standard Tetris tem 10 níveis de dificuldade, numeradas 1 (um) através 10 (dez), com nível 1 a ser o “menos difícil.”
O índice é o nível máximo de dois valores:
actualLevel = max( initialLevel, earnedLevel );
initialLevel O valor é o nível que o jogador escolhe quando se inicia um novo jogo.
O padrão de nível como uma função de linhas concluída é facilmente observado na fase pré-comercial MS-DOS versão de 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
Assim, o earnedLevel valor é calculado de acordo com o seguinte algoritmo:
if (linesCompleted <= 0)
{
earnedLevel = 1;
}
else if ((linesCompleted >= 1) && (linesCompleted <= 90))
{
earnedLevel = 1 + ((linesCompleted - 1) / 10);
}
else if (linesCompleted >= 91)
{
earnedLevel = 10;
}
5.10 Standard Tetris queda iteração demora
Standard Tetris em tempo real, tem um atraso entre sucessivas linha queda livre iterações que é uma função da dificuldade actual nível.
A seguinte relação entre nível e índice de queda iteração atraso é baseada em medições repetidas cronómetro em todos os níveis da pré-comercial MS-DOS versão de 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
Assim, temos a seguinte fórmula para determinar o valor iteração atraso como uma função do nível real índice:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Se o tabuleiro está vazio, e não há informações fornecidas pelo usuário, uma peça desovado em nível real 1 terras em cerca 10 segundos, e um pedaço desovado em nível real 10 terras em cerca 1 segundo.
5.11 Standard Tetris “pontuação”
Standard Tetris apenas prêmios pontos para o ato de uma peça desembarque.
Não há pontos concedidos para o ato de preenchimento de uma única linha, ou completando dois, três ou quatro linhas em simultâneo.
[Nota: Algumas variantes de Tetris adjudicação pontos para o ato de preenchimento de linhas, com um bônus para um aumento exponencial aumento do número de linhas simultaneamente preenchidos.
Assim, a estratégia de maximização de pontuação em tais variantes de Tetris envolve a criação de oportunidades para “obter uma Tetris,” usando a gíria para “I” forma simultânea para obter quatro linhas e recebendo lotes de pontos. ]
Se você tem um tabuleiro vazio, e você não deixar um pedaço “I” fazer uma queda livre e de terrenos, ou você imediatamente uma queda não-“I” peça, você pode definir o ponto seguinte tabela utilizando o pré-comercial MS-DOS versão de 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, não-“I” peças cair um total de 18 linhas.
Tal explica a diferença entre o ponto a queda-livre e instantânea-gota casos.
Por intermédio experimentação de casos, é fácil de deduzir o ponto seguinte fórmula:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Note que esta fórmula não tem nada a ver com a distância cai um pedaço!
É estritamente uma função do nível real, e uma penalidade para o número de iterações uma peça é deixado cair livremente.
Este castiga um usuário que necessitam de tempo para pensar.
Observe também que, porque uma peça não pode ser girado inicialmente no momento em que primeiro desovas, um jogador é punido por, pelo menos, uma queda livre iteração se rotações são obrigados a colocar uma peça na película.
Isso provavelmente nunca afeta humanos jogadores, a menos que algum modo: reconhecer a peça, pressione as teclas tradução “(à esquerda” ou “à direita),” pressione a tecla “rodar” uma ou mais vezes, e pressione a tecla “queda,” tudo dentro de menos de 0.5 segundo a nível 1, ou 0.05 menos, segundo a nível 10.
6. Standard estratégia Tetris
6.1 Introdução
Uma estratégia para jogar um jogo depende das regras do jogo.
Uma estratégia depende do parâmetro que está a ser otimizado.
Em Standard Tetris, uma sobrevive ao completar linhas, recebe pontos de desembarque pedaços, e as pontuações mais pontos possíveis para cada peça a execução de uma gota antes de uma ou mais iterações transpire queda livre.
Um A.I. possível otimizar os pontos atribuídos a cada peça simplesmente a decidir sobre a iniciativa de avançar rapidamente e “pressionando as teclas” para executar a jogada.
Mais importante para a sobrevivência é um A.I., porque significa uma sobrevida indefinida arbitrariamente pontuação elevada pode ser atingida. Devido ao facto de a cair em pedaços Tetris uma taxa específica, o A.I. deve tomar decisões, pelo menos, este rápido - e os A.I. deve fazer jogadas que completa as linhas a uma taxa média que pelo menos 1 linha por 2,5 peças. (Cada peça tem 4 células, e cada linha tem 10 células.)
Claro que podemos adiar a conclusão linhas acumulando peças e construir uma grande pilha, mas há apenas 200 células em todo o tabuleiro, que, em princípio, só podem deter 50 peças, de modo nenhum jogador (como um A.I.) devem ter completar as linhas uma prioridade fundamental.
Em Standard Tetris, o jogo inclui o estado actual bordo e ocupação do actual queda peça (tipo, posição e orientação). O jogo pode opcionalmente incluir o estado "Próximo Piece".
6.2 Uma seqüência de alternância "S" e "Z" pedaços
Heidi Burgiel, Ph.D., da Department of Mathematics, Statistics and Computer Science no University of Illinois at Chicago, provou que uma seqüência de alternância "S" e "Z" pedaços irá forçar uma norma (10-coluna, 20-fila) jogo Tetris para terminar dentro de um certo número previsível de jogadas.
Citação de o artigo: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Associado impressos artigo: Mathematical Gazette, julho de 1997, "How to Lose at Tetris"
Heidi Burgiel oferece uma Java applet que roda em um navegador Internet que apresenta um clone que alterou Tetris desovas alternância "S" e "Z" pedaços.
[O "Standard Tetris" software associados com o documento que está a ler também tem um modo que desovas alternância "S" e "Z" pedaços. ]
Heidi Burgiel alegou que um jogo envolvendo alternância "S" e "Z" pedaços (para um padrão Tetris conselho de 10 colunas e 20 linhas) deve terminar antes de menos de 70000 peças tenham diminuído.
A Norma Tetris software incluído com este documento permite que uma pessoa a jogar com alternância "S" e "Z" pedaços, e alterar a bordo de largura.
É fácil ver que placas cujas larguras são inteiros múltiplos de quatro colunas (exemplos: 4 colunas, colunas 8, 12 colunas, etc) pode ser jogado para sempre quando peças alternadas entre "S" e "Z", com a subida não rima mais elevado do que 4 linhas. Digo isto para que fique claro que a uma capacidade limitada de sobrevivência descrita na investigação referido documento é específico para o caso de uma norma Tetris bordo (com 10 colunas e 20 linhas).
6.3 Insolúvel peça seqüências em geral
Não há categorias inteiras de seqüências patológicas que não podem ser sobreviveu.
Seria interessante para calcular a probabilidade total de encontrar um jogo-encerra seqüência, porque isso iria colocar um limite superior sobre o desempenho de qualquer estratégia, mesmo com total conhecimento de todas as futuras peças em qualquer ponto em um jogo.
6.4 Total de configurações possíveis bordo
Tendo em conta que o conselho de administração tem 10 * 20 = 200 células, e dado que cada célula pode ser apenas em um dos dois estados (vazia ou ocupada), o número total de configurações bordo deve ser igual ou inferior a: (2 ^ 200).
Tendo em conta que cada peça acrescenta 4 células de um conselho, e cada linha conclusão de células a partir de 10 elimina a bordo, o número de células ocupadas no conselho de administração serão sempre mesmo. Por exemplo, (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, etc Assim, apenas metade do tabuleiro (2 ^ 200) configurações podem ser alcançados por jogar o jogo.
Assim, o número total de bordo é de aproximadamente configurações: (2 ^ 199) = 8.03469... * 10^59.
No entanto, não deve excluir a nossa total de qualquer configuração que inclui as linhas cheias, uma vez preenchidos filas são eliminados antes do final de cada jogada concluída. Qualquer configuração com uma ou mais filas cheias entrará em colapso para outra configuração que não contém qualquer preenchido linhas.
Além disso, devemos excluir qualquer configuração que inclui uma linha não vazia acima uma ou mais linhas vazias, porque um não-vazio linha acima será sempre uma linha vazia queda, e todos os pára de cair antes do final de cada jogada.
Cada linha pode ser na 2^10 = 1024 estados, um dos quais é "vazio", um dos quais é "completa", e (1024 - 2) = 1022-dos quais são parcialmente ocupados. Nós excluir o "pleno" processo de reflexão.
Se a linha inferior está vazio e, em seguida, todas as linhas acima da linha inferior deve ser igualmente vazia.
Se a linha inferior é ocupado parcialmente-e, em seguida, a segunda linha pode ser vazia ou parcialmente-ocupados.
Continuando nesta análise, podemos calcular um certo número de bordo configurações que leva em conta que a exclusão das linhas e completa as restrições às linhas vazias: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), ou seja, cerca ((1022 ^ 19) * (1023)).
Assim, nós encontramos uma estimativa mais precisa do número total de bordo estável configurações: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199); ou seja, cerca de 3,74% inferior à estimativa (2 ^ 199).
No entanto, o número real de estável, acessível bordo estados é susceptível de ser mais baixos devido nomeadamente ao facto de a maior parte de cima para linhas só pode ser preenchido de duas maneiras. Como a maior parte de cima para encher linhas, um recém-gerada peça não pode ser movida ou girada muito. Isso limita o número de maneiras de cima para a maior parte dos registros possam ser cheios.
6.5 Em princípio, a melhor jogada pode ser encontrado por qualquer peça conselho de administração e configuração
Porque nós podemos obter qualquer das sete peças possíveis para um dado bordo estado, o número total de estados é de aproximadamente 7 * (2 ^ 199) = 5.624... * 10^60 jogo.
Porque nós podemos, em princípio, fazer uma profunda pesquisa de todos os futuros possíveis para todas as jogadas possíveis para um determinado jogo Estado, podemos ter uma única "melhor" mover estado associado a cada jogo.
Presumimos que não temos acesso a qualquer informação que não seja o actual conselho de administração e atual peça, assim o "melhor" significa "passar o que oferece a maior chance de satisfazer o nosso objectivo de longo prazo de sobrevivência".
Uma mudança é apenas uma tradução (até 10 opções) e de uma rotação (até 4 opções), podemos facilmente codificar o melhor jogada em um único byte.
Assim, em princípio, poderíamos formar uma tabela com 10^61 entradas (bytes) disse-nos que a melhor jogada dado qualquer conselho estadual e atual peça.
É claro que isto é impraticável, assim como a enumeração de todos os "Go" tábuas ou "Chess" placas é impraticável. Mas o ponto é que há uma verdadeira solução, e há uma melhor jogada para qualquer configuração determinada. Poderá haver igualmente boas jogadas para uma determinada configuração, mas podemos escolher arbitrariamente um único movimento nesse caso.
Muitos jogo-jogando algoritmos têm tabelas que enumerar exaustivamente todas as possibilidades no jogo estado limitado contextos, tais como a "abertura (inicial) move" ou "final de jogo (final) move", em Xadrez. Talvez enumeração exaustiva das superfícies Tetris pilha (aproximadamente (20 ^ 10) estados) é viável. É uma ideia interessante.
Enumeração exaustiva de todos os estados das duas linhas abaixo, multiplicado pelos sete peças possível, e armazenando a melhor jogada em um único byte, seria muito fácil, exigindo apenas 7 MB de memória. Talvez otimização de desempenho para esses sete milhões de casos iria fornecer dados brutos para ambas as análises eo desenvolvimento de modelos simples de dados, tais modelos poderiam ser consideradas como parte de toda a estratégia ideal Tetris-playing.
Note que executa as melhores jogadas ainda não nos proteger contra eventuais jogo patológico peça encerra-seqüências. É exatamente isso que vamos executar movimentos sempre que nos oferece o máximo potencial de sobrevivência futura, dado que todas as futuras peças são totalmente aleatórios (e desconhecidos no momento em que nós estamos a decidir sobre a forma de passar uma única corrente conhecida peça).
6.6 Em tempo real de desempenho
Um constrangimento enfrenta alguns algoritmos estratégia é a necessidade de desempenho em tempo real - o que significa que o algoritmo deve tomar uma decisão dentro de um determinado período de tempo.
Quando um homem joga Tetris, as peças não param queda de dar ao jogador a oportunidade de pensar. Isso é parte do desafio de Tetris. Assim, A.I. um sistema que é utilizado para simular o papel de um jogador humano deve também tomar decisões a um ritmo ditado pelo jogo Tetris.
6.7 Row e peça totaliza
Note que, no longo prazo, diminuiu o número de peças é muito próximo de 2.5 vezes o número de linhas concluída - porque cada linha tem 10 células, e cada peça é de 4 células, e temos de completar uma linha, em média, uma vez a cada (10/4) = 2.5 pedaços caiu.
Assim, podemos usar "concluídas as linhas" e "caiu pedaços" quase indiferentemente com a devida proporcionalidade constante. O maior erro é quando o tabuleiro está completamente preenchida com excepção de um único diferencial em cada linha (((10*20)-20)/4) = 45 pedaços caiu, mas uma deficiência do previsto (45/2.5) = 18 concluída linhas.
6.8 Actual-peça (e de bordo) estratégia
Se nós só permitem a A.I. de ter conhecimento do actual conselho de administração e os actuais peça, e nós apenas considerar o resultado do movimento atual da peça, em especial as formas, então isso pode ser chamado de um "pedaço" análise.
Aqui está um esboço rudimentar do modo como uma peça-uma análise pode decidir por uma jogada no Tetris:
Actual-peça análise de um jogo Tetris estado
Basicamente tentamos todas as jogadas possíveis e escolher o movimento que gera o melhor resultado.
A parte difícil é rating cada resultado.
Temos de avaliar um jogo hipotético estado de acordo com a forma como um tal estado suporta o nosso curto prazo e metas de longo prazo.
O nosso objectivo a longo prazo é sobrevivência. Sobrevivência depende de evitar que a pilha de superlotados a bordo. Nós podemos reduzir a pilha altura, formando linhas completas que são posteriormente eliminados a partir da pilha.
Para formar uma linha completa, temos de encaixar partes de peças em que a coluna de cada linha. Assim, solicitamos a todas as partes de uma fila para ser exposto ao cair pedaços, se quisermos acabar preenchimento de toda a fileira.
Se por alguma razão, até cobrir vazios de partes de uma linha por peças em qualquer linha superior e, em seguida, agora somos incapazes de preencher os vazios partes da fileira. A única forma (assumindo que nenhum deslizamento) para aceder a esses "enterrado buracos" é a eliminação das linhas acima que tenham partes agindo como obstáculos.
Os seguintes fatores estão entre os que podemos usar para avaliar um determinado estado bordo:
Overall pile height
Quanto maior a pilha, o pior parece ser a nossa situação, porque estamos mais perto de superlotados a bordo.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
O rougher a pilha, o mais provável é que será difícil de preencher em todos os contornos do complexo embutido que eles estiverem expostas à superfície.
Number of buried empty cells
Quanto mais buracos temos enterrado, a nossa situação é pior, pois temos de descobrir enterrado buracos antes que possamos concluir as correspondentes linhas.
Você pode imaginar outros fatores que geralmente a bordo de uma hipotética taxa bem como a sua pilha pode acomodar todas as peças do futuro possível, e como boa a situação olha para todas essas peças possível.
A próxima questão é o modo de determinar a importância relativa destes factores.
Uma abordagem geral é a seguinte. Atribuir um conjunto de "peso" (importância relativa) para estes factores e, em seguida, simular inúmeros jogos e gravar o resultado destes jogos (pontuação final, etc). Em seguida, atribuir um novo conjunto de pesos e simular um novo conjunto de jogos. Baseia-se na existência ou não da nova série de jogos tiveram melhores resultados do que o anterior conjunto de jogos, sabemos se o novo conjunto de pesos foi melhor que a anterior conjunto de pesos.
No meu próprio experimentos Tentei sistemática pesquisando e procurando por acaso boas combinações peso, mas eu não detectar quaisquer tendências de larga escala que eu poderia prosseguir. No entanto, eu vi muitas surpreendentemente bom solavancos. Eu pensava que era interessante que o desempenho médio poderiam formar uma curva suave quando um parâmetro foi lentamente variado com os outros parâmetros realizada em algum valor combinação.
O melhor tempo real, uma peça de Tetris algoritmo em todo o mundo, criado por Pierre Dellacherie (França) em 2003, deve muito de seu sucesso ao seu conjunto de medições (ou métricas). Encontrar pesos quando é necessário otimizar a uma estratégia, mas é também crítico para começar com os tipos de medições que revelam as características pertinentes do estado.
Pierre Dellacherie's invenção de novas formas para caracterizar a bordo de cada um faz o seu algoritmo realmente excelente; o conselho de administração caracterizações capturar os importantes dimensões estratégicas do conselho de administração estadual.
Poder-se-ia desenvolver um conjunto de caracterização muito diferentes dimensões que trabalharam igualmente bem, estou confiante de que é possível atravessar a bordo de estado relevante espaço de muitas formas diferentes que podem ser usadas para especificar uma estratégia funcionar. A chave é encontrar características que o projeto do estado espaço para baixo para uma série de pequenas dimensões que podem ser usados para desenvolver uma função simples classificação (exemplo: o linear ponderada combinações de características utilizada pelos Pierre's algoritmo).
A peça-um algoritmo utilizado pelo "bot" no "xtris" software (1996) escrito por Roger Espel Llima usa pesos determinados por uma exploração em larga escala de possíveis combinações peso por "algoritmos genéticos". Simulated Annealing é possível uma outra forma de explorar o espaço multidimensional de peso combinações.
Parece que, com base em várias observações, o Tetris multidimensional função da média como uma função da performance dos pesos, por exemplo: F(w1,w2,w3,...), é "grosseira" (local de lotes mínimos e máximos), o que significa que uma simples multidimensional "subir morro" poderá não funcionar.
6.9 Estratégia momento atual peça, próxima peça, e de bordo são conhecidos
Se uma estratégia algoritmo é dada a actual peça, próxima peça, e de bordo e, em seguida, ele pode tomar decisões que tirem partido da combinação de peças.
O conhecimento da próxima peça pode melhorar o sucesso de um algoritmo Tetris jogando por várias ordens de grandeza. É fácil compreender como o conhecimento da próxima peça faz uma grande diferença na estratégia.
Pode-se fazer "louco" se move, como abrangendo enormes buracos, etc, porque eles já sabem que a próxima peça pode ser usada para "corrigir" a situação. Se você não tem conhecimento da próxima peça, que estão constantemente a tentar reproduzir a contradição, tentando manter suas opções em aberto, caso a próxima peça não é o ideal.
O esquema seguinte mostra como todas as jogadas possíveis do actual peça são considerados, e para cada uma dessas jogada que consideramos todas as jogadas possíveis envolvendo a próxima peça.
Estratégia envolvendo atual e próxima peça peça
A Norma Tetris software usa essa estratégia quando o "Próximo Piece" é ativado pelo usuário e é visível na tela, e quando um pedaço de dois A.I. está ativado (como a um escrito por mim, Colin Fahey). Se o "Próximo obra" não é visível na tela, os meus dois-uma peça cai de volta para uma peça-A.I..
Meu uma peça-A.I. é terrível, quando comparado aos outros AIs na Norma Tetris software; tão presente mostra-lhe benéfica mais informações (por exemplo: a próxima peça) pode ser o de um sistema A.I.; é o suficiente para melhorar o desempenho da minha própria medíocre de dois pedaço A.I. por várias ordens de grandeza - facilmente superando o desempenho das melhores-um pedaço A.I. no mundo.
(No entanto, convertendo-o melhor um pedaço A.I. em todo o mundo a considerar duas peças seriam facilmente melhorá-lo por várias ordens de grandeza, também! Conhecendo a próxima peça é enorme!)
Meu primeiro teste com o meu jogo de duas peças A.I. durou aproximadamente 182 horas (7,6 dias) em um 800 MHz PC, completando 7216290 linhas. Eu não testei o algoritmo em um computador mais rápido.
Quando você salvar o estado de um jogo Tetris (Shift-W) para um arquivo texto, então você pode copiar e colar a lista de números, a partir da secção "heightHistogram", para uma planilha Excel.
Cada contentor no histograma indica o número de jogadas que completou terminou com uma pilha especial altura (após completar as linhas são eliminados). Como você pode imaginar, fazendo um movimento que elimina totalmente uma pilha é raro, de modo que o número total de jogadas que termina com uma pilha de altura zero é relativamente baixo.
Enquanto isso, você pode esperar que a pilha altura geralmente oscila em torno de alguns média, de forma tulhas correspondentes a estas linhas vão dominar o histograma. Por último, tulhas para a maioria dos top-filas (onde estamos em perigo de superlotados o conselho de administração) têm muito baixas totais.
Ao longo de muitas horas, com a A.I. jogar um único jogo usando a estratégia que envolve o conhecimento da "Próximo Piece", eu levei amostras aleatórias do jogo Estado, copiando a pilha histogramas a altura de uma planilha como mostrado a seguir:
Pilha de altura histogramas registados em diversos pontos em um típico jogo (com a actual-e-próxima estratégia de peça)
Você pode escala cada histograma com o número total de peças (número total de movimentos concluído) para obter os seguintes dados:
Redimensionado histogramas, e uma teoria
O notável é que estes escalados histogramas olhar idênticos apesar das diferentes ordens de grandeza do número de peças (concluída move) envolvidas.
Basta olhar para os números em que fiz a hipótese de que a cauda da curva exponencial é uma decadência. Por tentativa e erro me apareceu com a teoria de que a cauda do avião acidentado foi descrito por:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
O gráfico seguinte mostra o histograma escalonada ao longo de todo o leque de linhas.
Gráfico de escaladas histogramas
Note que a curva de 50000 peças, bem como a curva de 2000000 peças, bem como a curva da cauda teoria são quase indistinguíveis a esta escala.
O que se segue é um olhar mais atento à frente da curva.
Parte de baixo altura histograma
O que se segue é um imenso-ampliada da extrema cauda final da medida e teórica histograma curvas.
Vista ampliada de extrema cauda final de escaladas histogramas
Como você poderia esperar, é muito raro que a pilha de chegar a estas alturas, mesmo em longos experimentos - mas mesmo com os nossos limitados provas neste extrema região, a teoria ainda parece aceitável.
Na tabela completa a teoria parece a sobreposição da cauda da distribuição "exatamente", enquanto no gráfico ampliada do rabo do rabo, vemos aparente erro. No entanto, devo afirmar que este é devido à insuficiência de dados para estas alturas extremas pilha. Se eu aumentou o tabuleiro de jogo para, digamos, uma altura de 25 linhas em vez de 20 linhas, de modo que os jogos não encerrar abruptamente, penso que a teoria eu teria apresentado acima coincidem perfeitamente com a tendência.
O meu sentimento é que este é um histograma directo resultado combinado do Tetris A.I. e as regras de Tetris. Portanto, esta mesma distribuição será observada por qualquer aleatória de longo prazo do jogo Tetris usando o meu particular A.I. estratégia para brincar com o "Próximo Piece" conhecimento.
Além disso, penso que este tipo de histograma pode ser usado para comparar AIs que empregam as mesmas informações ao jogar. Assim, você não tem que jogar jogos completos (o que pode durar dias ou anos) para comparar o desempenho de longo prazo da estratégia diferente algoritmos.
Por exemplo, apesar da simplicidade do meu modelo, eu acho que pode ser usada para prever a duração média jogo! Nós simplesmente descobrir quantos pedaços faz a "linha 21" pilha altura um número significativo, tais como a contagem de um.
A freqüência relativa à linha 21, de acordo com a minha simples teoria, é o seguinte:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Você deve multiplicar esse número por (5.3 * 10^(7)), cerca de 50 milhões de euros, para obter um valor de um.
Assim, eu praticamente prever que o meu atual "Próximo Piece" estratégia só é bom para a ordem de aproximadamente 10 milhões de linhas concluída. Uma razão me fazer essa estimativa conservadora, é o fato de que até mesmo 18 linhas pode ser mortal para o meu A.I. porque eu não permitem considerar a minha A.I. peças até que tenha caído em pelo menos uma fila! (É assim que eu não têm que se preocupar com a não ser capaz de rodar peças.)
Estou impressionado com o facto de jogar apenas 50000 unidades (e possivelmente muito menos peças) pode dar-lhe uma muito boa estimativa da altura histograma de longo prazo e, consequentemente, uma boa estimativa da ordem de grandeza de linhas concluída antes do jogo termina. Esta abordagem é extremamente valioso para avaliar rapidamente sutis mudanças em um A.I. que já está a fazer muito bem.
6.10 Câmara avaliação métricas imitá-especulativa olhar em frente
Se um algoritmo, como a que me apresentou a este projecto, simplesmente tenta todas as traduções e peça orientações para cair, e as taxas resultantes bordo de cada configuração de acordo com alguma medida de mérito, o algoritmo é essencialmente imitando "antecipado".
Quando um emprega métricas, como a "pilha altura", "enterrado buracos", "rugosidade superficial" ou "bem profundidades", é uma realidade através de uma forma simplificada de "olhar em frente". Estas caracterizações geral do conselho de administração dar alguma indicação sobre a viabilidade a longo prazo do conselho de administração.
O ideal abordagem, dada uma infinita quantidade de computação poder, seria a de avaliar um conselho dado todas as configurações possíveis seqüências peça que pode seguir.
Embora você deve considerar todas as 7 peças como sendo igualmente provável em cada nível do olhar de frente, você precisa otimizar as traduções real (até 10) e orientações (até 4) para cada peça, em cada seqüência possível! Isso é até (7*10*4) = 280 sucursais em todos os níveis da avaliação bordo! Então, isso é até ((280)^(LookAheadLevels)) bordo configurações de considerar.
Porque temos de encerrar a análise após um número finito de níveis, precisamos ter alguns não olhar em frente-método de avaliação do estado bordo - uma forma de dar aos valores para a folha gânglios da nossa pesquisa árvore. Portanto, para estes folha nós, estamos de volta para usar uma fórmula que encarna geral preditores de viabilidade futura do conselho de administração!
Este tipo de especulação pode ser tentado com os One Piece-e-Piece Dois algoritmos em lugar de a bordo simplista avaliação métricas. Assumir todas as peças são igualmente provável ea soma das capacidades de um conselho para acomodar todos os tipos de peças, da melhor maneira possível. Isso pode ser realizado com um, dois, ou de qualquer movimento especulativo número de profundidades - com todas as peças sendo igualmente provável (p=1/7).
O terminal de nós esta árvore ainda poderá vir a exigir a ponderação métricas para avaliar, mas o especulativo camadas mais precisamente captar a essência daquilo que queremos fazer: determinar o desempenho de um determinado bordo pode aceitar todas as peças, incluindo factores positivos, tais como linhas completando e de factores negativos tais como o aumento global de pilha altura, etc
7. Tetris A.I. sistema de demonstração
7.1 Sistema de visão
Este diagrama seguinte mostra a minha experimental set-up.
Sistema global para a demonstração
7.2 Equipamento
Aqui está uma breve lista dos equipamentos utilizados nesta demonstração:
[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)
É claro que você pode usar equipamento similar para conseguir os mesmos resultados. Mais detalhes sobre os equipamentos estão descritos nas correspondentes secções do presente artigo.
Aqui estão breves descrições dos computadores pessoais usados nesta demonstração:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Esta manifestação poderia facilmente ser reproduzido em outros sistemas operacionais, tais como Linux. É mais importante ter um CPU velocidade da ordem de 800 MHz ou mais rápido para o computador que está a correr o A.I. software, porque este computador será feito em tempo real de processamento de vídeo.
7.3 Vídeo captura hardware
Eu usei uma câmera comum USB vídeo como um dispositivo de captura vídeo A.I. meu sistema. Especificamente, eu usei a Creative "WebCam Pro", uma câmera com USB vídeo 640 * 480 resolução.
Creative(TM) USB câmaras vídeo descrição
USB câmaras vídeo (em ângulo)
USB câmaras vídeo (frente)
USB câmaras vídeo (bordo com CCD)
USB câmaras vídeo (principal chips)
OV511 principais blocos (nota: USB vídeo câmera é OV511+)
7.4 OV511 ficha
ov511ds.pdf
OV511 fichas de dados
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "plus") característica diferenças
ov511plus_101.pdf
OV511+ característica diferenças
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Vídeo captura software
Microsoft tem uma estrutura muito antiga API chamado "Video for Windows" (VFW) que eu utilizado com sucesso para este projecto. (Você link para "vfw32.lib" C++ em seu projeto, ou fazer uma DllImport de "vfw32.dll" C# em seu código.) Exemplos de utilizar o VFW API estão amplamente disponíveis.
Uma alternativa é usar Microsoft's "DirectShow" API para fazer captura vídeo.
Porque VFW teve apenas uma dúzia de linhas de código de usar, e realizada em aceitavelmente 800 MHz minha máquina, eu não incomodar a explorar a alternativa APIs. Mas DirectShow é uma forma mais contemporânea API para Windows vídeo captura, rendimentos e, potencialmente, uma taxa muito mais elevada moldura para o mesmo hardware.
Olhe para o "CPF.StandardTetris.STVideoCapture" código fonte em arquivos do Standard Tetris software para ver como é fácil chegar em vídeo para capturar os seus próprios projectos.
7.7 Computer interface de relés (via RS232)
Para que um computador "pressione as teclas" no teclado do outro computador, eu usei um "relay bordo" controlada pelo texto comandos enviados a partir de uma porta de comunicação serial (exemplo: "COM1") através de um cabo RS-232. Eu costumava cada relé para ligar os dois fios de uma tecla específica teclado para simular uma chave imprensa.
Para isso foi necessário abrir o teclado e fazer ligações. Existem muitos métodos mais fáceis para simular pressionando a tecla de um computador, mas eu queria fazer algo que parecia o mais próximo possível de uma pessoa realmente digitando num teclado.
Um muito versátil e bem-feito relay ADR2200 a bordo é feita por Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Você pode olhar para o "CPF.StandardTetris.STRS232" ficheiros de código fonte para ver como é fácil enviar bytes através de uma porta serial, que pode ser usado para controlar dispositivos como o ADR2200 bordo mostrado acima.
8. Standard Tetris software
8.1 Download de software
Ir para o início deste artigo para encontrar um link para baixar o código fonte (C# e C++ versões) e construída software (*.exe).
8.2 Resumo das Características
Software características:
Instrução telas e créditos
Modo monocromático
Modo de Sombra
Sugestão Modo
Lixo filas
Taxa de controlo
Próxima peça
Câmara tamanho
S/Z pedaços
Modo de Calibração
Video captura e reconhecimento
Depuração console
Salvar jogo
Carga jogo
8.3 Começando aparecimento
Aspecto quando o software for iniciado:
Aspecto quando o software for iniciado
8.4 Modo monocromático
Por padrão a bordo aparece em cor:
Por padrão a bordo aparece em cor.
A cor pode ser alterado para o modo monocromático (Shift + K):
A cor pode ser alterado para o modo monocromático.
8.5 Modo de Sombra
Shadow modo indica onde uma peça vai aterrar. Isto é muito útil para os conselhos muito grande, porque é difícil julgar onde terá um pedaço terra.
Shadow modo indica onde uma peça vai aterrar.
8.6 Sugestão Modo
Sugestão modo mostra-lhe onde atualmente o AI-seleccionados seria possível avançar devido à actual situação. (Shift + H)
Sugestão modo mostra o momento em que iria mover-selecionados AI.
8.7 Lixo filas
Inserir "junk" linhas na parte de baixo da pilha, uma por uma, manualmente. (Shift + J)
Inserir "junk" linhas na parte de baixo da pilha.
8.8 Taxa de controlo
O '+' (mais) e '-' (menos) chaves controlar a velocidade do jogo.
Por defeito, o jogo é executado em uma velocidade normal, de acordo com as regras da Norma Tetris (velocidade base no nível).
Aqui está uma tabela dos sentidos da velocidade viés:
-3,-4,...: lentidão proporcional ao preconceito
-2: mais lento do que o nível 1
-1: normal, mas limitada ao nível 6 (0,2 seg) velocidade;
0: normal; Standard Tetris regulamentação da velocidade;
+1: ligeiramente mais rápido do nível 9 (0.05 sec atrasos);
+2: delimitadas por taxa de renderização (exemplo: 75 Hz);
+3,+4,...: várias iterações prestados por frame;
Eu gosto de correr o A.I. em uma configuração de "+2" (hit '+' tecla duas vezes viés se inicia em zero).
Velocidade viés altera a velocidade do jogo.
8.9 Mostre a próxima peça
Hit "N 'para alternar o" Próximo Piece "visor. O A.I. irá utilizar o "Próximo Piece" informação apenas se o "Próximo Piece" aparece na tela.
Você pode estar certo de que a AI não está usando "Próximo Piece" informações quando você não pode ver o "Próximo Piece" na tela.
Mostrar a próxima peça
8.10 Câmara tamanho
Pressionando Ctrl + (esquerda, direita, para baixo, até), pode ajustar a bordo de um tamanho arbitrário de tamanhos de 4 * 4 até 200 * 400.
Câmara tamanho: 4 * 8
Board Size: 20 * 40
Board Size: 40 * 80
Board Size: 20 * 5
Câmara tamanho: 4 * 100
8.11 S/Z peças só
Estudo da alternância S/Z padrão interessante.
Este padrão não pode ser resolvido por um 10 * 20 bordo (largura * altura).
No entanto, tábuas que têm larguras que são múltiplos de 4 são mostrados trivialmente para permitir a sobrevivência infinita.
O AIs sobreviver indefinidamente, nestes casos, mesmo que não fossem especificamente sintonizado para lidar com esta situação patológica.
S/Z peças só
8.12 Vídeo de calibração Modo
Hit "C 'para entrar" Calibração Mode ". Quando estiver em modo de calibração, você pode pressionar as teclas numéricas: {1,2,3,4,5,6,7} para selecionar um pedaço {O,I,S,Z,L,J,T} no topo do tabuleiro jogando.
Isso é útil como uma referência para a imagem do vídeo captura em um segundo Standard Tetris software.
Se você acertar o 0 (zero)-chave, ela irá tornar o conselho de administração em branco.
Você pode fingir que desovam peças por seleccionar um pedaço (1..7) e, em seguida, selecionando um (0) em branco, enquanto um segundo computador a fazer vídeo para capturar relógios peças.
Você pode executar o A.I. sobre o segundo computador e ver como ele lida com o seu manual entrou patológica Tetris cenários!
Modo de calibração é a única vez em que você pode manipular o video da captação de processamento de imagem modelo (4 * 2 grid). Você pode usar o mouse para desenhar o retângulo, mas então você pode usar as teclas do cursor ( "up", "prevê", "esquerda", "direita") para ter o controle de fronteiras multa - usando a tecla para seleccionar Shift oposto fronteiras do rectângulo (exemplo: "Shift-esquerda" combo é diferente de "esquerda").
Vídeo de calibração Modo
8.13 Video captura e reconhecimento
Pressionando "V 'alterna Modo de captura de vídeo. Se for devidamente calibrada (ver "video calibragem", em uma seção anterior), os pedaços de uma tela remota vídeo será capturado pela câmera de vídeo e classificados - e as peças serão desovado no local do jogo para o A.I. a analisar ea reagir .
O A.I. saída deve então ser transmitidos (através da interface RS-232 na demonstração descrito no presente artigo) para fazer face ao afastamento jogo entrada (exemplo: teclado) para o A.I. para desempenhar com êxito as remotas jogo.
Se em algum momento deste ciclo fechado é perturbado (exemplo: video captura disfunção, avaria ou sinal de saída), então a A.I. irá desenvolver uma falsa impressão sobre o estado do jogo remoto, e irá tornar a A.I. decisões inadequadas que rapidamente perder o jogo .
(Nota: Este problema pode ser ultrapassado com uma modesta quantia de esforço: A.I. O sistema precisa apenas analisar a totalidade do ecrã Tetris remoto para um curso "realidade" de toda a bordo, e A.I. o sistema deverá estar preparado para alguns comandos de saída falhar em algum modo.)
Video captura e reconhecimento
9. Original Tetris AI experimento (2003)
A seguir mostra a primeira versão de trabalho do Tetris A.I. sistema em 2003.
Video # 1 câmera enfrenta computador rodando qualquer jogo Tetris planície
Computador # 2 Standard Tetris software rodando em modo A.I.
Esquerda: Desenho grid para calibrar imagem vídeo reconhecimento;
Direita: Tetris peça reconhecimento casos.
Frame de vídeo de Tetris A.I. experimento, em 2003
10. Melhor uma peça-Tetris-playing algoritmo no mundo
10.1 Pierre Dellacherie (2003; França)
Pierre Dellacherie (2003; França), o desenvolvedor de uma melhor peça-Tetris-playing algoritmo no mundo
O melhor de peça única, em tempo real de Tetris algoritmo para o meu conhecimento foi criado por Pierre Dellacherie da França.
Sua surpreendente algoritmo vezes enche mais de 2 milhões de linhas!
O desempenho médio é da ordem de 650000 linhas.
O algoritmo tem muito pouca memória, e roda em alta velocidade (cerca de 160 linhas por segundo em 800 MHz meu computador).
Desempenho do algoritmo Pierre Dellacherie's:
A minha actual modelo para o desempenho de Tetris autenticidade é que para qualquer dado peça há uma constante probabilidade de que o jogo irá encerrar, p.
Assim, a probabilidade de que uma peça não vai encerrar um jogo é q=(1-p).
A probabilidade de o jogo encerra após k move é simplesmente o produto da probabilidade de sobreviver (k-1) move, ou seja, q^(k-1), e que a probabilidade de o rescindir sobre o próximo movimento, ou seja, p.
Isto corresponde a um "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 )
Para as pequenas p, ln(q) é aproximadamente (-p), e nós temos o seguinte:
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 )
Esperamos que a fração do número total de jogos jogados para encerrar com uma série de linhas concluída no intervalo [k1, k2] a ser:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Após completar 36 jogos no meu computador, durante um período de dois dias, eu encontrei uma média de 674827 concluída linhas.
De acordo com a teoria geral acima, gostaria de esperar o seguinte parente fração de jogos para terminar na fila intervalos preenchidos os seguintes:
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
Aqui está um gráfico que compara a teoria com a observada Exponential Distribution distribuição de jogos.
Desempenho do algoritmo Pierre's completou mais de 36 jogos
Ainda há muito poucos jogos neste conjunto de dados, verifica-se que o modelo é bastante bom em observar a distribuição de correspondência.
Pierre's introdução ao seu algoritmo:
Pierre iniciou os trabalhos sobre esta peça de um algoritmo de 2003,1.
Pierre me enviou um e-mail sobre o seu algoritmo sobre 2003.4.9, denunciando o seguinte desempenho ao longo de 20 jogos consecutivos:
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.
"O algoritmo é implementado em 7000 e completa Turbo Pascal linhas / min. Athlon 1600+ com uma."
Eu convertido Pierre's algoritmo para C++ em 2003,6, depois de várias trocas de e-mails com Pierre. Verificamos que o A.I. no C++ versão fez a mesma decisões do Pascal versão.
Eu observado um comportamento semelhante ao seu relatório original; média de cerca de 650000 linhas concluída, e alguns jogos completando 2 milhões de linhas.
Incrível!
10.2 Conversas com Pierre Dellacherie
[1] Quando você fez o primeiro criar esse código?
Eu já trabalho com o algoritmo final de janeiro de 2003 até agora.
[2] Há quanto tempo você trabalhou com ele?
Eu trabalhei com ele quase todas as semanas ... mas não todos os dias longos, porque tenho outras atividades: infelizmente tenho de ganhar dinheiro como ninguém!
[3] O que inspirou o design do código?
Eu jogado Tetris 10 ou 15 anos atrás, mas eu não tivesse jogado novamente por um longo tempo. Eu diria que sou uma "média" jogador que conhece as regras e alguns truques.
No entanto, quando eu comecei a trabalhar com o algoritmo que eu não jogar tanto porque eu achei que era bastante mais eficazes para assistir a jogar computador e analisar seus pontos fracos.
[4] Você quis usar qualquer automação para “formar” o seu código para um melhor desempenho? Você tem algum comentário para melhorar o algoritmo?
Ou você simplesmente assistir os resultados e decidir fazer modificações?
Estou de “idade escolar:” Eu simplesmente assistiu os resultados e decidiu fazer modificações.
"Automática de aprendizagem" é um tipo de meta-algoritmo não estou tão certo de que iria fazê-lo desta maneira mais fácil obter uma vez que esta meta-algoritmo teria de ser construído e que também não é assim tão fácil!
Além do mais, eu concordo com Roger Penrose quando ele diz (em seu livro "Shadows of the mind") que a compreensão ea intuição humana não pode ser algorítmica (por exemplo: computável).
[5] Quando você fez o primeiro começar a jogar Tetris, e quando você tem a idéia de resolver um Tetris com A.I.?
Eu ensino algorítmicos e programação informática (Turbo Pascal e Scilab) para alunos que treinam para ingresso exame graduação em engenharia da escola.
Na primeira, "Computer desempenha Tetris" Foi uma idéia que gostaria de desenvolver no próximo ano para os meus alunos.
Eu não tinha conhecimento da sua página da web quando eu comecei a trabalhar com o algoritmo.
Na verdade eu tive sorte de estar conscientes de sua página da web apenas algumas semanas atrás, porque eu acho que teria sido desencorajado por seus resultados (como você pode imaginar, as versões iniciais do meu algoritmo não joga tão bem!).
[6] Qual é o seu estado atual?
Estou quase 30 [antes de 2003 abril 27]. Eu tenho várias atividades: Eu sou um cellist, eu me ensinar compor músicas e programação informática.
Eu tenho um mestrado em musicology (1994) e um "Artificial Intelligence and Algorithmic" diploma (1998).
Em França, este diploma corresponde ao 5 º ano estudando na Universidade (4 º ano é o mestrado e 6 º ano é a tese).
Pierre's composições:
[7] Onde você mora?
Eu sou francês e moro em Rouen (Normandia).
[8] Outras observações:
Eventualmente eu não tenho qualquer ideia nova para a melhorar.
Eu tenho tentado tanto inútil (e idiota) coisas que duvido que pode ser melhorado.
Por outro lado, penso que se poderia existir completamente diferentes algoritmos que poderia ter um melhor desempenho.
A propósito, um rápido teste consistirá no lançamento de as peças em uma meia-box (10 linhas X 10 colunas): em um meio-casa, meu algoritmo faz uma média de 280 linhas concluída.
Só mais uma coisa: o algoritmo pode ser facilmente modificado de uma dupla cruzam permanentemente algoritmo ([vou fazer] os testes em breve).
Eu adoro cinema: tornar-se um filme compositor faz parte dos meus sonhos principal (mas é apenas sonho!).
11. Melhor jogador do mundo humano
11.1 Tetris japonês Master (2001 janeiro 27) video
Tetris mestre (2001; Japão) video
Arika apresenta o japonês Tetris Finals mestre (2001 janeiro 27). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Resposta
12.1 Slashdot thread (2003)
Em 2003, meu Tetris A.I. projeto foi discutido sobre o fórum Slashdot Internet (
http://slashdot.org).
Slashdot (http://slashdot.org) Internet manchete fórum para a discussão do meu projeto Tetris A.I.
Benefactor of mankind--thank you! (Score:4, Funny)
by EnlightenmentFan (617608) on Tuesday January 28, @02:29PM
(#5176294)
(http://betsydevine.weblogger.com/ | Last Journal: Tuesday
January 21, @01:55PM)
Now I can set up computer #1 to play an infinite, obsessive
game of Tetris on computer #2, leaving me free at last to sit
down at computer #3 and get some work done. The $200 for
webcam and other hardware is cheap for an invention like this,
with the revolutionary potential of the wheel, or fire, or
even pizza delivery.
Thank you! Thank you! Thank you!
[ Reply to This ]
The New 4th law... (Score:5, Funny)
by gokubi (413425) on Tuesday January 28, @02:09PM (#5176135)
(http://www.gokubi.com/kinggeorge)
1. A robot may not injure a human being, or, through inaction,
allow a human being to come to harm.
2. A robot must obey the orders given it by human beings
except where such orders would conflict with the First Law.
3. A robot must protect its own existence as long as such
protection does not conflict with the First or Second Law.
4. A robot must never place the long skinny ones horizontally,
unless it leads to a long skinny vertical hole so 4 rows can
be cleared at once the next time a long skinny one comes
around.
[ Reply to This ]
Re:The New 4th law... (Score:5, Funny)
by GuyMannDude (574364) on Tuesday January 28,
@02:14PM (#5176179)
I thought Directive 4 was that any attempt to arrest a
senior officer of OCP Corporation would result in
immediate shutdown!
GMD
[ Reply to This | Parent ]
Comic inspirado pelo meu Tetris A.I. projeto (2003) (a primeira vez que eu já inspirou uma quadrinhos!)
Comic inspirado pelo meu Tetris A.I. projeto (2003) (a segunda vez que eu já inspirou uma quadrinhos!)
13. História do Tetris A.I. projeto
Na Primavera de 1989 eu estava ocupado pulando (e falta)-segundo semestre freshman classes no University of Pennsylvania.
Um dos meus quarto, Bill Matthews, teve a Mac Classic e, às vezes, jogou jogos de vídeo.
Pessoas que se admitiu a Ivy League escolas são tipicamente inclinado a concorrer com outras pessoas em todos os tempos - Bill assim quando começou o jogo Tetris para a sua Mac, nós imediatamente iniciada uma batalha de longo prazo para a pontuação elevada.
Como a pontuação subiu, o investimento necessário tempo para fazer um pequeno ganho aumentou dramaticamente.
Para fazer uma longa história curta, Bill supostamente detém a pontuação elevada entre nós, mas eu suspeito de usar ele ResEdit e hacking a pontuação arquivo!
Bill tinha aulas na escola de negócios Wharton, o alma mater de Michael Milken e Donald Trump, portanto, não é inconcebível que alguém viciada impossìvel uma pontuação elevada ...
No verão de 1990 me emprestou uma 30 MHz Intel 80386 IBM PC do meu quarto, Alex Haidas.
Eu comprei um teclado Mac em um mercado de pulgas $ 1.
Eu construído porta paralela circuito para permitir que o PC para controlar o Mac teclado.
(I CMOS 4040 usado um chip de agir como um tipo de relé de estado sólido para se juntar teclado Mac contatos no interior do teclado.)
Eu escrevi um programa de computador que uma decisão de árvore utilizada como a sua estratégia para jogar o jogo Tetris. Dentro de poucas semanas, tive um PC jogar o jogo Tetris rodando em um Mac.
No entanto, eu era obrigado a utilizar o teclado PC para dizer a A.I. sobre cada peça caindo na tela.
Eu comecei a trabalhar em um circuito usando CdS (Cadmium Sulfide) luz detectores que seria magra contra o Mac tela e "ver" a queda peças, mas CdS sensores reagido muito lentamente às mudanças no brilho, o contraste entre Tetris e peças e de fundo sobre a tela Mac Classic era demasiado baixo para discriminar fiável.
Naquela época eu não tinha muito dinheiro, de modo que era demasiado arriscado para a compra de US $ 2 Radio Shack Fototransístor que talvez não faça o que eu queria.
Além disso, dado o contraste problema, eu estava pessimista sobre toda a abordagem.
Quando eu comprei o meu primeiro computador pessoal em 1996, eu não poderia obter um software sob Windows 95 em 100 MHz CPU para fazer vídeo processamento rápido o suficiente para fazer um simples sistema de visão trabalho.
Eu escrevi o código de processamento de imagem em linguagem assembly, mas houve tanta gerais antes de o meu código realmente recebida video dados que lhe parecia impossível de se fazer nada de bom.
Em 2003, tecnologia, em especial CPU velocidade, tinha atingido um nível que fez terminar o projeto quase trivial.
Eu cavada até o meu velho projecto pessoal e, finalmente acabado-lo, obtendo algum sentido de encerramento.
Foi muito emocionante para ver jogar um computador a outro computador através USB máquina fotográfica e de vídeo a relés.
O som dos centros clicar, e assistindo as peças giro e solte a ridículo, superhomens velocidades, feita a experiência extremamente gratificante, em um multisensory forma.
Em 2003, meu trabalho foi reconhecido pelo Slashdot (
http://slashdot.org), e recebi um lote de grande gabarito.
Eu fui convidado para aparecer na "Screen Savers" televisão mostram TechTV sobre a rede de televisão digital.
Fui a São Francisco e apareceu no show, ea experiência foi muito grande.
Mais tarde, em 2003, recebi uma mensagem de Henk Rogers, convidando-me a ele e Havaí para satisfazer Alexey Pajitnov de falar de criar uma espécie de padrão para Tetris, para os efeitos de ter Tetris torneios.
Um particular interesse foi permitindo aos jogadores utilizar telemóveis para “competir uns com os outros,” indirectamente, através A.I. que imita jogadores (a prévia análise de cada jogador de acções), evitando, assim, os efeitos do telefone celular latência de acesso à Internet, e permitindo aos jogadores “competir contra” * Os melhores jogadores humanos no mundo (*..., ou melhor, A.I. imitando os melhores jogadores humanos em todo o mundo).
Eu estava entusiasmada com a perspectiva da reunião do criador de Tetris. Infelizmente, voar faz-me ansioso, e eu declinou o convite.
Em 2006, eu convertido meu "Standard Tetris" software de C++ a C# para tornar o software mais acessíveis e úteis para programadores contemporânea.
