La première partie (analyse de code) est ici: https://habr.com/post/420725/ .

Algorithme

La description

L'algorithme effectue en continu les étapes suivantes:

1. Il attend qu'un nouveau tetrimino soit créé.
2. Vérifie le type du tetrimino nouvellement créé, le type du tetrimino suivant (figure dans le champ d'aperçu) et le contenu du terrain de jeu.
3. Explore toutes les façons possibles d'ajouter deux tetriminos au terrain de jeu et évalue chaque probabilité.
4. Déplace le tétrimino nouvellement créé pour qu'il corresponde à l'emplacement de la meilleure probabilité détectée.

Chacune de ces étapes est décrite en détail ci-dessous.

Verrouiller la recherche

Prenons une version simplifiée de Tetris, dans laquelle les formes ne tombent pas automatiquement. La seule façon de faire baisser le chiffre est de l'abaisser doucement. Après avoir supprimé les temps du jeu, nous pouvons décrire complètement l'état du tetrimino actif par sa position et son orientation. La figure a un lieu connu de création initiale, et les opérations suivantes sont utilisées pour convertir d'un état à un autre:

• Un pas vers le bas
• Un pas à gauche
• Déplacer d'un pas vers la droite
• Tournez d'un pas dans le sens antihoraire
• Rotation dans le sens horaire

Ces opérations ne sont applicables que lorsque les carrés du tétrimino résultant correspondent à des cellules vides du terrain de jeu. Lorsqu'il est impossible de descendre d'une étape, l'état est considéré comme bloqué. Cependant, comme nous avons simplifié Tetris et que l'attente de verrouillage est essentiellement infinie, l'état verrouillé peut être transformé par d'autres opérations par glissement et défilement.

De nombreux états bloqués avec une séquence minimale d'opérations qui les créent peuvent être trouvés à l'aide de la recherche en largeur (BFS). Comme indiqué ci-dessous, il utilise une file d'attente pour stocker les résultats intermédiaires.

1. Nous mettons en file d'attente l'état à la création.
2. Nous déduisons l'état de la file d'attente.
3. Nous obtenons les états suivants en utilisant l'opération de conversion.
4. S'il n'y a pas de mouvement vers le bas entre eux, l'état qui est supprimé de la file d'attente est bloqué.
5. Nous mettons en file d'attente les états suivants que nous n'avons pas encore visités.
6. Si la file d'attente n'est pas vide, répétez à partir de l'étape 2.

Le programme représente chaque état comme un objet avec les champs suivants:

{ x, y, rotation, visited, predecessor }

En cours de préparation, le programme crée un tableau tridimensionnel d'objets d'état (20 lignes × 10 colonnes × 4 tours), initialisant x , y et la rotation conséquence.

Le champ visited est marqué lorsque l'état est mis en file d'attente. Dans BFS, cela est valide car chaque état suivant augmente la longueur totale du chemin de 1. Autrement dit, en augmentant la longueur du chemin, il est impossible de créer un état suivant qui doit être inséré ailleurs qu'à la fin de la file d'attente pour maintenir l'ordre.

Le champ predecessor indique l'objet d'état à partir duquel l'état actuel est dérivé. Il est défini lorsque l'état est mis en file d'attente. L'état de création n'a pas d'états précédents.

L'ensemble des états bloqués détectés lors de la recherche est déterminé par le type de tetrimino et les blocs remplis sur le terrain de jeu. La séquence des mouvements qui les ont générés peut être clarifiée (dans l'ordre inverse) en suivant les liens predecessor vers l'état de création. Lorsque la constante PLAY_FAST est définie sur true au début du programme, elle ignore complètement les états précédents en mettant directement tetrimino sur le terrain et en le bloquant.

Un tableau tridimensionnel d'objets d'état, une file d'attente et BFS sont regroupés dans une classe. Il a une méthode de recherche qui reçoit le terrain de jeu (tableau bidimensionnel), le type de tetrimino et l'auditeur. Chaque fois qu'un état verrouillé est détecté, le terrain de jeu est mis à jour en ajoutant du tetrimino à l'emplacement approprié. Ensuite, le terrain de jeu modifié ainsi que des informations sur les changements sont transmis à l'auditeur pour traitement. Une fois que l'auditeur a terminé le retour, le terrain de jeu est restauré.

L'auditeur est utilisé pour combiner plusieurs opérations de recherche dans une chaîne, ce qui permet de trouver toutes les façons possibles d'ajouter deux (ou plus) tetriminos au terrain de jeu. Le premier moteur de recherche de la chaîne n'exécute BFS qu'une seule fois. Cependant, le deuxième moteur de recherche exécute BFS chaque fois que la première recherche détecte un état verrouillé. Et ainsi de suite, s'il existe d'autres moteurs de recherche dans la chaîne.

L'auditeur du dernier moteur de recherche évalue le terrain de jeu modifié. Lorsqu'il trouve le terrain de jeu meilleur que ce qui a été étudié précédemment, il écrit l'objet utilisé de l'état verrouillé, qui utilise actuellement le premier moteur de recherche de la chaîne. Étant donné que le premier moteur de recherche exécute BFS une seule fois, les champs predecessor de ses objets d'état restent valides jusqu'à la fin de l'ensemble du processus de recherche. C'est-à-dire que le dernier auditeur enregistre essentiellement le chemin sur lequel le premier tétrimino doit aller afin d'arriver à la meilleure configuration du terrain de jeu en conséquence.

Fonction d'évaluation

La fonction de notation attribue une valeur au terrain de jeu modifié - une somme pondérée de divers paramètres d'influence. La fonction d'évaluation utilisée dans ce cas est basée sur la fonction développée par Islam Al-Ashi . Il utilise les paramètres suivants:

• Nombre total de lignes effacées : il s'agit du nombre total de lignes qui seront effacées par l'ajout de deux tetriminos.
• Hauteur de blocage totale : la hauteur de blocage est la hauteur au-dessus du sol du terrain de jeu à laquelle la figure est verrouillée. Il s'agit de la distance verticale à laquelle une figure verrouillée tomberait si vous supprimez tous les autres carrés occupés du terrain de jeu et gardez l'orientation de la figure. La hauteur totale de blocage est la somme des hauteurs de blocage des deux tétriminos.
• Nombre total de cellules «puits» : une cellule puits est une cellule vide située au-dessus de toutes les cellules occupées dans une colonne de sorte que ses voisins gauche et droit sont des cellules occupées; lors de la détermination des puits, les murs du terrain de jeu sont considérés comme des cellules occupées. L'idée est qu'un puits est une structure ouverte en haut, fermée en bas et entourée de murs des deux côtés. La probabilité d'intervalles intermittents dans les parois du puits signifie que les cellules du puits ne se produisent pas nécessairement en tas continu dans une colonne.
• Nombre total de trous dans les colonnes : le trou dans la colonne est une cellule vide située immédiatement en dessous de la cellule occupée. Le sexe du terrain de jeu n'est pas comparé à la cellule au-dessus. Il n'y a pas de trous dans les colonnes vides.
• Nombre total de transitions dans les colonnes : une transition dans les colonnes est une cellule vide adjacente à une cellule occupée (ou vice versa) dans une seule colonne. La combinaison du bloc de colonnes occupé le plus haut avec un espace vide au-dessus n'est pas considérée comme une transition. De même, le sol du terrain de jeu n'est pas non plus comparé à la cellule au-dessus. Par conséquent, il n'y a aucune transition dans une colonne complètement vide.
• Nombre total de transitions dans les lignes : une transition dans les lignes est une cellule vide adjacente à une cellule occupée (ou vice versa) dans la même ligne. Les cellules vides près des murs du terrain de jeu sont considérées comme des transitions. Le montant total est calculé pour toutes les lignes du terrain de jeu. Cependant, les lignes complètement vides ne sont pas prises en compte dans le nombre total de transitions.

El-Ashi a suggéré que des poids utiles peuvent être trouvés en utilisant l'algorithme d'optimisation des essaims de particules (PSO), qui améliore de manière itérative l'ensemble des solutions en imitant le comportement de l'essaim observé dans la nature. Dans notre cas, chaque solution est un vecteur de poids, et l'adéquation de l'option est déterminée par le jeu dans Tetris; c'est le nombre total de tetriminos pendant lesquels il a survécu jusqu'à la fin de la partie.

Ces idées sont appliquées dans la version Java décrite ci-dessous; il s'exécute en dehors de FCEUX et peut être configuré pour un jeu en mémoire non graphique fonctionnant à une vitesse beaucoup plus élevée. Après avoir préparé le PSO, j'ai été surpris de voir que l'algorithme ne bouge plus après l'itération initiale. Après cette itération, plusieurs variantes de solutions générées aléatoirement fonctionnaient déjà assez bien. Pendant plusieurs jours, la taille de cet ensemble a diminué jusqu'à ce qu'il ne reste qu'une option. Voici les valeurs de cette solution:

Paramètre	Le poids
Nombre total de lignes effacées	1.000000000000000
Hauteur totale de blocage	12.885008263218383
Nombre total de cellules de puits	15.842707182438396
Le nombre total de trous dans les colonnes	26.894496507795950
Le nombre total de transitions dans les colonnes	27.616914062397015
Total des sauts de ligne	30.185110719279040

Le terrain de jeu a été estimé en multipliant les paramètres par leurs poids respectifs et en additionnant les résultats. Plus la valeur est basse, meilleure est la solution. Étant donné que tous les paramètres et poids ont des valeurs positives, tous les paramètres nuisent à l'évaluation globale; chacun d'eux doit être minimisé. Cela signifie également que le meilleur score est 0.

Étant donné que ces poids ont été sélectionnés au hasard, la plage de valeurs appropriées peut être très large. Cet ensemble particulier de nombres et l'importance relative estimée de chaque paramètre peuvent ne pas être pertinents. Néanmoins, il sera intéressant de les observer de près.

Le paramètre le moins nuisible est le nombre total de lignes effacées. Le fait que cette option soit nuisible est contre-intuitif. Mais le principal objectif de l'IA est la survie. Il ne cherche pas le plus de points. Au lieu de cela, il joue de façon conservatrice, effaçant généralement les rangs un à la fois. Pour obtenir le Double, le Triple ou le Tetris, vous devez faire croître un groupe qui va à l'encontre de l'objectif à long terme.

Dans la liste, la hauteur totale de blocage est la suivante. Il peut être minimisé en abaissant le tetrimino aussi près du sol que possible. Il s'agit d'une stratégie simple qui contribue à long terme à la survie et à court terme à un emballage de qualité des pièces.

Le poids attribué au nombre total de cellules de puits semble un peu surprenant, car les joueurs expérimentés construisent généralement intentionnellement des puits profonds pour collecter plusieurs Tetris (combinaisons à quatre lignes) d'affilée. Mais comme mentionné ci-dessus, c'est un jeu risqué, contrairement à l'objectif principal - la survie. De plus, le nombre de puits est un indicateur de la «rugosité» du pieu. Un certain niveau d'inégalité est bénéfique lors du placement de certaines figures ou combinaisons de figures. Mais une rugosité élevée endommage l'emballage étanche.

Le nombre total de trous dans les colonnes représente environ la moitié du nombre total de transitions dans les colonnes. Ces paramètres peuvent être combinés et regroupés en un paramètre connexe commun, obtenant un paramètre plus étendu et plus nuisible: le nombre total de transitions.

Les zones densément peuplées ont un petit nombre de transitions dans toutes les directions. Par conséquent, la stratégie principale, conduite par l'intelligence artificielle, peut être brièvement décrite comme suit: emballer les pièces aussi près que possible les unes des autres.

Autres options

Voici une liste de quelques paramètres supplémentaires que j'ai expérimentés lors du développement de l'IA:

• Hauteur du tas : les blocs occupés peuvent pendre au-dessus des cellules vides, créant des saillies et des trous; cependant, il n'est pas possible de verrouiller des blocs occupés sur des lignes complètement vides. Par conséquent, la hauteur de segment est le nombre de lignes qui contiennent au moins un bloc occupé.
• Nombre total de colonnes occupées : il s'agit du nombre de colonnes contenant au moins une cellule occupée.
• Nombre total de cellules occupées : le nombre de cellules occupées sur le terrain de jeu.
• Nombre total de zones connectées : l'algorithme de remplissage est utilisé ici pour calculer le nombre de zones connectées en continu. En plus de trouver des "îles" occupées, il découvre des trous qui s'étendent le long des deux axes.
• Dispersion de la hauteur de la colonne : Il s'agit d'une mesure statistique de la variation de la hauteur des colonnes. C'est un indicateur de rugosité de surface.
• Valeur d'adaptation totale : calcule la valeur d'adaptation du tas pour le prochain chiffre inconnu. Il compte le nombre total de façons dont 7 types de formes peuvent être ajoutés au terrain de jeu sans l'apparition de nouveaux trous. Pour un comptage précis, l'utilisation répétée de BFS sera nécessaire. Mais pour un calcul approximatif, l'arbre de recherche peut être considérablement tronqué.
• Note moyenne pour la figure suivante : ce paramètre approfondit la recherche en analysant toutes les possibilités pour la prochaine figure inconnue. Il utilise d'autres paramètres pour séparer l'emplacement de chaque type de figure, puis renvoie la moyenne pour 7 notes. Pour chaque placement de la figure, BFS est requis.
• Jeu simulé moyen : le paramètre simule une série de jeux dans Tetris, sélectionnant des pièces à l'aide de son propre générateur de nombres pseudo-aléatoires et utilisant l'IA pour travailler avec eux. À la fin de chaque partie, le terrain de jeu est évalué à l'aide d'autres paramètres. La valeur moyenne de tous les lots est renvoyée.

Tous les paramètres peuvent être personnalisés en ajoutant des facteurs personnalisés. Par exemple, au lieu de simplement calculer les lignes effacées, vous pouvez attribuer vos propres poids pour Simple, Double, Triple et Tetris, en simulant un système de points. Si le nettoyage simultané de plusieurs rangées nuit à l'objectif à long terme de survie, un poids négatif peut être attribué à des rangées uniques, tandis que d'autres peuvent devenir positifs.

Un autre facteur utile est la valeur de décalage. Par exemple, une surface parfaitement plate d'un tas a une dispersion de hauteurs de colonne de 0. Mais une surface parfaitement plate ne s'adapte pas à S et Z, ainsi qu'à d'autres combinaisons de formes. Par conséquent, en soustrayant la constante, la variance doit être centrée autour de la rugosité optimale.

Les paramètres ajustés et biaisés peuvent être augmentés dans une certaine mesure de sorte qu’avant de calculer la somme pondérée, ils peuvent être mis à l’échelle logarithmique ou exponentielle. Toutes ces probabilités peuvent être considérées comme des poids supplémentaires qui peuvent potentiellement être optimisés par des méthodes telles que PSO.

De nombreux paramètres permettent de comprendre dans quelle mesure le tas peut gérer des pièces supplémentaires, par exemple, celles qui traitent de la rugosité de la surface, mais la «quantité totale d'adaptation», «note moyenne de la figure suivante» et «jeu simulé moyen» évaluent le terrain de jeu modifié insérer des chiffres qui ne sont pas inclus dans les deux connus. Dans l'étude des chiffres ultérieurs, en raison de l'élimination rapide de la série, la quantité de connaissances supplémentaires obtenues diminue avec la profondeur. Cela signifie que le cours du parti depuis longtemps n'est pas si important, et le cours du parti dans un avenir lointain n'est pas non plus très important. En fait, si une courte séquence de chiffres est mal définie au hasard, l'IA restaure rapidement le jeu, en utilisant les quelques chiffres suivants pour effacer les lignes affectées. La détermination de la valeur optimale pour l'analyse des chiffres ultérieurs nécessite des recherches supplémentaires.

Un autre aspect de l'utilité d'un paramètre est le coût de calcul. Les coûts sont considérablement augmentés car la fonction d'évaluation est appelée pour chaque placement possible de deux figures. Étant donné que l'IA doit pouvoir jouer à Tetris en temps réel, les facteurs de coût qui fournissent des informations précieuses peuvent être échangés contre des techniques plus approximatives qui s'exécutent plus rapidement.

Formation IA

Il existe des séquences pathologiques qui peuvent conduire à Game Over, quelle que soit la stratégie. L'exemple le plus simple est la séquence sans fin de tetrimino S et Z, qui, comme le montre l'animation, conduit rapidement l'IA à perdre.


Puisqu'il faut des jours pour exécuter la variante AI avant l'achèvement de plusieurs lots et calculer la moyenne, il est complètement impossible d'utiliser la durée moyenne des lots comme métrique de contrôle PSO. Au lieu de cela, vous pouvez augmenter la complexité du jeu à une vitesse contrôlée en augmentant la fréquence de S et Z, ce qui, au fil du temps, entraînera la création alternative de cette seule paire de chiffres.

J'ai essayé d'utiliser cette méthode d'enseignement, mais j'ai découvert qu'enseigner l'IA à travailler avec des S et Z fréquents nuit en fait à la capacité de faire face à des formes aléatoires uniformément réparties.

Dans une méthode alternative inspirée du jeu de type B, la métrique PSO contrôle la fréquence de nettoyage des rangées. Le terrain de jeu est un diagramme de 10 lignes de blocs d'ordures aléatoires, et chaque fois que la ligne est effacée, une nouvelle ligne d'ordures apparaît en dessous, rétablissant la hauteur du tas. Étant donné que le terrain de jeu a une largeur de 10 colonnes et que chaque tetrimino se compose de 4 carrés, en moyenne, l'IA devrait effacer une ligne tous les 2,5 tetrimino. Et pour se débarrasser des ordures, il doit le faire encore plus vite.

Malheureusement, cette technique n'a pas non plus amélioré les performances. Une raison probable est que les trous d'ordures aléatoires ne correspondent pas exactement aux chaînes avec lesquelles l'IA traite dans le vrai jeu. De plus, le nettoyage de la rangée est un objectif à court terme; le nettoyage gourmand des rangs n'améliore pas nécessairement la survie à long terme. De temps en temps, les lignes ne doivent pas être touchées pour traiter certaines combinaisons de figures suivantes.

Colin Fei a suggéré une approche différente sur sa page Web. Il a créé des histogrammes qui montrent le pourcentage de formes qui sont bloquées dans chaque rangée pendant les lots d'essai. Fait intéressant, tous les histogrammes semblent presque identiques quel que soit le nombre de figures créées. Sur cette base, il a suggéré que vous puissiez utiliser une image approximative de la fonction pour tout lot d'essai lors de l'évaluation de l'attente statistique de bloquer une figure dans la ligne de création, obtenant ainsi le temps pendant lequel l'IA jouera jusqu'à la fin du jeu. J'ai décidé d'explorer cette possibilité.

Vous trouverez ci-dessous une carte thermique de nombreux lots d'essai contenant au total 2 039 900 000 tétrimino. Chaque cellule est colorée en fonction du pourcentage de formes qui y sont verrouillées. Pour améliorer le contraste visuel, une palette non linéaire est sélectionnée. La carte a été créée en normalisant les valeurs des cellules en divisant par le pourcentage maximal de cellules, puis en annonçant à la puissance de 0,19 (voir "correction gamma" ).

La couleur Pourcentage ■ 0.00000000 ■ 0.00000315 ■ 0.00024227 ■ 0.00307038 ■ 0.01860818 ■ 0.07527774 ■ 0.23582574 ■ 0.61928352 ■ 1.42923040 ■ 2.98867416 ■ 5.78182519

Les rayures orange foncé et rouges sur les lignes 17 et 18 signifient que la grande majorité des personnages s'y retrouvent. La teinte vert pâle d'en bas est une conséquence de la géométrie des figures: seuls 4 des 7 types de tétrimino peuvent apparaître sur la ligne du bas. Les coins inférieurs sont noirs car il est impossible de s'y rendre.

La couleur le long de chaque ligne est presque uniforme, ce qui suggère que les formes sont réparties uniformément horizontalement. De légères lacunes peuvent être expliquées en regardant les histogrammes des différents types de formes:

T

J

Z

O

S

L

Je

T s'avère être le type le plus universel: son histogramme est plus uniforme que tous les autres. Anomalies dans l'histogramme J - le résultat de l'influence des murs; seuls Jr et Jl peuvent être dans les colonnes latérales, ce qui fait que l'IA utilise plus souvent les colonnes 1 et 9 pour compenser. Il en va de même pour L. Les histogrammes Z et S sont approximativement les mêmes, ce qui souligne le déséquilibre dû au fait que Zv et Sv ne sont pas des images miroir parfaites les unes des autres. Le type O est limité à un terrain de jeu de 19 × 9, et il semble que l'IA soit plus susceptible d'utiliser O sur les côtés qu'au centre. Tetrimino I est décalé vers la droite, car son point de départ se trouve là; par conséquent, le verrouillage dans la colonne 1 est rare.

Le tableau montre le pourcentage de chiffres bloqués dans chaque ligne.

String	Pourcentage
0	0.0000000000
1	0.0000000000
2	0.0000004902
3	0,0000026472
4	0,0000066180
5	0,0000172557
6	0,0000512280
7	0.0001759400
8	0.0006681210
9	0,0023187901
10	0,0077928820
11	0,0259672043
12	0,0866187068
13	0,2901315751
14	0,9771663807
15	3.3000408353
16	10.6989059268
17	28.5687976371
18	50.0335706162
19	6.0077671454

Voici un graphique des valeurs:


Si la ligne 19 n'est pas prise en compte, le graphique montre une croissance exponentielle.

Voici une liste des ratios du nombre de formes verrouillées dans les rangées adjacentes.

String A / String B	Ratio (%)
1/2	0,00
2/3	18,52
3/4	40,00
4/5	38,35
5/6	33,68
6/7	29/12
7/8	26,33
8/9	28,81
9/10	29,76
10/11	30/01
11/12	29,98
12/13	29,85
13/14	29,69
14/15	29,61
15/16	30,84
16/17	37,45
17/18	57,10
18/19	832.81

Les lignes 16–19prennent en compte les figures qui interagissent avec le sol du terrain de jeu, afin qu'elles puissent être jetées. En lignes, la 0–5sélection est trop petite pour être significative. Les rapports restants, les paires 6 / 7–14 / 15, sont presque identiques; leur valeur moyenne est de 29,24%. Cela signifie que la probabilité que le tas croisse d'une ligne est approximativement la même quelle que soit la hauteur du tas. Cela est logique, car les règles de Tetris limitent l'interaction en haut du tas lorsqu'il est bien emballé.

Le graphique suivant montre le log de ₁₀ % des chiffres des lignes 6 à 15.


Elle est proche d'une ligne parfaitement droite avec un coefficient de détermination proche de 1 . La formule dérivée de la régression linéaire montrée ci-dessus nous donne l'intersection avec l'axe Y, en supposant que le pourcentage de formes dans la ligne 0 est d'environ 10 ^-7,459 %. L'inverse de cette valeur nous donne une attente statistique de 2 877 688 349 tetrimino ou 1 151 175 340 lignes jusqu'à la fin de la partie.

Cela nous fait comprendre que le journal ₁₀le pourcentage de chiffres dans chaque ligne reste linéaire jusqu'à la ligne 0. Cependant, lorsque le tas atteint presque le plafond du terrain de jeu, la liberté de mouvement est limitée à un point tel que cette propriété est violée. De plus, bloquer une pièce sur la ligne 0 ne signifie pas nécessairement que la partie est terminée; vous pouvez toujours être sauvé s'il y a un endroit pour créer de nouvelles figures.

Une autre façon d'évaluer la force de l'IA est de mesurer le nombre moyen de formes créées entre un nettoyage complet du terrain de jeu. Un nettoyage complet peut être obtenu avec seulement 5 tetriminos. Par exemple, entre autres possibilités, cela peut être réalisé par cinq chiffres O disposés sur le sol du terrain de jeu. En général, étant donné que chaque tetrimino se compose de 4 carrés et que la largeur du terrain de jeu est de 10 carrés, le nombre de chiffres créés entre un nettoyage complet doit être un multiple de 5 ( depuis4 × 5n = 2 × 10n ).

Mon IA a un nombre moyen de formes créées entre 1 181 nettoyages sur le terrain - un nombre assez petit. Puisqu'un nettoyage complet est comme le redémarrage d'un jeu, un lot complet peut être vu comme une série extrêmement longue de redémarrages de jeu, suivie d'une avance rapide pour terminer le jeu. Comme la séquence d'alternatives décrite ci-dessus SZ, les séquences pathologiques menant à la fin du jeu sont généralement très courtes.

L'histogramme ci-dessous montre la probabilité (en pourcentage) que l'IA obtienne un effacement complet du champ après le nombre spécifié de figures créées.


L'ordre des degrés dans la formule ci-dessus détermine le taux de diminution et, vraisemblablement, la force de l'IA. Selon cette formule, environ 0,4%, soit environ 1 match sur 253 commençant avec un terrain de jeu vide, se termine par un nettoyage complet après seulement 5 tétriminos.

Contrairement à ce que Faye a suggéré, les constantes dans les approximations linéaires et exponentielles nécessitent une très grande taille d'échantillon pour que R ²approché 1, donc cette méthode n'est pas applicable pour PSO. Cependant, les constantes obtenues avec des lots longs peuvent être utilisées pour optimiser la fonction d'approximation qui crée des valeurs constantes possibles pour des lots courts. Dans une sorte de boucle de rétroaction de développement, la fonction d'approximation optimisée peut être utilisée dans le PSO, ce qui améliore l'IA, qui à son tour peut être utilisée pour calculer de nouvelles constantes, servant de critères de référence pour la fonction d'approximation.

Version Java

À propos du programme

Pour les développeurs peu familiers avec Lua, j'ai ajouté un port Java AI au fichier zip source . Les classes sont des traductions quasi linéaires d'objets Lua basées sur des fermetures .

Forfaits

Le code est divisé en deux packages:

• tetris.ai contient des classes et des interfaces AI.
• tetris.gui crée un modèle graphique du terrain de jeu.

Classes et interfaces IA

Une classe avec le nom approprié Tetriminosdécrit le tétrimino. Il est utilisé de la même manière enumet contient des constantes pour tous les types de tétrimino:

 public static final int NONE = -1; public static final int T = 0; public static final int J = 1; public static final int Z = 2; public static final int O = 3; public static final int S = 4; public static final int L = 5; public static final int I = 6; 

NONEsignifie une valeur non affectée. Il est utilisé pour les cellules vides du terrain de jeu.

Contient également Tetriminosdeux modèles de la table d'orientation. PATTERNS- il s'agit d'un tableau entier à 4 dimensions (type × rotation × carré × coordonnées) contenant les coordonnées relatives des carrés; les lignes sont disposées de sorte que dans chaque type, l'orientation de création de la forme soit la première. ORIENTATIONSEst un autre modèle, un tableau bidimensionnel (type × rotation) d'objets Orientation. Chacun Orientationcontient les coordonnées du carré sous forme de tableau d'objets Point. Il contient également des champs qui décrivent la plage de positions autorisées pour l'orientation correspondante.

 public class Orientation { public Point[] squares = new Point[4]; public int minX; public int maxX; public int maxY; ... } 

 public class Point { public int x; public int y; ... } 

La rotation tetrimino (le deuxième index dans les deux tables d'orientation) est utilisée dans les objets Stateque BFS manipule.

 public class State { public int x; public int y; public int rotation; public int visited; public State predecessor; public State next; ... } 

x, yEt en rotationmême temps décrire la position et l' orientation de la figure. Étant donné que le type Tetrimino reste constant du moment de la création au blocage, un champ pour celui-ci est facultatif.

La classe Searcherqui contient l'algorithme BFS crée un ensemble complet de tous les objets possibles Statelors de sa création:

 private void createStates() { states = new State[AI.PLAYFIELD_HEIGHT][AI.PLAYFIELD_WIDTH][4]; for(int y = 0; y < AI.PLAYFIELD_HEIGHT; y++) { for(int x = 0; x < AI.PLAYFIELD_WIDTH; x++) { for(int rotation = 0; rotation < 4; rotation++) { states[y][x][rotation] = new State(x, y, rotation); } } } } 

Bien que Java possède une API de collections riche, elle Searchercontient sa propre implémentation de la file d'attente. La classe Queueutilise State.nextpour joindre des objets Statedans une liste chaînée. Étant donné que tous les objets Statesont prédéfinis et que chacun Statene peut être ajouté à la file d'attente qu'une seule fois, la file d'attente peut fonctionner en place, ce qui élimine le besoin d'objets conteneurs temporaires inutiles utilisés dans les implémentations générales de la file d'attente.

Le «cœur» de BFS est la méthode illustrée ci-dessous search.

 public boolean search(int[][] playfield, int tetriminoType, int id) { int maxRotation = Tetriminos.ORIENTATIONS[tetriminoType].length - 1; int mark = globalMark++; if (!addChild(playfield, tetriminoType, mark, null, 5, 0, 0)) { return false; } while(queue.isNotEmpty()) { State state = queue.dequeue(); if (maxRotation != 0) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == 0 ? maxRotation : state.rotation - 1); if (maxRotation != 1) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == maxRotation ? 0 : state.rotation + 1); } } addChild(playfield, tetriminoType, mark, state, state.x - 1, state.y, state.rotation); addChild(playfield, tetriminoType, mark, state, state.x + 1, state.y, state.rotation); if (!addChild(playfield, tetriminoType, mark, state, state.x, state.y + 1, state.rotation)) { lockTetrimino(playfield, tetriminoType, id, state); } } return true; } 

Il génère une file d'attente avec l'état du tétrimino créé, puis récupère séquentiellement les éléments enfants des états qui sont supprimés de la file d'attente, en les ajoutant à la file d'attente lorsqu'ils apparaissent sur le terrain de jeu.

Un searchchamp de jeu contenant une combinaison de cellules occupées et vides, le type Tetrimino créé et un identifiant arbitraire est transmis à la méthode . Pendant l'exécution du BFS, un écouteur est appelé chaque fois qu'une position de verrouillage est détectée.

 public interface ISearchListener { public void handleResult(int[][] playfield, int tetriminoType, int id, State state); } 

L'auditeur reçoit un terrain de jeu modifié contenant un tetrimino verrouillé en place. Le type de Tetrimino créé et un identifiant arbitraire sont également transmis. Le dernier paramètre est celui Statedans lequel le tétrimino est bloqué. En suivant la chaîne de liens State.predecessor, vous pouvez restaurer la Statecréation d'une forme.

State.visitedpourrait être mis en œuvre comme boolean; mais avec tous les équipements nécessaires pour trier avant de chercher Statepour le soulagement visitedsur false. Au lieu de cela, j'ai fait une visitedvaleur intpar rapport à un compteur, en incrémentant à chaque appel.

La méthodeaddChildmet en file d'attente les états suivants. L'état suivant doit être dans le champ et être situé sur 4 cellules vides du terrain de jeu. De plus, l'état suivant ne doit pas être visité State. Si la position est valide, addChildretourne truemême si l'état suivant n'a pas pu être mis en file d'attente car il a déjà été visité.

La méthode searchutilise la addChildvaleur de retour pour déterminer si une forme peut être créée. Si la figure ne peut pas être créée, le tas a atteint le sommet et la recherche ne peut plus être effectuée; donc il revient false.

RetournableaddChildon étudie également la possibilité de franchir une autre étape. Si cela ne peut pas être fait, l'état actuel est la position de verrouillage et l'appel commence lockTetrimino. La méthode lockTetriminomodifie le terrain de jeu, appelle l'auditeur, puis restaure le terrain de jeu.

Chaque ligne du tableau playfieldcontient 1 élément supplémentaire, qui stocke le nombre de cellules occupées dans la ligne. L'incrémentation d'un élément est effectuée par la méthode lockTetriminocar elle marque les cellules comme occupées.

Lorsque l'auditeur reçoit un terrain de jeu modifié, il appellePlayfieldUtil.clearRowsPour supprimer des lignes remplies la méthode les reconnaît en vérifiant la valeur dans l'élément supplémentaire du tableau. Pour supprimer une chaîne, le code profite du fait qu'en Java, les tableaux bidimensionnels sont essentiellement des tableaux de tableaux; il pousse simplement les liens vers les chaînes. PlayfieldUtilcontient des lignes libres; il termine le processus de nettoyage en insérant un lien vers l'un d'eux. Avant d'effectuer le décalage, l'index de la ligne effacée est stocké dans un élément de ligne supplémentaire. Ensuite, le lien vers la ligne est poussé sur la pile.

Ensuite, l'auditeur appellePlayfieldUtil.restoreRowspour annuler les modifications apportées au terrain de jeu. Les étapes sont annulées dans l'ordre inverse. D'abord, nous obtenons une rangée gratuite par le haut. Ensuite, la ligne remplie est récupérée de la pile et l'index de l'élément supplémentaire est restauré. Il est utilisé pour décaler les références de ligne et revenir à l'emplacement de la ligne supprimée. Enfin, un élément supplémentaire est restauré, on lui attribue la valeur de la largeur du terrain de jeu - le nombre de cellules occupées dans la ligne remplie.

Il existe PlayfieldUtilégalement une méthode evaluatePlayfieldqui calcule et écrit 4 paramètres d'évaluation dans la classe de conteneur illustrée ci-dessous.

 public class PlayfieldEvaluation { public int holes; public int columnTransitions; public int rowTransitions; public int wells; } 

La classe gère tout cela AI. Il contient deux objets Searcherconnectés ensemble par l'auditeur ci-dessous.

 public void handleResult( int[][] playfield, int tetriminoType, int id, State state) { if (id == 0) { result0 = state; } Orientation orientation = Tetriminos.ORIENTATIONS[tetriminoType][state.rotation]; int rows = playfieldUtil.clearRows(playfield, state.y); int originalTotalRows = totalRows; int originalTotalDropHeight = totalDropHeight; totalRows += rows; totalDropHeight += orientation.maxY - state.y; int nextID = id + 1; if (nextID == tetriminoIndices.length) { playfieldUtil.evaluatePlayfield(playfield, e); double fitness = computeFitness(); if (fitness < bestFitness) { bestFitness = fitness; bestResult = result0; } } else { searchers[nextID].search(playfield, tetriminoIndices[nextID], nextID); } totalDropHeight = originalTotalDropHeight; totalRows = originalTotalRows; playfieldUtil.restoreRows(playfield, rows); } 

Une classe AIpeut gérer n'importe quel nombre d'objets Searcher, mais Nintendo Tetris n'affiche qu'une seule forme à l'avance. Les objets Searchersont stockés dans un tableau et le code ci-dessus sert d'écouteur commun. L'identifiant aléatoire transmis à la méthode Searcher.searchest en fait l'index du tableau, qui est également la profondeur de la recherche. Lorsque l'auditeur est appelé, l'identifiant dirige l'appel vers le suivant Searcherdans la chaîne. S'il atteint la fin du tableau, évalue alors le terrain de jeu. Et quand il trouve un terrain de jeu avec un score de fitness plus élevé, il écrit celui qui est bloqué Statedès le premier Searcherde la chaîne.

AIcontient une méthode searchqui reçoit le terrain de jeu et un tableau contenant les types du tetrimino créé et du suivant. Il revientStatecontenant la position et la rotation dans lesquelles le premier tétrimino doit être bloqué. Il ne se concentre pas sur le deuxième tetrimino; la prochaine fois qu'il est appelé, il recalcule le score. Si le tas est trop haut et que la chaîne Searcherne place pas les deux tetriminos, il AI.searchreviendra null.

 public State search(int[][] playfield, int[] tetriminoIndices) { this.tetriminoIndices = tetriminoIndices; bestResult = null; bestFitness = Double.MAX_VALUE; searchers[0].search(playfield, tetriminoIndices[0], 0); return bestResult; } 

Défi IA

Étant donné que la version Java n'est pas liée à FCEUX, elle peut potentiellement être utilisée pour d'autres projets. Pour ceux qui souhaitent intégrer l'IA ailleurs, cette section décrit tout ce dont vous avez besoin.

Tout d'abord, créez une instance AI, une instance PlayfieldUtilet un tableau pour contenir tous les types connus de tetrimino. De plus, créez une PlayfieldUtil.createPlayfieldinstance du terrain de jeu en appelant ; il renvoie un tableau à deux dimensions avec une colonne supplémentaire, que nous avons examinée ci-dessus. Vous aurez probablement aussi besoin d'un générateur de nombres aléatoires.

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); 

Au départ, le terrain de jeu est vide et toutes les cellules sont pertinentes Tetriminos.NONE. Si vous remplissez les cellules par programme, n'oubliez pas de noter le playfield[rowIndex][AI.PLAYFIELD_WIDTH]nombre de cellules occupées dans chaque ligne.

Remplissez le tableau des types tetrimino avec les types de la forme initialement créée et de la forme suivante, qui sont généralement sélectionnés manuellement.

 tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); 

Ensuite, nous passons le terrain de jeu et le tableau des types à la méthode AI.search. Il reviendra Statedans lequel vous devrez bloquer le premier tetrimino. S'il revient null, la partie est inévitable.

 State state = ai.search(playfield, tetriminos); 

Si vous avez besoin d'un moyen de créer une figure au verrouillage, passez-le à la Stateméthode AI.buildStateList.

 State[] states = ai.buildStatesList(state); 

Pour mettre à jour le terrain de jeu, nous le transmettrons PlayfieldUtil.lockTetriminoavec son type et son objet State. Cette méthode efface automatiquement les lignes remplies.

 playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); 

Avant d'appeler à nouveau, AI.searchvous devez sélectionner au hasard le prochain tetrimino.

 tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); 

Ensemble, cela ressemble à ceci:

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); while(true) { // ... print playfield ... State state = ai.search(playfield, tetriminos); if (state == null) { break; // game over } playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); } 

Au lieu d'afficher le terrain de jeu sous forme de texte, vous pouvez utiliser une façon plus intéressante d'afficher ce qui se passe ...

Affichage du terrain de jeu

La classe TetrisFrameimite les graphiques de Nintendo Tetris, y compris les fonctionnalités comportementales décrites dans la partie précédente de l'article.


Pour le voir en action, exécutez-le tetris.gui.Main. Comme avec la version Lua, nous pouvons ajuster la vitesse du jeu en changeant la valeur constante au début du fichier.

 public static final boolean PLAY_FAST = true; 

TetrisFramedispose de 4 méthodes pour manipuler l'écran. La méthode displayTetriminorend le tetrimino actif dans les coordonnées spécifiées. Il reçoit un paramètre de délai, qui fait attendre la méthode avant de renvoyer le nombre spécifié d'images d'animation.

 public void displayTetrimino(int type, int rotation, int x, int y, int delay) 

La méthode lockTetriminoverrouille la figure en place. Le compteur de lignes, les points, le niveau et les couleurs tetrimino sont mis à jour en conséquence, démontrant le comportement curieux attendu lorsque les valeurs dépassent les valeurs autorisées. L'attribution d'une animatevaleur à un paramètre truecomprend des animations de nettoyage des lignes et un scintillement de l'écran lors de la réception de Tetris. La méthode est bloquée jusqu'à la fin de l'animation.

 public void lockTetrimino(int type, int rotation, int x, int y, boolean animate) 

updateStatisticsAndNext effectue un incrément du compteur de statistiques pour le tétrimino nouvellement créé et met à jour l'affichage de la figure suivante.

 public void updateStatisticsAndNext(int activeTetrimino, int nextTetrimino) 

La méthode dropTetriminocrée une forme et lui permet de descendre sous l'influence de la «gravité», sans tenter de la faire pivoter ou de la déplacer. Mainl'utilise pour les deux derniers chiffres lors de son AI.searchretour null. Si le paramètre est animateimportant true, alors s'il est impossible de créer une figure, le rideau de fin de partie tombera. Comme pour toutes les autres méthodes, cette méthode se bloque jusqu'à la fin de l'animation. Il truene revient que lorsqu'il peut créer une figure sur un terrain de jeu occupé.

 public boolean dropTetrimino(int type, boolean animate) 

Ces 4 méthodes doivent être appelées par le workflow, mais TetrisFramedoivent être créées dans le thread de répartition d'événements lui-même. Pour voir comment cela se fait, consultez la classe Main.

Par intérêt, il Mainutilise une classe Randomizerqui simule un générateur de nombres pseudo-aléatoires biaisé de Nintendo Tetris.

Le package tetris.gui.imagescontient des fichiers liés à l'affichage. tiles.png- Il s'agit d'un tableau de motifs contenant tous les graphiques de tuiles. background.datstocke les identifiants des tuiles qui composent l'arrière-plan; données extraites de $BF3F. Et il colors.datcontient des octets qui génèrent des couleurs carrées inhabituelles qui apparaissent à partir du niveau 138. Il

ImageLoadercontient un tableau de palettes NES, et l' ImagePaneensemble complet des valeurs de niveau affichées est stocké.

Autres projets

Potentiellement, le code peut être utilisé au lieu d'écrire pour le mode démo. En fait, une telle démo peut être rendue pour toujours, profitant de la rapidité avec laquelle l'IA est en mesure d'effacer tout le terrain de jeu. Pour y parvenir, dans le générateur de nombres pseudo-aléatoires, vous devez utiliser une constante arbitraire comme graine, ce qui nous donnera une séquence tetrimino déterministe. Les deux premières séquences tetrimino seront enregistrées. Lorsque l'IA atteint un nettoyage complet du champ, les deux prochains tétriminos seront comparés aux deux premiers de la séquence. S'ils correspondent (cet événement est attendu tous les 49 nettoyages de champs complets), le générateur de nombres pseudo-aléatoires peut recevoir la même constante que seed, ce qui créera une boucle de démonstration infinie. La durée du cycle peut être très longue pour masquer le fait qu'il s'agit d'un cycle. Aussila démo peut commencer à un point aléatoire de la boucle, créant une nouvelle démo à chaque fois.

Une autre possibilité d'utiliser l'IA est de créer un mode «joueur contre ordinateur». Dans le Tetris multijoueur, tout en effaçant plusieurs lignes en même temps, des lignes d'ordures apparaissent dans la partie inférieure du terrain de l'adversaire, augmentant le terrain de jeu. L'IA doit pouvoir se protéger des débris pour la même raison qu'elle peut jouer à des jeux de type B. Cependant, comme indiqué précédemment, l'IA joue de manière conservatrice, s'efforçant généralement d'effacer une ligne à la fois. Autrement dit, il sera en mesure de se défendre contre les attaques, mais il ne sera pas en mesure d'attaquer. Pour pouvoir changer son comportement, j'ai créé une interface appelée IChildFilter.

 public interface IChildFilter { public boolean validate(int[][] playfield, int tetriminoType, int x, int y, int rotation); } 

AIa un constructeur alternatif qui obtient une implémentation IChildFilter. S'il est disponible, IChildFilter.validateil sert de vérification supplémentaire de l'autorisation de l'État enfant; s'il revient false, l'état enfant n'est pas mis en file d'attente.

WellFilterEst une implémentationIChildFiltervisant à ramasser quatre rangées (Tetris). Comme les joueurs vivants, elle construit progressivement un puits dans la colonne la plus à droite du terrain de jeu, en augmentant ligne par ligne de bas en haut. Puisqu'il fonctionne ligne par ligne, il rejette les états enfants qui ajoutent un carré à la colonne la plus à droite. Lorsque la ligne entière, à l'exception de la colonne de puits, est complètement pleine, l'IA passe à la ligne suivante. Lorsque 4 ou plus de ces lignes sont prêtes, cela permet au «bâton» de tomber dans le puits et d'obtenir Tetris. De plus, la hauteur du tas est suivie; s'il devient trop gros, il WellFiltercesse d'affecter l'IA.


Pour le tester en fonctionnement, apportez les Mainmodifications suivantes:

 AI ai = new AI(new WellFilter()); 

WellFilterfonctionne, mais pas particulièrement efficace. Il contient une heuristique simple conçue pour démontrer le concept. Pour obtenir Tetris plus souvent, vous devez utiliser une stratégie plus sophistiquée, peut-être qui peut être optimisée à l'aide de PSO.

De plus, vous pouvez utiliser le filtrage des états enfants pour générer des modèles. Voici un exemple de ce dont il est capable PatternFilter.


PatternFilterConstruit les images ligne par ligne de bas en haut, de la même manière que cela fonctionne WellFilter; cependant, au lieu de conserver la colonne la plus à droite, il PatternFilterapprouve uniquement les états enfants qui correspondent à un modèle particulier.

Le constructeur PatternFilterobtient le nom d'une des images du package tetris.gui.patterns, qu'il utilise comme modèle. Chaque image 20 × 10 contient des pixels noir et blanc correspondant aux cellules du terrain de jeu.

 AI ai = new AI(new PatternFilter("tetriminos")); 

La ligne de code ci-dessus crée les silhouettes de sept types de tetrimino.


Un autre exemple avec un grand tetrimino T tourné en biais.


Un autre exemple. Si vous regardez attentivement, vous verrez le nom du jeu.


Comme WellFilter, ce PatternFiltern'est rien de plus qu'une preuve de concept. Les modèles qu'il traite sont limités au fond du terrain de jeu, car les tentatives pour les obtenir se terminent généralement par la fin du jeu. Cependant, c'est une idée intéressante qui mérite une étude plus approfondie.

Version de la manette de jeu

Le script Lua et le programme Java ignorent la gravité; pour eux, la vitesse de descente n'est pas importante, car en fonction de la configuration, ils téléportent les chiffres immédiatement à l'endroit souhaité ou traînent le long du chemin choisi. D'une certaine manière, ils imitent simplement Tetris, pas le jouent. Cependant, dans le fichier zip avec les sources, il y a un autre script Lua qui joue en générant les signaux des boutons de la manette de jeu, ce qui permet au jeu de contrôler le mouvement des figures, la gravité et tout le reste.

L'ajout de gravité élargit considérablement l'espace de recherche, forçant l'IA à prendre en compte les règles astucieuses de la manipulation des formes. Le détail de ces règles est décrit dans la première partie de l'article, et peut être pleinement apprécié par une étude directe du code. Voici les plus importants:

• : , .
• «» .
• «» «» .
• .
• .
• .
• .
• , .
• A B .
• «» «» 6 16 . «» «» , .
• «» 3 .
• 96 . , — .

Pour tenir compte de toutes ces règles, les informations historiques doivent être intégrées dans les états de recherche. Ils ont besoin de champs dans lesquels le nombre de cadres de maintien pour chaque bouton et le nombre de cadres après la dernière version automatique seront stockés. Chaque ensemble unique de valeurs, y compris les coordonnées x, yet la rotation tetrimino caractérisent un état séparé et unique. Malheureusement, le nombre de possibilités est si vaste qu'une recherche complète de cet espace est impossible. La version AI pour la manette de jeu n'en explore qu'un sous-ensemble.

AI utilise un objet Stateavec les champs suivants:

 { x, y, rotation, Left, Right, Down, A, B, fallTimer, visited, predecessor } 

Au lieu d'utiliser le décalage AI automatique dans des images alternatives, appuyez et relâchez le bouton Shift. Par conséquent, il n'a besoin de contrôler que si le bouton est enfoncé et non pendant combien de temps. Puisque aucune rotation automatique, la même idée s'applique aux boutons A et B. Par conséquent , le champ Left, Right, Aet Bpeut être interprété comme une liste contenant des valeurs suivantes:

 { RELEASED, PRESSED } 

En revanche, pour une descente en douceur, vous devez dans un premier temps maintenir enfoncé le bouton «Bas» pour trois images, ce qui nécessite l'existence de 4 états:

 { RELEASED, PRESSED_FOR_1_FRAME, PRESSED_FOR_2_FRAMES, PRESSED_FOR_3_FRAMES } 

Downaugmente progressivement de la valeur RELEASEDà PRESSED_FOR_3_FRAMES, à laquelle une descente douce se produit. Après cela, il peut recevoir une valeur RELEASEDou revenir à PRESSED_FOR_2_FRAMES, provoquant une descente en douceur toutes les deux images après le délai initial. Cela ne peut pas être RELEASEDde PRESSED_FOR_1_FRAMEou de PRESSED_FOR_2_FRAMES.

En fait, le code Lua utilise une constante entière, mais le principe est le même. De

même, visitedet predecessor, fallTimeril est attribué la valeur obtenue lors de l' écriture dans l'état de file d'attente subsidiaire; ce fallTimersera un de plus que la valeur de l'état parent. Condition contenantfallTimer, qui est égale à la vitesse de descente, implique que la descente automatique se produit dans cette trame, et l'état suivant de cet état fallTimersera 0.

Chaque Searcherprédéfinit un 8-tableau contenant tous les états possibles ( 20 × 10 × 4 × 2 × 2 × 4 × 2 A × 2 B), et BFS est exécuté de manière similaire à la méthode indiquée pour le tableau. Le pseudo-code ci-dessous décrit comment les états suivants sont obtenus à partir des états de repos.

 Slide = (Left == PRESSED) or (Right == PRESSED) Rotate = (A == PRESSED) or (B == PRESSED) if Down == RELEASED or Down == PRESSED_FOR_3_FRAMES then if Down == RELEASED then nextDown = PRESSED_FOR_1_FRAME else nextDown = PRESSED_FOR_2_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end if Slide then addChild() if not Rotate then addChild(A = PRESSED) addChild(B = PRESSED) end else addChild(Left = PRESSED) addChild(Right = PRESSED) if not Rotate then addChild(Left = PRESSED, A = PRESSED) addChild(Left = PRESSED, B = PRESSED) addChild(Right = PRESSED, A = PRESSED) addChild(Right = PRESSED, B = PRESSED) end end else if Down == PRESSED_FOR_1_FRAME then nextDown = PRESSED_FOR_2_FRAMES else nextDown = PRESSED_FOR_3_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end end 

Comme indiqué dans le pseudo-code ci-dessous, la fonction addChildprend en compte l'ordre des événements qui se produisent dans chaque image (par exemple, décalage, rotation et descente).

 nextFallTimer = fallTimer + 1 if Left == PRESSED and testPosition(x - 1, y, rotation) then x = x - 1 elseif Right == PRESSED and testPosition(x + 1, y, rotation) then x = x + 1 end if A == PRESSED and testPosition(x, y, nextClockwiseRotation) then rotation = nextClockwiseRotation elseif B == PRESSED and testPosition(x, y, nextCounterclockwiseRotation) then rotation = nextCounterclockwiseRotation end if Down == PRESSED_FOR_3_FRAMES or nextFallTimer >= dropSpeed then if testPosition(x, y + 1, rotation) then y = y + 1 nextFallTimer = 0 else lockTetrimino() return end end childState = states[y][x][rotation][Left][Right][Down][A][B] if not childState.visited then childState.visited = mark childState.predecessor = state childState.fallTimer = nextFallTimer queue.enqueue(childState) end 

Comme dans la version précédente, il AI.searchrenvoie une chaîne d'objets State. Mais dans ce cas, chacun Statecontient de nombreux boutons qui doivent être enfoncés dans chaque image. Champ x, yet rotationne sont pas utilisés pour manipuler les chiffres, mais il peut être utilisé pour vérifier l'exactitude du mouvement des chiffres.

Bien que l'espace de recherche ait été considérablement réduit en raison des limitations décrites ci-dessus, il faut 1 à 3 secondes pour terminer la recherche. Si vous l'exécutez, vous remarquerez une pause après la création de chaque tetrimino. De plus, les mouvements semblent très peu naturels; généralement, un virage est effectué un instant avant le verrouillage. Cependant, cette IA joue presque de la même manière que la version qui ignorait la gravité, même à vitesse maximale.

Pour le vérifier, exécutez-le lua/NintendoTetrisAIGamepadVersion.lua, situé dans le fichier zip avec les sources .

Un moyen plus simple de tenir compte de la gravité consiste à limiter le mouvement des figures uniquement en tournant, suivi d'un décalage, puis en descendant vers le bas. L'idée est que si vous vous débarrassez du glissement et du défilement, la vitesse verticale des figures aura peu d'effet sur l'IA; tout ce qu'il doit faire est de livrer la figure à la colonne souhaitée, et la gravité fera le reste. Un autre avantage de cette technique est que l'espace de recherche est très petit, ce qui vous permet de jouer en temps réel, sans délai pour les calculs. Cependant, l'inconvénient de cette approche est que sans glissement et défilement, l'IA joue bien pire. Cependant, le Tetris AI, incapable de jouer en temps réel, est pratiquement sans valeur.

Addition

Plus tôt, j'ai écrit un plugin qui simulait procéduralement un joueur dans Tetris. Cependant, mon projet avait quelques inconvénients:

1. Le bot a désactivé la gravité, vous permettant d'effectuer des glissements et des défilements, dépassant les capacités du joueur au niveau très minimal de Nintendo Tetris. Il n'augmente jamais les chiffres, mais la seule façon de les abaisser est une descente douce contrôlée. Autrement dit, il joue dans un monde théorique idéalisé. Pour le dire franchement, il triche.
2. . — , . Double, Triple Tetris, — , . 90. , , 29 - .
3. . . . , Tetris .

Dans cette section, je vais parler d'un bot avancé qui joue à Nintendo Tetris sans désactiver la gravité. Il évalue le risque et le gère, s'efforçant agressivement d'obtenir le maximum de points avant d'atteindre une vitesse de descente élevée.

---

Vidéo

Regardez le bot gagner le nombre maximum de points Nintendo Tetris à partir du niveau 19 dans toutes les vidéos présentées ci-dessous.

---

Téléchargez

TetrisAI_2018-01-28.zip

Le fichier .zipcontient:

• src - arbre de code source.
• TetrisAI.jar - fichier binaire compilé.
• lgpl-2.1.txt - licence de logiciel libre.

---

Lancement

Prérequis

• Nintaco est un émulateur NES / Famicom.
• Tetris (U) [!].nes - Fichier ROM Nintendo Tetris.

Lancement du plugin

1. Lancez Nintaco et ouvrez Tetris (U) [!].nes.
2. Extrait TetrisAI.jardu téléchargement .zip.
3. Ouvrez la fenêtre Exécuter le programme en choisissant Outils | Exécuter le programme ...
4. JAR Find JAR… .
5. Load JAR, .
6. Run.
7. , GAME TYPE MUSIC TYPE . D-pad ( ) A-TYPE . Start (Enter), .
8. A-TYPE D-pad ( ) LEVEL 9 . , A Start ( X Enter), 19, .

Il convient de noter que le bot est conçu uniquement pour le niveau 19 et supérieur. Aux niveaux inférieurs, il ne pourra pas contrôler les pièces.

Référence de vitesse

Pour accélérer le jeu, sélectionnez Machine | Vitesse | Max

---

Détails

Plateau

En dessous du niveau 10, la vitesse de descente à chaque niveau est légèrement supérieure à celle du précédent. Mais au niveau de 10 et au-dessus il y a plusieurs plateaux où la vitesse reste constante pour plusieurs niveaux. C'est une conséquence du fonctionnement du mécanisme de déclenchement. La vitesse est présentée comme le nombre d'images par descente, qui est une valeur entière. Autrement dit, pour les niveaux supérieurs, il n'y a pas beaucoup d'options disponibles: 10–12, 13–15, 16–18, 19–28 et 29+ sont 5, 4, 3, 2 et 1 image pour la descente.

Le bot a été développé en ne prenant en compte que le plateau 19-28. Dans les images paires, il clique sur la manette de jeu "Gauche", "Droite", A, B ou rien. Et dans des cadres impairs, il permet une descente automatique sans appuyer sur aucun bouton. Il semble que le jeu ne perçoive pas le mouvement horizontal coïncidant avec la rotation; par conséquent, chaque bouton est appuyé indépendamment dans des images paires.

Contrairement aux maîtres qui jouent à des niveaux élevés, le bot ne profite pas du décalage automatique différé (DAS), également connu sous le nom de répétition automatique, et des techniques connexes. Son travail rappelle davantage la technique du pouce vibrant de Thor Akerlund . Cependant, cela augmente la fréquence des vibrations au maximum théorique autorisé par le jeu.

Les joueurs sont récompensés par 40, 100, 300 et 1200 points pour Single, Double, Triple et Tetris. Et les points sont multipliés par le nombre de niveaux plus 1. En d'autres termes, pour obtenir le score maximum, le joueur doit viser le nombre maximum de Tetris, en jouant le plus longtemps possible à des niveaux élevés.

Le niveau 19 est le plus élevé pouvant être sélectionné comme niveau initial, ce qui permet au bot de sauter directement sur le plateau 19-28. Cependant, en raison d'un bug dans le mécanisme de calcul de niveau que j'ai mentionné dans la partie précédente, le jeu passera au niveau 20 après avoir effacé 140 lignes, au lieu des 200 attendus. Après cela, le jeu changera de niveau toutes les 10 lignes. Cependant, après avoir atteint 230 rangées, le bot se lèvera du plateau et abandonnera rapidement. Autrement dit, il doit composer autant de Tetris que possible avant de nettoyer 230 lignes.

Descente douce

La descente en douceur peut également augmenter le nombre de points. Pour obtenir des points, la figurine doit être doucement abaissée pour se verrouiller sur le terrain de jeu. Toute descente douce à court terme qui se produit en cours de route lors du positionnement d'une figure n'affectera pas le score. Si la descente est réussie, le joueur recevra un point pour chaque ligne franchie lors de la descente en douceur. Et la valeur résultante n'est pas multipliée par le numéro de niveau, même si une descente douce conduit à effacer les lignes.

La descente en douceur a peu d'effet sur le score global. Cependant, si possible, le bot termine le placement de la figure en cliquant sur «Bas» pour obtenir ces points. Dans de rares cas, il peut faire la moyenne de la différence entre un score très élevé et dépasser le score maximum.

Algorithme d'IA

Lors de la création d'une forme, le bot explore tous les emplacements possibles des formes actuelles et suivantes. Le placement autorisé est la position dans laquelle la figurine repose soit sur des cellules occupées, soit sur le sol du terrain de jeu. Depuis le lieu de création de la figure, cette position peut être atteinte par une séquence de mouvements horizontaux, de virages et de descentes. Les emplacements valides et les séquences de chemins sont trouvés à l'aide de BSF.

Placer un morceau sur le terrain de jeu a des conséquences: 4 cellules vides deviennent occupées, et toutes les lignes remplies sont effacées, laissant les lignes descendre. Pour chaque placement autorisé de la figure actuelle et les conséquences qui y sont associées, le bot vérifie chaque placement autorisé de la figure suivante, évaluant la combinaison des conséquences. Une telle chaîne de recherche est présentée SearchChain.

Chacune des conséquences combinées est transférée vers une fonction d'évaluation qui calcule le contenu du terrain de jeu. La combinaison avec le score le plus bas gagne et la pièce actuelle est placée en conséquence. Les résultats de la chaîne de recherche affectent uniquement la forme actuelle. Lors de la création de la figure suivante, elle est évaluée en combinaison avec la figure qui la suit, etc.

Fonction d'évaluation

La fonction d'évaluation est une somme pondérée des paramètres suivants:

• Le nombre total de lignes effacées est le nombre de lignes effacées par l'ajout des deux tétriminos.
• – , . — , , .
• - – .
• – , -.
• – , . . .
• – . , 1. , , .
• – , . — , — .
• – . , (20).
• – . , 0.
• – , ( ) .
• : — , ( ) . . . .
• – . , 1 , 1, — 0.
• – .
• – .
• – .
• – . .
• – .

Apprentissage automatique

Pour trouver les poids de la fonction d'évaluation, nous avons utilisé une variante de la méthode d'optimisation des essaims de particules (PSO) décrite dans la note de bas de page [1]. Pour obtenir un bon comportement convergent, les coefficients d'inertie et d'accélération proposés sont appliqués. Et les tailles maximales des pas de particules sont déterminées par la limitation de leurs valeurs de vitesse.

Au cours de chaque itération, les particules ont été évaluées en parallèle pour utiliser pleinement les ressources informatiques disponibles. De plus, une fois la convergence détectée (aucune amélioration après un certain nombre d'itérations), le PSO a été configuré pour redémarrer automatiquement avec des poids sélectionnés au hasard, ce qui nous a permis d'explorer davantage l'espace de recherche.

Chaque vecteur de position des particules a été évalué en simulant l'achèvement de 100 lots sur un plateau de niveaux 19 à 28. Un lot complet implique le nettoyage de 230 lignes, mais beaucoup se sont terminées par un débordement du champ. Les scores des lots ont été triés et les scores des particules ont été déterminés comme la moyenne de 33 lots sur 100. L'idée était de choisir en fonction de l'agressivité. Les particules du tiers supérieur ne s'habituent qu'aux séquences de chiffres souhaitées, ce qui limite la nécessité d'un jeu conservateur. En conséquence, ils ont tendance à pousser le jeu habituel au bord du gouffre, en attendant le prochain «bâton».

Des séquences de motifs pour 100 lots ont été générées avant la PSO, et les mêmes séquences ont été utilisées encore et encore. Cela était nécessaire pour fixer l'espace de recherche, afin que les options de solution puissent être comparées les unes aux autres. Les séquences ont été créées en utilisant la logique d'un vrai PRNG Nintendo Tetris, qui est conçu pour réduire les chances de doublons les uns après les autres. Mais PRNG a également des faiblesses (voir la section «Choisir Tetrimino» d'un article précédent): il ne sélectionne pas les chiffres de manière uniforme.

Les premières tentatives ont conduit les bots à agir de manière trop agressive. S'ils surmontaient le plateau 19-28, ils atteignaient généralement le score maximum. Mais, malheureusement, elles ont souvent conduit trop tôt à des débordements sur le terrain. En réponse à cela, quatre mesures ont été prises pour «calmer» les robots:

1. : Tetris, . «» . . ; 230 . , Tetris . Single, Double Triple. ; .
2. . , , 7 . .
3. , , . , 7 .
4. , , . , . , .

Après avoir appliqué toutes ces règles pour «calmer» les bots, la méthode PSO a donné les poids suivants:

Paramètre	Le poids
Nombre total de lignes effacées	0,286127095297893900
Hauteur totale de blocage	1.701233676909959200
Nombre total de cellules de puits	0,711304230768307700
Nombre total de puits profonds	0,910665415998680400
Le nombre total de trous dans les colonnes	1.879338064244357000
Total des trous de colonne pondérés	2.168463848297177000
Nombre total de profondeurs de trous dans les colonnes	−0,265587111961757270
Profondeur minimale du trou de colonne	0,289886584949610500
Profondeur maximale du trou de colonne	0,362361055261181730
Le nombre total de transitions dans les colonnes	−0,028668795795469625
Total des sauts de ligne	0,874179981113233100
Hauteur totale des colonnes	−0,507409683144361900
Hauteur de tas	−2.148676202831281000
Dispersion des hauteurs de colonne	−1.187558540281141700
Nombre total de cellules occupées	−2,645656132241128000
Nombre total pondéré de cellules occupées	0,242043416268706620
Dispersion des hauteurs de colonne	0,287838126164431440

Étant donné que la chaîne cherche une combinaison qui minimise la fonction d'évaluation, les paramètres qui ont des poids positifs peuvent être considérés comme des bonus, et le reste - des amendes. Mais les poids ne montrent pas nécessairement la signification des paramètres correspondants; ils ne sont pas normalisés, ils ne peuvent donc pas être comparés.

Force de l'IA

Pour évaluer la force de l'IA, environ 1,7 million de résultats (en points) de jeux simulés ont été collectés sur un plateau de 19 à 28. Le score ne reflète pas le jeu au niveau 29 ou supérieur et ne prend pas en compte les points obtenus en descente douce. Cependant, il comprend des parties prématurément terminées en raison de débordements sur le terrain. La logique Nintendo Tetris PRNG a été utilisée pour générer les séquences Tetrimino.

Parmi ces résultats, le score le plus élevé est de 1 313 600. Le minimum est de 0. La

moyenne est de 816 379, et il semble être faible. Mais comme mentionné ci-dessous, les données sont déformées, de sorte que le score médian de 989 200 points donne une meilleure idée de la valeur typique.

Comme indiqué ci-dessus, les poids optimisés par PSO sont basés sur la moyenne du meilleur tiers des lots. Dans ce cas, le score moyen du meilleur tiers est de 1 108 860. En fait, le score moyen des meilleurs 75% est de 1 000

000. Le bot a une probabilité de 47% d'atteindre la limite de points au niveau 29. Il a une probabilité de 61% d'obtenir 900 000 points au niveau 29. Le graphique ci-dessous montre les probabilités de marquer jusqu'au niveau 29.


Il semble que la probabilité diminue linéairement à environ 900 000 points. Il entre ensuite dans une courbe sigmoïde inversée.

Vous trouverez ci-dessous un histogramme lissé avec le nombre de parties pour chacun des points marqués. Sa forme est déterminée par la dérivée du graphique ci-dessus.


Si vous ignorez les fluctuations, alors jusqu'à environ 900 000, il est plat, puis passe dans une distribution normale avec le centre autour de 1 050 000 points. Les raisons des fluctuations ne sont pas claires. Il semble que le nombre de points préfère sauter par incréments de 20 000 points. Cela est peut-être dû au cycle de construction du tas et à l'obtention de Tetris.

Allocation de RAM et de ROM

Pour manipuler la mémoire du processeur, transmettre des clics sur les boutons et recevoir des événements de rendu d'image, le plugin utilise l' API Nintaco . Toutes les adresses mémoire ont été découvertes à l'aide des outils de débogage Nintaco et des informations ont été ajoutées au wiki Data Crystal ROMhacking.net . Dans le code source, ils ressemblent à des constantes dans l'interface Addresses.

---

Les références

1. van den Bergh, F.; Engelbrecht, AP (2006)
   A study of particle swarm optimization particle trajectories
   In: Information Sciences 176 (2006) (pp. 937–971)
   Retrieved from http://researchspace.csir.co.za/dspace/bitstream/handle/10204/1155/van%20den%20bergh_2006_D.pdf