Nous avons secoué vos filtres mentaux et le résultat a été une réponse. La méthode a fonctionné, elle sera toujours efficace. Il suffit de se débarrasser du fardeau supplémentaire des préjugés ...
Raymond Jones " Niveau de bruit "Dagaz n'est pas apparu de toutes pièces. J'ai toujours aimé les jeux de société et les puzzles, et je fais de la programmation autant que je me souvienne, mais l'idée d'un certain moteur «universel» n'aurait tout simplement pas pu me traverser l'esprit. J'étais sceptique quant à cette idée. Jusqu'à ce que je voie
Zillions . Malheureusement, le produit, à cette époque, ne se développait plus, le code source n'était pas disponible et, en effet, le programme ne fonctionnait que sous Windows. Après un certain temps, j'ai décidé de me lancer dans un projet ouvert.
Comme je l'ai déjà dit, je n'avais pas de code source, mais j'ai un peu
touché Zillions et j'ai pris son idée principale - la réutilisation maximale du code d'application, qui permet d'utiliser les mêmes constructions dans différentes, qui sembleraient complètement différentes les unes des autres cas. Il s'agissait du bon cas d'utilisation. Et j'ai fait un
plan .
Dames
Cette famille de jeux importante mais extrêmement sous-estimée a posé la première pierre du projet. Tous les jeux de "dames" sont similaires les uns aux autres et ne diffèrent que par les détails. En termes de conception de jeux, ils sont tous unis par trois idées principales:
- Par chèque
- Prise prioritaire
- Mouvement composé
Le premier paragraphe ne soulève pas de questions particulières, mais si le développement est axé sur les parties d'échecs, cela peut surprendre. Pas dans tous les jeux, la capture a lieu sur le même terrain où la pièce complète le mouvement. Avec les mouvements prioritaires, les choses sont un peu plus intéressantes. Dans les dames, cette règle vous permet de construire un jeu combinatoire complexe, attirant l'ennemi dans des pièges fonctionnant sur le principe de «donner moins - ramasser plus».
Bien sûr, le mécanisme des mouvements prioritaires a été implémenté dans Zillions (et a migré de là vers Dagaz). Sans cela, presque tous les jeux de dames (certainement inclus dans le "gentleman's set" de jeux de société obligatoires pour la mise en œuvre) ne pourraient tout simplement pas fonctionner correctement. Tout est dans les détails. Voyons comment ce mécanisme a été implémenté:
En zillions(move-priorities jump-type normal-type) ... (define checker-shift ( $1 (verify empty?)
Ceci est une description presque complète du jeu de vérification le plus simple. Le concept de modes de déplacement (
type de déplacement ) est introduit dans
ZRF , et la
construction des priorités de déplacement nous permet de dire que s'il y a des déplacements de priorité plus élevée (prises), moins de priorité (mouvements silencieux) ne devrait pas être considérée. Les niveaux de priorité peuvent être définis et plus de deux, à cet égard, la conception est assez universelle, mais en travaillant sur les jeux dans Dagaz, je suis tombé sur certaines limites de ce mécanisme.
Dans ce
jeu , inventé par Solomon Golomb, en plus des dames, il y a aussi des pièces d'échecs. La difficulté réside dans le fait que la prise, tout en restant une priorité pour les pions, n'est pas telle pour les pièces d'échecs (sinon il serait trop facile de les piéger et de les manger). Une priorisation naïve utilisant le mot
- clé
move-priorités ne fonctionnera pas dans ce jeu.
En fait, si les pièces d'échecs ne sont pas incluses dans les coups prioritaires, s'il y a la possibilité de prendre à la fois une pièce de damier et une pièce d'échecs, nous ne pourrons pas jouer une pièce d'échecs, car une capture de chèque est une priorité. Si les mouvements d'échecs sont considérés comme tout aussi prioritaires, nous serons obligés de prendre des pièces d'échecs chaque fois que l'occasion se présentera. Les deux contredisent les règles du jeu.
Dans Zillions, ce problème n'est pratiquement pas résolu. Et c'est la principale raison pour laquelle j'ai pensé à introduire un mécanisme d'extension JavaScript dans Dagaz. L'idée, en soi, est assez simple: comme certaines mécaniques de jeu sont assez difficiles à exprimer en ZRF, pourquoi ne pas introduire la phase de post-traitement des mouvements? Le module d'extension, dans ce cas, analyse l'intégralité de la liste des mouvements générés et peut prendre des décisions sur le rejet de certains mouvements. Voici à quoi cela
ressemble pour
Shashmat :
Code simple et compact var CheckInvariants = Dagaz.Model.CheckInvariants; Dagaz.Model.CheckInvariants = function(board) { var design = Dagaz.Model.design; var types = []; types.push(design.getPieceType("Bishop")); types.push(design.getPieceType("Camel")); var isPriority = false; _.each(board.moves, function(move) { if (isCapturing(board, move)) { if (_.indexOf(types, getType(board, move)) < 0) isPriority = true; } }); if (isPriority) { _.each(board.moves, function(move) { if (!isCapturing(board, move)) { move.failed = true; } }); } CheckInvariants(board); }
À l'avenir, l'idée d'extensions s'est développée et s'est épanouie avec une couleur magnifique. J'ai obtenu un mécanisme pratique et puissant pour coder de nombreux jeux dont la mise en œuvre sur du ZRF pur serait extrêmement problématique, mais cela signifie-t-il que la priorisation dans le style ZRF est obsolète? Bien sûr que non! Tout d'abord, écrire une ligne en ZRF est plus facile que cinquante en JavaScript, mais plus important encore, les priorités de style ZRF «dures» fonctionnent de telle manière que les mouvements de faible priorité ne sont même pas générés! C'est important en termes de performances. Générer des déménagements à Dagaz est une opération très coûteuse.
Un autre jeu avec des priorités difficilesDablot est un jeu quelque peu similaire aux
brouillons italiens , mais plus ancien. En plus des personnages ordinaires, il y a des «princes» et des «rois», et les plus jeunes n'ont pas le droit de battre les anciens. Mais ce n'est pas la difficulté. Pour les rois (et dans certaines variétés du jeu pour les princes aussi), la capture est facultative! Ici, le même problème se pose qu'avec
Shashmat . Si nous déclarons que le roi est une priorité, nous violons gravement les règles du jeu, sinon, nous ne pourrons pas battre le roi avec la possibilité d'une bataille alternative avec une simple figure. Seul le moteur d'extension Dagaz résout ce problème.
Au fait, avec "Italian Drafts", tout n'est pas si simple. Dans de nombreuses variétés de brouillons, une règle stipule que le joueur est obligé de prendre le maximum de pièces. Autrement dit, il ne peut pas simplement interrompre la chaîne de captures, mais doit choisir le chemin sur lequel il prendra plus de pièces! Pour des raisons que j'examinerai ci-dessous, cette règle n'a pas pu être implémentée dans Zillions sous une forme universelle et les développeurs ont été obligés de la coder en dur. Dans les brouillons italiens, la "règle de la majorité" semble encore plus compliquée: "vous devez battre le plus grand nombre possible de brouillons de l'adversaire, et avec des options de combat égales, vous devez battre le nombre maximal de dames".
Les mouvements composés sont le deuxième élément important des jeux de dames. Tellement important que le
test pour la capture correcte dans les "
Brouillons turcs " que je lance périodiquement jusqu'à présent. À quelques reprises, lorsque j'ai cassé le modèle avec les changements suivants, cela a vraiment aidé.
Déménagements - composite et partielVoyons comment les mouvements composites sont implémentés dans ZRF (define checker-shift ( $1 (verify empty?) (if (in-zone? promotion) (add King) else add ) )) (define checker-jump ( $1 (verify enemy?) capture $1 (verify empty?) (if (in-zone? promotion) (add King) else (add-partial jump-type) ) )) (define king-shift ( $1 (verify empty?) add )) (define king-jump ( $1 (verify enemy?) capture $1 (verify empty?) (add-partial jump-type) ))
C'est aussi simple que cela. La commande
add-partial indique que le mouvement peut être poursuivi (avec la même pièce, c'est important) s'il y a encore des mouvements avec le mode spécifié. En d'autres termes: "le chiffre doit continuer à prendre, alors qu'il existe une telle opportunité". Tout semble aller bien, mais il y a une mise en garde. Zillions voit chacune de ces prises comme un mouvement «partiel» distinct. Voyons à quoi cela peut conduire.
Dans ce
jeu , le nombre de "pas" effectués par une pièce est déterminé par l'icône sur laquelle elle se trouve. Maintenant, le mouvement de White et Damyo marche (un morceau marqué d'une perle rouge). Dans Zillions, après avoir effectué deux mouvements partiels, elle peut facilement aller dans le coin supérieur gauche, d'où elle ne peut plus effectuer le dernier mouvement restant (vous ne pouvez pas revenir en arrière). Il est également interdit de prendre la pièce adverse dans le deuxième coup partiel. Dans Zillions, il n'y a aucun moyen d'interdire la séquence de mouvements menant à une impasse.
Chez Dagaz, c'est différent! Une séquence de mouvements partiels est
toujours assemblée en un mouvement composite complet. Un mouvement qui ne peut pas être accompli ne se produira tout simplement pas! Il s'agit d'une approche plus gourmande en ressources et, par conséquent, générer une liste de déplacements dans Dagaz est une opération très coûteuse. Mais ses avantages sont importants. Par exemple, le bot reçoit le mouvement composé entier dans son intégralité et ne doit pas regarder vers l'avant, effectuant les mouvements partiels restants.
Plus important encore, cette approche offre la possibilité de considérer la liste complète des mouvements conditionnellement acceptables, d'effectuer des vérifications plus complexes et d'interdire certains mouvements en fonction de la présence d'autres. Par exemple, la «règle de la majorité», que j'ai mentionnée ci-dessus, dans Dagaz est mise en œuvre tout
simplement . De plus, pour les "Italian Checkers" aussi. Les développeurs de Zillions ont "résolu" le problème qu'ils connaissaient pour les jeux de dames en codant en dur l'option "
captures maximales ", mais il existe un grand nombre de jeux avec d'autres vérifications complexes, qu'ils n'avaient à l'époque aucune idée!
Dans le processus de travail sur de nouveaux jeux, le concept d'un mouvement composé a également été développé.
Fanorona et
Pasang ont suggéré une mécanique de jeu intéressante, dans laquelle un groupe de pièces retirées du plateau devrait être sélectionné par le joueur effectuant le mouvement:
De plus,
Fanorona est l'un de ces rares jeux dans lesquels un joueur a le droit d'interrompre la chaîne de captures. La première capture est obligatoire, la suivante, dans le même mouvement - à la discrétion du joueur. Dans Dagaz, cette option (
passe-partielle ) est implémentée en déplaçant la figure en place. Missclick peut être ici, et cela n'est apparemment pas très pratique, mais avec l'introduction du
gestionnaire de session , les mouvements erronés peuvent maintenant être annulés.
Un autre développement du sujet a été les mouvements de "tir". Je les ai d'abord faites à
Hanga Roa et
Ko Shogi , mais comme il s'est avéré plus tard, je me suis trompé! L'implémentation erronée n'a pas fonctionné sous le contrôle des bots (et comme je n'ai toujours pas de bots pour ces deux jeux, il n'est pas surprenant que je n'ai rien remarqué). Beaucoup plus tard, quand j'ai fait des
Amazones , j'ai réussi à localiser le problème et à le résoudre. Cette idée a atteint son apogée dans un
jeu inventé par l'un de nos compatriotes en 1957.
Il existe un autre problème lié à l'implémentation de mouvements composites à Dagaz. Le fait est que la liste des mouvements autorisés, à partir d'un état de jeu spécifique, est formée immédiatement - le tout. Dans Zillions, avec ses mouvements partiels, ce n'est pas très critique, mais à Dagaz, si la pièce a la possibilité de «tourner en place», la phase de génération du mouvement ne sera jamais terminée (il est évident qu'il est impossible de résoudre ce problème avec les extensions, car il est facile de les gérer n'atteint pas). Voici l'un des jeux pour lesquels cela est important:
Ici, les pièces ne sont pas retirées du plateau et la même pièce peut être sautée plusieurs fois de suite. La solution évidente est d'interdire de visiter le même champ deux fois par tour, mais j'ai dû pénétrer à fond dans le noyau pour implémenter une telle vérification. Cela ressemblait un peu à la mise en œuvre de l'option de «
capture différée », mais comme j'ai fait
des brouillons russes beaucoup plus tôt, cela posait beaucoup moins de problèmes.
Malheureusement, il existe des jeux dans lesquels même de tels chèques ne sont pas enregistrésLes règles du
Stapeldammen (il s'agit d'une sorte de «
piliers » stipule explicitement que la même pièce peut être touchée plusieurs fois par tour. La pièce effectuant le mouvement revient plusieurs fois à la même position et continue la bataille, tandis qu'en ennemi il y a des chiffres dans les colonnes. Les mouvements composés de Dagaz ne peuvent pas faire face à ce problème. La logique de la bataille des pôles est trop compliquée pour le noyau, et elle n'atteindra pas les extensions, car la génération de la boucle est bouclée. Bien sûr, il existe une issue:
Il n'y a pas de mouvements partiels dans Dagaz, mais nous pouvons les émuler en sautant le prochain mouvement de l'adversaire (la même approche est utilisée dans les
décalcomanies ). Et juste cette logique est facilement implémentée par l'
extension . Nous interdisons simplement tous les mouvements sous certaines conditions, et l'option
pass-turn = forcé génère automatiquement un mouvement vide. Voici un autre
jeu avec une émulation similaire.
Diviser artificiellement les mouvements composites en mouvements partiels n'est pas très bon pour les robots IA, mais parfois, il n'y a tout simplement pas d'autre issue.
En général, le concept de composé fait bouger des vies et se développe. Plus récemment, j'ai dû faire une autre nouvelle option (
complète-partielle ) pour un ancien
jeu égyptien.
En plus de compléter automatiquement le mouvement des figures le long des flèches, il a également d'autres solutions techniques intéressantes. Mais à ce sujet une autre fois.