Tetris
Colin Fahey
1. Software
StandardTetris_2007June4.zip
Tetris código fuente (C# y C++ versiones) y programa (“exe”);
4068277 bytes
MD5: 4e957e0ead66064183e9f7e04e618ec0
2. Introducción
Este artículo describe cómo un ordenador puede jugar el clásico videojuego de Tetris para obtener información sobre el tablero, la determinación de buenas acciones, y la realización de esas acciones.
Este artículo incluye software capaz de jugar al Tetris en tiempo real.
El software incluye los mejores en tiempo real de juego Tetris algoritmo en el dominio público.
Este artículo define las normas “estándar” para “Tetris,” una especificación basada en la original 1986 previa a la versión comercial de Tetris para el ordenador personal (PC).
En 2003, el software incluido en este artículo se utilizó para permitir un ordenador para jugar Tetris funcionando en un ordenador.
Un ordinario USB cámara de vídeo fue utilizado para permitir el ordenador para “ver” la pantalla de otra computadora.
A bordo de relé se controla a través de un interfaz RS-232 para que el equipo de “prensa teclas” en el teclado de otro ordenador.
Por lo tanto, el primer ordenador tiene una relación con el segundo equipo que es similar a un típico jugador humano a la relación de un ordenador al jugar Tetris, el juego de estado sólo se conoce mirando a la pantalla, reproductor y acciones sólo pueden ser presentadas a través de un teclado .
La configuración de esta manifestación demuestra que un ordenador puede jugar Tetris mejor que un ser humano, bajo condiciones normales de tiempo real las condiciones de juego Tetris.
3. Historia de Tetris
En 1985, Alexey Pajitnov y Dmitry Pavlovsky eran ingenieros informáticos a la Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre de la Russian Academy of Sciences
Alexey y Dmitry estaban interesados en el desarrollo y la venta de juegos de ordenador adictivo.
Se probó a cabo varios juegos diferentes.
Alexey se inspiró en la antigua Grecia, donde el juego de puzzle, Pentaminos, en el que participaron la organización de piezas hechas de cinco plazas.
Alexey pensamiento de la idea de organizar Pentamino piezas, ya que cayó en un vaso rectangular, pero se dio cuenta de que las doce de cinco diferentes formas cuadradas son demasiado complejos para un videojuego.
Alexey pasa a utilizar “tetramino” siete piezas, cada una de cuatro plazas.
En 1985.6, Alexey Pajitnov programado la primera versión de Tetris en un Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov, y Tetris.
En 1985-1986, Vadim Gerasimov, de 16 años, alta escuela ordenador prodigio que trabajó en la academia, ejecutado por el Tetris IBM PC ejecutando el sistema operativo MS-DOS.
(Vadim Gerasimov más tarde hizo una investigación en el MIT Media Laboratory, desde 1994 hasta 2003, recibiendo un doctorado después de terminar muchos proyectos interesantes:
http://vadim.www.media.mit.edu)
La introducción de la pantalla 1987-1988 pre-lanzamiento comercial de Tetris para la PC
El juego de la pantalla 1987-1988 pre-lanzamiento comercial de Tetris para la PC
Después de 1987, Tetris propagación en todo el mundo.
The Tetris Company, LLC, Tetris es el propietario de la marca.
4. Los proyectos inspirados por Tetris
4.1 0-dimensional Tetris
Pendiente de desarrollar.
4.2 1-dimensional Tetris
Ziga Hajdukovic ha elaborado 1-dimensional Tetris software que se pueden reproducir en un navegador de Internet.
Ziga Hajdukovic también ha elaborado 1-dimensional Tetris software para teléfonos móviles utilizando la plataforma Java J2ME.
4.3 2-dimensional Tetris
Todas las variantes de Tetris convencionales se encuentran en esta categoría.
Esta sección incluye interesantes variantes.
4.3.1 Tetris más grande de todos los tiempos: Delft University of Technology (1995)
Tetris jugado en un edificio; 2000 m^2 superficie; Delft University of Technology (1995)
Tetris jugado en un edificio; 2000 m^2 superficie; Delft University of Technology (1995)
4.3.2 Otro juego Tetris en un edificio: Brown University (2000)
Tetris juego se muestra mediante luces en las ventanas de un edificio en Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
“Creo que fue simplemente la más increíble de un día, cosa que yo puedo imaginar en mi vida. Al igual que Steve Jobs siempre dice, el viaje es la recompensa.”
“Se me hizo pensar en proyectos que hicimos en la universidad. Las cosas que eran casi deshacer que otras personas no piensan de hacer.”
Steve Wozniak (2000)
4.3.3 Navegador de Internet con el juego MIT “Edificación” imagen
Vadim Gerisimov's navegador de Internet Tetris
Este navegador de Internet variante de Tetris fue creado por Vadim Gerasimov.
Este navegador de Internet Tetris características “Green” el edificio en el campus de MIT.
Esta variante de Tetris sólo tiene nueve columnas en lugar de los diez columnas.
Esta variante de Tetris presenta nuevas piezas con orientaciones al azar.
Vadim Gerasimov es la persona que escribió el código de computadora para la PC versión de Tetris en 1986.
Vadim Gerasimov hizo Ph.D. investigación en el MIT Media Laboratory durante 1994-2003, trabajando en muchos proyectos interesantes.
4.3.4 PIC16F84 12 MHz basado en microcontrolador NTSC / PAL video juego Tetris
PIC16F84 12 MHz basado en microcontrolador NTSC / PAL video juego Tetris
La imagen de arriba muestra la NTSC / PAL salida de vídeo producida por un microcontrolador PIC16F84 12 MHz correr software escrito por Rickard Gunee en 1998.
La señal de vídeo es generado por un programa informático de control de salidas digitales.
4.3.5 “Scopetris” osciloscopio de Tetris Lars Pontoppidan (2007.8)
“Scopetris” osciloscopio de Tetris Lars Pontoppidan (2007.8)
Lars Pontoppidan escribió el código para el microcontrolador AtMega32, y agregó sencillo de circuitos analógicos, para crear una versión de Tetris que podrían desempeñar en un osciloscopio.
Algunos registros de la AtMega32 control microcontrolador de 8 bits señales de salida y, cuando pasa a través de una resistencia eléctrica “R-2R” circuito de digital a analógica (D/A) conversión, la resultante señales analógicas puede controlar la (x,y) las coordenadas de un osciloscopio haz (cuando el osciloscopio es conjunto a “modo de X-Y).”
YouTube video:
FLV video:
4.3.6 Código ofuscado Tetris: C / Unix
El siguiente fue galardonado con “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 Código ofuscado Tetris: Perl código
El siguiente es el Tetris para Perl intérprete: Perltris (versión 20050717) de 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) es un estándar para la descripción gráfica de objetos que utilizaban XML.
Mozilla SVG Tetris: Tetris aplicado usando una descripción Scalable Vector Graphics (SVG)
4.3.9 Google “widget” Tetris
Google, Yahoo!, y Microsoft, y otras empresas, han promovido en miniatura basadas en Internet software llamado “widgets” que son por lo general se caracteriza por el uso de algunos datos dinámicos en Internet.
Uno de esos widget disponibles a través de Google es un juego Tetris.
El siguiente ejemplo es lindo, pero las formas en rotar molesto maneras:
Google “widget” Tetris
Otros Google widgets:
4.3.10 MIT trabajo de investigación: “Tetris is Hard, Even to Approximate” (2002)
El siguiente documento de investigación contiene una prueba de que un cierto tipo de variante de Tetris es “NP-completa.”
Erik D. Demaine, Susan Hohenberger, y David Liben-Nowell, “Tetris is Hard, Even to Approximate”, Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
“NP-es” una “completa” clasificación de los gastos tiempo y el espacio costo de un algoritmo.
Otras clasificaciones incluyen “P” y “NP”.
Una clasificación de “NP-completo” implica que, para los problemas más grandes que algunos pequeños tamaño, el algoritmo es poco probable que encontrar una solución deseada en un punto de vista práctico cantidad de tiempo o espacio.
4.3.11 Documento de investigación: “Applying reinforcement learning to Tetris”
El siguiente documento, publicado 2005.5.30, por Donald Carr en el departamento de Ciencias de la Computación en Rhodes University, Sudáfrica, presenta la solicitud de “refuerzo de aprendizaje” a Tetris.
4.3.12 Tetris falda (2007.11)
Tetris falda (2007.11)
La falda Tetris fue creado por “Lucy” (“hissyfitoly” en etsy.com) antes de 2007.11.
A partir de la descripción del creador de la falda (a la venta en 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."
Foro de comentarios respecto a esta falda:
“El hombre que aspira a falda Tetris”
“Ahahahaha, pensé lo mismo.”
“Hay una línea completa abajo en la parte inferior ... completado las líneas desaparecen.” “HACER MÁS” “.”
“Debería haber un terreno en la parte trasera o delantera, donde a largo pieza encajaría perfectamente ...”
“Esa es una realidad fea aunque falda. Mi novio no podía comprar suficiente me chocolate y flores para convencer a mí para que lo use.”
4.3.13 Tetris etapa acto (2007.4)
Tetris etapa acto (2007.4)
“De los que le trajo la Triforce en 2006 ... Viene la próxima generación de objeto inanimado dramatización ... Tetris.”
A nivel local-en caché de vídeo en Flash vídeo (FLV) formato (uso VLC a desempeñar):
4.3.14 Tetris hilarante variaciones sobre un japonés de televisión
Tetris variaciones en japonés de televisión
Este segmento de video de un japonés de televisión hilarante incluye las variaciones de Tetris, entre ellas:
piezas que desaparecen en el aterrizaje, una pieza que llena toda una fila (completando así una fila en el aterrizaje), varias piezas pertenecientes al mismo tiempo, piezas de forma irregular, una larga pieza que es un poco demasiado grandes para caber en una laguna (la prevención de una fila de 4 conclusión!), Mario golpear a un hongo y se convierta en un enorme y morir!, pequeña pieza que queda después de desechos filas se destruyen, al alza gravedad de toma piezas flotan a la parte superior, etc
A nivel local-en caché de vídeo en Flash vídeo (FLV) formato (uso VLC a desempeñar):
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 de la descripción que figura en YouTube:
“TETRIS real desempeñado por seres humanos sentados en un auditorio:”
TETRIS es el 4 º video de la ejecución GAME OVER Project, dirigida por el artista suizo Guillaume REYMOND (NOTsoNOISY agencia creativa).
Este stop-motion video fue filmado y jugó para “LES URBAINES” festival
http://www.urbaines.ch en el Palais de Rumine (Lausanne, Suiza) en November 24th 2007.
A nivel local-en caché de vídeo en Flash vídeo (FLV) formato (uso VLC a desempeñar):
4.3.16 2.5-dimensional Tetris
El término “2.5-dimensional” se utiliza aquí en el sentido de no ortogonales de una vista bidimensional versión de Tetris, con algunas espesor en la tercera dimensión.
(Encuentre el vínculo “tetris3d” en “F7: GAMES”.)
4.4 3-dimensional Tetris
Linux / GTK versión
Tridimensionales Tetris en la forma de un applet Java para los navegadores de Internet:
Tridimensionales para el Tetris Windows sistema operativo:
4.5 4-dimensional Tetris
Greg Kaiser's “HyperTetris” (1996): a 4-dimensional Tetris
En [1996], [...], Greg Kaiser juntos un período de cuatro dimensiones variante en el juego clásico.
El uso de IrisGL (a.k.a. igl) creó un grupo de trabajo, si es difícil de jugar, juego con cuatro sub-pantallas diferentes para representar en tres dimensiones aspectos del juego-todo el espacio.
[Porque] no hay una manera fácil [comprensible] manera de sacar cuatro objetos-D en un período de dos D pantalla, los cuatro sub-puntos de vista son un método práctico para manipular y visualizar la rotación y la traducción de las piezas a través de las cuatro dimensiones ( en el juego llamado x,y,z,w).
En lugar de completar líneas de bloques como en el original, el objetivo en este caso es para llenar un cubo completo en la x,y,z subview (normalmente 4 de 4 en 4).
El otro subviews que contienen la dimensión “w” se organizan en un 4 por defecto de 4 por 10 bloques acuerdo con “w” ser el largo, “vertical” dimensión en los tres casos, con diferentes bases de (x,y), (x,z), (y,z).
Gravedad en los actos “-w” dirección, por lo que los pedazos “caen” en las tres largas subviews que incluyen “w”, y no se mueven a menos que el control de jugador en los últimos (x,y,z) subview.
Se toma un tiempo para acostumbrarse, por decir lo menos.
Si por algún milagro de paciencia o cambiar los parámetros del juego, uno no completa un cubo, que desaparecerá como el concluido líneas hacer en el original Tetris, aunque no Resultado se mantiene en HyperTetris.
Benjamin Bernard (2000)
4.6 N dimensiones Tetris
Polytope Tetris (2003): un N dimensiones variante de Tetris
Polytope Tetris es dimensionalmente n-Tetris.
Inspirado por la HyperTetris programa, permite que usted Polytope Tetris toneladas jugar Tetris en cualquier NÚMERO DE dimensión.
Juega Tetris en 3D, 4D, 5D, o más.
HyperTetris es mucho más catchier nombre Polytope (def) Tetris, pero no puedo robar el nombre.
5. “Tetris” especificación “estándar”
5.1 Introducción
La definición de la “norma Tetris” es un modelo idealizado de las más importantes características y comportamientos de la primera IBM-PC aplicación del juego Tetris (circa 1986-1988).
El modelo idealizado se basa en deducir la aparente intención de los desarrolladores de la primera IBM-PC aplicación del juego Tetris.
Por ejemplo, parece razonable inferir que los desarrolladores de la primera IBM-PC aplicación del juego de Tetris para seleccionar la forma de cada pieza nueva caída “al azar,” y que el uso de la Borland C aplicación de la rand() función era simplemente una práctica de aproximación la intención.
La definición de la “norma Tetris” especifica que la forma de cada pieza nueva caída se seleccionaron “al azar.”
Este ideal de conducta no pueden ser alcanzados por cualquier aplicación, pero las implementaciones pueden aproximar el comportamiento ideal.
Aunque no aplicación puede aplicar perfectamente a la definición de la “norma Tetris,” los ideales de la “norma” la participación de “Tetris” características objetivas, y las implementaciones se pueden comparar en función de su relativa proximidad a los ideales de la “norma Tetris.”
Esta sección describe un conjunto de elementos, los comportamientos y las normas que, colectivamente, definir “Standard Tetris.”
5.2 Norma Tetris bordo
La placa es una red de células, observando las 10 columnas y 20 filas, con un total de 10 * 20 = 200 células.
Norma Tetris bordo (10 columnas, 20 filas)
Cada celda puede ser desocupadas (vacías) u ocupados (lleno).
5.3 Norma piezas de Tetris
Hay siete (7) estándar de piezas de Tetris, con los siguientes nombres de letras:
{ O, I, S, Z, L, J, T }
Los nombres de letras se inspiran en las formas de las piezas.
Las siete piezas estándar de Tetris y sus “orientaciones”
El punto en (0,0) coincide con la posición (6,20) bordo cuando la pieza aparece por primera vez.
La primera columna muestra la “orientación” inicial.
En el siguiente, la palabra “de orientación” se utiliza para describir cualquier estado de una pieza, dentro de un conjunto de estados permitidos, que puede ser resultado de una rotación caso contrario.
El cambio de “orientación” de una determinada “orientación” de un “I, S,” o “Z” pieza, requiere la combinación de una rotación y una traducción.
Por lo tanto, la “orientación” palabra se usa aquí para significar algo más que la rotación por sí solo.
Sin embargo, la “orientación” sólo puede cambiar en respuesta a una rotación caso contrario, y el ciclo de distintas “orientaciones” de cada pieza se aproxima, o partidos, como resultado del ciclo de rotaciones puras.
El especial uso de la palabra “de orientación” en este contexto es casi equivalente al significado de la palabra o “ángulo de rotación,” pero la palabra “de orientación” se utiliza en lugar de la “rotación” para tratar de llamar la atención sobre el hecho de que algunas piezas requieren más de rotación para producir la conjunto de estados resultantes permitido La “rotación” de los acontecimientos.
Las piezas sólo pueden cambiar las orientaciones (o someterse a un específico horizontal o vertical de traducción) si el estado resultante de la pieza no tendría ningún ocupados (lleno) células más allá de la zona del tablero y no tendría ningún ocupados células que se solapan cualquier actualmente ocupado células de la junta.
(En este estado, los ocupados (lleno) las células de la pieza no se consideran como parte de los “que actualmente ocupan las células de la junta”
En los siguientes comentarios, cualquier referencia a un resultado de un evento La rotación se hace con el supuesto de que dicha rotación puede ser realizada, debido a las condiciones existentes de la pieza y el tablero.
El “O” (véase el recuadro) pieza sólo tiene una sola orientación, y no cambia la ubicación de cualquiera de sus ocupados (lleno) las células en respuesta a cualquier evento en sentido de rotación.
El “I” (línea) pieza tiene dos orientaciones posibles, que aparece inicialmente en una orientación horizontal.
La pieza “I” alterna entre las dos orientaciones en respuesta a los sucesivos acontecimientos en sentido de rotación.
El “S” y “Z” piezas tienen cada uno dos posibles orientaciones.
Estas piezas cada una alternativa entre dos orientaciones en respuesta a los sucesivos acontecimientos en sentido de rotación.
El “L”, “J”, y “T” piezas tienen cada uno cuatro posibles orientaciones, y estas orientaciones son el resultado de las rotaciones simples puntos sobre el centro en las formas.
Cuando una pieza aparece por primera vez en el tablero, la pieza tiene su “eje mayor” en una orientación horizontal, y la pieza es en la parte superior del tablero.
Por lo tanto, no son piezas inicialmente capaz de haber cambiado sus orientaciones. La pieza debe descender por una fila para tener la posibilidad de haber cambiado su orientación.
Una vez que una pieza se ha reducido de una fila en el tablero, todas las orientaciones pieza se puede alcanzar (suponiendo que la pieza no está demasiado cerca de las paredes laterales o al actual montón de piezas).
5.4 Norma Tetris diagrama de flujo
El siguiente es un diagrama de flujo aproximado de una norma Tetris juego.
Diagrama de flujo aproximado de una norma Tetris juego
Diagrama de flujo aproximado de una norma Tetris juego
5.5 Norma Tetris pieza creación
El siguiente diagrama muestra la (4 * 2 celular móvil) región en el tablero todas las piezas que aparecen cuando creada.
Región en la que las piezas aparecen cuando creada en la Norma Tetris
Cuando una nueva pieza aparece por primera vez en el tablero, su origen coincide con el punto en este diagrama, y la pieza será completamente contenida por el área sombreada en este diagrama.
Cuando un nuevo juego se inicia, una plena caída libre transcurre demora, y en la primera caída libre iteración un pedazo es generado en la parte superior del tablero.
En condiciones normales de juego, cuando una caída libre de “tierras” iteración un pedazo, una plena caída libre y demora transcurre en la próxima caída libre de un pedazo de iteración es generado en la parte superior del tablero.
Cuando una pieza es engendrado, del tipo de pieza se selecciona mediante el siguiente algoritmo:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Porque hay una constante p (= 1/7) oportunidad de seleccionar un tipo específico de la pieza, y todas las piezas del mismo tipo son indistinguibles, la probabilidad de tener exactamente k piezas de un tipo específico después de los ensayos n sigue una distribución 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 )
Cuando se elige de entre los 7 (siete) piezas al azar, la probabilidad de obtener una determinada pieza es p=(1/7).
Si hacemos esto n=70 veces, por ejemplo, la probabilidad de obtener exactamente k piezas (con k en el rango 0 a n) está dado por la distribución binomial, tal y como se muestra en la siguiente imagen.
Distribución binomial para n=70, p=(1/7)
De este modo, se puede predecir el promedio total de piezas de un solo tipo dado un número total de piezas al azar, y también se puede calcular la diferencia esperada y desviación estándar (raíz cuadrada de la varianza):
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
Cuando convertimos un valor aleatorio a una pieza índice, que lo interpretan como sigue:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[El pre-comercial MS-DOS versión de Tetris utiliza la función de números aleatorios ofrecido por el Borland Pascal compilador.
Esta función utiliza una de 32 bits variable de estado.
Por lo tanto, la secuencia de números aleatorios se limitó a 2^32 distintos valores.
Por lo tanto, en principio, un jugador puede descubrir, después de caer tal vez 10 piezas, el lugar exacto en el conjunto de 2^32 números correspondientes al estado actual del juego.
Si Tetris simulaciones se ejecutan con la secuencia fija de 2^32 piezas, entonces decisiones óptimas se puede encontrar para cada lugar en la secuencia.
(Al parecer hay suficientes oportunidades para que la junta directiva a una junta totalmente vacía estado, lo que nos permite obtener sincronizado con la solución óptima precomputed camino.)
El riesgo de utilizar un simple generador de números aleatorios en una simulación destinada a encontrar una solución óptima a un problema es que la solución sea óptima sólo para el particular ruta por el problema de espacio seleccionado por el simple generador de números aleatorios. ]
5.6 Norma Tetris controles
Durante el juego, los siguientes insumos están disponibles:
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
Todas las entradas en vigor el aumento de punta de los aspectos positivos de entrada (pulse sobre el botón, a diferencia de botón de liberación).
Cuando pulse un botón se produce, este cuenta como una solicitud.
La celebración de un botón abajo más allá de un determinado periodo de tiempo podría dar lugar a la “auto-repetición” característica de un teclado, la generación de nuevas presionar un botón -, pero esta característica es externo al juego motor.
Las entradas se establece más arriba se ajustan a la original Tetris.
Rotar las solicitudes se pueden ejecutar si no hay coincidencia entre la orientación deseada y establecer células en la actual junta (con exclusión de la caída de pieza), y si la orientación deseada no ha establecido las células fuera del tablero.
Traducir las solicitudes se pueden ejecutar si no hay coincidencia entre la configuración deseada traducido y establecer células en la actual junta (con exclusión de la caída de pieza), y si la configuración deseada traducido no ha establecido las células fuera del tablero.
Entrada solicitudes se procesan con una latencia que depende de la velocidad de cuadro de juego (por ejemplo: 75 Hz), y pide a surtir efecto (si es válido) al instante.
Una pieza puede ser disminuido sin ningún tipo de línea de caída se producen pasos.
Una pieza puede ser traducido en varias ocasiones a la izquierda oa la derecha, y posteriormente descendió, todos sin experimentar una caída de la línea oficial de paso.
Debido a generado una nueva pieza no puede ser rotado (porque se ha quedado atascado contra el borde superior de la placa), el jugador debe aceptar al menos una pieza caída de paso si las rotaciones son conveniente o necesario.
El efecto sobre la puntuación es insignificante.
5.7 Norma Tetris pieza “de aterrizaje”
Si una pieza es más que caer, cae de una sola fila en cada pieza caída de iteración.
Se llevará a cabo una iteración que se mueve desde un lugar sin contacto con las superficies horizontales a un lugar que tiene contacto con las superficies horizontales. Una vez que esto ocurre iteraciones, las piezas son de descanso en contacto.
Si una iteración comienza con una pieza de descanso en contacto con una superficie horizontal, la pieza “tierras,” y se convierte en parte de la estática de pilotes.
5.8 Norma Tetris “líneas terminado”
Una fila se completó una fila de la pila en la que todas las celdas están ocupadas. Cuando un componente se elimina la fila de la pila, y las filas por encima de la fila eliminada se desplaza hacia abajo por una fila para eliminar la brecha, esta cuenta como una “línea de” terminado.
Cuando un pedazo de tierras se convierte en parte del montón.
Inmediatamente después de la pieza tierras, la pila está marcada por terminado filas, y todo terminó, se eliminan las filas.
Hasta cuatro líneas se puede hacer a la vez.
En el cuadro siguiente se da el límite superior en las líneas por terminado al mismo tiempo una sola pieza:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Norma Tetris “niveles”
Norma Tetris tiene 10 niveles de dificultad, que llevan los números 1 (uno) a través de 10 (diez), con nivel 1 ser el “menos difícil.”
El nivel es el índice máximo de dos valores:
actualLevel = max( initialLevel, earnedLevel );
El initialLevel valor es el nivel que el jugador selecciona al iniciar un nuevo juego.
El patrón de nivel en función de líneas terminado es fácilmente observado en el pre-comerciales MS-DOS versión 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
De este modo, el earnedLevel valor se calcula de acuerdo con el siguiente 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 Norma Tetris caída de iteración demora
Norma tiene un Tetris en tiempo real de demora entre los sucesivos línea de caída libre de iteraciones que es una función del actual nivel de dificultad.
La siguiente relación entre el nivel del índice y la caída de iteración demora se basa en mediciones repetidas cronómetro en todos los niveles de la pre-comerciales MS-DOS versión 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
Por lo tanto, establecemos la siguiente fórmula para la iteración demora valor en función del nivel real índice:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Si la junta está vacía, y no hay entrada del usuario, una pieza generado a nivel real 1 tierras en aproximadamente 10 segundos, y una pieza generado a nivel real 10 tierras en aproximadamente 1 segundo.
5.11 Norma Tetris “Resultado”
Norma Tetris sólo concede puntos para el acto de una pieza de aterrizaje.
No hay puntos adjudicados para el acto de completar una sola línea, o para completar dos, tres o cuatro líneas simultáneamente.
[Nota: algunas variantes de Tetris adjudicación de puntos para el acto de completar líneas, con un aumento exponencial de bonificación para un número cada vez mayor de líneas simultáneamente terminado.
Por lo tanto, la estrategia de maximización de Resultado en tales variantes de Tetris lleva consigo la creación de oportunidades para “obtener un Tetris,” argot para el uso de la “I” forma a obtener cuatro líneas simultáneamente y obtener un montón de puntos. ]
Si usted tiene un tablero vacío, y le permite a un no-“I” hacer una pieza caída libre y la tierra, o si una gota de inmediato no “I” pieza, puede establecer el punto siguiente gráfico usando el pre-comerciales MS-DOS versión 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, no “I” piezas caen un total de 18 filas.
Esto explica la diferencia entre el punto de caída libre y al instante de que retiraran los cargos.
Al experimentar con casos intermedios, es fácil deducir el punto siguiente fórmula:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Tenga en cuenta que esta fórmula no tiene nada que ver con la distancia un pedazo cae!
Es estrictamente una función de el nivel real, y una pena para el número de iteraciones un pedazo se le permite caer libremente.
Este castiga a un usuario para que necesitan tiempo para pensar.
También tenga en cuenta que, debido a que una pieza no puede inicialmente ser rotado en sus desoves, un jugador es castigado con pena de al menos una caída libre de iteración si las rotaciones son necesarias para colocar una pieza en la pila.
Esto probablemente nunca afecta a los jugadores humanos, a menos que de alguna manera: reconocer la pieza, presione las teclas de traducción (a la “izquierda” oa la “derecha),” pulse la tecla “girar” una o más veces, la prensa y la “caída” clave, todo ello en menos de 0.5 segundos a nivel 1, o menos de 0.05 segundos a nivel 10.
6. Norma Tetris estrategia
6.1 Introducción
Una estrategia para jugar un juego depende de las reglas del juego.
Una estrategia depende de que el parámetro es para ser optimizado.
En la norma Tetris, uno sobrevive de completar las filas, recibe puntos de desembarque de piezas, y anota la mayoría de puntos posibles para cada pieza de ejecución de una caída antes de que uno o más de caída libre de iteraciones reflejado.
Un A.I. pueden optimizar los puntos adjudicados a cada pieza simplemente de decidir en un movimiento rápido y “presionando las teclas” para ejecutar el movimiento.
Más importante es un A.I. supervivencia, porque la supervivencia indefinida significa una arbitraria puntuación más alta se puede alcanzar. Debido a que las piezas de Tetris caída en un determinado tipo de cambio, la A.I. debe tomar decisiones, al menos, este rápido - y la A.I. debe hacer que se mueve completa filas a un ritmo promedio de al menos 1 fila por 2,5 unidades. (Cada pieza tiene 4 células, y cada fila tiene 10 celdas.)
Por supuesto, uno puede aplazar completar las filas de la acumulación de piezas y construcción de un gran montón, pero sólo hay 200 células por todo el tablero, que, en principio, sólo puede tener 50 unidades, por lo que cualquier jugador (como un A.I.) debe tener como completar las líneas una prioridad fundamental.
En la norma Tetris, el juego incluye el estado actual bordo de la ocupación y la actual caída de pieza (tipo, la posición y orientación). El juego estado puede incluir opcionalmente en "Siguiente Piece".
6.2 Una secuencia alterna de "S" y "Z" piezas
Heidi Burgiel, Ph.D., de la Department of Mathematics, Statistics and Computer Science a la University of Illinois at Chicago, ha demostrado que una secuencia alterna de "S" y "Z" piezas obligará a una norma (10 de la columna, fila 20) Tetris juego a finales dentro de un número previsible de movimientos.
La frase del artículo: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Asociado impresa artículo: Mathematical Gazette, de julio de 1997, "How to Lose at Tetris"
Heidi Burgiel ofrece una Java applet que se ejecuta en un navegador de Internet que cuenta con un clon de Tetris alterado que genera la alternancia "S" y "Z" piezas.
[El "Standard Tetris" software asociado con el documento que está leyendo también tiene un modo que genera la alternancia "S" y "Z" piezas. ]
Heidi Burgiel alegó que la participación de un juego alternativo "S" y "Z" piezas (por una norma Tetris bordo de 10 columnas y 20 filas) debe terminar antes de que menos de 70000 piezas han caído.
La Norma Tetris software incluido con este documento permite a una persona para jugar con la alternancia "S" y "Z" piezas, así como cambiar el ancho de junta.
Es fácil ver que las juntas cuyos anchos son entero múltiplos de cuatro columnas (ejemplos: 4 columnas, 8 columnas, 12 columnas, etc) se pueden reproducir piezas para siempre cuando se alternan entre "S" y "Z", con el aumento de la pila no superior a 4 filas. Menciono esto para dejar claro que la escasa supervivencia se describe en el documento de investigación se ha mencionado anteriormente es específicamente para el caso de una norma Tetris pensión (con 10 columnas y 20 filas).
6.3 Insolubles pieza secuencias en general
Hay categorías enteras de secuencias patológicas que no pueden sobrevivir.
Sería interesante calcular el total de probabilidad de encontrar un juego-se da por concluida la secuencia, porque esto pondría un límite superior sobre el desempeño de cualquier estrategia, aun con el conocimiento completo de todas las futuras piezas en cualquier punto dado en un juego.
6.4 Total de posibles configuraciones bordo
Habida cuenta de que la junta ha 10 * 20 = 200 células, y teniendo en cuenta que cada célula sólo puede estar en uno de dos estados (vacío u ocupado), el número total de configuraciones junta debe ser inferior o igual a: (2 ^ 200).
Teniendo en cuenta que cada pieza se añade a 4 células de un órgano, y cada fila finalización 10 elimina células de la placa, el número de ocupados células en el tablero siempre será aún. Por ejemplo, (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 Por lo tanto, sólo la mitad de la junta (2 ^ 200) configuraciones se puede llegar por jugar el juego.
De este modo, el número total de configuraciones bordo es de aproximadamente: (2 ^ 199) = 8.03469... * 10^59.
Sin embargo, debemos excluir de nuestro total de cualquier configuración que incluye lleno filas, porque llena las filas se eliminan antes del final de cada completado movimiento. Cualquier configuración con uno o más filas se llenaron colapso a otra configuración que no contenga ninguna lleno filas.
Asimismo, debe excluir cualquier configuración que incluye un no-vacío fila por encima de una o más filas vacías, porque no fila vacía encima de una fila vacía siempre otoño, y todo se detiene antes de caer al final de cada movimiento.
Cada fila puede ser en 2^10 = 1024 estados, uno de los cuales es "vacía", una de las cuales es "completo", y (1024 - 2) = 1022 de los cuales están parcialmente ocupadas. Se excluye la "plena" caso de examen.
Si la fila de abajo está vacío, entonces todas las filas por encima de la fila inferior, también debe estar vacío.
Si la fila inferior, está parcialmente ocupada, entonces la segunda fila puede estar vacío o parcialmente ocupado.
La continuación de este análisis, podemos calcular una serie de configuraciones bordo que tenga en cuenta a la exclusión completa de las filas y las restricciones en las filas vacías: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), que es de aproximadamente ((1022 ^ 19) * (1023)).
Por lo tanto, nos encontramos con una estimación más precisa del número total de configuraciones estables bordo: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199), es decir, aproximadamente el 3,74% menos que la estimación (2 ^ 199).
Sin embargo, el número real de estable, accesible bordo de los estados es probable que sea inferior en particular debido al hecho de que la parte superior de la mayoría de las filas sólo puede ser llenado en varias formas. Como la parte superior de la mayoría de llenar las filas, generado una nueva pieza no puede moverse o girar mucho. Esto limita el número de formas en que la parte superior de la mayoría de las filas puede ser llenado.
6.5 En principio, la mejor jugada se puede encontrar para cualquier pieza de tablero y de configuración
Debido a que puede conseguir cualquiera de siete posibles piezas para cualquier consejo estatal, el número total de estados juego es de aproximadamente 7 * (2 ^ 199) = 5.624... * 10^60.
Porque podemos, en principio, hacer una búsqueda profunda de todos los futuros posibles para todos los movimientos posibles para un determinado estado de juego, podemos tener una sola "mejor" pasar asociados con cada juego de estado.
Suponemos que no tenemos acceso a cualquier información distinta de la actual junta directiva y actual pieza, por lo que "mejor" significa "el paso que ofrece las mayores posibilidades de satisfacer nuestro objetivo a largo plazo de supervivencia".
Un movimiento no es más que una traducción (hasta 10 opciones) y una rotación (hasta 4 opciones), podemos fácilmente codificar la mejor jugada en un solo byte.
Así que, en principio, se podría formar un cuadro con las entradas 10^61 (bytes) nos dijo que la mejor jugada dio ningún consejo estatal y actual pieza.
Por supuesto que esto es impracticable, así como la enumeración de todos "Go" juntas o "Chess" juntas es impracticable. Pero el punto es que hay una verdadera solución, y hay un mejor pasar para cualquier configuración. Puede ser igualmente buenos movimientos para una determinada configuración, pero podemos elegir arbitrariamente un solo paso en ese caso.
Muchos de juego de juego de algoritmos que tienen cuadros enumerar exhaustivamente todas las posibilidades de juego en estado limitado, como es el caso "de apertura (inicial) se mueve" o "final de juego (final) se mueve" en ajedrez. Quizás enumeración exhaustiva de las superficies de Tetris pila (aproximadamente (20 ^ 10) estados) es factible. Es una idea interesante.
Enumeración exhaustiva de todos los estados de la parte inferior dos filas, multiplicado por las siete piezas posible, y almacenar la mejor jugada en un solo byte, sería muy fácil, que requiere sólo el 7 MB de memoria. Tal vez optimizar el rendimiento de estos siete millones de casos proporcionaría datos en bruto tanto para el análisis y el desarrollo de modelos simples de los datos; esos modelos podrían ser considerados como parte del conjunto ideal Tetris-la estrategia de juego.
Tenga en cuenta que la ejecución se mueve mejor todavía no nos protegen contra los posibles patológicas juego-se da por concluida pieza secuencias. Es sólo que vamos a realizar se mueve siempre que nos ofrece el máximo potencial para la futura supervivencia, dado que todas las futuras piezas son totalmente al azar (y desconocidos en el momento en que vamos a decidir la forma de mover una sola pieza conocida actual).
6.6 En tiempo real el rendimiento
Una limitación que enfrentan algunos algoritmos de estrategia es la necesidad de que en tiempo real el rendimiento - lo que significa que el algoritmo debe tomar una decisión dentro de una determinada cantidad de tiempo.
Cuando un ser humano desempeña Tetris, las piezas no dejan de caer para dar al jugador la oportunidad de pensar. Eso es parte del desafío de Tetris. Por lo tanto, una A.I. sistema que se pretende simular el papel de un jugador humano debe también tomar decisiones a un ritmo dictado por el juego Tetris.
6.7 Línea pieza y totales
Tenga en cuenta que en el largo plazo, el número de piezas se cayó muy cerca de 2.5 veces el número de filas -, ya que cada fila tiene 10 celdas, y cada pieza es de 4 células, y tenemos que completar una fila, en promedio, una vez cada (10/4) = 2.5 piezas se redujo.
Por lo tanto, podemos usar "completado filas" y "piezas se redujo" casi intercambiable con la constante de proporcionalidad. El mayor error es cuando el tablero está completamente lleno con excepción de una sola brecha en cada fila (((10*20)-20)/4) = 45 piezas se redujo, sino una deficiencia de las previsiones (45/2.5) = 18 completado filas.
6.8 Actual-pieza (y cartón) estrategia
Si sólo se permitirá la A.I. a tener conocimiento de la actual junta directiva y la actual pieza, y sólo considerar el resultado del traslado de la actual pieza en particular, los medios, entonces esto puede ser llamado una "pieza" análisis.
Aquí hay un esbozo de cómo una pieza de análisis puede decidir sobre un cambio en Tetris:
Actual-pieza análisis de un juego de Tetris estado
Básicamente tratamos todos los movimientos posibles y elegir el paso que da el mejor resultado.
La parte difícil la calificación de cada resultado.
Tenemos que valorar una hipotética situación de juego en función de lo bien que tal estado apoya nuestros corto plazo y metas a largo plazo.
Nuestro objetivo a largo plazo es la supervivencia. La supervivencia depende de la prevención de desbordamiento de pila de la placa. Podemos reducir la altura de pila completa la formación de filas que luego son eliminados de la pila.
Para formar una fila, hay que encajar piezas de piezas en las que cada columna de esa fila. Por lo tanto, obligaría a todas las partes de una fila de estar expuestos a la caída de piezas, si vamos a llenar el tiempo en toda la fila.
Si por alguna razón que vamos a cubrir vacíos hasta las partes de una fila de piezas en cualquier fila superior, entonces nos encontramos ahora incapaz de llenar los vacíos en partes de la fila. La única manera (suponiendo que no deslizante) para acceder a esos "agujeros enterrado" es eliminar las filas más arriba que tienen partes que actúan como obstáculos.
Los siguientes factores se encuentran entre los que podemos utilizar para un determinado tipo de pensión estatal:
Overall pile height
Cuanto más alto sea el montón, la peor nuestra situación parece ser, porque estamos más cerca de desbordamiento del tablero.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
El ásperas el montón, más probable es que será difícil de llenar en todos los contornos complejos incorporados a medida que estén expuestos a la superficie.
Number of buried empty cells
Cuanto más agujeros que hemos enterrado, la peor situación es nuestra, porque tenemos que descubrir los agujeros enterrado antes de que podamos completar los correspondientes registros.
Puede imaginar otros factores que, en general, tasa de un hipotético tablero de lo bien que su pila puede acomodar todas las piezas posibles, y lo bueno se ve la situación de todos los posibles piezas.
La siguiente cuestión es cómo determinar la importancia relativa de estos factores.
Un planteamiento general es la siguiente. Asigne un conjunto de "pesos" (importancia relativa) a estos factores y, a continuación simular numerosos juegos y registrar los resultados de estos juegos (puntuación final, etc.) Entonces, designar a un nuevo conjunto de pesas y simular un nuevo conjunto de juegos. Sobre la base de si o no la nueva serie de juegos tenía mejores resultados que la anterior serie de juegos, sabemos si la nueva serie de pesos era mejor que el anterior conjunto de pesos.
En mi propia experiencia he intentado buscar sistemática y aleatoria en busca de buenas combinaciones de peso, pero no noté en gran escala las tendencias que podía seguir. Sin embargo, he visto muchos baches sorprendentemente suave. Me pareció interesante que el promedio de rendimiento podría ser una curva suave cuando un parámetro varía lentamente fue con los demás parámetros se celebró en combinación algún valor.
El mejor tiempo real, de una sola pieza de Tetris algoritmo en el mundo, creado por Pierre Dellacherie (Francia) en 2003, se debe en gran medida de su éxito a su serie de mediciones (o métrica). Encontrar pesos cuando es necesaria la optimización de una estrategia, pero también es fundamental para empezar con los tipos de mediciones que revelan las características pertinentes del Estado.
Pierre Dellacherie's invención de nuevas formas para caracterizar cada uno de bordo de su algoritmo hace realmente excelente; las caracterizaciones bordo de la captura de importantes dimensiones estratégicas de la junta estatal.
Se podría elaborar un conjunto muy diferente de la caracterización de las dimensiones que trabaja igual de bien; Estoy seguro de que es posible abarcar la junta estatal de espacio en muchas formas diferentes que pueden utilizarse para especificar una estrategia función. La clave es encontrar las características del proyecto que el estado del espacio a un pequeño número de dimensiones que pueden ser utilizados para desarrollar una simple función de clasificación (ejemplo: la combinación lineal ponderada de las características utilizadas por Pierre's algoritmo).
Los de una sola pieza algoritmo usado por el "bot" en el "xtris" de software (1996) escrito por Roger Espel Llima usos pesos determinada por una gran escala de exploración de posibles combinaciones de peso "algoritmos genéticos". Recocido simulado es otro posible método de explorar el espacio multidimensional de combinaciones de peso.
Parece que, sobre la base de diversas observaciones, la función multidimensional de Tetris rendimiento promedio en función de las pesas, por ejemplo: F(w1,w2,w3,...), es "áspero" (lotes mínimos de los entes locales y maxima), lo que significa que un simple multidimensional "escalar la colina" puede que no funcione.
6.9 Estrategia actual cuando pieza, junto pieza, y la placa se conocen
Si una estrategia algoritmo es dada la actual pieza, junto pieza, y la placa, entonces puede tomar decisiones que tome ventaja de la combinación de piezas.
El conocimiento de la próxima pieza puede mejorar el éxito de un algoritmo de juego Tetris en varios órdenes de magnitud. Es fácil comprender cómo a sabiendas de la próxima pieza hace una gran diferencia en la estrategia.
Uno puede hacer "loco" se mueve, como la que cubre enormes agujeros, etc, porque ya saben que la próxima pieza puede ser usada para "arreglar" la situación. Si usted no tiene conocimiento de la siguiente pieza, que está constantemente tratando de desempeñar las probabilidades, tratando de mantener sus opciones abiertas en caso de que la próxima pieza no es ideal.
El siguiente esquema muestra cómo todos los movimientos posibles de la actual pieza se consideran, y para cada uno de esos mover consideramos todos los posibles movimientos que impliquen la siguiente pieza.
Estrategia de participación actual y la próxima pieza pieza
La Norma Tetris software utiliza esta estrategia cuando la "Siguiente Piece" está activada por el usuario y es visible en la pantalla, y cuando una de dos piezas A.I. está activado (como el escrito por mí, Colin Fahey). Si el "Siguiente Piece" no es visible en la pantalla, mis dos piezas corresponde a una de una sola pieza A.I..
Mi de una sola pieza A.I. es terrible si se compara con los demás AIs en el software estándar de Tetris; por lo que este le muestra la información más beneficiosa (por ejemplo: la siguiente pieza) puede ser A.I. a un sistema, es suficiente para mejorar el rendimiento de mi propia mediocre de dos piezas A.I. de varios órdenes de magnitud - superando fácilmente el rendimiento de los mejores de una sola pieza A.I. en el mundo.
(Sin embargo, la mejor conversión de una sola pieza A.I. en el mundo a considerar dos piezas fácilmente que mejorar en varios órdenes de magnitud, también! Conocer la próxima pieza es enorme!)
Mi primera prueba con mi juego de dos piezas A.I. duró aproximadamente 182 horas (7,6 días) en un 800 MHz PC, completando 7216290 filas. No he probado el algoritmo en un ordenador más rápido.
Cuando se guarda el estado de un juego de Tetris (Shift-W) a un archivo de texto, puede copiar y pegar la lista de números, desde la sección "heightHistogram", a una hoja de cálculo de Excel.
Cada bin en el histograma indica el número de movimientos que terminó con una pila de altura (después de completar las filas se eliminan). Como puede imaginar, haciéndole un gesto que elimina totalmente un montón es poco frecuente, por lo que el número total de movimientos que termina con un montón de altura cero es relativamente baja.
Mientras tanto, se puede esperar que la pila de altura generalmente fluctúa en torno a algunos medios, a fin de papeleras correspondientes a estas filas dominará el histograma. Por último, los silos para la parte superior de la mayoría de filas (en las que se encuentran en peligro de desbordamiento la junta) tienen muy bajas totales.
En el curso de muchas horas, con la A.I. jugar un solo juego usando la estrategia de conocimiento de la "Siguiente Piece", tomé muestras aleatorias del juego del Estado, copiando el montón altura histogramas a una hoja de cálculo como se muestra a continuación:
Pila altura histogramas registrada en diversos puntos en un típico juego (con la actual y la próxima estrategia de pieza)
Es posible ajustar la escala de cada histograma el número total de piezas (en total número de movimientos) para obtener los siguientes datos:
Histogramas escala, y una teoría
La cosa notable es que estos escala histogramas ver idénticas a pesar de los diferentes órdenes de magnitud del número de piezas (terminado se mueve) que participan.
Sólo mirando a los números que hice la hipótesis de que la cola de la curva es un decaimiento exponencial. Por ensayo y error hasta que vine con la áspera la teoría de que la cola fue descrito por:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
El gráfico siguiente muestra el histograma de escala para todo el rango de filas.
Gráfico escala de histogramas
Tenga en cuenta que la curva de 50000 piezas, y la curva de 2000000 piezas, y la curva de la cola teoría son casi indistinguibles a esta escala.
La siguiente es una mirada más atenta a la cabeza de la curva.
Parte inferior de altura histograma
La siguiente es una magnifica enormemente de vista de la extrema cola fin de medir el histograma y curvas teóricas.
Magnificado vista de la extrema cola fin de ampliar histogramas
Como se podría esperar, es muy raro que el montón para llegar a estas alturas incluso en experimentos a largo - pero incluso con nuestros limitados pruebas en esta región extrema, la teoría parece aceptable.
En el gráfico completo la teoría parece superponerse a la cola de la distribución "exactamente", mientras que en el gráfico magnificada de la cola de la cola, vemos aparente error. Sin embargo, afirman que esto se debe a la insuficiencia de datos para estas alturas extremas montón. Si se me aumentó el tablero para, por ejemplo, a una altura de 25 filas en lugar de 20 filas, de modo que los juegos no terminar abruptamente, creo que la teoría que he presentado anteriormente coincidiría perfectamente con la tendencia.
Mi sensación es que este es un histograma directo resultado combinado de los Tetris A.I. y las normas de Tetris. Así, esta misma distribución se observó para cualquier azar a largo plazo juego de Tetris usando mi particular A.I. estrategia para jugar con "Siguiente Piece" conocimiento.
Por otra parte, creo que este tipo de histograma se puede utilizar para comparar AIs que emplean la misma información mientras se reproduce. Por lo tanto, usted no tiene que jugar juegos completos (que pueden durar días o años) para comparar el rendimiento a largo plazo de diferentes algoritmos de estrategia.
Por ejemplo, a pesar de la sencillez de mi modelo, creo que puede ser usado para predecir la duración media de juego! Simplemente averiguar cuántas piezas hace que la "línea 21" montón altura un número significativo, tales como contar de uno.
La frecuencia relativa de la fila 21, de acuerdo con mi simple teoría, es la siguiente:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Usted debe multiplicar este número por (5.3 * 10^(7)), aproximadamente 50 millones de personas, para obtener un valor de uno.
Por lo tanto, más o menos predecir que mi actual "Siguiente Piece" estrategia sólo es bueno para el orden de aproximadamente 10 millones de terminado filas. Una razón por la cual hago esta estimación es el hecho de que incluso 18 filas puede ser mortal para mi A.I. porque yo no permitir que mi A.I. para examinar las piezas hasta que han caído en por lo menos una fila! (Esto es para no tener que preocuparse por no ser capaz de rotar las piezas.)
Estoy impresionado por el hecho de que sólo jugando 50000 piezas (y posiblemente un número mucho menor de piezas) puede darle una muy buena estimación de las consecuencias a largo plazo altura histograma, y por lo tanto, una buena estimación del orden de magnitud de las filas antes de terminado el juego termina. Este enfoque es sumamente valiosa para evaluar rápidamente los cambios sutiles en una A.I. que ya lo está haciendo muy bien.
6.10 Junta de evaluación métrica imitar especulativo look-ahead
Si un algoritmo, como el que he presentado con este proyecto, simplemente intenta todos pieza orientaciones y las traducciones para dejar caer, y las tasas resultantes de cada junta de configuración de acuerdo con alguna medida de mérito, el algoritmo es esencialmente imitando "look-ahead".
Cuando se emplea estadísticas como "pila de altura", "enterrados agujeros", "la rugosidad superficial" o "así profundidades", uno es realmente utilizando una forma simplificada de "mirar hacia el futuro". Estas caracterizaciones general de la junta dar alguna indicación acerca de la viabilidad a largo plazo del consejo de administración.
El enfoque ideal, habida cuenta de una infinita cantidad de potencia de cálculo, sería la de evaluar la configuración de una junta dotada de todas las posibles secuencias de pieza que puede seguir.
A pesar de que usted debe considerar las 7 piezas como son igualmente probables en cada nivel de look-ahead, que usted necesita para optimizar la traducción (hasta 10) y las orientaciones (hasta 4) para cada pieza en todo lo posible secuencia! Eso es hasta (7*10*4) = 280 sucursales en todos los niveles de la junta de evaluación! Por lo tanto, eso es hasta ((280)^(LookAheadLevels)) la configuración de la tarjeta considerar.
Porque tenemos que terminar el análisis después de un número finito de niveles, necesitamos tener algunos no-look-ahead método de evaluación de la junta estado - una forma de dar valores a los nodos hoja del árbol de nuestra búsqueda. Así que, para estos nodos hoja, nos vuelve a utilizar una fórmula que encarna general predictores de viabilidad futura de la junta!
Este tipo de especulación puede ser juzgado con las de una sola pieza y de dos piezas algoritmos en lugar de la junta de evaluación simplista métrica. Supongamos que todas las piezas son igualmente probables y resumir las capacidades de una junta para dar cabida a piezas de todo tipo en las mejores formas posibles. Esto puede llevarse a cabo con uno, dos, o cualquier número de pasar profundidades especulativo - con todas las piezas son igualmente probables (p=1/7).
La terminal de nodos de este árbol todavía podría exigir la ponderado métricas para evaluar, pero las capas más especulativo, precisamente, captar la esencia de lo que queremos hacer: Determinar la eficacia de una determinada tarjeta puede aceptar todas las piezas posibles, incluidos los factores positivos, tales como completar las líneas y factores negativos como el aumento general de pila altura, etc
7. Tetris A.I. sistema de demostración
7.1 Sistema de visión general
Este diagrama siguiente muestra experimental mi set-up.
En general el sistema de demostración
7.2 Equipo
Aquí hay una pequeña lista de los equipos utilizados en esta demostración:
[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)
Es evidente que puede utilizar aparatos similares para lograr los mismos resultados. Más detalles sobre el equipo se describen en las secciones correspondientes de este artículo.
He aquí una breve descripción de las computadoras personales utilizadas en esta demostración:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Esta demostración puede ser reproducida fácilmente con otros sistemas operativos, como Linux. Es más importante tener una CPU velocidad del orden de 800 MHz o más rápido para el ordenador que es correr el A.I. software, porque este equipo va a estar haciendo en tiempo real, procesamiento de vídeo.
7.3 Hardware de captura de vídeo
He utilizado una cámara de vídeo USB como un dispositivo de captura de vídeo para mi A.I. sistema. En concreto, he utilizado el Creative "WebCam Pro", USB una cámara de vídeo con resolución 640 * 480.
Creative(TM) USB cámara de vídeo descripción
USB cámara de vídeo (en ángulo)
USB cámara de vídeo (frontal)
USB cámara de vídeo (con junta CCD)
USB cámara de vídeo (principal chips)
OV511 grandes bloques (nota: USB cámara de vídeo es OV511+)
7.4 OV511 hoja de datos
ov511ds.pdf
Las hojas de datos OV511
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( "y más") característica diferencias
ov511plus_101.pdf
OV511+ característica diferencias
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Software de captura de vídeo
Microsoft tiene un muy antiguo API llamado "Video for Windows" (VFW) que he utilizado con éxito para este proyecto. (Usted enlace a "vfw32.lib" C++ en su proyecto, o hacer una DllImport de "vfw32.dll" C# en su código.) Ejemplos del uso de la VFW API están ampliamente disponibles.
Una alternativa es usar Microsoft's "DirectShow" API a hacer de captura de vídeo.
Porque VFW tomó sólo una docena de líneas de código a utilizar, y se lleva a cabo aceptablemente en mi 800 MHz máquina, no me molestan a explorar la alternativa APIs. Pero es un DirectShow más contemporáneo API para Windows de captura de vídeo, y posiblemente produce una mucho mayor velocidad de cuadro para el mismo hardware.
Vea la "CPF.StandardTetris.STVideoCapture" archivos de código fuente en el software estándar de Tetris para ver lo fácil que es obtener de captura de vídeo a su propios proyectos.
7.7 Interfaz de ordenador para relés (a través de RS232)
Para tener una computadora "presione las teclas" en el teclado de otro ordenador, he usado una "junta de relevo" controlada por los comandos de texto enviados desde un puerto de comunicaciones serie (por ejemplo: "COM1") a través de un cable RS-232. He utilizado cada relé para conectar los dos cables de un teclado para simular clave de pulsar una tecla.
Para ello era necesario abrir el teclado y hacer las conexiones. Hay muchos métodos más fáciles para simular clave pulsando en un ordenador, pero yo quería hacer algo que parecía lo más cerca posible de una persona realmente a escribir sobre un teclado.
Uno muy versátil y bien hecho bordo de relevo es el ADR2200 realizados por Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Usted puede ver el "CPF.StandardTetris.STRS232" archivos de código fuente para ver lo fácil que es enviar bytes a través de un puerto serie, que puede utilizarse para controlar dispositivos tales como los ADR2200 bordo se muestra arriba.
8. Tetris software estándar
8.1 Descargar software
Ir al principio de este artículo para encontrar un enlace para descargar el código fuente (C# y C++ versiones) y construido software (*.exe).
8.2 Resumen de las características
Características del software:
Instrucción y pantallas de créditos
Monocromo modo
Shadow modo
Sugerencia modo
Junk filas
Tasa de control
Siguiente pieza
Junta tamaño
S/Z piezas
Modo de calibración
Captura de vídeo y el reconocimiento
Consola de depuración
Guardar juego
Cargar partida
8.3 A partir de la apariencia
Apariencia cuando el software se inicia:
Apariencia cuando el software se inicia
8.4 Monocromo modo
Por defecto el consejo aparece en color:
Por defecto el consejo aparece en color.
El modo de color se puede cambiar a monocromo (Shift + K):
El modo de color se puede cambiar a monocromo.
8.5 Shadow modo
Shadow indica el modo en que un pedazo de tierra. Esto es muy útil para las grandes juntas, porque es difícil juzgar cuando un trozo de tierra.
Shadow indica el modo en que un pedazo de tierra.
8.6 Sugerencia modo
Sugerencia le muestra el modo en que el seleccionado actualmente-AI se trasladaría dada la situación actual. (Shift + H)
Sugerencia muestra el modo en que el seleccionado actualmente-AI se trasladaría.
8.7 Junk filas
Insertar "basura" filas en la parte inferior de la pila, uno por uno, manualmente. (Shift + J)
Insertar "basura" filas en la parte inferior de la pila.
8.8 Tasa de control
El '+' (más) y '-' (menos) las teclas de control de la velocidad del juego.
Por defecto, el juego funciona a un nivel de velocidad, de acuerdo con las normas estándar de Tetris (basada en la velocidad).
Aquí está un cuadro de los significados de velocidad sesgo:
-3,-4,...: lentitud proporcional al sesgo
-2: más lento que el nivel 1
-1: normal, pero limitada al nivel 6 (0,2 seg) de velocidad;
0: normal; Tetris estándar de control de velocidad;
+1: ligeramente más rápido que el nivel 9 (0.05 sec retrasos);
+2: delimitadas por tipo de prestación (por ejemplo: 75 Hz);
+3,+4,...: múltiples iteraciones prestados por marco;
Me gusta correr el A.I. en un entorno de "+2" (hit '+' clave dos veces si el sesgo comienza en cero).
Velocidad sesgo altera la velocidad del juego.
8.9 Mostrar siguiente pieza
Hit 'N' para alternar en "Siguiente Piece". El A.I. usaremos el siguiente pieza "información sólo si la" Siguiente Piece "aparece en la pantalla.
Usted puede estar seguro de que la AI no está utilizando "Siguiente Piece" información cuando usted no puede ver el "Siguiente Piece" en la pantalla.
Mostrar la siguiente pieza
8.10 Junta tamaño
Al presionar Ctrl + (izquierda, derecha, abajo, arriba), se puede ajustar el tamaño a bordo de tamaños arbitrarios de 4 * 4 hasta 200 * 400.
Junta tamaño: 4 * 8
Junta tamaño: 20 * 40
Junta tamaño: 40 * 80
Junta tamaño: 20 * 5
Junta tamaño: 4 * 100
8.11 S/Z sólo piezas
Estudio de la alternancia interesante S/Z patrón.
Este patrón no puede resolverse por un 10 * 20 bordo (anchura * altura).
Sin embargo, las juntas que tienen anchos que son múltiplos de 4 son trivially mostrado para permitir la supervivencia infinita.
El AIs sobrevivir indefinidamente en estos casos, aun cuando no estaban específicamente sintonizado para manejar esta situación patológica.
S/Z sólo piezas
8.12 Video modo de calibración
Hit 'C' para entrar en "modo de calibración". Cuando en modo de calibración, puede golpear las teclas numéricas: {1,2,3,4,5,6,7} para seleccionar una pieza {O,I,S,Z,L,J,T} en la parte superior del tablero que juega.
Esto es útil como referencia para la imagen de captura de vídeo en un segundo Tetris software estándar.
Si usted acierta los 0 (cero) clave, se efectuarán el tablero en blanco.
Usted puede pretender para desovar piezas de la selección de una pieza (1..7) y, a continuación, seleccionar un (0) en blanco, mientras que un segundo ordenador haciendo de captura de vídeo para piezas de relojes.
Puede ejecutar el A.I. en el segundo ordenador y ver cómo se trata de su introducido manualmente escenarios patológicos Tetris!
Modo de calibración es la única vez que se puede manipular la captura de vídeo de procesamiento de imagen plantilla (4 * 2 red). Puede usar el ratón para dibujar el rectángulo, pero entonces usted puede utilizar las teclas de cursor ( "arriba", "abajo", "izquierda", "derecho") para tener buen control de las fronteras - con ayuda de la Shift clave para seleccionar frente a las fronteras del rectángulo (por ejemplo: "Shift izquierda" combo es diferente a la "izquierda").
Video modo de calibración
8.13 Captura de vídeo y el reconocimiento
Al pulsar "V 'cambia el modo de captura de vídeo. Si bien calibrado (véase el "vídeo de calibración" en una sección anterior), las piezas de una pantalla de vídeo remoto serán capturados por la cámara de vídeo y clasificado - y las piezas se generó en el local de juego para la A.I. para examinar y reaccionar .
El A.I. de salida debe ser de transmisión (a través de la interfaz RS-232 en la manifestación se describe en este artículo) para el mando a distancia juego de entrada (por ejemplo: el teclado) para la A.I. para desempeñar con éxito el juego a distancia.
Si en algún momento de este circuito cerrado se ve perturbado (por ejemplo: el mal funcionamiento de captura de vídeo, la señal de salida o mal funcionamiento), entonces la A.I. desarrollará una falsa impresión del estado de juego del mando a distancia, y la A.I. hará inadecuado decisiones que pierden rápidamente el juego .
(Nota: Este problema se puede superar con una modesta cantidad de esfuerzo: A.I. El sistema sólo necesita examinar toda la pantalla remota Tetris en curso para una "realidad" de toda la junta, y la A.I. sistema debe estar preparado para algunos comandos de salida para no de alguna manera.)
Captura de vídeo y el reconocimiento
9. Tetris original experimento AI (2003)
Lo siguiente muestra la primera versión de trabajo del sistema A.I. Tetris en 2003.
La cámara de vídeo frente a la computadora # 1 de lanzar cualquier sencillo juego Tetris
Ordenador # 2 en funcionamiento el software estándar de Tetris en modo A.I.
Izquierda: Dibujo red para calibrar el reconocimiento de imágenes de vídeo;
Derecha: Tetris pieza reconocimiento casos.
Frame del vídeo de Tetris A.I. experimento en 2003
10. Mejor de una sola pieza de juego Tetris algoritmo en el mundo
10.1 Pierre Dellacherie (2003; Francia)
Pierre Dellacherie (2003; Francia), desarrollador de los mejores de una sola pieza de juego Tetris algoritmo en el mundo
La mejor de una sola pieza, en tiempo real Tetris algoritmo a mi conocimiento fue creado por Pierre Dellacherie de Francia.
Su increíble algoritmo a veces se llena más de 2 millones de filas!
El rendimiento medio es del orden de 650000 registros.
El algoritmo tiene muy poca memoria, y corre a alta velocidad (alrededor de 160 líneas por segundo a 800 MHz mi ordenador).
La ejecución de Pierre Dellacherie's algoritmo:
Mi modelo actual para el desempeño de Tetris IAs es que para cualquier obra hay una constante probabilidad de que el juego dará por terminado, p.
Por lo tanto, la probabilidad de que una pieza no terminar un juego es q=(1-p).
La probabilidad de que el juego se da por concluida después de k mueve es simplemente el producto de la probabilidad de supervivencia (k-1) se mueve, es decir, q^(k-1), y la probabilidad de que se termine en el siguiente movimiento, es decir, p.
Esto corresponde a un "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 los pequeños p, ln(q) es aproximadamente (-p), y tenemos las siguientes:
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 la fracción del número total de juegos desempeñado a terminar con un número de filas en el intervalo de [k1, k2] a ser:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Después de completar 36 juegos en mi equipo, a lo largo de un período de dos días, me encontré con un promedio de 674827 completado filas.
De acuerdo con la teoría general por encima, espero que la siguiente fracción relativa de juegos para terminar en la siguiente fila completará las gamas:
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
Aquí hay un gráfico que compara los Exponential Distribution teoría con la que se observa la distribución de juegos.
La ejecución de Pierre's algoritmo completado más de 36 juegos
Aunque hay muy pocos juegos en este conjunto de datos, es evidente que el modelo es bastante bueno se pongan en venta en la distribución observada.
Pierre's introducción de su algoritmo:
Pierre empezó a trabajar en esto de una sola pieza en el algoritmo de 2003,1.
Pierre me envió un e-mail acerca de su algoritmo en 2003.4.9, enviando el siguiente rendimiento de más de 20 juegos 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.
"El algoritmo se ejecuta en Turbo Pascal completa y 7000 filas / min. Athlon 1600+ con una".
I convertidos Pierre's algoritmo para C++ a 2003,6, después de varios intercambios por correo electrónico con Pierre. Hemos comprobado que la A.I. en la versión C++ hecho las mismas decisiones de la Pascal versión.
Me observó un rendimiento similar a su informe original; media de alrededor de 650000 completado filas, y algunos juegos de completar 2 millones de filas.
Increíble!
10.2 Conversación con Pierre Dellacherie
[1] ¿Cuándo fue la primera creación de este código?
He estado trabajando en el algoritmo de finales de enero de 2003 hasta ahora.
[2] ¿Cuánto tiempo has trabajado?
He trabajado en casi todas las semanas ... pero no todos los días largo porque tengo otras actividades: por desgracia, tengo que ganar dinero como cualquier otra persona!
[3] Lo que inspiró el diseño del código?
Tetris he jugado 10 ó 15 años atrás, pero yo no había jugado de nuevo durante mucho tiempo. Yo diría que soy un "medio" jugador que conoce las reglas y algunos trucos.
Sin embargo, cuando comencé a trabajar en el algoritmo no jugar tanto porque me pareció que era bastante más eficaz para vigilar el ordenador de jugar y analizar sus debilidades.
[4] ¿Utilizó alguna de automatización para “capacitar” a su código para realizar mejor? ¿Tiene usted alguna información para mejorar el algoritmo?
¿O simplemente mirar los resultados y decidir que hacer modificaciones?
Soy de “la vieja escuela:” Yo simplemente miraba los resultados y decidió a realizar modificaciones.
"Aprendizaje automático" es un tipo de meta-algoritmo para que no estoy seguro de que hacerlo de esta manera sería más fácil llegar ya que este meta-algoritmo tendría que ser construido demasiado y que no es tan fácil!
Lo que es más, estoy de acuerdo con Roger Penrose cuando dice (en su libro "Shadows of the mind") que la comprensión humana y la intuición no puede ser algorítmico (ejemplo: computable).
[5] ¿Cuándo empieza a jugar Tetris, y cuándo usted tiene la idea de la solución de Tetris con un A.I.?
Enseño algorítmica y programación informática (Turbo Pascal y Scilab) para los estudiantes que entrenar para examen de ingreso a ingeniero de las escuelas.
En un primer momento, "juega Tetris Computer" fue una idea que quería desarrollar para mis alumnos el próximo año.
Yo no estaba consciente de su página web cuando empecé a trabajar en el algoritmo.
De hecho yo fui afortunado al ser conscientes de su página web sólo hace unas semanas, porque creo que habría sido desalentados por los resultados (como podría adivinar, las primeras versiones de mi algoritmo no jugar tan bien!).
[6] ¿Cuál es su situación actual?
Estoy casi 30 [antes de 2003 Abril 27]. Tengo varias actividades: Soy un violonchelista, componer música y enseñar la programación de computadoras.
Tengo una maestría en musicología (1994) y un "Artificial Intelligence and Algorithmic" diploma (1998).
En Francia, este diploma se corresponde con el 5 º año estudiando en la Universidad (4 º año es la maestría y 6 º año es la tesis).
Pierre's composiciones:
[7] ¿Dónde vive?
Soy francés y vivo en Rouen (Normandía).
[8] Otros comentarios:
Al final no he cualquier nueva idea para mejorarla.
He tratado tanto inútil (y tonto) las cosas que dudo que se podría mejorar.
Por otro lado, creo que pueden existir completamente diferentes algoritmos que podría tener mejores actuaciones.
Por cierto, una prueba más rápido consistirá en el lanzamiento de las piezas en una caja de media (10 filas x 10 columnas): en un medio-box, mi algoritmo hace un promedio de 280 completado filas.
Una cosa más: el algoritmo puede ser fácilmente modificado de una doble capas algoritmo ([lo haré] las pruebas antes).
Me encanta la música de cine: convertirse en un compositor de cine es parte de mis principales sueños (pero es sólo sueño!).
11. Mejor jugador humanos en el mundo
11.1 Japonés Tetris Master (2001 Enero 27) vídeo
Tetris maestro (2001, Japón) vídeo
Arika presenta el japonés Tetris Finales maestro (2001 Enero 27). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Reacción
12.1 Slashdot hilo (2003)
En 2003, mi Tetris A.I. proyecto fue discutido en el foro Slashdot Internet (
http://slashdot.org).
Slashdot (http://slashdot.org) titular foro en Internet para una discusión de mi proyecto 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 en mi Tetris A.I. proyecto (2003) (la primera vez que he inspirado un cómico!)
Comic inspirado en mi Tetris A.I. proyecto (2003) (la segunda vez que he inspirado un cómico!)
13. Historia del proyecto Tetris A.I.
En la primavera de 1989 yo estaba ocupado saltar (y no) de segundo semestre primer año clases en la University of Pennsylvania.
Uno de mi habitación, Bill Matthews, tuvo la Mac Classic, ya veces jugado videojuegos.
Las personas que obtener Ivy League admitidos a las escuelas suelen ser inclinados a competir con otras personas en todo momento - por lo que cuando se Bill el juego Tetris para su Mac, que inmediatamente comenzó a largo plazo batalla por la puntuación más alta.
Como los puntajes subieron, el tiempo las inversiones necesarias para hacer una pequeña ganancia aumentado espectacularmente.
Para hacer una larga historia corta, Bill supuestamente tiene la puntuación más alta entre nosotros, pero sospecho que lo de utilizar ResEdit hacking y la puntuación de archivo!
Bill tenido clases en la escuela Wharton de los negocios, los alma mater de Michael Milken y Donald Trump, por lo que no es inconcebible que alguien amañado un imposible puntuación más alta ...
En el verano de 1990 tomé prestado un 30 MHz Intel 80386 IBM PC de mi habitación, Alex Haidas.
Compré un teclado Mac en un mercadillo de $ 1.
I construido puerto paralelo circuitos para permitir la PC para controlar la Mac teclado.
(I CMOS 4040 utilizado un chip para actuar como un tipo de estado sólido relevo a unirse teclado contactos Mac en el interior del teclado.)
Yo escribí un programa de ordenador que utiliza un árbol de decisiones como su estrategia para jugar el juego Tetris. En apenas unas semanas tuve una PC jugando el juego Tetris se ejecuta en un Mac.
Sin embargo, me ha obligado a utilizar el teclado PC decirle al A.I. caer sobre cada pieza en la pantalla.
Comencé a trabajar en un circuito utilizando CdS (Cadmium Sulfide) detectores de luz que magra Mac contra la pantalla y "ver" la caída de piezas, pero CdS sensores reaccionado con demasiada lentitud a los cambios en el brillo y el contraste entre piezas de Tetris y el fondo en la pantalla Mac Classic era demasiado bajo para discriminar fiable.
En aquellos días yo no tenía mucho dinero, por lo que era demasiado arriesgado comprar a $ 2 Radio Shack fototransistor que no podría hacer lo que yo quería.
Además, habida cuenta del contraste problema, yo estaba pesimista acerca de todo el enfoque.
Cuando compré mi primer ordenador personal en 1996, no he podido obtener en virtud de software Windows 95 en un 100 MHz CPU a hacer de procesamiento de vídeo con la suficiente rapidez como para hacer un simple sistema de visión trabajo.
Yo escribí el código de procesamiento de imágenes en lenguaje ensamblador, pero había tanto generales antes de que mi código en realidad recibió datos de vídeo que parecía imposible de hacer cualquier cosa que vale la pena.
En 2003, la tecnología, en particular CPU velocidad, ha llegado a un nivel que hizo terminar el proyecto casi trivial.
I excavado hasta mi viejo proyecto personal y, por último, acabados, obteniendo un cierto sentido de cierre.
Fue muy emocionante ver un equipo jugando otro ordenador a través de la USB cámara de vídeo y los enlaces.
El sonido de clic en los enlaces, y viendo girar las piezas y soltar en ridículo, superhuman velocidades, hizo la experiencia muy satisfactoria en una forma multisensorial.
En 2003, mi labor fue reconocida por Slashdot (
http://slashdot.org), y he recibido mucho de las opiniones.
Fui invitado a aparecer en el "Screen Savers" de televisión sobre la televisión digital TechTV red.
Fui a San Francisco y apareció en el show, y la experiencia fue genial.
Más tarde en 2003, he recibido un mensaje de Henk Rogers, haberme invitado a Hawai a reunirse con él y Alexey Pajitnov para hablar sobre el establecimiento de algún tipo de norma para Tetris, a los fines de contar con torneos de Tetris.
Un especial interés se permita a los jugadores utilizar los teléfonos móviles para “competir unos con otros,” indirectamente, a través de A.I. que imita a los jugadores (de un análisis previo de cada una de las acciones del jugador), evitando así los efectos del teléfono móvil de latencia de acceso a Internet, y permitiendo a los jugadores “competir contra” * Los mejores jugadores humanos en el mundo (*... o, más bien, A.I. imitando a los mejores jugadores humanos en el mundo).
Yo estaba muy emocionado por la perspectiva de la reunión el creador de Tetris. Por desgracia, volando me hace ansiosa, y yo declinó la invitación.
En 2006, convertido mi "Standard Tetris" software de C++ a C# para hacer el software más accesible y útil para los programadores contemporánea.
