salut!



Nous sommes dans notre première année d'études de premier cycle en mathématiques appliquées et en informatique au HSE de Saint-Pétersbourg. Tout en travaillant sur un projet d'équipe semestriel en C ++, nous avons décidé d'écrire une version informatique de l' Intellector avec un bot - une partie d'échecs sur un plateau hexagonal avec des personnages spéciaux.



Dans cet article, nous parlerons du déroulement du développement du jeu, comment apprivoiser un plateau hexagonal, comment dessiner sur la ligne de commande, et aussi comment nous avons créé un bot que nous ne pouvons presque pas vaincre.







Il y a 3 personnes dans notre équipe: Yura Khudyakov, Valera Golovin, Misha Savrasov. Pour chacun de nous, c'est le premier projet d'équipe, donc dans le processus de travail, nous avons non seulement écrit sur les pros, mais aussi appris à travailler en équipe et à utiliser des systèmes de contrôle de version (dans notre cas, git). Il y a un certain nombre de bizarreries dans le projet, en particulier les vélos - il existe de bonnes solutions toutes faites qui pourraient être utilisées. Cependant, le but de notre projet était d'acquérir de l'expérience, nous avons donc beaucoup inventé et mis en œuvre nous-mêmes.

Qu'est-ce qu'un intellectuel?

Pour commencer, cela vaut la peine d'expliquer quel type de jeu nous avons écrit.



Le jeu "Intellector" est apparu récemment et gagne toujours en popularité. Le premier championnat ouvert a eu lieu à Saint-Pétersbourg cette année .





L'intellector diffère des échecs par la structure du champ, les règles et un ensemble de pièces. Cependant, de nombreux éléments sont similaires: par exemple, il y a une figurine Progressor dans le jeu, qui joue le rôle d'un pion. Elle ne marche que vers l'avant et peut se transformer en une autre silhouette lorsqu'elle atteint la rangée extrême.



Le roi ici est un personnage appelé l'Intellecteur. Le but du jeu est de couper cette pièce, pas de la mater (bien que ce soit presque la même chose).



Les différences dans la mécanique du jeu proviennent des spécificités du terrain. Le champ Intellect est symétrique, ce qui le distingue considérablement des échecs avec son côté roi et son côté reine.



Pour comprendre cet article, la connaissance des règles et la capacité de jouer ne sont pas requises.

Architecture générale

Que voulons-nous dans notre application?

Pour que le jeu fonctionne, vous devez implémenter son composant principal: la logique du jeu. Il comprend un modèle de plateau et des règles de déplacement. De plus, pour plus de commodité, il vaut la peine de garder l'historique des mouvements et de mettre en œuvre l'annulation / la restauration.



Le tableau doit être affiché et permettre à l'utilisateur de jouer. Ceci est fait par le composant graphique du jeu - l'interface. Une interface conviviale doit avoir des menus et des paramètres.



Après tout, vous avez besoin d'un adversaire pour jouer. Nous avons décidé de créer un bot à ces fins afin que le joueur puisse rivaliser avec l'ordinateur. Dans ce cas, la complexité du bot doit être ajustable.

Plan d'application:

1. Logique du jeu
   • Modèle de carte hexagonale
     
     Stocké sous forme de tableau bidimensionnel de cellules hexagonales
   • Règles pour les pièces mobiles
     
     Vérifier l'admissibilité d'un coup, obtenir tous les coups disponibles pour une pièce, pour un joueur
   • Historique des déplacements
     
     Annuler et refaire un déplacement
2. Interface
   
   prévue 2 interfaces: ncurses et Qt. Seul ncurses est implémenté dans le projet, voir la section Interface pour plus de détails.
   • Affichage d'un champ Rendu
     
     et mise à jour d'un champ dans la console
   • Déplacer le curseur avec les touches du clavier, jouer sans souris
   • Affichage de l'historique textuel des mouvements
   • Affichage du menu principal
3. Le bot
   • Bot aléatoire
   • Bot gourmand
   • Bot alpha-bêta
     
     optimisé pour itérer sur tous les mouvements

Comment est-il fait?

Une architecture d'application très simplifiée est décrite par ce schéma:





La section Jeu est responsable de toute la logique du jeu et stocke le plateau.



Lorsque le jeu avec l'ordinateur est allumé, le jeu interagit avec le bot depuis le Bot



Controller, prend des données sur le jeu du jeu et les transfère vers l'interface pour les afficher aux joueurs. L'interface, à son tour, renvoie le résultat de l'interaction de l'utilisateur au jeu via le contrôleur.



Le lien intermédiaire sous forme de contrôleur est utile lorsqu'il y a plusieurs interfaces (au départ nous avions prévu de faire 2 interfaces: console et graphique). Tous communiquent avec le jeu de manière uniforme via le contrôleur, au lieu que chacun le fasse différemment.

Détails techniques

Modèle de jeu

Conseil hexagonal

Considérez la section Jeu du diagramme ci-dessus. Il doit stocker le plateau et gérer toute la logique du jeu.



Pour une meilleure compréhension, vous pouvez lire l' article dont nous avons tiré cette idée.



Nous allons stocker la carte entière dans un tableau bidimensionnel de cellules, dont les éléments sont indexés par paires de coordonnées (w,h)comme le montre la figure ci-dessous. Un tel choix de coordonnées semble naturel, mais il est peu pratique pour décrire le mouvement des formes (observer, par exemple, comment les coordonnées changent lors du déplacement le long de la diagonale).





^{Coordonnées des cellules le long de l'axe horizontal wet de l'axe verticalh}



Pour la commodité de la description du mouvement des figures, nous utiliserons des coordonnées tridimensionnelles. Choisissons une cellule comme cellule de référence avec des coordonnées {0,0,0}(pour plus de commodité, elle coïncidera avec la cellule du (0, 0)tableau).





^{Coordonnées tridimensionnelles des cellules par rapport à la cellule centrale avec coordonnées Le{0,0,0}}



déplacement le long de la diagonale "de droite à gauche, de bas en haut" est désigné par la coordonnée x, le déplacement de bas en haut - par la coordonnée yet le déplacement le long de la diagonale "de gauche à droite, de bas en haut" - par la coordonnée z. Lors du déplacement vers une cellule adjacente, la coordonnée correspondante changera de un. Ainsi, chaque cellule reçoit trois coordonnées, comme dans l'image ci-dessus.



Dans ce cas, les cellules sont numérotées de manière ambiguë. Par exemple, si à partir de la cellule centrale avec les coordonnées, {0,0,0}nous nous déplaçons à gauche vers le bas puis vers le haut, nous obtenons les coordonnées de la cellule {0,1,-1}. Mais la même cellule a des coordonnées {1,0,0}si vous y accédez directement depuis la cellule centrale, comme vous pouvez le voir sur la figure précédente.





^{Une autre option pour spécifier les coordonnées de la cellule {1,0,0}.}



Traverser n'importe quelle cellule dans un cycle "gauche-bas" - "haut" - "droite bas" nous amène à la même cellule, mais ajoute un vecteur à ses coordonnées {-1,1,-1}, dont la somme des coordonnées est -1. En effectuant mentalement un tel parcours dans le même sens ou dans le sens opposé plusieurs fois, on peut changer les coordonnées de n'importe quelle cellule en équivalente, qui différera par un vecteur proportionnel {-1,1,-1}. Pour se débarrasser de l'ambiguïté, dans chaque classe d'équivalence, on choisit comme représentant un triplé de coordonnées dont la somme est égale à zéro. Ce choix de coordonnées est unique (prouvez-le!).



Décrivons plus en détail l'algorithme de conversion de coordonnées bidimensionnelles en coordonnées tridimensionnelles et vice versa au sein de la classe Position.

Position(int w, int h) //    
        : x_{-w/2 — w % 2 - h}
        , y_{w % 2 + 2 * h}
        , z_{w / 2 — h} {
}

int posW() const { //       
    return -x_ + z_;
}

int posH() const { //       
    return (x_ + z_ — (x_ + z_)%2) / 2 + y_;
}

Notez que le constructeur produit des coordonnées (x,y,z)qui totalisent zéro. Dans ce cas, la conversion des coordonnées (x,y,z)en (w,h)fonctionne correctement pour tout ensemble de coordonnées (la somme n'a pas besoin d'être nulle).



Comment avons-nous trouvé toutes ces formules? Par la méthode scientifique poke: en analysant le changement des coordonnées tridimensionnelles lorsque l'une des coordonnées bidimensionnelles est décalée de 1(constructeur) et dans la direction opposée (méthodes).



En utilisant des coordonnées tridimensionnelles, nous pouvons facilement vérifier que les cellules sont colinéaires. Par exemple, pour vérifier que deux cellules se trouvent sur la même diagonale z, vous devez trouver un vecteur reliant ces cellules et vérifier que sa classe d'équivalence contient un vecteur de la forme{0, 0, z}... Z peut être n'importe quoi - ce nombre donne la distance entre les cellules. Il sera très simple de mettre en œuvre la vérification de l'exactitude du coup et de trouver toutes les cellules disponibles pour le coup.



Dans un tableau bidimensionnel qui représente la carte, nous stockerons des informations sur la position des figures. Dans chaque cellule, s'il y a une pièce d'échecs, nous stockerons son type et sa couleur.



Dans notre implémentation dans la classe board, nous stockons uniquement les types de pièces dans des cellules. Nous avons besoin d'une classe qui puisse trouver tous les coups possibles pour les pièces sur ce plateau et vérifier l'exactitude des coups.

Se déplace pour les pièces

Nous avons fait une classe FigureMoveValidatorqui a 6 héritiers pour chaque type de figure (il était possible de se passer d'héritiers, si dans chaque méthode on faisait un switch case pour le type de figure). Le constructeur de classe a 2 paramètres: la position et la référence de la carte. Également dans la classe, il existe deux méthodes allMoveset checkMove.



Considérons la méthode allMoves. Pour trouver tous les déplacements, composons un tableau de vecteurs de déplacements possibles et parcourons-le. Pour les pièces qui bougent d'un pas, nous devons vérifier que nous n'avons pas sauté du plateau et ne sommes pas entrés dans la cellule où se trouve notre pièce. Pour les figures qui déplacent plusieurs cellules en ligne droite, ajoutez un vecteur de déplacement pendant que la condition précédente passe.



MaintenantcheckMove... Nous nous souvenons que nous savons vérifier si les chiffres sont sur la même ligne droite. Si nous vérifions qu'il n'y a pas d'autres pièces sur cette ligne, nous obtenons une méthode toute faite pour le Dominator (analogue de la tour). Si les pièces se trouvent sur une ligne droite, alors nous pouvons trouver la distance entre elles et obtenir des méthodes pour le Progressor (pion), le Defenser (marche comme un roi), l'Intelligence (le roi ne peut pas couper) et le Liberator (peut traverser une cellule vers n'importe quel côté). Il y a toujours un agresseur (analogue d'un éléphant), qui se déplace dans les cellules en diagonale dans six directions à partir de l'actuelle (de la cellule {0, 0, 0}à {0, 1, 1}, à {0, 2, 2}, etc.: voir les cellules grises dans l'image ci-dessous). Pour cette figure, vous pouvez essayer de remettre à zéro l'une des coordonnées et vérifier que les 2 coordonnées restantes sont égales en valeur absolue (grâce aux coordonnées tridimensionnelles).





^{Mouvements possibles pour l'agresseur}



Nous devons maintenant déterminer ce qu'il faut faire avec les mouvements. Créons une classe Move qui stockera toutes les informations nécessaires pour le déplacement. Nous avons décidé de stocker 2 positions et 4 pièces: la position à partir de laquelle la pièce se déplace, la position d'où elle viendra, et des informations sur les pièces qui se trouvaient dans chacune de ces cellules et celles qui se tiendront après l'application du mouvement. Cela facilitera la mise en œuvre du système d'historique des déplacements et la restauration des déplacements.

Interface

Architecture

L'application est écrit dans la bibliothèque de la console ncurses (voici un tutoriel pour cela ) . Cette bibliothèque vous permet de créer des pseudo graphiques dans la console. Par exemple, Midnight Commander et Nano sont basés dessus .



Le choix peut paraître très étrange: il existe de nombreuses autres bibliothèques, plus belles, pratiques et multiplateformes. C'est lié au fait qu'au départ nous avions prévu de faire 2 interfaces: console et graphique. Nous n'avons pas réussi à écrire 2 interfaces au moment de la livraison du projet et avons plutôt créé plus de fonctionnalités dans la version console. Bien que sur le plan architectural, l'application est toujours conçue pour différentes interfaces.



Il y a 2 entités principales: affichage et contrôleur... Les mappages montrent l'image aux joueurs et le contrôleur sert d'intermédiaire entre les différents mappages et le modèle de jeu interne.



L'affichage gère toutes les interactions de l'utilisateur: position et mouvement du curseur, sélection de forme, mise en évidence des champs disponibles, achèvement du jeu, etc. Les actions qui affectent la carte font référence au contrôleur et envoient / reçoivent les informations nécessaires vers / depuis le modèle.



L'affichage crée sa propre version du tableau, mais avec des paramètres supplémentaires dont il a besoin, tels que la position du curseur et la couleur des cellules. Ces paramètres ne peuvent pas être ajoutés au modèle principal car différents mappages nécessitent des paramètres différents. Par exemple, dans l'interface de la console, vous devez stocker la position du curseur, mais pas dans l'interface graphique, car la sélection et le déplacement de la figure se font à la souris.



Voici ce qui se passe si un joueur souhaite connaître les champs disponibles pour le déplacement:

1. Le joueur déplace le curseur sur le champ de la figure et appuie sur la barre d'espace
2. Le champ avec la forme est marqué comme sélectionné
3. L'interface fait référence à une méthode selectCellsur le contrôleur
4. La méthode selectCellfait référence à la méthode du allFigureMovesmodèle
5. allFigureMovescrée FigureMoveValidatorqui calcule tous les coups disponibles
6. allFigureMoves les transferts trouvés reviennent au contrôleur
7. Le contrôleur les transmet à l'interface
8. L'interface redessine le champ, mettant en évidence les champs disponibles

^{Le curseur se trouve au milieu du plateau: sur un carré bleu pâle. Avant de le déplacer vers cette position, l'utilisateur a sélectionné une forme. Les mouvements disponibles sont surlignés en vert et la cellule sélectionnée elle-même est en violet.}

Comment le champ est-il dessiné?

L'interface de la console est rendue dans une fenêtre rectangulaire avec des lignes de texte. Si vous mettez des symboles aux bons endroits et que vous les coloriez, vous obtenez une image:





^{(Evil Pacman, dessiné avec les lettres "o")}



Une fonction move(int y, int x)dans ncurses change la position actuelle, et la fonction addch(chtype c)ajoute un caractère et décale la position actuelle 1 vers la droite ( x —> x+1).



Une image complexe peut être stockée sous forme de tableau bidimensionnel et affichée ligne par ligne: à la fin de la ligne, déplacez la position actuelle au début de la ligne suivante. Le principe est très similaire à une machine à écrire.



Sur l'ordinateur de l'utilisateur, le champ de notre jeu sera coloré si le terminal prend en charge les couleurs et autres attributs de texte.



Ncurses permet au développeur de modifier les attributs du texte lors de sa sortie sur la console (couleur, gras, clignotement). Pour ce faire, écrivez dans le code:

attron( *attributes* );
addch(c);
attroff( *attributes* );

Chaque symbole a sa propre couleur et sa couleur d'arrière-plan. Les consoles modernes prennent en charge un maximum de 256 couleurs, vous devez donc travailler avec un ensemble limité : assez triste en termes de conception de couleurs.



Les images pour la sortie peuvent être stockées dans le code (comme nous l'avons fait initialement), ou elles peuvent être stockées dans des fichiers séparés et lues à partir de ceux-ci lorsque le programme démarre. Pour cela, nous avons mis au point notre propre format de fichier *.btn.



Il stocke une image de texte que le jeu lira et affichera. Par exemple, une forme, ou l'inscription «Blanc gagne» / «Noir gagne», ou un bouton de menu. Dans ce cas, vous pouvez parfois avoir besoin de transparence pour ne pas écraser ce qui a été dessiné précédemment. Pour ce faire, vous pouvez ajouter un hachage dans la première ligne #et après la liste des symboles "transparents" qui seront ignorés dans la sortie.



Par exemple, disons que nous avons 3 rectangles dessinés à l'écran:





Ajoutez un rectangle du fichier suivant au centre:

#C
AAAAAAAAA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
AAAAAAAAA

Et nous obtenons l'image suivante:





^{(surligné en jaune pour plus de clarté)}



Ce format était particulièrement utile lors du développement de menus.

Menu

Le jeu a également un menu qui contient des paramètres et est dessiné avant le début du jeu et après sa fin.



Les boutons de menu sont lus à partir des fichiers *.btn. Ces boutons doivent avoir un texte grand et beau. Nous ne savons pas comment dessiner magnifiquement en utilisant des caractères ASCII, mais figlet , un utilitaire permettant d'afficher du texte ASCII dans différentes polices, peut:





Les boutons encadrent les étiquettes lues dans le fichier:





Ils sont ensuite centrés et sortis séquentiellement:





Dans certains menus, vous pouvez échouer et, par exemple, ajuster la complexité et la couleur du bot:





La partie la plus intéressante de la conception d'un système de menus consiste à combiner ses éléments en un seul système. Ceci est fait par un élément séparé du système, que nous avons appelé le multiplexeur. Le nom est inspiré des multiplexeurs terminaux .



Le multiplexeur accepte la touche pressée par l'utilisateur et l'envoie à tous les menus actuellement affichés. Chaque menu décide de lui-même quoi faire avec la clé: ignorer ou traiter d'une manière ou d'une autre. Le résultat du traitement du menu est renvoyé au multiplexeur, qui décide de la suite: fermer le menu, en créer un nouveau, modifier les paramètres, fermer l'application ...



Cette approche s'est avérée adaptée à nos besoins, même si en général elle peut ne pas suffire: 2 menus différents peuvent répondre à la même touche, et l'utilisateur doit pouvoir choisir quel menu doit répondre. La solution serait un raccourci clavier spécial qui vous permet de basculer entre différents menus. Par exemple, comme dans tmux . Mais c'est exagéré et n'était pas nécessaire.

Le bot

Comme mentionné ci-dessus, notre jeu a un bot. Nous avons essayé de le rendre intéressant à la fois pour un joueur débutant et expérimenté.



Avant de décrire les bots, j'aimerais parler de quelques détails d'implémentation. Nous avons attribué un poids à chaque forme. Plus il est grand, plus ce chiffre est précieux. Nous déterminons la qualité d'une position sur le plateau en utilisant la formule (somme des poids des pièces blanches) - (somme des poids des pièces noires). Il est avantageux pour le blanc de maximiser cette expression et pour le noir de la minimiser.



Un calcul complet de l'arbre entier des coups est une tâche trop difficile, nous n'avons donc calculé que les premiers coups (en regardant en avant, je dirai qu'il s'est avéré être calculé 6 coups en avant). Nous avons considéré tous les états du plateau à une certaine profondeur comme des feuilles de l'arbre de traversée.



Il existe trois types de robots différents dans le jeu:

• RandomBot — . .
• GreedyBot — «» , , .
• AlphaBetaBot — , - .

Lorsque nous avons commencé à expérimenter des optimisations, nous avons réalisé que nous ne pouvions pas nous passer de tests unitaires pour le bot, nous avons donc créé un frère jumeau pour AlphaBetaBot«a», que nous avons nommé OptimizedAlphaBetaBot. Nous avons testé toutes les idées d'optimisation sur OptimizedAlphaBetaBot, et les tests unitaires ont permis de s'assurer que deux frères jumeaux trouvent le même mouvement utile. RandomBot nous a bien servi en générant des motifs aléatoires sur le tableau. Pour ce faire, il suffisait de demander RandomBotet d'aller plusieurs dizaines de fois pour les deux côtés.



Au total OptimizedAlphaBetaBot , 3 optimisations majeures ont été implémentées (ici elles sont présentées par ordre décroissant d'utilité):

• Utilisation des restaurations. Après cette optimisation, il n'était plus nécessaire de copier plusieurs fois le tableau pour faire un mouvement.
• FigureKeeper, , . std::vector .
• std::unordered_map Zobrish hashing.

En plus des optimisations majeures, il y en avait aussi de plus petites. Par exemple, si, avant le tri, vous calculez toutes les valeurs des positions sur le plateau, en tenant compte d'un certain mouvement, alors vous n'avez plus besoin de trier les objets complexes Move, mais simplement ceux int.



Au départ, il était prévu de mettre en place plusieurs ensembles de fonctions d'évaluation: par exemple, un personnage menacé par un ennemi est estimé à la moitié du coût. Mais il s'est avéré que le bot joue assez "proprement", perdant peu de pièces, donc une simple quantité était plus efficace.



Cependant, l'architecture du bot prend toujours en charge l'ajout de nouvelles fonctions d'évaluation. Pour ce faire, vous devez définir seulement trois choses:

1. Fonction si vous devez calculer le coût "à partir de zéro" pour un arrangement donné de chiffres
2. Fonction Delta, qui devrait recalculer rapidement le coût d'un déménagement donné.
3. Le nombre de cet ensemble de fonctions pour le constructeur de la classe personnalisée FunctionSet.

Vous pouvez activer la bataille des bots et regarder le processus.





^{Un jeu de 2 bots de même difficulté (niveau 4 sur 6). Le curseur est au centre du champ pendant toute la partie}

Conclusion

Nous avons implémenté un jeu similaire aux échecs, mais avec des règles différentes et un plateau inhabituel. Notre implémentation peut se développer. Intellector lui-même se développe et change également: il y a récemment eu une mise à jour des règles, que nous n'avons pas encore prise en charge dans notre application. Par exemple, vous ne pouvez plus traverser la ligne médiane pendant les 2 premiers tours.



De plus, il existe diverses fonctionnalités que nous avions initialement prévues, mais que nous n'avions pas le temps de mettre en œuvre au moment du projet. Par exemple, dans cette application, j'aimerais vraiment voir un jeu en réseau. De plus, une belle interface multiplateforme, par exemple sur Qt, ne ferait pas de mal.



Peut-être que tout ou partie de cela apparaîtra dans un proche avenir. Jusque-là, merci d'avoir lu!



Dépôt Github