Dagaz: un nouveau départ

Il court au sud et tourne au nord, encerclant, encerclant pour courir avec son vent
Et selon ses circuits le vent revient;
Toutes les rivières se jettent dans la mer - et la mer ne déborde pas,
À l'endroit où les fleuves coulent, - Là, ils continuent de couler;

Le livre des ecclésiastes

En 1998, une application tout à fait unique, pour son époque, a été développée qui vous permet de réduire le processus de développement d'un jeu de société abstrait (ou puzzle) à un petit langage de description de texte, rappelant vaguement Lisp . Ce projet s'appelait Zillions of Games . Cela a fait fureur parmi les fans de jeux de société. Actuellement, plus de 2 000 applications ont été créées à l'aide de cette technologie.

Il est rapidement devenu évident que ZoG avait de nombreux inconvénients. J'ai déjà écrit à ce sujet dans Habr et je ne vais pas me répéter. Permettez-moi simplement de dire que les développeurs n'ont pas pris en compte les caractéristiques d'un grand nombre de jeux existants et que certaines options importantes ont été codées en dur, de sorte que leur changement est devenu extrêmement problématique. Greg Schmidt, en 2007, a tenté de rectifier la situation en publiant le kit de développement Axiom , mais son intégration étroite avec ZoG ne permet pas de résoudre tous les problèmes.

Le projet Ludi a mis en évidence de nouvelles frontières, en utilisant le «moteur» de jeu universel et des algorithmes génétiques pour automatiser le processus de développement de nouveaux jeux de société. Malheureusement, cette approche a été initialement envisagée comme une simplification délibérée des mécanismes de jeu et du niveau de l'IA employée. La discussion des objectifs de ce projet dépasse le cadre de cet article, mais certaines de ses solutions techniques ont sans aucun doute servi de point de départ à mon propre développement.

Mon objectif est le développement d'un «moteur» plus polyvalent et convivial pour la création de jeux de société abstraits. Depuis près d'un an, j'étudie la possibilité de ZoG et Axiom et j'ai beaucoup appris sur leurs limites. Je pense que je peux résoudre leurs problèmes en créant une solution plus universelle et multiplateforme. Sur l'état d'avancement des travaux sur ce projet, je ferai rapport.

Ouverture et modularité

Peut-être que le principal inconvénient de ZoG est sa fermeture. Le produit a été assemblé «une fois pour toutes» sous une seule plate-forme - Windows. S'il s'agissait de code open-source, on pourrait essayer de le porter sous Linux, Android, iOS ... Un autre problème est sa monolithicité.

Dans ZoG, il y a les débuts de la modularité, permettant la connexion à la DLL de jeux, y compris les implémentations personnalisées de l'IA. Axiom va un peu plus loin, vous permettant d'exécuter des applications en mode de lecture automatique, sans utiliser le noyau ZoG. Malgré les sérieuses limitations de cette solution (ne prenant en charge les applications que pour deux joueurs), cet exemple montre à quel point la modularité serait utile! L'opportunité d'organiser un jeu avec deux bots (en utilisant différents paramètres d'IA) et de collecter des statistiques sur un grand nombre de jeux ne peut pas être surestimée. Mais combien il serait préférable que le produit soit entièrement modulaire!

• Module de génération de mouvements
• Déplacer le module d'exécution
• Module de commande
• Module AI
• Module de visualisation

Tout le travail décrivant les jeux doit être effectué par le module de génération de mouvements. C'est le «cœur» du projet. Le transfert de toutes les tâches non liées à cette fonction vers d'autres modules le rendra aussi simple que possible. Vous pouvez améliorer ce module, sans regarder les problèmes d'IA et l'interaction des utilisateurs. Vous pouvez changer complètement le format de la description des jeux ou ajouter un support pour les descriptions au format ZoG, Axiom et Ludi. La modularité est la base de la flexibilité de la solution!

Le module d'exécution des mouvements est le gardien de l'état du jeu. Les informations sur l'état actuel du jeu sont transférées à tous les autres modules sur demande. Pour les raisons que je donnerai ci-dessous, la progression de l'exécution doit passer par le module de génération, dont la tâche est la formation d'une commande en termes d'exécution du module. De plus, la tâche du module de génération de mouvements est la configuration principale de l'espace de jeu, basée sur la description du jeu.

Le module de contrôle est en fait l'application elle-même. Il demande au module de génération de coups une liste des coups possibles et change l'état du jeu, en passant le coup sélectionné au module d'exécution des coups. Le module de contrôle peut être connecté pour jouer à un ou plusieurs robots AI. Autant que vous en avez besoin (et éventuellement différents)! Le type d'unité de contrôle est déterminé par la répartition des tâches. Cela peut être une lecture automatique pour collecter des statistiques de jeu, un serveur de jeu (il peut contrôler plusieurs magasins d'état, menant un grand nombre de sessions de jeu) ou des applications individuelles pour jouer hors ligne.

La possibilité de connecter différentes implémentations de l'IA améliorera la qualité du jeu. Il est entendu que les modules du jeu d'échecs et de go doivent utiliser des approches différentes. Les jeux avec des informations incomplètes et les jeux utilisant des données aléatoires nécessitent également une approche individuelle. La mise en œuvre universelle de l'IA sera également mauvaise pour tous les jeux! L'IA de connexion modulaire permettra de comparer la «force» des algorithmes, y compris un mode de jeu «les uns aux autres». Puisque l'architecture de l'IA est séparée de l'état de stockage du jeu, une instance du bot de jeu peut prendre en charge un nombre illimité de sessions de jeu simultanément.

La visualisation du processus de jeu peut également varier. La première chose qui me vient à l'esprit sont les implémentations 2D et 3D. La plate-forme pour laquelle l'application est en cours de développement est également importante. Moins évident est que la visualisation peut être une partie importante du jeu! Par exemple, dans le jeu Surakarta , prendre des pièces sera complètement non évident en l'absence d'animation appropriée des mouvements.


En général, la modularité semble une bonne idée pour un tel projet, et le code open source permettra à tous ceux qui souhaitent participer au projet. À l'heure actuelle, je ne me fixe pas d'objectifs commerciaux, mais je pense que, si je le souhaite, je trouverai un moyen de gagner de l'argent sans fermer le code source.

L'espace de jeu

Avant de commencer le spectacle, vous devez préparer le terrain. La planche n'est pas seulement un endroit où les pièces sont rangées. En plus de cela, le sens de déplacement des pièces peut être déterminé (en fait, les connexions entre les positions du plateau), des zones de jeu (par exemple, des zones de conversion des pièces), des champs interdits, etc. Voici à quoi ressemble la définition de l'échiquier dans l'implémentation ZoG:


Vous remarquerez peut-être qu'en plus des paramètres du jeu, voici les paramètres associés à la visualisation. Je suis fermement convaincu que ces paramètres n'appartiennent pas ici. Lors de la mise en œuvre d'un module de visualisation, plusieurs paramètres peuvent être utilisés et différents paramètres peuvent être requis. De plus, les jeux de simulation peuvent fonctionner sans aucun module de visualisation (comme la lecture automatique dans Axiom). En effet, puisque Axiom est utilisé pour visualiser ZoG, la définition ne contient rien de superflu:


Malheureusement, Axiom n'a pas non plus de moyen de déterminer les zones de jeu (l'emplacement des zones de jeu doit être déterminé manuellement dans le code). Ce n'est pas la seule simplification d'Axiom. La définition de la carte dans ce projet ne peut pas contenir plus d'une grille et cette grille doit être bidimensionnelle. La carte, ainsi définie, est un tableau unidimensionnel, mais pour la commodité du programmeur, des synonymes sont définis pour chacun des espaces comme suit:


Comparées au schéma plus flexible de définition de grille dans ZoG, ces restrictions sont assez inconfortables (surtout compte tenu du fait que le schéma de nommage imposé utilisait ces champs dans le but même de la visualisation). Heureusement, il est possible de définir une planche de forme arbitraire. Axiom et ZoG offrent tous deux la possibilité d'identifier chaque élément sur la carte ainsi que la possibilité de déterminer les liens entre des paires de positions arbitraires. En utilisant cette approche, nous pouvons définir une carte de n'importe quelle topologie. Son seul inconvénient est l'extrême verbosité et la complexité de la description.

En plus de l'emplacement des pièces sur le plateau et dans la réserve, le système devrait avoir la possibilité de stocker des attributs pour des pièces individuelles et pour les espaces sur le plateau. Un bon exemple de la nécessité d'utiliser les attributs d'une règle de « roque » dans les échecs . Il s'agit d'un mouvement difficile, qui comprend le mouvement simultané du roi et d'une tour, autorisé, à condition qu'aucune de ces pièces n'ait bougé avant d'effectuer ce mouvement. Un attribut pourrait être utilisé pour stocker une balise booléenne indiquant si la pièce a déjà bougé. Les attributs de champ peuvent également trouver des applications intéressantes.

Il convient de noter que les attributs ne sont pas seulement des variables mais font partie de l'état du jeu. Une valeur d'attribut peut être modifiée par l'exécution d'un tour (y compris par le module AI) et devrait être disponible pour tous les tours suivants, mais pas pour les tours effectués dans une autre branche du jeu. Actuellement, ZoG prend en charge le stockage des attributs booléens des pièces. Les attributs de stockage Axiom ne sont pas pris en charge, mais vous pouvez ajouter à la définition de la carte une description des variables et des tableaux. Ces variables peuvent être utilisées, telles que les compteurs de la quantité de pièces capturées:

 {board 5 18 {grid} {variable} WhitePieces {variable} BlackPieces board} 

Encore une autre limitation de ZoG et d'Axiom est la règle selon laquelle chaque position de la planche ne peut contenir plus d'une pièce. Si une pièce complète un mouvement vers une position occupée par une autre pièce, la pièce occupant précédemment la position est automatiquement considérée comme «mangée». Cette règle va bien avec le principe «d'échecs» de prendre des pièces et sert à simplifier la description de ce jeu, mais complique la mise en œuvre de jeux tels que « bashni checkers » et « tavreli ».



Dans ces jeux, les pièces peuvent être organisées en «colonnes». Une telle «colonne» peut être déplacée tous ensemble, comme une seule pièce. Après réflexion, j'ai décidé qu'il valait mieux ne pas abandonner l'implémentation automatique de la capture «Chess», mais améliorer les mécanismes de déplacement des groupes de pièces. En effet, pour l'implémentation des «piliers», vous pouvez toujours ajouter à bord une autre dimension (c'est particulièrement facile, tant que le module de visualisation est séparé du module de génération de mouvement et de l'IA, alors vous pouvez utiliser n'importe quelle logique que ce soit pour rendre la carte en trois dimensions dans sa visualisation en deux dimensions). Un autre argument en faveur de cette décision était que le mouvement de pièces «à empilement élevé» n'est pas le seul type de voyage de groupe. Par exemple, dans les panneaux « Pentago », les fragments peuvent être tournés avec les pièces montées dessus.


En résumé, je peux dire que, pour mon cadre de jeu, j'ai décidé de prendre tout ce qui a été pensé dans ZoG, Axiom et Ludi, et d'ajouter tout ce qui, à mon avis, leur manque.

Déplacer la génération

La génération de mouvements s'apparente à une programmation non déterministe . La tâche du générateur de déplacement fournit, sur demande, une liste de tous les déplacements possibles à partir de la position actuelle. Le mouvement de cette liste sera sélectionné par un joueur ou l'IA n'est pas sa fonction. Voyons comment la génération de mouvements se fait dans ZoG. À titre d'exemple, nous prenons la macro de génération de mouvement pour une pièce à longue portée (une reine ou un évêque). Voici comment il est utilisé pour déterminer les mouvements de ces pièces:

 (piece (name Bishop) (image White "images\Chess\SHaag\wbishop.bmp" "images\Chess\wbishop.bmp" Black "images\Chess\SHaag\bbishop.bmp" "images\Chess\bbishop.bmp") (moves (slide ne) (slide nw) (slide se) (slide sw) ) ) 

En paramètre, une macro passe la direction du mouvement sur la planche. Si vous n'envisagez pas la possibilité d'installer de nouvelles pièces sur la planche, la génération d'un coup semble simple. Pour chacune des pièces du plateau, tous les mouvements possibles selon les règles sont calculés. Puis la magie commence ...

Chacune des définitions peut ajouter à la liste un certain nombre de mouvements possibles! L'ajout d'un coup à la liste se fait avec la commande add (en positionnant en même temps chaque pièce en mouvement sur le plateau). J'ai déjà écrit à quel point cette solution architecturale est extrêmement pauvre. La commande pour la formation du mouvement doit être séparée des commandes qui manipulent les pièces (comme cela a été fait dans Axiom). Voyons comment fonctionne la macro:

 (define slide ( $1 (while empty? add $1 ) (verify not-friend?) add )) 

Tout d'abord, le déplacement est effectué par une cellule, dans la direction donnée, puis dans un cycle, l'espace atteint est vérifié pour l'absence des pièces dessus, un mouvement est formé et l'arrangement se poursuit vers une autre cellule dans la même direction. Si vous vous arrêtez ici, la pièce peut «glisser» à travers des cellules vides, mais comment pouvez-vous prendre des pièces ennemies?

Très simple! Après avoir exécuté la commande Verify, la vérification que le champ n'est pas occupé par une pièce amie, nous formons une autre commande d'ajout, terminant le déplacement. Si sur cette cellule se trouvait une pièce ennemie, elle sera prise automatiquement (comme sur une case du plateau, à la fois, vous ne pouvez pas avoir plus d'une pièce). Si la pièce était conviviale, le calcul du coup sera abandonné avec la commande vérifier (la violation des conditions spécifiées dans cette commande met immédiatement fin au calcul du coup en cours).

Dans ZoG et Axiom, on ne peut déplacer que ses propres pièces (ou plutôt, déplacer les pièces de l'adversaire est possible, mais uniquement si cela est spécifié dans le mode de calcul d'un déplacement d'une de ses propres pièces). Je trouve que c'est une restriction extrêmement gênante, car il existe de nombreux jeux dans lesquels vous pouvez déplacer directement la pièce de l'adversaire (dans « Stavropol Checkers », par exemple). Il serait plus cohérent d'effectuer le calcul de déplacement pour toutes les pièces, quelle que soit leur affiliation. Dans la macro qui détermine le mouvement, il suffirait d'ajouter une seule vérification pour permettre de déplacer uniquement ses propres pièces:

 (define slide ( (verify friend?) $1 (while empty? add $1 ) (verify not-friend?) add )) 

Il est important de pouvoir exécuter un mouvement composé de plusieurs mouvements «partiels». Dans les implémentations de brouillons, cette capacité est utilisée pour effectuer des captures «en chaîne»:

 (define checker-jump ($1 (verify enemy?) capture $1 (verify empty?) (if (not-in-zone? promotion-zone) (add-partial jumptype) else (add-partial King jumptype) ) ) ) 

La commande de déplacement partiel est formée avec add-partial (pour cette commande, ainsi que pour la commande add, il y a une variation du déplacement, avec «transformation» des pièces). Un tel mouvement fait toujours partie d'un mouvement plus large et «composite». En règle générale, pour les mouvements ultérieurs, un «mode» est défini, que la suite doit implémenter. Ainsi, dans les dames, une capture ne peut se poursuivre qu'avec les captures suivantes, mais pas avec un mouvement «doux» (sans capture).


Un tel système de description des règles est très flexible, mais une logique parfois plus complexe est nécessaire. Par exemple, si la pièce, lors d'une progression «partielle», ne doit pas repasser à travers un champ précédemment parcouru, il est logique d'utiliser les drapeaux associés aux positions sur la carte. Après avoir visité un espace, nous avons mis un drapeau, donc par la suite de ne plus y retourner:

 (verify (not-position-flag? my-flag)) (set-position-flag my-flag true) 

En plus des indicateurs «positionnels», dans ZoG, vous pouvez utiliser des indicateurs globaux. Ces capacités ne doivent pas être confondues avec les attributs des pièces. Contrairement à ce dernier, ceux-ci ne font pas partie de l'état du jeu. Malheureusement, les attributs des pièces et des drapeaux dans ZoG ne peuvent être que booléens (dans Axiom, les attributs ne sont même pas pris en charge). Cette limitation rend difficile l'exécution d'opérations associées aux différents types de comptage. Par exemple, dans ce petit casse-tête, je devais utiliser pour «compter» des pièces, prises dans une «fourchette», une paire de drapeaux booléens (le nombre exact dont je n'avais pas besoin, tant que les pièces étaient plus d'une).

Une autre chose à corriger est l'absence d'un «cycle de vie» clair dans l'exécution du déménagement. Tous les drapeaux sont automatiquement réinitialisés avant de commencer le déplacement, mais il serait plus facile d'identifier clairement la phase d'initialisation. À mon avis, dans le calcul du déménagement, il devrait se produire les phases suivantes:

1. Initialisation des variables et vérification des conditions préalables au mouvement composite
2. Initialisation des variables et vérification des conditions préalables au déplacement partiel
3. Génération du mouvement partiel
4. Vérification des postconditions du déménagement partiel
5. Génération, achèvement et vérification des postconditions du mouvement composite
6. Vérification des conditions de résiliation du jeu

Le groupe d'étapes de la deuxième à la quatrième, dans le mouvement composite complet, peut être répété plusieurs fois. L'idée de pré- et post-conditions, que j'appelle des invariants, je me suis inspirée du projet Ludi. Je vous en dirai plus sur l'utilisation des invariants plus tard.

Sur l'importance de la notation

La génération de tous les mouvements possibles à partir de la position n'est que la moitié de l'histoire. Pour contrôler l'état du jeu, une présentation compacte des mouvements générés est nécessaire. Dans ZoG, à cet effet, la notation ZSG est utilisée. Voici un compte rendu d'un début possible d'une partie d'échecs sous cette forme:

 1. Pawn e2 - e4 1. Pawn e7 - e5 2. Knight g1 - f3 2. Knight b8 - c6 3. Bishop f1 - c4 3. Knight g8 - f6 4. King e1 - g1 Rook h1 - f1 @ f1 0 0 @ g1 0 0 4. Pawn d7 - d5 5. Pawn e4 x d5 5. Knight f6 x d5 

Ce script est proche de la notation d'échecs habituelle et généralement convivial. Seul le quatrième coup du blanc peut semer la confusion. Donc, dans ZSG, cela ressemble à du roque . La partie de la description du déplacement avant le caractère «@» est assez claire; c'est le mouvement simultané de la tour et du roi, mais qu'est-ce qui suit? Ainsi, dans ZSG, il semble qu'une réinitialisation des attributs des pièces soit nécessaire afin d'éviter la possibilité de roque répétée.


L'enregistrement d'un coup en notation ZSG doit contenir des informations complètes suffisantes pour changer correctement l'état du jeu. Si des informations sur un changement d'attributs sont perdues, dans un jeu selon un tel record, un mouvement pourrait être incorrectement répété (par exemple, le joueur aurait la possibilité de réexécuter le roque). Malheureusement, dans les extensions DLL (comme Axiom), les informations étendues ne peuvent pas être transmises.

En travaillant avec les extensions DLL, ZoG est obligé de faire une manipulation assez astucieuse lors du positionnement sur un mouvement sélectionné (par exemple, lorsque vous annulez un mouvement). À partir de [chaque] position précédente [depuis le début du jeu], tous les coups possibles sont générés, puis, dans cette liste, il faut rechercher un coup avec la représentation ZSG [correspondante]. Les [effets secondaires de chaque] mouvement généré sont appliqués à [chaque état de jeu] successif, car il est possible d'effectuer des effets secondaires non reflétés dans la représentation ZSG du mouvement.

La situation est aggravée par le fait que la seule façon d'accéder à l'état de jeu lors d'un coup dans le passé est l'application cohérente de tous les coups depuis le début de la partie jusqu'à l'état initial du plateau. Dans des cas vraiment complexes , ce type de navigation ne se fait pas rapidement. Un autre inconvénient de la notation ZSG peut être illustré par l'enregistrement du mouvement suivant dans le jeu de Go :

 1. White Stone G19 x A19 x B19 x C19 x D19 x E19 x F19 

Ici, dans la position G19, une pierre blanche est placée qui capture un groupe de pierres noires. Étant donné que toutes les pièces impliquées dans la performance du placement doivent être mentionnées dans la performance ZSG, l'enregistrement du tour peut sembler très long (en Go, une goutte peut capturer jusqu'à 360 pierres). À quoi cela peut conduire, j'ai écrit plus tôt . La taille de la mémoire tampon allouée pour l'enregistrement du mouvement ZoG peut ne pas être suffisante. De plus, si pour une raison quelconque l'ordre de retrait des pierres change (dans le processus de développement du jeu, cela se produit), une tentative d'application d'un mouvement, d'un ancien ordre de captures, échouera.

Heureusement, il existe un moyen simple de résoudre tous ces problèmes. Voyons comment définir les mouvements de pièces dans ZRF:

 (piece (name Pawn) (image White "images\Chess\SHaag\wpawn.bmp" "images\Chess\wpawn.bmp" Black "images\Chess\SHaag\bpawn.bmp" "images\Chess\bpawn.bmp") (moves (Pawn-capture nw) (Pawn-capture ne) (Pawn-move) (En-Passant e) (En-Passant w) ) ) 

Les noms de mouvements, définis dans les macros ZoG, sont inaccessibles en tant que générateur de mouvements. Mais qu'est-ce qui nous empêche de renoncer aux macros et de décrire les mouvements avec leurs noms? Voici à quoi ressemblerait le dossier pour une partie d'échecs:

 1. e2 - e4 Pawn-move 1. e7 - e5 Pawn-move 2. g1 - f3 leap2 n nw 2. b8 - c6 leap2 n ne 3. f1 - c4 slide nw 3. g8 - f6 leap2 n nw 4. e1 - g1 OO 4. d7 - d5 Pawn-move 5. e4 x d5 Pawn-capture nw 5. f6 x d5 leap2 w nw 

Les avantages d'un tel enregistrement ne sont pas évidents, mais il présente un avantage important. Tous les mouvements sont décrits de manière uniforme et ces descriptions ne contiennent rien de plus (les noms des descriptions de mouvements, bien sûr, pourraient être rendus plus «descriptifs»). Dans la description du roque, on a réussi à se débarrasser à la fois des changements d'attributs et de la description du déplacement de la tour (cette description ne dépend plus des détails d'implémentation du déplacement). Une utilité encore plus claire de ces enregistrements existe dans le cas du jeu de Go:

 1. G19 drop-to-empty White Stone 

Et c'est tout! Si les pierres de l'adversaire sont prises conformément aux règles du jeu, il n'est pas nécessaire de toutes les énumérer dans la description du coup. Il suffit d'indiquer l'espace de déplacement initial et final (éventuellement avec un signe à prendre), le nom du mouvement en cours d'exécution et la ligne de paramètres qui lui est passée. Bien sûr, pour effectuer un déplacement selon cette description, pour le décodage, il est nécessaire d'accéder au module de génération de déplacement, mais ZoG le fait!

Une autre possibilité, que l'on devrait prendre en charge, apparaît dans la fonctionnalité des déplacements «partiels». Voici un exemple de « dames russes »:

 1. Checker g3 - f4 1. Checker f6 - g5 2. Checker e3 - d4 2. partial 2 Checker g5 - e3 = XChecker on f4 2. Checker e3 - c5 = XChecker on d4 x d4 x f4 

Ici, les noirs, à leur deuxième coup, prennent deux pièces en d4 et f4. Une «transformation» préliminaire de ces pièces en XChecker est une caractéristique de cette implémentation et sert à empêcher la reprise des pièces «vaincues» du même coup. L'expression «partielle 2» décrit le début d'un cours «composite», qui consiste en deux mouvements «partiels». Cette forme de description n'est pas pratique, car au moment de la génération du premier mouvement, la durée de la séquence de mouvements "partiels" peut ne pas être connue. Voici à quoi ressemblera cette description dans un nouveau format:

 1. g3 - f4 checker-shift nw 1. f6 - g5 checker-shift ne 2. e3 - d4 checker-shift nw 2. + g5 - e3 checker-jump nw 2. + e3 - c5 checker-jump sw 2. + 

Les détails de mise en œuvre liés à la «transformation» des pièces ne sont pas pertinents. La capture des pièces n'est pas non plus spécifiée, car dans les dames, la capture se produit comme un «effet secondaire» du mouvement de la pièce et non selon le «principe des échecs». La progression partielle sera codée avec le symbole «+» au début de la ligne. Un seul «+» indique la fin d'un «coup composite» (en fait, c'est le coup «partiel» habituel, contenant un coup manquant, une chaîne vide).

Ainsi, en utilisant des règles nommées pour l'implémentation des mouvements, on a réussi à créer une notation universelle, satisfaisant pleinement nos exigences. Bien sûr, cela n'a rien à voir avec les échecs standard ou avec toute autre notation, mais il se trouve que la notation conventionnelle des échecs, des dames et d'autres jeux n'a rien à voir entre eux. Le module de visualisation peut toujours convertir l'enregistrement de mouvement en une forme plus familière acceptée pour un jeu particulier. La conversion peut également prendre une forme universelle, comme SGF (Smart Game Format) .

Le cycle de vie du jeu

En plus des informations sur le placement de pièces sur le plateau, la séquence de tours fait partie intégrante de l'état du jeu, une variable dans le processus de jeu. Dans le cas le plus simple (et le plus courant), pour stocker ces informations, un bit suffira, mais ZoG offre quelques opportunités supplémentaires pour implémenter des cas plus complexes. Voici à quoi pourrait ressembler une description d'une séquence de mouvements pour le jeu Splut! :

 (players South West North East) (turn-order South West West repeat North North North East East East South South South West West West ) 

Dans ce jeu, chaque joueur fait trois coups à la fois, mais si vous donniez au premier joueur la possibilité de faire trois coups à partir de la position initiale, il pourrait détruire l'une des pièces de l'adversaire, ce qui lui donnerait un avantage significatif. Pour cette raison, le premier joueur ne doit effectuer qu'un seul coup (cela donne la possibilité de se préparer à attaquer un joueur adverse, mais pas à l'attaquer), le second - deux coups (ce n'est pas non plus suffisant pour attaquer un joueur adverse), après où chaque joueur fait toujours trois coups.


La répétition d'étiquette indique le début d'une séquence cyclique répétitive de mouvements. S'il n'apparaît pas, la description complète est répétée cycliquement. ZoG ne permet pas de répéter l'utilisation de l'étiquette plus d'une fois. Une autre caractéristique importante est la spécification de l'ordre du tour. Voici à quoi pourrait ressembler une description de la séquence de tours d'un jeu dans lequel chaque joueur effectue deux tours (le premier coup - déplacer des pièces, le second - capturer les pièces de l'adversaire):

 (players White Black) (turn-order (White normal-move) (White capture-move) (Black normal-move) (Black capture-move) ) 

Il y a une capacité supplémentaire associée à la description du déplacement des pièces de quelqu'un d'autre, mais il est très gênant à utiliser. Le problème est qu'une telle description n'a pas d'alternative. Si la description indique que le mouvement doit être effectué par une pièce ennemie, le joueur doit effectuer ce mouvement! Dans ZoG, il est impossible de décrire un choix de déplacer sa propre pièce ou celle d'une autre personne. Si une telle capacité est nécessaire dans un jeu (comme dans " Stavropol Checkers "), il est nécessaire de rendre toutes les pièces neutres (créant à cet effet un joueur qui ne participe pas au jeu) et de déterminer pour tous les joueurs l'opportunité pour déplacer une pièce neutre. J'ai dit ci-dessus qu'il est beaucoup plus facile par défaut de permettre à tous les joueurs de déplacer n'importe quelle pièce (la leur ainsi que celle de leur adversaire) en ajoutant les vérifications nécessaires dans les algorithmes de génération de mouvement.

Comme vous pouvez le voir, la gamme d'options fournies par ZoG pour la description de la séquence de virages est extrêmement limitée. Axiom échoue également à ajouter de nouvelles fonctionnalités, car il s'exécute (généralement) sur ZoG. Ludi, à cet égard, est encore plus pauvre. Afin de maximiser l'unification des règles du jeu (nécessaire pour la possibilité d'utiliser des algorithmes génériques), dans ce projet, toutes les capacités descriptives ont été délibérément simplifiées, ce qui a entraîné une élimination de couches entières de jeux.


" Bao Swahili " est un bon exemple d'un jeu avec un cycle de vie complexe. Dans ce jeu, il y a deux phases avec des règles d'exécution de mouvement qui diffèrent considérablement. Au début du jeu, une partie des pierres est "dans la main" "De chaque joueur. Alors qu'il y a encore des pierres" en main ", des pierres sont mises dans les puits, une pierre à la fois. Lorsque les pierres" en main "s'épuisent, la deuxième phase du jeu commence, avec la distribution des insérés On ne peut pas dire que ce jeu ne peut pas être décrit dans ZRF (le langage de description de ZoG), mais en raison des limites de ZoG, cette mise en œuvre serait extrêmement déroutante (ce qui n'est certainement pas le meilleur pour la qualité du travail de l'IA). Voyons à quoi ressemblerait la description d'un tel jeu dans un «monde idéal»:

 (players South North) (turn-order (turn-order (South pi-move) (North pi-move) ) (label phase-ii) (turn-order (South p-ii-move) (North p-ii-move) ) ) 

Ici, chaque liste d'ordre de tour détermine sa séquence répétée de mouvements (en se distinguant par le mode d'exécution du mouvement). Le mot-clé label définit un label vers lequel une transition peut être effectuée lors de la génération du dernier mouvement. Vous remarquerez peut-être que nous partons ici de l'hypothèse implicite qu'une telle transition se produit toujours après le coup du deuxième joueur (sinon cela violerait la séquence des coups). Comment faire la transition vers la phase suivante à un moment arbitraire?

 (players South North) (turn-order (turn-order (South pi-move) (North pi-move) ) (turn-order (labels - phase-ii) (South p-ii-move) (labels phase-ii -) (North p-ii-move) ) ) 

Ici, les étiquettes sont portées dans le corps de la boucle et comprennent deux noms. Les noms d'étiquette dans les listes d'étiquettes apparaissent dans l'ordre de transfert des joueurs dans la liste des joueurs. Le nom utilisé pour la transition est déterminé par le joueur qui a fait le dernier mouvement. S'il s'agissait du Nord, il passera à la première étiquette, sinon, à la seconde. Si aucun des noms des étiquettes n'est utilisé, la position correspondante peut être remplie par un tiret.


Un aspect important dans la gestion des mouvements alternés est la possibilité d'effectuer un tour répété. Dans les jeux de la famille Tables , comme Nard , Backgammon ou Ur , par exemple, la possibilité d'effectuer des tours répétés est un élément important des tactiques de jeu. Dans ZoG, on peut utiliser passer un tour pour émuler cette fonctionnalité, mais cette approche complique considérablement la description du jeu (en particulier avec plus de joueurs). Il serait beaucoup plus logique d'utiliser une étiquette pour répéter un tour:

 (players South North) (turn-order (label repeat) South (label repeat) North ) 

Le jeu ayant sauté sur la répétition de l'étiquette, le joueur jouera à nouveau son tour (l'étiquette la plus proche de la position actuelle dans la liste des tours prendra effet). J'aime l'approche de Perl dans ses définitions implicites. La génération implicite de structures de contrôle peut simplifier considérablement la description du jeu. Dans la mesure où des mouvements répétés peuvent être utilisés dans de nombreux jeux, les étiquettes se répètent, anticiper la répétition possible d'un tour peut être implicite:

 (players South North) (turn-order South North ) 

De plus, puisque la séquence de tours est entièrement cohérente avec l'ordre écrit des joueurs dans la construction des joueurs, vous pouvez générer automatiquement la phrase d'ordre de tour entière:

 (players South North) 

Plus la description est facile à écrire, mieux c'est.

Invariant cassable

La principale chose que je n'aime pas dans ZoG peut être exprimée en un seul mot - échec et mat. À première vue, c'est juste une condition (très courante dans les jeux de la famille des échecs ) liant la fin de la partie à la formation d'un partenaire. Hélas, à y regarder de plus près, la simplicité se révèle trompeuse. L'utilisation de ce mot-clé signifie non seulement l'exécution, après chaque coup, d'une vérification de la fin du jeu, mais impose également au joueur un certain «comportement».


Du Shogi habituel, ce jeu ne diffère que par le nombre de joueurs. Malheureusement, cette différence est suffisante pour rendre incorrect le travail de détermination du mat (et tout ce qui est associé à ce mot «magique»). La vérification de la mise en échec n'est effectuée que par rapport à l'un des joueurs. En conséquence, le roi peut devenir attaqué et être dévoré [par une combinaison de tours d'adversaires même lorsqu'il n'est pas laissé en «échec»]! Que ce ne soit pas optimal se reflétera dans le travail de l'IA.

Si ce problème semble insignifiant, il convient de rappeler que les coalitions se forment généralement dans des parties à quatre joueurs «paire contre paire». Dans le cas de la formation de coalitions, il faut considérer que des pièces amies au roi ne le menacent pas! Ainsi, par exemple, deux rois amis peuvent bien résider sur les espaces voisins du plateau.


Cela devient plus compliqué que jamais si un joueur peut avoir plusieurs rois. Dans " Échecs Tamerlan ", le pion royal se transforme en prince (en fait, un deuxième roi). Si cela se produit, vous ne pouvez gagner qu'en capturant le premier roi (l'un des deux) et en accouplant le second. Dans ce jeu, vous pouvez même obtenir un troisième roi, doublant les dépenses pour la transformation du «pion des pions»! Les capacités expressives de «échec et mat» ne suffisent pas à décrire adéquatement cette situation.

Une autre difficulté peut être le processus même de donner du maté. Ainsi, aux échecs mongols ( Shatar ), le résultat de la tentative d'accouplement dépend de l'ordre dans lequel les pièces exécutent le «contrôle» séquentiel. Le résultat peut s'avérer être soit une victoire ou un match nul (comme un pion par un pion), soit même une défaite (pote de cheval interdit, mais vous pouvez donner un chèque). À cet égard, le shogi japonais est un peu moins exotique. Dans ce jeu, il est interdit de donner un compagnon avec un pion abandonné, mais vous pouvez donner un chèque avec un pion abandonné et donner un compagnon avec un pion déplacé.


Évidemment, il faut séparer la logique de vérification de la fin de partie du test du roi tombé en échec, qui est une règle invariable qui est vérifiée après chaque tour. La violation de la règle rend impossible l'exécution du mouvement (le mouvement est supprimé de la liste des mouvements disponibles). Ainsi, un test (simplifié) pour un roi en échec pourrait ressembler à ceci pour "les échecs de Tamerlan":

 (verify (or (> (count (pieces my? (is-piece? King))) 1) (= (count (pieces my? (is-piece? King) is-attacked?)) 0) ) ) 

Il est important de comprendre que ce test ne doit être effectué que pour ses propres rois (j'ai utilisé le prédicat mon?, Parce que le prédicat ami?, Avec le soutien des coalitions, sera satisfait non seulement pour ses propres pièces, mais aussi pour le morceaux de tous les joueurs amis). Acceptable (et souhaitable, [s'il y a plusieurs rois amis]) est la situation dans laquelle le roi ennemi tombe sous contrôle, après un mouvement, mais par son propre roi. Cette situation devrait être impossible [à moins qu'il y ait plusieurs rois amis]! Après avoir fourni un support pour vérifier ces règles, vérifier la fin du jeu par échec et mat devient trivial. S'il n'y a pas de coups possibles et que le [seul] roi est en échec, la partie est terminée [si ce roi appartient au dernier joueur survivant de l'avant-dernière coalition survivante]:

 (loss-condition (and (= (count moves) 0) (= (count (pieces my? (is-piece? King)) 1) (> (count (pieces my? (is-piece? King) is-attacked?)) 0) ) ) 

La capacité de déterminer les invariants sera utile dans d'autres jeux, comme les dames . La plus grande difficulté dans la mise en œuvre des jeux de cette famille, est liée à la mise en œuvre de la «règle de la majorité». Dans presque tous les jeux de dames, la capture est obligatoire. De plus, dans la plupart des jeux de cette famille, il y a une réalisation caractéristique des «captures de chaîne» en un seul tour. Le vérificateur, après avoir capturé, continue de prendre d'autres pièces, si possible. Dans la plupart des jeux, le joueur doit effectuer des captures de chaîne jusqu'à la fin, mais il existe des exceptions à cette règle, par exemple Fanorona .


En utilisant le mécanisme des mouvements partiels, la mise en œuvre d'une «capture en chaîne» est assez simple. Des difficultés surgissent lorsque, de plus, on impose une condition dans laquelle, de toutes les options possibles, on doit choisir une chaîne dans laquelle un nombre maximal de pièces est capturé. Dans ZoG, cette logique doit être implémentée à partir de zéro au niveau du «hardcoding»:

 (option "maximal captures" true) 

Ce paramètre convient aux « contrôleurs internationaux », mais dans les « contrôleurs italiens », la règle de la majorité est formulée différemment. Dans cette version du jeu, s'il existe plusieurs options pour le même nombre de captures, vous devez sélectionner une option qui capture le plus grand nombre de pions transformés (rois). Les développeurs de ZoG l'ont fourni. Vous entrez le paramètre suivant:

 (option "maximal captures" 2) 

Dans ce cadre, on compte non seulement le nombre de pièces capturées, mais aussi leur type. Malheureusement, tout n'est pas prévisible. Voici comment la «règle de la majorité» est formulée dans les «vieux dames françaises»:

Si par une série de captures il est possible de capturer le même nombre de pions avec un homme simple ou avec un roi, le joueur doit utiliser le roi. Cependant, si le nombre de pions est le même dans les deux cas, mais dans l'un il y a un roi ennemi (ou il y en a plus), le joueur doit choisir cette option, même si la capture se fait ensuite à l'aide du simple pion, et non en utilisant le roi.

Bien sûr, à l'heure actuelle, presque personne ne joue cette version des dames, mais son existence même démontre clairement les lacunes de la mise en œuvre «codée en dur». L'utilisation du mécanisme des invariants permet toutes les options possibles pour la «règle de la majorité» de manière universelle. Pour les « vieux dames françaises », la mise en œuvre serait la suivante:

 (verify (>= capturing-count max-capturing-count) ) (if (> capturing-count max-capturing-count) (let max-capturing-count capturing-count) (let max-capturing-sum capturing-sum) (let max-attacking-value attacking-value) ) (verify (>= capturing-sum max-capturing-sum) ) (if (> capturing-sum max-capturing-sum) (let max-capturing-sum capturing-sum) (let max-attacking-value attacking-value) ) (verify (>= attacking-value max-attacking-value) ) (let max-attacking-value attacking-value) 

Ici, nous supposons que les règles de génération de capture remplissent correctement [les] variables locales suivantes:

• capture-count - nombre total de pièces capturées
• capture-sum - nombre de rois capturés
• attacking-value - valeur de la capture de pièce

À chacune de ces variables est associé un accumulateur de valeurs, stocké dans une variable avec le préfixe max. Les trois contrôles sont exécutés en série. La violation de l'une des conditions de vérification interrompt immédiatement la génération de l'option de tour suivant (la capture n'est pas stockée dans la liste des tours possibles). Les contrôles effectués étant associés à des valeurs variables, il ne suffit pas [de tester uniquement la nouvelle option de capture actuelle]. Chaque test génère une «règle flexible» associée à la capture générée [qui peut réviser la valeur maximale accumulée]. Après chaque modification d'un accumulateur, toutes les règles associées doivent être vérifiées à nouveau [pour chaque option de la liste]. Si l'une des conditions n'est pas respectée pour une option générée précédemment, cette option doit être supprimée de la liste des options de virage possibles.

Conclusion

Ceci est la traduction de mon article de l'année 2014. Depuis, j'ai beaucoup repensé et le projet Dagaz est devenu réalité, mais je n'ai presque rien changé dans le texte. Cet article a été traduit par mon ami Howard McCay et je lui suis reconnaissant pour le travail accompli.