Tetris
Colin Fahey
1. Logiciels
StandardTetris_2007June4.zip
Tetris code source (C# et C++ versions) et des programmes (« exe »);
4068277 bytes
MD5: 4e957e0ead66064183e9f7e04e618ec0
2. Introduction
Cet article décrit comment un ordinateur peut jouer le classique jeu vidéo Tetris par obtenir des informations sur le conseil, la détermination de bonnes actions, et la réalisation de ces actions.
Cet article comprend un logiciel capable de jouer Tetris en temps réel.
Le logiciel comprend les meilleurs temps réel du jeu Tetris algorithme dans le domaine public.
Cet article définit des règles « standard » pour « Tetris, » une spécification basée sur l'original 1986 pré-version commerciale de Tetris pour les Personal Computer (PC).
En 2003, le logiciel inclus dans le présent article a été utilisé pour permettre à un ordinateur pour jouer Tetris tourne sur un ordinateur distinct.
Un simple USB caméra vidéo a été utilisée pour permettre à l'ordinateur pour « voir » l'écran de l'autre ordinateur.
Un relais bord a été contrôlé par une interface RS-232 pour permettre à l'ordinateur « appuyez sur des touches » sur le clavier de l'autre ordinateur.
Ainsi, le premier ordinateur a une relation à la deuxième ordinateur qui est semblable à un joueur humain typique de la relation à un ordinateur lors de la lecture de Tetris, le jeu état n'est connue que par la recherche à l'écran, des actions et le joueur ne peut se faire qu'à travers un clavier .
La configuration dans cette démonstration établi qu'un ordinateur peut jouer Tetris mieux que l'homme, dans des conditions normales en temps réel conditions de jeu Tetris.
3. Histoire de Tetris
En 1985, Alexey Pajitnov et Dmitry Pavlovsky sont les ingénieurs informaticiens à la Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre du Russian Academy of Sciences
Alexey et Dmitry étaient intéressés dans le développement et la vente de dépendance des jeux vidéo.
Ils ont testé plusieurs jeux différents.
Alexey a été inspiré par le grec ancien jeu de puzzle, Pentaminos, qui implique l'organisation de pièces de puzzle de cinq places.
Alexey pensée de l'idée d'organiser Pentamino pièces comme ils sont tombés à une coupe rectangulaire, mais s'est rendu compte que les douze cinq différentes formes carrés étaient trop complexe pour un jeu vidéo.
Alexey connectée à la base de sept « tetramino » morceaux, chacun constitué de quatre carrés.
En 1985.6, Alexey Pajitnov programmé la première version de Tetris sur un Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov, et Tetris.
En 1985-1986, Vadim Gerasimov, une de 16 ans de lycée ordinateur prodige qui a travaillé à l'académie, mise en œuvre de Tetris pour la IBM PC fonctionnement du système d'exploitation MS-DOS.
(Vadim Gerasimov plus tard que la recherche au MIT Media Laboratory, de 1994 à 2003, la réception d'un doctorat après l'achèvement de nombreux projets intéressants:
http://vadim.www.media.mit.edu)
L'introduction de l'écran 1987-1988 pré-commerciale de Tetris pour la PC
Le jeu écran de l'1987-1988 pré-commerciale de Tetris pour la PC
Après 1987, Tetris se propager partout dans le monde entier.
The Tetris Company, LLC, est propriétaire de la marque Tetris.
4. Projets inspirée par Tetris
4.1 0-dimensional Tetris
Pas encore développé.
4.2 1-dimensional Tetris
Ziga Hajdukovic a développé 1-dimensional Tetris logiciel qui peut être joué dans un navigateur Internet.
Ziga Hajdukovic a également mis au point 1-dimensional Tetris logiciels pour les téléphones mobiles utilisant la plate-forme Java J2ME.
4.3 2-dimensional Tetris
Toutes les variantes de Tetris classique sont dans cette catégorie.
Cette section comprend intéressantes variantes.
4.3.1 Le plus grand jeu jamais Tetris: Delft University of Technology (1995)
Tetris joué sur un bâtiment; 2000 m^2 surface; Delft University of Technology (1995)
Tetris joué sur un bâtiment; 2000 m^2 surface; Delft University of Technology (1995)
4.3.2 Un autre jeu Tetris sur un bâtiment: Brown University (2000)
Tetris jeu en utilisant les lumières dans les fenêtres d'un immeuble à Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
« Je pense qu'il était tout simplement le plus incroyable d'un jour chose que j'ai pu imaginer dans ma vie. Comme Steve Jobs toujours dit, le voyage est la récompense. »
« Il me fait penser de projets que nous ne retour au collège. Les choses qui étaient presque annulée que d'autres personnes ne pensent de faire. »
Steve Wozniak (2000)
4.3.3 Navigateur Internet jeu avec MIT « Green Building » image
Vadim Gerisimov's navigateur Internet Tetris
Ce navigateur Internet variante de Tetris a été créé par Vadim Gerasimov.
Ce navigateur Internet Tetris « Green » les caractéristiques de construction sur le campus de MIT.
Cette variante de Tetris a seulement neuf colonnes au lieu de la norme dix colonnes.
Cette variante de Tetris présente de nouvelles pièces avec des orientations aléatoires.
Vadim Gerasimov est la personne qui a écrit le code informatique pour la PC version de Tetris en 1986.
Vadim Gerasimov n'a Ph.D. à la recherche MIT Media Laboratory au cours de 1994-2003, travaillant sur de nombreux projets intéressants.
4.3.4 PIC16F84 12 MHz microcontrôleur à base de NTSC / PAL jeu vidéo Tetris
PIC16F84 12 MHz microcontrôleur à base de NTSC / PAL jeu vidéo Tetris
L'image ci-dessus montre la NTSC / PAL vidéo produite par un microcontrôleur PIC16F84 12 MHz fonctionner des logiciels écrits par Rickard Gunee dans 1998.
Le signal vidéo est généré par un logiciel de contrôle des sorties numériques.
4.3.5 « Scopetris » oscilloscope Tetris par Lars Pontoppidan (2007.8)
« Scopetris » oscilloscope Tetris par Lars Pontoppidan (2007.8)
Lars Pontoppidan a écrit le code pour AtMega32 microcontrôleur, et a ajouté simple circuit analogique, de créer une version de Tetris qui pourrait être joué sur un oscilloscope.
Certains registres du contrôle AtMega32 microcontrôleur 8 bits signaux de sortie et, le cas passés par une résistance électrique « R-2R » circuit numérique-analogique (D/A) de conversion, les signaux analogiques peuvent contrôler la (x,y) coordonnées d'un oscilloscope de faisceau (lorsque l'oscilloscope est réglé sur « le mode X-Y). »
YouTube vidéo:
FLV vidéo:
4.3.6 Obfuscated code Tetris: C / Unix
Les informations suivantes ont été accordées « 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 code Tetris: Perl code
Ce qui suit est Tetris pour la Perl interprète: Perltris (version 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) est un standard pour décrire les objets graphiques en utilisant XML.
Mozilla SVG Tetris: Tetris mises en place en utilisant une description Scalable Vector Graphics (SVG)
4.3.9 Google « widget » Tetris
Google, Yahoo!, et Microsoft, et d'autres entreprises, ont fait la promotion de miniatures Internet des logiciels basés sur le nom « widgets » qui sont généralement caractérisés par une utilisation dynamique des données disponibles sur l'Internet.
L'un de ces widget disponibles par le biais de Google est un jeu Tetris.
L'exemple suivant est mignon, mais les formes tourner dans ennuyeux façons:
Google « widget » Tetris
Autres Google widgets:
4.3.10 MIT document de recherche: « Tetris is Hard, Even to Approximate » (2002)
Le document de recherche ci-après contient une preuve qu'une certaine variante de Tetris est « NP-complet. »
Erik D. Demaine, Susan Hohenberger, et David Liben-Nowell, « Tetris is Hard, Even to Approximate », Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
« NP-complet » est un classement des temps et l'espace coût coût d'un algorithme.
D'autres classifications, « P » et « NP ».
Une classification des « NP-complet » implique que, pour les problèmes de plus de quelques petites taille, l'algorithme est peu probable de trouver une solution souhaitée dans une pratique de temps ou d'espace.
4.3.11 Document de recherche: « Applying reinforcement learning to Tetris »
Le document suivant, publié 2005.5.30, par Donald Carr au département Informatique à Rhodes University, l'Afrique du Sud, présente l'application de « l'apprentissage par renforcement » de Tetris.
4.3.12 Tetris jupe (2007.11)
Tetris jupe (2007.11)
La jupe de Tetris a été créé par « Lucy » (« hissyfitoly » sur etsy.com) avant 2007.11.
De la description du créateur de la jupe (offert à la vente sur 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."
Forum de commentaires au sujet de cette jupe:
« Jupe homme qui aspire à Tetris »
« Ahahahaha, je pensais la même chose. »
« Il ya une ligne vers le bas au fond ... achevé lignes disparaissent. » «&NBSP;FAIRE PLUS DE&NBSP;» « . »
« Il devrait y avoir une place à l'arrière ou l'avant long morceau où s'intégrerait parfaitement ... »
« C'est vraiment une jupe si moche. Mon ami n'a pas pu m'acheter suffisamment de chocolat et des fleurs à me convaincre de porter ce truc. »
4.3.13 Tetris stade acte (2007.4)
Tetris stade acte (2007.4)
« De ceux qui ont la Triforce vous en 2006 ... Comes la prochaine génération de sketch objet inanimé ... Tetris. »
- En cache localement dans Flash vidéo (FLV) le format vidéo (utilisation VLC à jouer):
4.3.14 Hilarious Tetris variations sur une émission de télévision japonais
Tetris variations sur japonais émission de télévision
Cette séquence vidéo à partir d'une émission de télévision japonaise comprend hilarante variations de Tetris, y compris:
pièces qui disparaissent à l'atterrissage, une pièce qui remplit toute une ligne (donc de remplir une ligne à l'atterrissage), plusieurs pièces relevant simultanément, pièces de forme irrégulière, un long morceau qui est un peu trop large pour s'adapter à un écart (prévention d'un 4-ligne achèvement!), Mario frapper un champignon et de devenir énorme et de la mort!, petit morceau de débris restant après les lignes sont détruits, la hausse la gravité des pièces flottent vers le haut, etc
- En cache localement dans Flash vidéo (FLV) le format vidéo (utilisation VLC à jouer):
4.3.15 « The Original Human TETRIS Performance by Guillaume Reymond » (2007.11)
« The Original Human TETRIS Performance by Guillaume Reymond » (2007.11)
De la description de YouTube:
« TETRIS joué par de vrais êtres humains-assis dans un auditorium: »
TETRIS est la 4ème performance vidéo de la GAME OVER Project, réalisé par l'artiste suisse Guillaume REYMOND (NOTsoNOISY agence de création).
Ce stop-motion vidéo a été tournée et jouée pour « LES URBAINES » festival
http://www.urbaines.ch au Palais de Rumine (Lausanne, Suisse) sur November 24th 2007.
- En cache localement dans Flash vidéo (FLV) le format vidéo (utilisation VLC à jouer):
4.3.16 2.5-dimensionnelle Tetris
Le terme « 2.5-dimensionnelle » est utilisée ici pour signifier un non-orthogonal vue d'un deux-dimensionnelle version de Tetris, avec peu d'épaisseur dans la troisième dimension.
(Trouvez le lien « tetris3d » dans « F7: GAMES ».)
4.4 3-dimensional Tetris
Linux / GTK version
Trois dimensions de Tetris, sous la forme d'une applet Java pour les navigateurs Internet:
Trois dimensions de Tetris pour la Windows système d'exploitation:
4.5 4 dimensions Tetris
Greg Kaiser's « HyperTetris » (1996): un 4-dimensional Tetris
En [1996], [...], Greg Kaiser mis en place un quatre dimensions variante sur le jeu classique.
Utilisation IrisGL (a.k.a. igl) il a créé un groupe de travail, si difficile à jouer, jeu en utilisant quatre sous-écrans pour décrire différentes dimensions de trois aspects de l'ensemble de l'espace-jeu.
[Car] il n'est pas facilement un [compréhensible] façon de tirer quatre-D objets sur un deux-D écran, les quatre sous-vues sont une méthode pratique pour manipuler et visualiser la rotation et la traduction des pièces à travers les quatre dimensions ( dans le jeu x,y,z,w).
Plutôt que de remplir des lignes de blocs comme dans l'original, l'objectif dans ce cas est de combler un cube dans la x,y,z subview (généralement 4 par 4 par 4).
Les autres subviews qui contiennent la dimension « w » sont classés par défaut dans un 4 par 4 de 10 bloc accord avec « w » être long, « vertical » dimension dans les trois cas, avec différentes bases de (x,y), (x,z), (y,z).
Gravité des actes dans l'« -w » direction, de sorte pièces « tomber » dans les trois à long subviews qui comprennent « w », et ne bougent pas à moins que par lecteur dans la dernière (x,y,z) subview.
Il prend un certain temps à s'habituer à-dire le moins.
Si, par miracle de patience ou de modifier les paramètres du jeu, on ne complète un cube, il disparaîtra comme les lignes ne achevé dans le Tetris original, mais pas de client est conservée dans HyperTetris.
Benjamin Bernard (2000)
4.6 N dimensions Tetris
Polytope Tetris (2003): un N dimensions Jeu de Tetris
Polytope Tetris est n dimensions Tetris.
Inspiré par le programme HyperTetris, Polytope Tetris vous permet de tonnes jouer en toute Tetris NOMBRE DE dimension.
Jouer à Tetris 3D, 4D, 5D, ou plus.
HyperTetris est beaucoup catchier nom que Polytope (bat) Tetris, mais je ne peux pas voler le nom.
5. « Tetris » spécification « standard »
5.1 Introduction
La définition de la « norme de Tetris » est un modèle idéalisé des caractéristiques les plus importantes et les comportements de la première IBM-PC mise en œuvre du jeu Tetris (vers 1986-1988).
Le modèle idéalisé est basée sur l'apparente déduire les intentions des développeurs de la première IBM-PC mise en œuvre du jeu Tetris.
Par exemple, il semble raisonnable de supposer que les développeurs de la première IBM-PC mise en œuvre du jeu Tetris destiné à sélectionner la forme de chaque nouvelle pièce relevant « hasard, » et que l'utilisation de la Borland C application de la rand() fonction est simplement un rapprochement des pratiques l'intention.
La définition de la « norme Tetris » précise que la forme de chaque pièce nouvelle baisse doit être choisi « de manière aléatoire. »
Cet idéal de comportement ne peut être réalisée par toute mise en œuvre, mais la mise en œuvre peut rapprocher les comportement idéal.
Bien qu'il n'existe pas de la mise en œuvre peut parfaitement appliquer la définition de la « norme de Tetris, » les idéaux de la « norme Tetris » associer des caractéristiques objectives, et la mise en œuvre peuvent être comparées en fonction de leur proximité par rapport aux idéaux de la « norme de Tetris. »
Cette section décrit un ensemble d'éléments, des comportements et des règles qui, collectivement, de définir « la norme de Tetris. »
5.2 Standard Tetris bord
Le conseil est une grille de cellules, ayant 10 colonnes et 20 lignes, pour un total de 10 * 20 = 200 cellules.
Standard Tetris bord (10 colonnes, 20 lignes)
Chaque cellule peut être soit inoccupés (vide) ou occupés (complet).
5.3 Standard Tetris pièces
Il ya sept (7) Tetris pièces standard, avec la lettre suivante noms:
{ O, I, S, Z, L, J, T }
La lettre noms sont inspirés par les formes des pièces.
Les sept pièces standard Tetris et leurs « orientations »
Le point à (0,0) coïncide avec la position (6,20) bord lorsque la pièce la première fois.
La première colonne indique les « orientations » initiales.
Par la suite, le mot « orientation » est utilisé pour décrire tout état d'une pièce, dans un ensemble de permis aux États, qui peuvent résulter d'un événement dans le sens de rotation.
Changer « l'orientation » de une « orientation » d'un « I, S, » ou « Z » pièce, exige la combinaison d'une rotation et une traduction.
Par conséquent, le mot « orientation » est utilisée ici pour signifier quelque chose de plus que la seule rotation.
Toutefois, « l'orientation » peut changer seulement en réponse à un événement dans le sens de rotation, et le cycle des « orientations » distinctes pour chaque pièce rapproche, ou des allumettes, le cycle résultant de la rotation pure.
L'utilisation particulière du mot « d'orientation, » dans ce contexte, est presque équivalente à la signification du mot ou de « l'angle de rotation, » mais le mot « orientation » est utilisé à la place de la « rotation » de tenter d'attirer l'attention sur le fait que certaines pièces nécessitent plus de rotation pour produire le ensemble de permis aux États résultant de « la rotation » dans le sens des événements.
Pièces ne peuvent changer leur orientation (ou subir une horizontale ou verticale traduction) si l'état résultant de la pièce n'aurait pas occupé (complet) des cellules au-delà du domaine du conseil et n'aurait pas occupé les cellules qui se chevauchent tout actuellement occupés cellules du conseil.
(Dans cette règle, occupés (complet) des cellules de la pièce ne sont pas considérés comme faisant partie des « cellules actuellement occupés du conseil »
Dans les observations ci-après, toute référence à un résultat d'un événement dans le sens de rotation est effectuée avec l'hypothèse qu'une telle rotation peut être effectué, étant donné les conditions actuelles de la pièce et le conseil.
Le « O » (boîte) le morceau ne dispose que d'une seule orientation, et ne modifie pas l'emplacement de l'un de ses occupés (complet) des cellules en réponse à un événement dans le sens de rotation.
Le « I » (ligne) pièce a deux orientations possibles, figurant initialement dans une orientation horizontale.
« I » La pièce alterne entre les deux orientations en réponse à successives dans le sens de rotation.
Le « S » et « Z » pièces ont chacun deux orientations possibles.
Ces pièces chaque alterner entre deux orientations en réponse à successives dans le sens de rotation.
Le « L », « J », et « T » pièces ont chacune quatre orientations possibles, et ces orientations sont le résultat de simples rotations sur des points centraux sur les formes.
Quand une pièce apparaît sur le plateau, la pièce a son « grand axe » dans une orientation horizontale, et la pièce est au dessus du conseil.
Par conséquent, aucune pièces sont d'abord susceptibles d'avoir changé leurs orientations. La pièce doit descendre par une rangée d'avoir la possibilité d'avoir changé son orientation.
Une fois un morceau a diminué par une rangée sur le plateau, toutes les orientations pièce peut être atteint (en supposant que la pièce n'est pas trop étroite aux parois latérales ou à la pile de pièces).
5.4 Standard Tetris organigramme
Ce qui suit est un schéma approximatif pour un jeu standard Tetris.
Diagramme approximatif pour un jeu standard Tetris
Diagramme approximatif pour un jeu standard Tetris
5.5 Standard Tetris pièce création
Le schéma suivant montre l'(4 * 2 cellule cell) région sur la carte où figurent toutes les pièces lors de sa création.
Région où les pièces apparaissent lors de sa création dans la norme Tetris
Quand une nouvelle pièce apparaît sur le plateau, son origine coïncide avec le point sur ce schéma, et la pièce sera entièrement contenu dans un endroit ombragé sur ce diagramme.
Quand un nouveau jeu est lancé, une chute libre délai s'écoule, et sur la première chute libre itération une pièce est donné naissance au sommet du conseil.
Dans des conditions normales de jeu, quand une chute libre itération « terres » une pièce, une chute libre de retard et s'écoule sur la prochaine chute libre itération une pièce est donné naissance au sommet du conseil.
Quand une pièce est donné naissance, le type de pièce est choisi en utilisant l'algorithme suivant:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Parce qu'il ya une constante p (= 1/7) chance de choisir un type de pièce, et toutes les pièces du même type sont identiques, la probabilité d'avoir exactement k pièces d'un type particulier après n procès suit une loi binomiale:
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 )
Lorsque nous choisissons parmi les sept (7) morceaux au hasard, la probabilité d'obtenir une pièce spécifique est p=(1/7).
Si nous ne n=70 cette fois, par exemple, la probabilité d'obtenir exactement k pièces (avec k dans la gamme 0 à n) est donnée par la loi binomiale, comme le montre l'image suivante.
Binomial distribution pour n=70, p=(1/7)
Ainsi, on peut prédire le total moyen des pièces d'un seul type donné un nombre total de pièces au hasard, et l'on peut également calculer la variation attendue et l'écart-type (racine carrée de la variance):
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
Lorsque nous convertir une valeur aléatoire à un morceau indice, nous l'interprétons comme suit:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[Le pré-commerciale MS-DOS version de Tetris utilisé la fonction de nombres aléatoires offert par le compilateur Borland Pascal.
Cette fonction utilisé une 32-bit variable d'état.
Par conséquent, la séquence de nombres aléatoires a été limitée à 2^32 valeurs distinctes.
Par conséquent, en principe, un joueur peut découvrir, peut-être après avoir déposé 10 pièces, le lieu exact de l'ensemble des 2^32 des numéros correspondant à l'état actuel de la partie.
Si Tetris simulations sont effectuées avec la séquence fixe de 2^32 morceaux, puis optimale les décisions peuvent être trouvées pour chaque lieu dans la séquence.
(Il semble y avoir suffisamment d'occasions d'être le conseil d'un conseil totalement vide état, ce qui nous permet d'obtenir synchronisé avec la solution optimale précalculées chemin.)
Le risque d'utiliser un simple générateur de nombre aléatoire dans une simulation visant à trouver une solution optimale à un problème, c'est que la solution optimale sera uniquement pour le chemin à travers l'espace, sélectionnez le problème par la simple générateur de nombres aléatoires. ]
5.6 Standard Tetris contrôles
Au cours de jeu, les entrées suivantes sont 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
Toutes les entrées de prise d'effet de l'augmentation de pointe de la contribution positive (appuyez sur le bouton, par opposition à la libération bouton).
Quand une pression sur le bouton se produit, cela est considéré comme une demande.
La tenue d'un bouton vers le bas au-delà d'un certain temps risquent de déboucher sur « l'auto-repeat » fonctionnalité d'un clavier, bouton générer de nouvelles presses - mais cette fonction est externe au jeu du moteur.
Les entrées indiquées ci-dessus sont conformes à l'original Tetris.
Rotation des demandes peut être exécuté s'il n'ya pas de chevauchement entre les orientations et fixer les cellules sur le bord (à l'exclusion de la baisse du morceau), et si l'orientation désirée a pas de cellules en dehors de la zone.
Traduire les demandes peuvent être exécutés en l'absence de chevauchement entre les traduit et mis en configuration de cellules sur le bord (à l'exclusion de la baisse du morceau), et si la configuration désirée a traduit pas de cellules en dehors de la zone.
Entrée les demandes sont traitées avec un temps de latence qui dépend de la vitesse du jeu (exemple: 75 Hz), et les demandes prennent effet (si valide) instantanément.
Une musique peut être abandonnée sans n'importe quelle ligne se relevant pas.
Une musique peut être traduit plusieurs fois vers la gauche ou la droite, puis a chuté, tous sans éprouver une ligne officielle relevant pas.
Parce que récemment donné naissance à une pièce ne peut être tournée (car il est coincé contre le bord supérieur du panneau), le joueur doit accepter au moins une pièce relevant pas si les rotations sont désiré ou nécessaire.
L'effet sur le client est insignifiant.
5.7 Standard Tetris pièce « d'atterrissage »
Si une pièce est tout simplement tomber, il tombe par une seule rangée au cours de chaque pièce relevant itération.
Il y aura une itération qui se déplace de l'endroit sans contact avec les surfaces horizontales à un endroit qui est en contact avec les surfaces horizontales. Une fois cette itérations se produit, les pièces sont en contact de repos.
Si une itération commence par une pièce de repos en contact avec une surface horizontale, la pièce « terres, » et devient partie statique de la pile.
5.8 Standard Tetris « lignes achevé »
Une ligne est achevé une ligne de la pile dans laquelle toutes les cellules sont occupées. Quand une ligne est terminée éliminé de la pile, et les lignes au-dessus de la ligne éliminés sont décalés par une ligne à éliminer l'écart, cela est considéré comme une « ligne » terminée.
Quand une pièce terres, il devient un élément de la pile.
Immédiatement après la pièce terres, la pile est vérifié pour les lignes terminé, achevé et toutes les lignes sont éliminés.
Jusqu'à quatre lignes peut être mené à bien simultanément.
Le tableau suivant donne la limite supérieure sur les lignes mené à bien simultanément par une seule pièce:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Standard Tetris « niveaux »
Standard Tetris a 10 niveaux de difficulté, numérotée 1 (un) par 10 (dix), avec le niveau 1 étant le « moins difficile. »
Le niveau indice est la durée maximale de deux valeurs:
actualLevel = max( initialLevel, earnedLevel );
La valeur initialLevel est le niveau que le joueur choisit pour lancer une nouvelle partie.
Le modèle de niveau en fonction de lignes est terminé facilement observés dans la pré-commerciale MS-DOS version 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
Ainsi, le earnedLevel valeur est calculée selon l'algorithme suivant:
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 relevant itération retard
Tetris standard a un réel délai écoulé entre la ligne successifs chute libre itérations qui est une fonction de l'actuel niveau de difficulté.
La relation suivante entre le niveau d'index et de la baisse itération retard est basée sur des mesures répétées chronomètre à tous les niveaux de la pré-commerciale MS-DOS version 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
Ainsi, nous établissons la formule suivante pour l'itération retard valeur en fonction du niveau réel indice:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
Si le conseil d'administration est vide, et il n'ya pas de saisie de l'utilisateur, donné naissance à une pièce au niveau réel 1 terres dans environ 10 secondes, et donné naissance à une pièce au niveau réel 10 terres dans environ 1 seconde.
5.11 Standard Tetris « client »
Standard Tetris seulement octroie des points pour le fait d'une pièce d'atterrissage.
Il n'existe pas de points attribués pour le fait de remplir une seule ligne, ou de l'achèvement de deux, trois ou quatre lignes en même temps.
[Note: Certaines variantes de Tetris attribuer des points de l'acte de l'achèvement des lignes, avec une croissance exponentielle de bonus pour un nombre croissant de lignes en même temps achevé.
Ainsi, la stratégie de maximisation de client dans les variantes de Tetris consiste à mettre en place les possibilités « d'obtenir un Tetris, » pour l'utilisation d'argot « I » la forme à obtenir quatre lignes simultanément et obtenir beaucoup de points. ]
Si vous avez un vide bord, et vous laisser un non-« I » pièce faire une chute libre et la terre, ou vous immédiatement une baisse non-« I » pièce, vous pouvez établir le point suivant en utilisant le tableau pré-commerciale MS-DOS version 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, la non-« I » morceaux tombent un total de 18 lignes.
Cela explique la différence entre la chute libre et instantanée cas de chute.
En expérimentant avec les intermédiaires cas, il est facile d'en déduire le point suivant la formule:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Il est à noter que cette formule n'a rien à voir avec la distance une pièce tombe!
Il est strictement une fonction du niveau réel, et une pénalité pour le nombre d'itérations est un morceau laisse tomber librement.
Cette punit un utilisateur ayant besoin de temps pour réfléchir.
Il convient également de noter qu'en raison une pièce ne peut pas d'abord l'objet d'une rotation lorsque le premier à fleurir, un joueur est passible d'une peine d'au moins une chute libre itération si les rotations sont nécessaires pour placer un morceau dans la pile.
C'est probablement ce qui n'a aucune influence sur les acteurs de l'homme, sauf s'ils en quelque: reconnaître la pièce, appuyez sur les touches de traduction (à « gauche » ou à « droite), » appuyez sur la touche « tourner » une ou plusieurs fois, puis appuyez sur la « baisse » touche tous à moins de 0.5 secondes à niveau 1, ou moins de 0.05 secondes à niveau 10.
6. Standard Tetris stratégie
6.1 Introduction
Une stratégie pour jouer un jeu dépend des règles du jeu.
Une stratégie dépend de quel paramètre doit être optimisé.
Dans la Version Standard, Tetris, un survit en remplissant les lignes, est pour l'atterrissage morceaux, et les évaluations le plus de points possibles pour chaque pièce par une baisse d'exécution avant une ou plusieurs chute libre itérations transpire.
Un A.I. peut optimiser les points attribués pour chaque morceau tout simplement en se prononçant sur un déplacer rapidement et en « appuyant sur les touches » pour exécuter le mouvement.
Plus important d'une A.I. est la survie, car la survie indéfinie moyens arbitrairement un score élevé peut être atteint. Parce que les pièces de Tetris automne à un taux spécifique, le A.I. doit prendre des décisions au moins aussi rapidement - et le A.I. doit se déplace que des lignes complètes à un taux que les moyennes au moins 1 ligne par 2,5 pièces. (Chaque pièce dispose de 4 cellules, et chaque ligne dispose de 10 cellules.)
Bien sûr, on peut retarder l'achèvement des lignes par l'accumulation de pièces et la construction d'un gros tas, mais il n'ya que 200 cellules sur tout le forum, qui, en principe, ne peut détenir 50 pièces, pour tout joueur (comme un A.I.) doivent avoir achevé lignes une priorité fondamentale.
Dans la Version Standard, Tetris, le jeu état comprend les actuels du conseil d'administration d'occupation et la chute pièce (type, la position et l'orientation). Le jeu état mai éventuellement inclure les "Suivant la pièce".
6.2 Une alternance de séquence "S" et "Z" morceaux
Heidi Burgiel, Ph.D., de la Department of Mathematics, Statistics and Computer Science au University of Illinois at Chicago, a prouvé que une alternance de séquence "S" et "Z" pièces vigueur une norme (10-colonne, ligne 20) Tetris à terme dans un nombre prévisible de coups.
Extrait de l'article: "You can't win a game in which only alternating 'S' and 'Z' pieces appear."
Associé imprimé article: Mathematical Gazette, Juillet 1997, "How to Lose at Tetris"
Heidi Burgiel offre une Java applet qui fonctionne dans un navigateur Internet qui met en vedette un clone de Tetris modifié qui engendre alternatif "S" et "Z" morceaux.
[Le "Standard Tetris" logiciel associé avec le document que vous lisez possède également un mode qui engendre alternatif "S" et "Z" morceaux. ]
Heidi Burgiel a fait valoir que un jeu alternatif "S" et "Z" morceaux (pour une norme de Tetris bord de 10 colonnes et 20 lignes) doivent impérativement se terminer avant moins de 70000 pièces ont chuté.
La norme Tetris logiciels inclus dans le présent document permet à une personne de jouer à des jeux en alternance avec "S" et "Z" morceaux, et changer la largeur de bord.
Il est facile de voir que les conseils dont les largeurs sont des multiples entiers de quatre colonnes (exemples: 4 colonnes, colonnes 8, 12 colonnes, etc) peuvent toujours être joué lorsque morceaux alternent entre "S" et "Z", avec la pile pas la hausse supérieure à 4 lignes. Je mentionne cela afin qu'il soit clair que l'insuffisance de survie décrite dans le document de recherche mentionnés ci-dessus est spécifiquement pour le cas d'une norme Tetris-pension (avec 10 colonnes et 20 lignes).
6.3 Séquences d'insolubles pièce en général
Il ya des catégories entières de séquences pathologiques qui ne peuvent être survécu.
Il serait intéressant de calculer la probabilité totale de rencontrer un jeu-séquence de fin, parce que cela mettrait une limite supérieure sur la performance de toute stratégie, même en toute connaissance de toutes les futures pièces en tout point donné dans un match.
6.4 Total des configurations possibles bord
Étant donné que le conseil d'administration a 10 * 20 = 200 cellules, et étant donné que chaque cellule ne peut être dans l'un des deux Etats (vide ou occupé), le nombre total de configurations de bord doit être inférieure ou égale à: (2 ^ 200).
Étant donné que chaque élément ajoute 4 cellules à un conseil d'administration, et chaque ligne d'achèvement 10 élimine les cellules du conseil, le nombre de cellules occupées sur le conseil sera toujours même. Par exemple, (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 Ainsi, la moitié seulement du bord (2 ^ 200) configurations peuvent être atteint par le jeu.
Ainsi, le nombre total de configurations de bord est d'environ: (2 ^ 199) = 8.03469... * 10^59.
Toutefois, nous devrions exclure de notre total que n'importe quelle configuration comprend rempli lignes, parce que rempli lignes sont éliminés avant la fin de chaque mouvement. Toute la configuration avec une ou plusieurs lignes remplis à un autre effondrement de configuration qui ne contient pas de remplir les lignes.
Enfin, nous devrions exclure toute configuration qui inclut un non-vide au-dessus de la ligne une ou plusieurs lignes vides, car une non-vide au-dessus d'une ligne vide est toujours rangée automne, et tous relevant s'arrête avant la fin de chaque déplacement.
Chaque ligne peut être en 2^10 = 1024 États, dont l'un est "vide", dont l'un est «pleine», et de (1024 - 2) = 1022 qui sont partiellement occupés. Nous excluons l'ensemble "complet" cas de l'examen.
Si la ligne du bas est vide, alors toutes les lignes au-dessus de la ligne du bas doit également être vide.
Si la ligne du bas est partiellement occupé, puis sur la deuxième ligne peut être vide ou partiellement occupés.
Poursuivant cette analyse, nous pouvons calculer un certain nombre de configurations de bord qui prend en compte l'exclusion complète de lignes et les restrictions sur les lignes vides: 1 + (1022 * (1 + 1022 * (1 + 1022 * (1 + 1022 * (... * (1023)))))), qui est d'environ ((1022 ^ 19) * (1023)).
Ainsi, nous trouvons une estimation plus précise du nombre total de bord stable configurations: (1/2) * ((1022 ^ 19) * (1023)) = 0.9625... * (2 ^ 199), c'est-à-dire, à peu près 3,74% de moins que l'estimation (2 ^ 199).
Toutefois, le nombre réel de la stabilité, accessible bord les Etats membres est susceptible d'être inférieur en raison notamment du fait que la plupart des haut-lignes ne peut être rempli en quelques manières. Comme le haut-remplir la plupart des lignes, nouvellement créées, une pièce ne peut pas être déplacé ou tourné beaucoup. Cela limite le nombre d'égards, le plus haut rangées peuvent être pourvus.
6.5 En principe, le meilleur mouvement peut être trouvée pour tout bord et les éléments de configuration
Parce que nous pouvons obtenir l'une des sept pièces possible quel que soit le bord état, le nombre total des États jeu est d'environ 7 * (2 ^ 199) = 5.624... * 10^60.
Parce que nous pouvons, en principe, faire une recherche profonde de tous les avenirs possibles pour tous les possibles pour un jeu d'état, on peut avoir un seul "meilleures" passer associées à chaque jeu État.
Nous supposons que nous n'avons pas accès à toute information autre que l'actuel conseil d'administration et pièce courante, "meilleur" signifie "le passage qui offre le plus de chances de satisfaire notre objectif à long terme de survie".
Un mouvement est juste une traduction (jusqu'à 10 options) et une rotation (jusqu'à 4 options), nous pouvons facilement encoder le meilleur déplacer dans un seul octet.
Donc, en principe, nous pourrions former une table avec 10^61 entrées (en octets) nous a dit que la meilleure compte tenu de déplacer tout bord et l'état actuel pièce.
Bien sûr, cela est impossible, tout comme l'énumération de toutes les "Go" conseils ou "Chess" conseils d'administration est impossible. Mais le point est qu'il existe une vraie solution, et il ya une meilleure passer pour une configuration. Il pourrait aussi être une bonne passe pour une configuration donnée, mais nous pouvons choisir arbitrairement un seul aller dans cette affaire.
De nombreux jeux algorithmes ont tableaux énumérer de manière exhaustive toutes les possibilités de jeu dans l'état limité des contextes, tels que "l'ouverture (initiale) se déplace" ou "fin de jeu (finale) se déplace" Aux échecs. Peut-être liste exhaustive de Tetris tas surfaces (environ (20 ^ 10) Etats) est possible. C'est une idée intéressante.
Liste exhaustive de tous les Etats du fond deux lignes, multiplié par les sept pièces possible, le stockage et le meilleur déplacer dans un seul octet, serait tout à fait facile, nécessitant seulement 7 MB de la mémoire. Peut-être l'optimisation de performance pour ces sept millions de cas de fournir des données brutes pour l'analyse et le développement de modèles simples pour les données, ces modèles pourraient être considérés comme faisant partie de l'ensemble idéal de jeu Tetris stratégie.
Il est à noter que l'exécution se déplace encore mieux ne pas nous protéger contre d'éventuelles jeu pathologique-pièce mettant fin à des séquences. C'est juste que nous allons toujours effectuer des mouvements que nous offre le maximum de potentiel de survie, étant donné que toutes les futures pièces sont totalement aléatoires (et inconnus au moment où nous voulons décider de la manière de déplacer une seule pièce connue en cours).
6.6 Des performances en temps réel
Une contrainte de certains algorithmes stratégie est la nécessité pour des performances en temps réel - ce qui signifie que l'algorithme doit prendre une décision dans un laps de temps.
Quand l'homme joue un Tetris, les pièces ne s'arrêtent pas à faire tomber le joueur une chance de penser. Cela fait partie du défi de Tetris. Ainsi, un A.I. système qui vise à simuler le rôle de l'homme un joueur doit également prendre des décisions à un taux dicté par le jeu Tetris.
6.7 Row et pièce totaux
Notez que dans le long terme, le nombre de morceaux, est tombé très près de 2.5 fois le nombre de lignes - parce que chaque rangée a 10 cellules, et chaque pièce est de 4 cellules, et nous devons compléter une ligne, en moyenne, une fois tous les morceaux (10/4) = 2.5 abandonnée.
Ainsi, nous pouvons utiliser "achevé lignes» et «laisser tomber des morceaux« presque interchangeable avec la constante de proportionnalité. La plus grande erreur est lorsque le conseil est complètement rempli, sauf pour une seule lacune dans chaque ligne (((10*20)-20)/4) = 45 pièces diminué mais un déficit des prévisions (45/2.5) = 18 achevé lignes.
6.8 Current-pièce (et repas) stratégie
Si nous ne le A.I. permettre d'avoir connaissance de l'actuel conseil d'administration et la pièce courante, et nous considérons que le résultat le déplacement de la pièce courante en particulier les moyens, cela peut être un nom "d'une seule pièce» analyse.
Voici un simple croquis de la façon dont un une-pièce analyse peut décider à aller dans un Tetris:
Au cours de l'analyse de la pièce un jeu Tetris état
Fondamentalement, nous essayons tous les coups possibles et choisir la démarche qui permet d'obtenir le meilleur résultat.
La partie difficile est des avis chaque résultat.
Il nous faut un taux hypothétique état jeu selon la façon dont un tel état que nous avons à court terme et à long terme.
Notre objectif à long terme est la survie. La survie dépend de la prévention de la pile pas saturer le conseil. Nous pouvons réduire la pile hauteur en formant des lignes complètes qui sont ensuite éliminées de la pile.
Pour former une rangée complète, nous devons adapter parties de pièces pour chaque colonne de cette ligne. Ainsi, nous avons besoin de toutes les parties d'une rangée d'être exposés à la chute des morceaux si nous voulons éventuellement remplir toute la rangée.
Si, pour une raison quelconque, nous vide de couvrir des parties d'une ligne par morceaux sur un rang supérieur, alors maintenant nous sommes incapables de remplir les vides parties du monde. Le seul moyen (en présumant qu'il n'ya pas de glissement) à accéder à ces "trous enterrés" est d'éliminer les lignes ci-dessus qui ont parties agissant comme des obstacles.
Les facteurs suivants sont parmi ceux que nous pouvons utiliser pour un taux de bord:
Overall pile height
Plus le tas, plus notre situation semble être, parce que nous sommes plus près de débordement du conseil.
Roughness of pile area (number of times cells alternate between empty and filled as any row or column is scanned)
Le plus difficile la pile, plus il est probable qu'il sera difficile de remplir tous les contours complexes intégrés dès qu'ils seront exposés à la surface.
Number of buried empty cells
Les trous plus, nous avons enterré, le pire est notre situation, parce que nous devons découvrir enterré trous avant que nous puissions remplir les lignes correspondantes.
Vous pouvez imaginer que d'autres facteurs généralement un taux hypothétique conseil sur la façon dont sa pile peut accueillir tous les futurs possibles morceaux, et quels bons, la situation semble pour l'ensemble de ces pièces possible.
La prochaine question est de savoir comment déterminer l'importance relative de ces facteurs.
Une approche générale est la suivante. Attribuer un ensemble de "poids" (importance relative) de ces facteurs, puis de simuler de nombreux jeux et d'enregistrer les résultats de ces jeux (client final, etc.) Puis, d'attribuer un nouveau jeu de poids et de simuler une nouvelle série de jeux. Basé sur l'opportunité ou non la nouvelle série de jeux ont de meilleurs résultats que la précédente série de jeux, nous savons si la nouvelle série de poids est meilleure que la précédente série de poids.
Dans ma propre expérience, j'ai essayé la recherche systématique et aléatoire la recherche de bonnes combinaisons, mais je ne l'ai pas remarqué tout à grande échelle les tendances que je pourrais poursuivre. Toutefois, j'ai vu de nombreuses bosses étonnamment bon. Je pense qu'il est intéressant de noter que la performance moyenne pourrait constituer un bon courbe est un paramètre varie lentement avec la tenue d'autres paramètres à une valeur combinaison.
Le meilleur temps réel, une pièce de Tetris algorithme dans le monde, créé par Pierre Dellacherie (France) en 2003, doit beaucoup de son succès à sa série de mesures (ou paramètres). Recherche de poids est nécessaire pour optimiser une stratégie, mais il est également essentiel de commencer par le type de mesures qui révèlent les caractéristiques de l'État.
Pierre Dellacherie's invention de nouvelles manières de caractériser chaque conseil fait de son algorithme vraiment excellent, le conseil caractérisations saisir les dimensions stratégiques importantes du conseil d'État.
On pourrait développer une très différentes dimensions de la qualification qui ont travaillé aussi bien, je suis convaincu qu'il est possible pour les s'étendent conseil d'état dans de nombreux différents moyens qui peuvent être utilisés pour préciser une fonction stratégique. La clé consiste à trouver des caractéristiques de ce projet l'espace d'état à un petit nombre de dimensions qui peuvent être utilisés pour développer une simple fonction des avis (exemple: les combinaisons linéaires pondérées des caractères utilisés par Pierre's algorithme).
La pièce-un algorithme utilisé par le "bot" dans le "xtris" logiciel (1996) écrit par Roger Espel Llima utilise poids déterminé par une grande échelle l'exploration de combinaisons possibles par "algorithmes génétiques". Recuit simulé est une autre méthode possible d'explorer l'espace multidimensionnel des combinaisons de poids.
Il semble que, sur la base d'observations diverses, les multiples fonction de la moyenne de Tetris performances en fonction des poids, par exemple: F(w1,w2,w3,...), est «difficile» (beaucoup de minima locaux et maxima), ce qui signifie qu'une simple multidimensionnelle »de côtes" peuvent ne pas fonctionner.
6.9 Stratégie lorsque le courant pièce, pièce suivante, et le conseil sont connues
Si une stratégie algorithme est donné la pièce courante, prochaine pièce, et les repas, il peut prendre des décisions qui profitent de la combinaison de pièces.
La connaissance de la prochaine pièce peut améliorer le succès de Tetris jouer un algorithme de plusieurs ordres de grandeur. Il est facile de comprendre comment connaître la prochaine pièce fait une grande différence de stratégie.
On peut faire "fou" se déplace, tel que le recouvrement d'énormes trous, etc, parce qu'ils savent déjà que le prochain morceau peut être utilisé pour «corriger» la situation. Si vous n'avez pas eu connaissance de la prochaine pièce, vous êtes constamment essayer de jouer les chances, en essayant de garder vos options ouvertes au cas où le prochain morceau est pas idéal.
Le schéma suivant montre comment tous les possibles de la pièce courante sont pris en compte, et pour chaque telle initiative nous considérons tous les mouvements de la pièce suivante.
Stratégie de pièce courante et pièce suivante
La norme Tetris logiciel utilise cette stratégie lors de la prochaine pièce "est activé par l'utilisateur et est visible sur l'écran, et quand un deux-pièces A.I. est activée (comme l'une écrite par moi, Colin Fahey). Si la "prochaine pièce" n'est pas visible sur l'écran, mes deux pièces se rabat sur un morceau A.I..
Mon une pièce A.I. est terrible si on les compare aux autres AIs dans la norme Tetris logiciel, donc cela montre bénéfique vous plus d'informations (par exemple: la pièce suivante) peuvent être d'une A.I. système, c'est assez pour améliorer les performances de mon propre médiocre deux pièces A.I. de plusieurs ordres de grandeur - dépassant facilement les performances des meilleurs d'une seule pièce A.I. dans le monde.
(Cependant, la conversion de la meilleure pièce A.I. au monde à examiner deux pièces facilement l'améliorer de plusieurs ordres de grandeur, trop! Connaissance de la prochaine pièce est énorme!)
Mon premier test match avec mes deux pièces A.I. a duré environ 182 heures (7,6 jours) sur un 800 MHz PC, complétant 7216290 lignes. Je n'ai pas testé l'algorithme sur un ordinateur plus rapide.
Lorsque vous enregistrez l'état d'un jeu Tetris (Shift-W) à un fichier texte, vous pouvez alors copier et coller la liste des numéros, de la section "heightHistogram", à une feuille de calcul Excel.
Chaque bin dans l'histogramme indique le nombre de mouvements qui a pris fin avec un tas de hauteur (après complète lignes sont éliminés). Comme vous pouvez l'imaginer, ce qui rend une décision qui élimine tout un tas est rare, de sorte que le nombre total de mouvements qui se termine avec un tas de hauteur zéro est relativement faible.
Pendant ce temps, vous pourrait s'attendre à ce que la pile hauteur varie généralement autour de certains moyenne, de sorte bacs correspondant à ces lignes de dominer l'histogramme. Enfin, des bacs pour la plupart des haut-lignes (où nous sommes en danger de débordement du conseil) ont une très faible totaux.
Au cours de nombreuses heures, avec l'A.I. jouer un seul jeu en utilisant la stratégie de connaissance de la "prochaine pièce", j'ai pris des échantillons aléatoires de l'état de jeu, la copie la pile à hauteur histogrammes une feuille de calcul comme indiqué ci-dessous:
Pile hauteur histogrammes enregistrées à différents points dans un match typique (avec du courant et la prochaine stratégie pièce)
Vous pouvez échelle chaque histogramme par le nombre total de morceaux (nombre total de mouvements terminé) pour obtenir les données suivantes:
L'échelle des histogrammes, et une théorie
La chose remarquable est que ces histogrammes chercher l'échelle identique malgré les différents ordres de grandeur du nombre de pièces (terminé mouvements) en cause.
Tout en examinant les chiffres que je fait l'hypothèse que la queue de la courbe exponentielle est une pourriture. Par essais et erreurs je suis venu avec bruts théorie que la queue a été décrit par:
relative_frequency = ((0.122) * ((0.375)^(row-5)))
Le graphique suivant montre l'histogramme échelle sur toute la plage de lignes.
Graphique de l'échelle des histogrammes
Il est à noter que la courbe de 50000 pièces, et la courbe de 2000000 pièces, et la courbe de la queue théorie sont presque identiques à cette échelle.
Ce qui suit est un examen plus attentif à la tête de la courbe.
Partie inférieure de hauteur histogramme
Ce qui suit est une très-vue agrandie de l'extrême arrière de la mesure et histogramme courbes théoriques.
Vue agrandie de l'extrême arrière de l'échelle des histogrammes
Comme on peut s'y attendre, il est très rare que le tas pour atteindre ces sommets en même temps des expériences - mais même avec notre peu de preuves dans cette région extrême, la théorie semble encore acceptable.
Dans le tableau complet de la théorie semble se chevaucher la queue de la distribution "exactement", alors que dans le tableau agrandie de la queue de la queue, nous voyons erreur manifeste. Toutefois, je tiens à affirmer que cela est dû à un manque de données sur ces hauteurs extrêmes tas. Si j'ai augmenté le plateau de jeu, par exemple à une hauteur de 25 lignes au lieu de 20 lignes, afin que les jeux n'a pas mis fin brusquement, je pense que la théorie que j'ai présenté ci-dessus coïncident parfaitement avec la tendance.
Mon sentiment est que cet histogramme est la conséquence directe résultat combiné du Tetris A.I. et les règles de Tetris. Donc, même cette distribution sera respectée pour toute aléatoire à long terme jeu de Tetris en utilisant ma A.I. stratégie pour jouer avec "Suivant Piece" connaissances.
En outre, je pense que ce type d'histogramme peut être utilisé pour comparer AIs qui emploient les mêmes informations lors de la lecture. Ainsi, vous n'avez pas à jouer des jeux complet (qui peut durer pendant des jours ou années) pour comparer la performance à long terme des différents algorithmes de stratégie.
Par exemple, malgré la simplicité de mon modèle, je pense qu'il peut être utilisée pour prédire la durée moyenne de jeu! Nous n'avons tout simplement savoir combien de pièces fait "ligne 21" hauteur tas un nombre important, comme un chef d'un.
La relative fréquence de ligne 21, en fonction de mon simple théorie, est la suivante:
((0.122) * ((0.375)^( 21 -5 ))) = 1.8 * 10^(-8)
Vous devez multiplier ce nombre par (5.3 * 10^(7)), environ 50 millions, pour obtenir une valeur de un.
Ainsi, j'ai à peu près prédire que ma "prochaine pièce" stratégie est bonne uniquement sur l'ordre d'environ 10 millions de lignes achevé. L'une des raisons-je faire cette estimation est le fait que même 18 lignes peut être mortel pour mon A.I. parce que je ne permettent pas de mon A.I. d'examiner pièces jusqu'à ce que ils ont reculé d'au moins une ligne! (Il en est ainsi, je n'ai pas à vous soucier de ne pas pouvoir faire pivoter pièces.)
Je suis impressionné par le fait que le jeu seulement 50000 pièces (et peut-être beaucoup moins de pièces) peut vous donner une très bonne estimation de long terme hauteur histogramme, et par conséquent, une bonne estimation de l'ordre de grandeur des lignes achevé avant le match se termine. Cette approche est extrêmement précieux pour évaluer rapidement les changements subtils dans une A.I. que fait déjà très bien.
6.10 Conseil d'évaluation des mesures imiter spéculative regarder à l'avance
Si un algorithme, comme celle que j'ai présenté à ce projet, tente simplement toutes les pièces et les orientations pour les traductions en baisse et les taux résultant chaque conseil selon la configuration dans une certaine mesure du mérite, l'algorithme est essentiellement imitant l'aspect à l'avance ".
Quand on emploie des indicateurs tels que la "pile hauteur", "enterrés trous", "la rugosité de la surface" ou "bien profond", on est vraiment en utilisant une forme simplifiée de "regarder vers l'avenir". Ces caractérisations générales du conseil donner une indication de la viabilité à long terme du conseil.
L'approche idéale, étant donné une quantité infinie de la puissance de calcul, serait d'évaluer un conseil de configuration de tous les possibles pièce séquences qui peuvent suivre.
Bien que vous devez tenir compte de l'ensemble des 7 pièces comme étant tout aussi probables à chaque niveau de regarder à l'avance, vous devez optimiser les traductions (jusqu'à 10) et les orientations (jusqu'à 4) pour chaque pièce de chaque séquence possible! C'est à (7*10*4) = 280 branches à tous les niveaux du conseil d'évaluation! Donc, c'est à bord ((280)^(LookAheadLevels)) configurations à prendre en considération.
Parce que nous devons mettre fin à l'analyse après un nombre fini de niveaux, nous avons besoin de certains non-look-ahead méthode d'évaluation du conseil d'État - une façon de donner des valeurs à la feuille de noeuds notre arbre de recherche. Donc, pour ces noeuds, nous sommes revenus à l'aide d'une formule générale qui incarne prédicteurs de la viabilité future du conseil!
Ce type de spéculation peut être essayé avec le une pièce et deux pièces algorithmes en place du conseil simpliste paramètres d'évaluation. Supposons que toutes les pièces sont également probables et résumer les capacités d'un conseil pour tenir compte des pièces de toutes sortes dans les meilleures manières. Cela peut être effectué avec une, deux, ou un nombre quelconque de mouvement spéculatif profondeur - avec toutes les pièces faisant également probable (p=1/7).
Le terminal nœuds de cet arbre peut-être encore besoin d'pondéré paramètres à évaluer, mais la spéculation couches plus précisément saisir l'essence de ce que nous voulons faire: Déterminer dans quelle mesure un conseil d'administration peut accepter toutes les pièces, y compris les facteurs positifs tels que l'achèvement des lignes et des facteurs négatifs tels que l'accroissement global tas hauteur, etc
7. Tetris A.I. système de démonstration
7.1 Système
Ce schéma suivant montre mon installation expérimentale.
Ensemble du système de démonstration
7.2 Matériel
Voici une brève liste du matériel utilisé dans cette démonstration:
[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)
Il est clair que vous pouvez utiliser des équipements similaires pour accomplir les mêmes résultats. Plus de détails concernant les équipements sont décrits dans les sections correspondantes du présent article.
Voici une brève description des ordinateurs personnels utilisés dans cette démonstration:
[1] Personal Computer (PC), 350 MHz, Windows 98 [Runs video game]
[2] Personal Computer (PC), 800 MHz, Windows 2000 [Runs AI program]
Cette démonstration peut facilement être reproduit avec d'autres systèmes d'exploitation, tels que Linux. Il est plus important d'avoir une CPU vitesse de l'ordre de 800 MHz ou plus rapide pour l'ordinateur qui est de lancer le logiciel A.I., parce que cet ordinateur sera fait en temps réel de traitement de la vidéo.
7.3 Matériel de capture vidéo
J'ai utilisé une caméra vidéo USB comme un périphérique de capture vidéo pour mon A.I. système. Plus précisément, j'ai utilisé la Creative "WebCam Pro", USB une caméra vidéo avec 640 * 480 résolution.
Creative(TM) USB caméra vidéo description
USB caméra vidéo (à l'angle)
USB caméra vidéo (devant)
USB caméra vidéo (conseil avec CCD)
USB caméra vidéo (principaux puces)
OV511 grands blocs (note: USB caméra vidéo est OV511+)
7.4 OV511 fiche
ov511ds.pdf
OV511 fiches de données
1136328 bytes
MD5: e927d786e16baea59b7e7e54529778c0
7.5 OV511+ ( «plus») figurent les différences
ov511plus_101.pdf
OV511+ fonction des différences
56271 bytes
MD5: 388a03c56d6f67d6d5d80e3d06c4de21
7.6 Logiciel de capture vidéo
Microsoft a un très vieux nom API "Video for Windows" (VFW) que j'ai utilisé avec succès à ce projet. (Vous lien "vfw32.lib" C++ dans votre projet, ou faire un DllImport de "vfw32.dll" C# dans votre code.) Exemples d'utilisation de la VFW API sont largement disponibles.
Une autre solution consiste à utiliser Microsoft's "DirectShow" API de faire la capture vidéo.
Parce que VFW a seulement une douzaine de lignes de code à utiliser et acceptable effectué sur 800 MHz ma machine, je n'ai pas pris la peine d'explorer l'alternative APIs. Mais DirectShow est un plus contemporain API pour Windows de capture vidéo, et éventuellement un rendement beaucoup plus élevé le taux d'armature pour le même matériel.
Regardez les "CPF.StandardTetris.STVideoCapture" fichiers de code source dans la norme Tetris logiciel pour voir comment il est facile pour obtenir la capture vidéo à vos propres projets.
7.7 Computer interface relais (via RS232)
Pour avoir un ordinateur "appuyez sur les touches" sur le clavier d'un autre ordinateur, j'ai utilisé un "relais conseil" texte contrôlée par des commandes envoyées à partir d'un port de communication série (exemple: "COM1") via un câble RS-232. J'ai utilisé chaque relais pour relier les deux fils d'une touche du clavier pour simuler un appui sur une touche.
Il a donc fallu ouvrir le clavier et l'établissement des connexions. Il existe de nombreuses méthodes plus facile pour la simulation clé pression à un ordinateur, mais je voulais faire quelque chose qui semblait le plus près possible à une personne vraiment taper sur un clavier.
Un très polyvalent et bien fait relais conseil est le ADR2200 faites par Ontrak Control Systems:
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Ontrak Control Systems ADR2200 RS232 / RS485 Relay I/O Interface
Vous pouvez regarder le "CPF.StandardTetris.STRS232" fichiers de code source pour voir comment il est facile d'envoyer des octets par le biais d'un port série, qui peuvent ensuite être utilisées pour les appareils de contrôle comme le ADR2200 tableau illustré ci-dessus.
8. Standard Tetris logiciel
8.1 Téléchargement de logiciels
Aller au début de cet article de trouver un lien pour télécharger le code source (C# et C++ versions) et de logiciels (*.exe).
8.2 Résumé des caractéristiques
Logiciels caractéristiques:
Instruction des écrans et des crédits
Mode monochrome
Shadow mode
Conseil mode
Junk lignes
Taux de contrôle
Suivant pièce
Taille du Conseil
S/Z pièces
Mode d'étalonnage
Capture vidéo et la reconnaissance
Console de débogage
Sauver jeu
Charge jeu
8.3 À partir de l'apparence
Aspect au démarrage du logiciel:
Aspect lorsque le logiciel est lancé
8.4 Mode monochrome
Par défaut, le conseil apparaît en couleur:
Par défaut, le conseil apparaît en couleur.
La couleur mode peut être changé à (Shift + K) monochrome:
La couleur mode peut être changé à monochrome.
8.5 Shadow mode
Shadow mode indique où une pièce terre. Ceci est très utile pour les très grands conseils, car il est difficile de juger où une pièce terre.
Shadow mode indique où une pièce terre.
8.6 Conseil mode
Conseil mode vous indique où actuellement, sélectionnez-Amnesty International se déplacer étant donné la situation actuelle. (Shift + H)
Conseil mode montre où actuellement, sélectionnez-Amnesty International se déplaceront.
8.7 Junk lignes
Insérer "junk" lignes au bas de la pile, un par un, manuellement. (Shift + J)
Insérer "junk" lignes au bas de la pile.
8.8 Taux de contrôle
Le '+' (plus) et '-' (moins) les touches de contrôle la vitesse du jeu.
Par défaut, le jeu tourne à une vitesse standard, selon les règles de la norme Tetris (vitesse en fonction du niveau).
Voici un tableau de la signification de la vitesse biais:
-3,-4,...: lenteur proportionnelle au parti pris
-2: plus lent que le niveau 1
-1: normal, mais limitée au niveau 6 (0,2 seconde) de vitesse;
0: normal; Tetris standard de contrôle de vitesse;
+1: légèrement plus vite que le niveau 9 (0.05 sec retards);
+2: délimitée par le taux de rendu (exemple: 75 Hz);
+3,+4,...: plusieurs itérations rendu par un cadre;
Je préfère courir le A.I. à une fixation de "+2" (appuyez deux fois sur la touche '+' si biais commence à zéro).
Parti pris de vitesse modifie la vitesse du jeu.
8.9 Voir la prochaine pièce
Appuyez sur la touche "N" pour basculer sur "Suivant Piece". Le A.I. utilisera la prochaine pièce de "l'information que si la" prochaine pièce "apparaît sur l'écran.
Vous pouvez être assuré que l'AI n'est pas en utilisant "Suivant Piece" informations lorsque vous ne pouvez pas voir la prochaine pièce "sur l'écran.
Voir la pièce suivante
8.10 Taille du Conseil
En appuyant sur Ctrl + (gauche, droite, le bas, jusqu'à), on peut ajuster la taille du conseil d'immixtions arbitraires tailles et de 4 * 4 jusqu'à 200 * 400.
Conseil taille: 4 * 8
Conseil taille: 20 * 40
Conseil taille: 40 * 80
Conseil taille: 20 * 5
Conseil taille: 4 * 100
8.11 S/Z pièces seulement
L'intéressante étude S/Z modèle alternatif.
Cette tendance ne peut être résolu pour une 10 * 20 bord (largeur * hauteur).
Toutefois, les conseils qui ont des largeurs qui sont des multiples de 4 sont trivialement indiqué pour permettre la survie infinie.
Le AIs survivre indéfiniment dans ces cas, même si elles n'étaient pas spécialement réglés pour gérer cette situation pathologique.
S/Z pièces seulement
8.12 Mode vidéo étalonnage
Appuyez sur la touche "C" pour entrer "Calibration Mode". Dans le mode d'étalonnage, vous pouvez frapper les touches numériques: {1,2,3,4,5,6,7} pour sélectionner un morceau {O,I,S,Z,L,J,T} en haut de la joue bord.
Ceci est utile comme une image de référence pour la capture vidéo sur une deuxième norme Tetris logiciel.
Si vous cliquez sur le 0 (zéro) clé, il fera le conseil en blanc.
Vous pouvez prétendre à frayer pièces en sélectionnant un morceau (1..7), puis en sélectionnant un (0) blanc, tandis qu'un deuxième ordinateur fait montres de capture vidéo pour les morceaux.
Vous pouvez exécuter le A.I. sur le second ordinateur et voir comment elle traite avec votre entrée manuellement pathologique scénarios Tetris!
Mode d'étalonnage est la seule fois où vous pouvez manipuler la capture vidéo modèle de traitement de l'image (grille 4 * 2). Vous pouvez utiliser la souris pour dessiner le rectangle, mais vous pouvez utiliser les touches de curseur ( "", "vers le bas", "left", "droit") d'avoir amende de contrôle des frontières - utilise les Shift pour sélectionner frontières en face du rectangle (par exemple: "Shift-gauche" combo est différent de "gauche").
Mode vidéo étalonnage
8.13 Capture vidéo et la reconnaissance
Appuyant sur la touche 'V "permet de basculer le mode de capture vidéo. Si elle est correctement calibré (voir vidéo étalonnage "dans une section précédente), les pièces d'un écran vidéo à distance seront captées par la caméra et classées - et les pièces sera donné naissance dans les locaux jeu pour les A.I. examiner et à réagir .
Le A.I. production doit ensuite être transmis (par le biais du RS-232 interface à la manifestation décrite dans cet article) de la télécommande d'entrée de jeu (exemple: clavier) pour la A.I. avec succès à jouer le jeu à distance.
Si, à tout moment ce circuit fermé est perturbé (exemple: mauvais fonctionnement de capture vidéo, ou signal de sortie fonctionnement défectueux), puis la A.I. mettra au point une fausse impression de l'état de la télécommande de jeu, et la A.I. fera des mauvaises décisions qui sont rapidement perdre le jeu .
(Note: Ce problème peut être surmonté avec un modeste montant de l'effort: Le système A.I. nécessité d'examiner l'ensemble à distance Tetris écran en cours pour une "vérification" de l'ensemble du conseil scolaire et du système A.I. doivent être établis pour certaines commandes à la production l'échec d'une certaine manière.)
Capture vidéo et la reconnaissance
9. Original Tetris expérience d'Amnesty International (2003)
Ce qui suit montre la première version du Tetris A.I. système en 2003.
Face caméra vidéo # 1 ordinateur exécutant toute simple jeu Tetris
# 2 ordinateur exécutant le logiciel standard de Tetris en mode A.I.
Gauche: Dessin grille pour calibrer de reconnaissance d'images vidéo;
À droite: Tetris pièce de reconnaissance.
Cadre de la vidéo de Tetris A.I. expérience en 2003
10. Best-une pièce de jeu de Tetris algorithme dans le monde
10.1 Pierre Dellacherie (2003, France)
Pierre Dellacherie (2003, France), développeur de la meilleure pièce de jeu de Tetris algorithme dans le monde
Le meilleur d'une seule pièce, en temps réel Tetris algorithme, à ma connaissance, a été créé par Pierre Dellacherie de la France.
Son incroyable algorithme remplit parfois plus de 2 millions de lignes!
La performance moyenne est de l'ordre de 650000 lignes.
L'algorithme prend très peu de mémoire, et fonctionne à haute vitesse (environ 160 lignes par seconde sur 800 MHz mon ordinateur).
Performance de Pierre Dellacherie's algorithme:
Mon modèle actuel de l'exécution de Tetris AIS est que, pour chaque pièce il ya une probabilité constante que le jeu prendra fin, p.
Ainsi, la probabilité qu'une pièce ne se terminera pas un jeu est q=(1-p).
La probabilité de mettre fin à la partie après k passe est tout simplement le produit de la probabilité de survie (k-1) déplace, à savoir q^(k-1), et la probabilité de la fin sur la prochaine étape, à savoir p.
Cela correspond à une "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 )
Pour les petits p, ln(q) est à peu près (-p), et nous avons le texte suivant:
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 )
Nous nous attendons à la fraction du nombre total de jeux joué de clore par un nombre de lignes dans l'intervalle [k1, k2] à:
Integral of the Exponential Distribution:
I(k1,k2) = exp[-p * k1] - exp[-p * k2]
Après avoir terminé 36 des jeux sur mon ordinateur, sur une période de deux jours, j'ai trouvé une une moyenne de 674827 lignes achevé.
Selon la théorie générale ci-dessus, je voudrais attendre le rapport suivant fraction de jeux pour terminer dans les gammes achevé ligne:
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
Voici un graphique qui compare la théorie Exponential Distribution avec la distribution observée des jeux.
Performance de Pierre's algorithme terminé plus de 36 jeux
Bien qu'il existe très peu de jeux dans cet ensemble de données, il est évident que le modèle est assez bonne à faire correspondre la distribution observée.
Pierre's introduction de son algorithme:
Pierre commencé à travailler sur cette pièce-un algorithme de 2003,1.
Pierre m'a envoyé un e-mail au sujet de son algorithme sur 2003.4.9, les rapports de performance suivants plus de 20 matchs consécutifs:
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.
"L'algorithme est mis en œuvre complète Turbo Pascal et 7000 lignes / min. Avec une Athlon 1600+."
Je convertis Pierre's algorithme pour C++ en 2003,6, après plusieurs e-mail des échanges avec Pierre. Nous avons vérifié que le A.I. dans la version C++ fait les mêmes décisions de la version Pascal.
J'ai observé des performances similaires à son rapport initial; moyenne autour de 650000 lignes achevé, et certains jeux de remplir 2 millions de lignes.
Incroyable!
10.2 Conversation avec Pierre Dellacherie
[1] Quand avez-vous tout d'abord créer ce code?
J'ai travaillé sur l'algorithme de la fin de Janvier 2003 jusqu'à maintenant.
[2] Combien de temps avez-vous travaillé?
J'ai travaillé sur presque chaque semaine ... mais pas tous les jours longtemps car j'ai d'autres activités: Malheureusement, je dois gagner de l'argent comme tout le monde!
[3] Qu'est-ce qui a inspiré la conception du code?
Tetris j'ai joué 10 ou 15 ans mais je n'avais pas lu de nouveau pour une longue période. Je dirais que je suis un "moyen" joueur qui connaît les règles et quelques astuces.
Toutefois, quand j'ai commencé à travailler sur l'algorithme je ne l'ai pas tellement parce que j'ai trouvé c'est plutôt plus efficace de regarder l'ordinateur de jouer et d'analyser ses faiblesses.
[4] Avez-vous utilisé toute l'automatisation de « former » votre code à obtenir de meilleurs résultats? Avez-vous eu des commentaires pour améliorer l'algorithme?
Ou bien il vous suffit de regarder les résultats et décider d'apporter des modifications?
Je suis de « l'ancienne école: » j'ai simplement regardé les résultats et a décidé de faire des modifications.
"Apprentissage automatique" est un type de méta-algorithme de sorte que je ne suis pas assuré que faire de cette façon serait plus facile que la présente méta-algorithme doivent être construites trop et ce n'est pas si facile!
Quoi de plus, je suis d'accord avec Roger Penrose quand il dit (dans son livre "Shadows of the mind") que l'homme de comprendre et de l'intuition ne peut être algorithmique (exemple: la comptabilisation).
[5] Quand avez-vous commencé à jouer de Tetris, et quand avez-vous eu l'idée de résoudre un Tetris avec A.I.?
J'enseigne algorithmique et la programmation informatique (Turbo Pascal et Scilab) pour les étudiants qui s'entraînent pour l'examen d'entrée à l'ingénieur diplômé de l'école.
Dans un premier temps, "Computer joue Tetris" était une idée que je voulais développer pour mes élèves l'année prochaine.
Je n'étais pas au courant de votre page Web quand j'ai commencé à travailler sur l'algorithme.
En effet j'ai eu la chance d'être au courant de votre page Web il ya quelques semaines seulement parce que je pense que j'aurais été découragé par les résultats obtenus (comme vous pouvez le deviner, les premières versions de mon algorithme ne pas jouer si bien!).
[6] Quelle est votre situation actuelle?
Je suis près de 30 [avant 2003 avril 27]. J'ai plusieurs activités: Je suis un violoncelliste, je compose la musique et je enseigner la programmation informatique.
J'ai une maîtrise en musicologie (1994) et une "Artificial Intelligence and Algorithmic diplôme (1998).
En France, ce diplôme correspond à la 5ème année d'études universitaires (4e année est la maîtrise et 6e année est la thèse).
Pierre's compositions:
[7] Où habitez-vous?
Je suis français et je vis à Rouen (Normandie).
[8] Autres commentaires:
Finalement je n'ai pas une idée nouvelle pour l'améliorer.
J'ai essayé tellement inutile (et stupide) des choses que je doute qu'il pourrait être amélioré.
D'autre part, je pense qu'il peut exister complètement différents algorithmes qui pourraient avoir de meilleures performances.
D'ailleurs, un test plus rapide consiste à lancer les morceaux en une demi-boîte (10 rangées X 10 colonnes): dans une demi-boîte, mon algorithme fait une moyenne de 280 lignes achevé.
Une dernière chose: l'algorithme peut être facilement modifié dans un double-couches algorithme ([je vais faire] les tests à venir).
J'aime la musique de film: devenir un film compositeur fait partie de mes grands rêves (mais c'est juste rêve!).
11. Meilleur joueur de l'homme dans le monde
11.1 Tetris Master japonais (2001 Janvier 27) vidéo
Tetris maître (2001, Japon) vidéo
Arika présente les japonais Tetris Finales maître (2001 Janvier 27). "TETRIS THE ABSOLUTE PLUS --The Grandmaster2-- DEATH-MODE"
12. Feedback
12.1 Slashdot thread (2003)
En 2003, mon Tetris A.I. projet a été examiné sur la Slashdot forum Internet (
http://slashdot.org).
Slashdot (http://slashdot.org) forum Internet titre pour une discussion de mon projet de 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 inspiré par mon projet A.I. Tetris (2003) (la première fois que j'ai jamais inspiré une BD!)
Comic inspiré par mon projet A.I. Tetris (2003) (la deuxième fois que je n'ai jamais inspiré une BD!)
13. Historique du projet de Tetris A.I.
Au printemps de 1989 que j'étais occupé à sauter (et l'échec de) la deuxième semestre freshman classes au University of Pennsylvania.
Un de mes colocataires, Bill Matthews, a eu l'Mac Classic, et parfois joué des jeux vidéo.
Les gens qui se admis à Ivy League écoles sont généralement enclins à rivaliser avec d'autres personnes en tout temps - quand Bill obtenu le jeu Tetris pour son Mac, nous avons immédiatement commencé un combat à long terme pour la haute client.
Comme les scores monté, prendre le temps nécessaire pour faire un petit gain augmenté de façon spectaculaire.
Pour faire une longue histoire courte, Bill prétendument détient le score élevé entre nous, mais je crains de lui en utilisant ResEdit et le piratage le fichier!
Bill avait cours dans le Wharton School of Business, le alma mater de Michael Milken et Donald Trump, il n'est pas inconcevable que quelqu'un truquées impossible un score élevé ...
Au cours de l'été 1990, j'ai emprunté un 30 MHz Intel 80386 IBM PC de mon colocataire, Alex Haidas.
J'ai acheté un clavier Mac à un marché aux puces pour 1 $.
J'ai construit le port parallèle des circuits pour permettre le contrôle PC à la Mac clavier.
(J'ai utilisé une puce CMOS 4040 d'agir comme un type de l'état solide relais à se joindre à clavier contacts dans le Mac clavier.)
J'ai écrit un programme informatique qui a utilisé un arbre de décision que sa stratégie pour le jeu Tetris. En quelques semaines, j'ai eu un PC jouer le jeu Tetris tourne sur un Mac.
Toutefois, j'ai été requis pour l'utilisation du clavier PC de dire la A.I. relevant de chaque pièce sur l'écran.
J'ai commencé à travailler sur un circuit en utilisant CdS (Cadmium Sulfide) détecteurs de lumière qui maigre Mac contre l'écran et "voir" la chute des morceaux, mais CdS capteurs réagi trop lentement aux changements de luminosité et le contraste entre Tetris pièces et l'arrière-plan sur l'écran Mac Classic était trop faible pour discrimination fiable.
À cette époque je n'avais pas beaucoup d'argent, de sorte qu'il était trop risqué d'acheter un 2 $ Radio Shack phototransistor qui pourraient ne pas faire ce que je voulais.
En outre, étant donné le contraste problème, j'étais pessimiste quant à l'approche dans son ensemble.
Lorsque j'ai acheté mon premier ordinateur personnel en 1996, je n'ai pas pu obtenir des logiciels sous des licences Windows 95 sur un 100 MHz CPU de faire le traitement de la vidéo assez rapide pour faire un simple système de vision.
J'ai écrit le code de traitement d'image en langage assembleur, mais il y avait tant de frais généraux avant mon code effectivement reçu des données vidéo qu'il semble impossible de faire quoi que ce soit utile.
En 2003, la technologie, en particulier CPU vitesse, a atteint un niveau de finition qui a fait le projet presque banale.
J'ai creusé mon vieux projet personnel et enfin terminé, obtenir un certain sens de fermeture.
C'était très excitant de voir un ordinateur jouant un autre ordinateur par le biais de la caméra vidéo USB et les relais.
Le son des relais en cliquant, et en regardant les pièces de spin et déposer au ridicule, une vitesse surhumaine, a fait l'expérience très satisfaisante dans un multisensorielles.
En 2003, mon travail a été reconnu par Slashdot (
http://slashdot.org), et j'ai reçu beaucoup de commentaires.
J'ai été invité à faire figurer sur le "Screen Savers" émission de télévision sur le TechTV réseau de télévision numérique.
Je suis allé à San Francisco et est apparu à l'émission, et l'expérience est grande.
Plus tard dans 2003, j'ai reçu un message de Henk Rogers, de m'avoir invité à Hawaï pour le rencontrer et de parler Alexey Pajitnov quant à la création d'une sorte de norme de Tetris, aux fins d'avoir des tournois de Tetris.
Un intérêt particulier est suffisant joueurs d'utiliser les téléphones portables de « rivaliser les uns avec les autres, » indirectement, par l'intermédiaire de A.I. qui imite les acteurs (par une analyse préalable de chaque joueur actions), ce qui permet d'éviter les effets de téléphonie mobile de latence d'accès à Internet, et en permettant aux joueurs « de rivaliser » * Les meilleurs joueurs humains dans le monde (*... ou, plutôt, A.I. imiter les meilleurs joueurs humains dans le monde).
J'ai été enthousiasmé par la perspective de rencontrer le créateur de Tetris. Malheureusement, le vol me fait anxieux, et j'ai refusé l'invitation.
En 2006, j'ai converti mon "Standard Tetris" logiciel de C++ à C# de rendre le logiciel plus accessible et utile pour les programmeurs contemporain.
