Dagaz: Hors du brouillard

Tout cela est la reine du Queen Mab.
Elle tisse dans les écuries d'une crinière
Et les cheveux font tomber un enchevêtrement ...

William Shakespeare

Ce fut une longue sortie , mais beaucoup a été fait. Un gestionnaire de session est apparu , vous permettant d'annuler les mouvements effectués par erreur. À certains endroits, la conception sonore a été ajoutée. Et pourtant, j'ai trouvé un moyen cool de proposer plusieurs options alternatives pour le placement initial dans un jeu. Et le plus important - je suis finalement arrivé aux jeux avec des informations incomplètes.

Je vais vous expliquer ce qui est en jeu. Dans les jeux de société habituels, tels que les échecs ou les dames , les joueurs, à tout moment du jeu, ont des informations complètes sur l'emplacement des pièces (les leurs et celles de l'adversaire), les règles de déplacement, les objectifs du jeu, etc. Ces jeux sont assez bien étudiés et entrent dans la catégorie des " jeux avec informations complètes ". Maintenant, imaginez que certaines de ces informations puissent être cachées au lecteur.


Le brouillard de guerre est une excellente illustration du thème. Selon les règles de " Blind Chess ", les joueurs ne peuvent pas voir toutes les pièces de l'ennemi, mais seulement celles qui sont placées sur les champs, qui peuvent être atteintes en un seul mouvement de l'une de leurs pièces. J'ai fait deux ajouts à cette règle:

1. Bien sûr, le joueur voit toujours ses pièces, mais par la façon dont elles sont affichées - sous forme normale ou translucide, il peut juger si l'adversaire les voit.
2. À des fins décoratives uniquement, j'ai placé des «nuages» sur des zones actuellement invisibles.

Ayant maîtrisé le principe général, je me suis un peu emporté et j'ai fait un très grand nombre de jeux avec le "brouillard de guerre". En plus des échecs , j'ai des options «sombres» pour Xiang , Changi , Shatrange , Sittuyin et bien d'autres jeux. Il y a même un " Blind Guns "! Tous ces jeux ont une chose en commun:


Cependant, en général, ce n'est pas une approche très correcte. Je veux voir un bot qui peut faire exactement avec les données de son adversaire - l'homme. Pourquoi est-ce important? Tout est très simple - par la façon dont le bot joue, il est parfois très facile de deviner s'il a accès à des informations cachées (peeps) ou non. Et bien sûr, il est beaucoup plus intéressant pour une personne de jouer avec ce bot qui ne lorgne pas (jouer avec une autre personne est encore plus intéressant, mais c'est une autre histoire).

Et ici, cela vaut la peine de choisir un jeu légèrement différent des échecs (puisque je ne suis pas prêt à développer un bot "honnête" jouant aux échecs "à l'aveugle"). Il y a beaucoup de ces jeux et on ne peut pas dire qu'ils sont plus simples que les échecs ou les dames. Ils sont juste différents et nécessitent une approche individuelle.


Pour commencer, j'ai décidé de m'attarder sur BanQi - Chinese Blind Chess. Il s'agit d'un jeu très original avec des informations cachées, semblable à la "Jungle". Il est important pour moi que les développements, liés à la création d'un bot pour ce jeu, puissent être utilisés dans d'autres jeux, comme Dou Shou Qi , Luzhan Qi , Stratego ou même (éventuellement) Tafl .


Je vais vous parler des règles. Le jeu se déroule sur la moitié du plateau pour "Chinese Chess" ( Xiang Qi ), tandis que la disposition d'origine du plateau ne joue aucun rôle. Les pièces sont placées à l'intérieur des cellules (comme dans les cellules traditionnelles), et non aux intersections des lignes (comme dans les échecs chinois). Au début du jeu, toutes les pièces sont soigneusement mélangées et placées face cachée sur le plateau (puisque les pièces traditionnelles de Syants sont une sorte de barils, et leur nombre coïncide avec le nombre de champs sur la moitié du plateau, il n'y a aucune difficulté).

Ensuite, les joueurs alternent leurs mouvements. En effectuant un mouvement, le joueur peut retourner n'importe laquelle des pièces fermées ou déplacer une pièce précédemment ouverte de sa couleur. Les couleurs des joueurs sont déterminées par le tout premier mouvement. Si la première pièce noire est ouverte, le joueur qui l'a ouverte jouera noir. Toutes les figures du jeu vont de la même manière (à l'exception du «canon» dans la version taïwanaise, dont je parlerai plus tard) - sur une cellule adjacente verticalement ou horizontalement. La possibilité de prendre est déterminée par l'ordre d'ancienneté des chiffres:

Général> Conseiller> Éléphant> Wagon> Cheval> Canon> Soldat

Les personnages plus âgés les battent plus jeunes ou égaux, à une exception près: un soldat frappe le général (une sorte de " Rock-Paper-Scissors "). Reste à dire quelques mots sur le BanQi taïwanais:

1. Contrairement à la version chinoise, à Taiwan BanQi, un général ne peut pas battre un soldat.
2. Le pistolet se déplace selon les règles de XiangQi , c'est-à-dire vers n'importe quel nombre de champs le long de la basse vitesse orthogonale (comme un char) ou frappe n'importe quelle figure ennemie, avec un saut à travers le "chariot", lors d'un mouvement d'attaque.

Il existe également une version hongkongaise, mais elle n'est pratiquement pas différente de la version chinoise, sauf que l'ordre d'ancienneté des chiffres a été modifié. J'ai décidé de me concentrer sur la version taiwanaise des règles, la plus intéressante tactiquement.


Tout d'abord, il est important de comprendre qu'il est peu probable qu'il puisse utiliser efficacement les algorithmes minimax ici. Les mouvements qui révèlent des pièces précédemment cachées changent trop radicalement l'estimation de la position. N'ayant aucune information sur les pièces cachées, il est presque impossible de visualiser une position que de nombreux mouvements avancent. Mais chaque nuage a une doublure argentée, mais nous pouvons utiliser des heuristiques beaucoup plus complexes (en termes de calcul) pour évaluer les mouvements eux-mêmes!

J'ai déjà un bot qui évalue les mouvements par leur heuristique (nécessaire pour un jeu amusant). Il s'agit d'un algorithme très simple. Tous les mouvements sont triés par ordre décroissant par heuristique (les mouvements avec une valeur heuristique négative sont généralement rejetés), après quoi ils sont analysés dans l'ordre. Si le coup suivant mène à une position à partir de laquelle aucune réponse ennemie ne mène à une victoire immédiate, le bot la considère comme la meilleure. En utilisant cet algorithme, vous ne pouvez pas vous embêter avec l'estimation de position, mais vous devez transpirer sur l' heuristique .


Bien sûr, je cache toutes les données intermédiaires dans l'état du jeu, afin de ne pas les lire plusieurs fois. De plus, une astuce est utilisée ici, ce qui est très utile pour calculer les zones connectées. J'itère le tableau de groupe , en y ajoutant des éléments supplémentaires dans la boucle, selon les besoins. Toutes les difficultés sont liées aux armes à feu. Pour eux, les buts des chaînes ne sont pas les figures elles-mêmes, mais les champs à partir desquels ces dernières peuvent être attaquées.


... en fonction de la longueur et de la parité de la chaîne, ainsi que de la prise en compte des coûts des personnages attaquants et attaqués. Mais ce n'est que la moitié de la bataille! Il est nécessaire d'évaluer chacun des mouvements possibles à l'aide des chaînes construites. J'introduis une autre structure intermédiaire - souhaite agréger les données disponibles. L'évaluation du cours consiste en des évaluations de souhaits, qu'il satisfait:


Quant à la fonction getWish elle - même , la magie commence ici (et c'est l'endroit où j'ai probablement labouré plus d'une fois). Tout d'abord, je partage l'évaluation des mouvements basée sur des informations ouvertes et l'introduction de nouvelles pièces dans le jeu. Ce n'est pas tout à fait exact, mais jusqu'à présent, je ne sais tout simplement pas comment concilier des opinions aussi diverses. Si sur la base d'informations ouvertes aucun souhait n'a été formé, le bot essaie d'ouvrir de nouvelles figures (il y a aussi quelques astuces ici).

1. Si un canon ennemi est ouvert, entouré de figurines fermées, il est logique d'ouvrir l'une des figurines à côté de lui, car il est probable qu'il sera en mesure d'attaquer le canon, et le canon ne pourra en aucun cas le battre.
2. Si une figurine autre qu'un canon est ouverte, vous pouvez essayer d'ouvrir une figurine située à travers le "chariot", car il y a une chance que ce soit un canon.
3. S'il y a une chaîne attaquante du côté de l'ennemi, une des pièces peut être ouverte, à côté de la chaîne, pour intercepter l'attaque.
4. Si vous ne pouvez pas protéger la figure, vous pouvez ouvrir la figure à côté de lui, en essayant de réduire la situation à un échange.

Le joueur peut évaluer les probabilités en gardant une trace des chiffres qui ont abandonné le jeu. En principe, le bot peut faire la même chose, mais il existe un moyen plus simple - d'examiner les chiffres encore non ouverts en vrac et d'évaluer la probabilité d'ouvrir celui souhaité en fonction des informations collectées. De plus, le succès du mouvement sélectionné n'est pas garanti, mais si la probabilité d'un résultat favorable est faible, le mouvement ne sera pas sélectionné du tout.


Et pour ceux qui me lisent encore, je peux offrir un autre jeu de puzzle amusant avec des informations cachées:


Je l'ai joué dans mon enfance, sur une calculatrice programmable appelée Fox Hunt. Huit renards sont cachés au hasard sur le terrain, qui doivent être trouvés à l'aide de la «méthode poke». Lorsque vous sélectionnez une zone vide, le nombre total de renards dans les huit directions s'affiche. Il est impossible de perdre, mais vous pouvez rivaliser pour le nombre minimum de clics. Et si vous jouez avec des écouteurs, baissez le son. Je l'ai peut-être exagéré avec des effets sonores.