Une capture d'écran de ce même jeu flash vous souhaite toujours la bienvenue sur toox.com/jeux/jeux-de-cartes/coinche
Énoncé du problème et de sa pertinence
Quosh, Belote et Tarot sont des jeux nationaux français. Selon les règles, c'est à peu près comme jouer la préférence dans un jeu fermé, et une paire est jouée pour une paire, donc par combien de pots-de-vin et sur quel atout votre partenaire propose d'annoncer le jeu pendant la négociation, vous pouvez approximativement comprendre quel type de cartes il a. Le jeu est long et l'existence d'une IA capable de mettre fin au jeu en quelque sorte est tout simplement vitale, car l'un des joueurs peut simplement quitter la table en décidant qu'il perd désespérément, et le gagnant veut naturellement le pousser jusqu'au score final du tableau de bord. Dans ce cas, l'IA l'emporte sur le joueur perdu. Mais puisque nous avons l'IA, pourquoi ne pas nous permettre de démarrer le jeu en ennuyant AI-shki sur des espaces vides. Nous avons donc lancé ces grands jeux au grand public et avons rapidement découvert qu'il y avait essentiellement deux options pour la façon dont les Français aiment jouer.Environ la moitié de toutes les tables attendent d'être remplies de personnes vivantes jusqu'à la victoire, et la moitié vient plus bas et commence le jeu contre trois IA, comme dans la capture d'écran ci-dessus.
En principe, puisque le jeu est fermé, les gens sont prêts à pardonner aux robots les erreurs de calcul mineures et les dons alternatifs. Principalement parce que les cartes du robot ne sont pas visibles. "Sous le joueur avec simak", "sous le vistuza avec l'as" et des règles simples similaires que j'ai écartées de notre client français nous ont permis de faire le lanceur minimum acceptable. Il a été nafigché en une semaine juste sur les ifs. Par contre, le jeu se joue "deux pour deux", les points sont comptés pour une paire, et tout naturellement le joueur ne veut pas que son stupide partenaire entre "du deuxième roi", c'est-à-dire, ayant un roi dans ses mains et une autre petite carte, il fait un mouvement vers cette couleur, au lieu de laisser l'adversaire jouer un as, le laisser passer avec une petite carte et faire le prochain coup dans cette couleur avec son roi. (En fait, dans ces jeux, la deuxième carte la plus ancienne est 10,mais ci-après je parlerai en termes russes). Mais si l'as pour une raison quelconque a quitté le jeu et que vous avez une reine et autre chose de petit, alors c'est presque comme le deuxième roi. Surtout si vous précommandez des atouts. Et vous, par exemple, ne jouez pas à la Belote, où 32 cartes sont utilisées, mais au Tarot, dans lequel le jeu se joue avec un jeu de 78 cartes (le même que certains supposent). Et là, dans certains cas, même pas la troisième reine, mais le quatrième valet, peut prendre le pot-de-vin. En général, tout cela donne lieu à un tel nombre de cas extrêmes qu'un mannequin stupide sur les ifs devient en quelque sorte complètement inacceptable. Et à ce stade, j'ai dit: «Bah! J'ai beaucoup lupar exemple, vous ne jouez pas à la Belote, où 32 cartes sont utilisées, mais au Tarot, dans lequel le jeu se joue avec un jeu de 78 cartes (le même que certaines personnes devinent). Et là, dans certains cas, même pas la troisième reine, mais le quatrième valet, peut ramasser le pot-de-vin. En général, tout cela donne lieu à un tel nombre de cas extrêmes qu'un mannequin stupide sur les ifs devient en quelque sorte complètement inacceptable. Et à ce stade, j'ai dit: «Bah! J'ai beaucoup lupar exemple, vous ne jouez pas à la Belote, où 32 cartes sont utilisées, mais au Tarot, dans lequel le jeu se joue avec un jeu de 78 cartes (le même que certaines personnes devinent). Et là, dans certains cas, même pas la troisième reine, mais le quatrième valet, peut prendre le pot-de-vin. En général, tout cela donne lieu à un tel nombre de cas extrêmes qu'un mannequin stupide sur les ifs devient en quelque sorte complètement inacceptable. Et à ce stade, j'ai dit: «Bah! J'ai beaucoup luBref et impressionné! " Ensuite, je me suis enfui du bureau pendant quelques jours, je me suis assis avec un ordinateur portable dans un café et quelques jours plus tard, j'ai engendré quelque chose.
Idées clés
Sur quoi le Prolog est-il fondé de manière déclarative? Sur les faits, par exemple:
('', '').
('', '').et selon des conditions ou des règles, par exemple, si A est la mère B, alors A est une fille:
() :- (, ).Bien sûr, je comprends qu'à notre époque tout n'est pas si simple, et en général c'est même un peu indécent de le dire, mais à l'époque où les gens croyaient à la logique formelle, il n'y avait rien de répréhensible dans de tels exemples. Disons pour la tolérance:
(A, B) :- (A, B).
(, ) :- (, ), (, ).Et puis tu me demandes comme ça:
?- (X, '')Et le Prologue terriblement logique vous répond:
X = ''
X = ''L'idée était que l'utilisateur ne se réchauffe pas la tête avec l'ordre dans lequel et en quelle quantité le système de prologue appliquerait les règles aux faits pour arriver à une réponse. Mais, bien sûr, ce n'est pas si simple. Le prologue est envahi par des béquilles, des ajouts fonctionnels, des couteaux de diverses branches du raisonnement et autres, et s'enfuit toujours régulièrement dans une récursivité infinie.
Dans le livre de ce très inspirant Bratko, un chapitre entier était consacré à la réalisation de la machine à prologue à l'intérieur. En bref, il parcourt l'arborescence de toutes les règles en profondeur, essayant d'appliquer chacune des règles à son tour à l'ensemble de tous les faits et variables connus pour obtenir un nouvel état, et si la règle ne peut pas être appliquée, il revient à l'étape précédente et essaie d'essayer une autre option.
De plus, si vous parvenez à rassembler quelque chose d'utile, la machine prend la liste des règles et commence à chercher les règles à appliquer à l'étape suivante dès le début de la liste. De plus, si une variable est trouvée dans les règles, la machine se souvient de quels états de ces variables, en tenant compte des règles déjà appliquées, peuvent l'être. C'est ce qu'on appelle le développement. S'il peut trouver une instanciation des variables qui rend la question vraie, il imprime cette instanciation. Ensuite, elle peut aller chercher la prochaine concrétisation et ainsi de suite. Dans l'exemple artificiel ci-dessus, le système a trouvé deux concrétisations qui satisfont les conditions.
Je voudrais en quelque sorte formuler de la même manière les règles du jeu, mais bien sûr pas littéralement. Ayant une certaine expérience du débogage de programmes dans Prolog, je n'étais pas du tout impatient de faire face à ce débogage et à ces frais généraux sur mon produit.
Tout d'abord, tout cela ne devrait pas fonctionner sur un tas de faits dispersés, mais sur l'arbre d'état du jeu - un modèle et appliquer les résultats de son travail au même arbre également. Deuxièmement, je veux écrire les règles de sorte qu'une valeur spécifique, une variable et une expression arithmétique puissent être dans la même position, et le système devrait gérer cela de manière appropriée sans poser de questions supplémentaires au programmeur et sans nécessiter de syntaxe supplémentaire. Troisièmement, bien sûr, il est d'une importance vitale d'abandonner la récursivité infinie, mais il reste encore à répéter l'application des règles. Quatrièmement, le système de règles devrait être rédigé dans un format lisible par l'homme très pratique, de sorte qu'à un coup d'œil, ce que l'auteur voulait dire soit clair. Et enfin, cinquièmement,tout cela doit être lié à un outil de journalisation et de débogage pratique afin qu'il soit facile de suivre le raisonnement de ce système et de comprendre pourquoi certaines règles ne fonctionnent pas contrairement aux attentes.
Ceci, bien sûr, n'est pas un solveur universel de logique de prédicat de premier ordre, mais simplement un système déclaratif pratique de règles du jeu. Ce qui dans un sens pratique est également très bon. Pour cela, j'ai trouvé le nom Logrus beaucoup plus tard sur l'un des projets suivants. Je décrirai tout de suite la version finale, en contournant toutes les étapes intermédiaires du développement du moteur.
La syntaxe résultante de la bibliothèque Logrus
Il y aura beaucoup de syntaxe.
1) Au moment de l'exécution, l'arbre de décision est stocké sous la forme de certaines classes, mais la première chose que je lui ai attachée, dès que cela a fonctionné, a été l'importation et l'exportation en JSON. Il s'est avéré que cela est également pratique car si votre structure de données n'a pas beaucoup changé, vous pouvez mettre à jour les règles à partir du fichier sans recompilation. L'écriture sous la forme de JSON s'est avérée si pratique que sur l'un des projets suivants, lorsque les programmeurs étaient pressés, parfois au lieu d'écrire une commande normale, ils le faisaient simplement
state.AplayJSON("...");et dans celui-ci, l'action requise a été insérée sous forme de chaîne JSON. Ceci, bien sûr, n’a pas très bien affecté les performances, mais si ce n’est pas régulièrement et uniquement en réponse aux clics des utilisateurs, alors ce n’est pas effrayant ... Tout le reste, je vais immédiatement illustrer avec JSON. Je reproduis des JSON approximativement de mémoire, car c'était un sacré long moment. Strictement parlant, JSON ne garantit pas l'ordre des nœuds dans l'objet, mais la plupart des bibliothèques le respectent toujours, et ici et ci-dessous l'ordre des nœuds est activement utilisé.
2) La règle est devenue la principale unité structurelle du moteur. Une règle se compose d'une condition et d'une action. Habituellement, les règles se présentaient dans des tableaux et étaient appliquées une par une à chaque fois:
[{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]3) Chaque règle contient une condition - il s'agit d'un modèle d'arbre, contenant éventuellement des variables. Le système recherchera si l'arborescence d'état correspond au modèle pour toutes les valeurs des variables. Et s'il trouve une telle spécification, il déclenchera une action. Par exemple:
{"condition":{
"player":{
"$X":{"gold" : "<20", "name":"$NAME"}
}},
"action":{}}Une telle construction signifiera que pour déclencher une action dans l'arborescence, il doit y avoir un nœud «player» au niveau supérieur dans lequel un ou plusieurs nœuds enfants, dont chacun a des champs «or» avec une valeur inférieure à 20 et «nom». Si une telle condition est remplie, alors l'action sera appelée, et comme entrée, elle sera passée dans la variable X - la clé du nœud, et dans la variable NAME le nom du joueur. S'il existe plusieurs nœuds appropriés et, par conséquent, plusieurs instanciations possibles, alors l'action sera appelée plusieurs fois avec chacune des instanciations trouvées en entrée.
4) Au départ, tout y était un peu moins flexible, mais ensuite Valyard, que beaucoup connaissent grâce à de nombreuses discussions lors de conférences sur Unity, nous a vissés avec un analyseur qui analyse les expressions arithmétiques dans un arbre de décision rapide et la flexibilité s'est finalement épanouie dans une couleur violente.
5) Les noms des variables C $ commencent. Ils peuvent apparaître comme une clé, telle que $ X, puis plusieurs instanciations seront sélectionnées, car une valeur de feuille, telle que $ NAME, peut être insérée dans des expressions arithmétiques: par exemple: {"gold": "<$ X * 10" } Et puis il peut être utilisé pour vérifier les conditions, seuls les joueurs qui ont plus d'or que leur nombre ordinal multiplié par 10 passeront le test, et enfin Ils peuvent être directement calculés dans une expression, par exemple: {"gold": "$ X = 3 + $ this "} où $ this est la valeur du point courant auquel le calcul a été appelé. Passer ce nœud spécifie la valeur de la variable $ X comme 3 + la quantité d'or que possède le joueur. Des possibilitéscela m'est venu à l'esprit n'a pas été implémenté, il n'y en avait qu'un - la variable ne peut pas apparaître d'abord sur le côté droit d'une expression arithmétique, ce sera une erreur, au moment où elle sera utilisée comme argument, elle doit déjà être concrétisée de plusieurs autres manières.
6) Une variable dans une expression peut apparaître autant de fois que vous le souhaitez, tandis que la première mention la spécifie, et les suivantes seront un test d'égalité. Par exemple, une telle construction prendra le premier joueur, vérifiera son argent, puis cherchera un autre joueur dont le premier serait la cible. S'il ne le trouve pas, il reviendra au point de concrétisation X sélectionnera le joueur suivant, vérifiera l'argent, et ainsi de suite jusqu'à ce qu'il passe par toutes les options possibles X et Y. En échangeant les lignes, le programmeur changera l'ordre des vérifications, mais pas le résultat final:
{ "player":{
"$X":{"gold":">20"},
"$Y":{"target":"$X"}
}}7) L'action est également un modèle d'arbre qui peut contenir des variables et des expressions arithmétiques, et l'arborescence d'état du jeu sera modifiée pour correspondre. Par exemple, ce modèle attribuerait le joueur X à un adversaire sous la forme du joueur Y, mais si pour une raison quelconque le joueur Y n'existait pas, il serait créé. Et le joueur "superflu" sera complètement supprimé. Au moment de la création du jeu à partir de la capture d'écran, le signe de suppression était nul, mais je l'ai ensuite remplacé par un mot réservé, au cas où quelqu'un aurait besoin d'insérer une valeur vide par clé. En général, je pense que le principe est clair, et la signification des actions effectuées avec le jeu est fondamentalement la même.
{
"condition":{
"player":{
"$X":{"gold":">20"},
"$Y":{"target":"$X"}}},
"action":{
"$X":{"target":"$Y"},
"superfluous":"@remove"}
}
8) Une action peut également ne pas être un modèle d'arbre, mais un tableau de règles. Chacun d'eux sera vérifié non pas à partir de zéro, mais avec l'instanciation initiale avec laquelle l'action a été appelée. Autrement dit, il peut y avoir tout un groupe de règles, et elles utiliseront toutes la variable X.
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":[
{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]
}9) La règle enfant peut être appliquée non pas à partir de la racine de l'arborescence d'états, mais à partir d'un point atteint pendant l'application de l'action. Dans ce cas, toutes les conditions et toutes les actions utiliseront ce point comme racine. Cela ressemble à ceci:
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":{
"$X":{"@rules":[
{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]}
}10) La répétition de la règle pourrait être spécifiée comme un autre nœud, ceci réalisant, si nécessaire, une récursion de profondeur limitée. Mais dans la pratique, une telle décision n'était généralement pas nécessaire. Il peut également être utilisé pour répéter un tas de règles selon les besoins en le plaçant dans une action:
{
"condition":{},
"action":{},
"repeat":5
}11) L'arbre de règles pouvait être chargé à partir de plusieurs fichiers JSON, leur structure arborescente était simplement superposée les unes aux autres. Il était pratique de diviser les règles en blocs significatifs distincts. Probablement certains Inclure seraient également utiles, maintenant je ne me souviens plus comment cela a été arrangé avec nous.
12) Journalisation! Toute règle pouvait avoir un nœud "@log": true, ce qui a conduit au fait que cette règle a commencé à chier en détail dans le journal décrivant le processus de solution. Quelles concrétisations nous essayons, quelles branches du raisonnement sont supprimées et pourquoi. La journalisation était hiérarchique, c'est-à-dire qu'une règle imbriquée pouvait être "@log": false et tout ce qui s'y passe et en dessous ne sera pas journalisé. Idéalement, j'aimerais que ce nœud puisse être laissé n'importe où dans l'arbre des conditions afin de ne regarder que ce qui se passe à un niveau du modèle, mais je ne semble pas avoir terminé une telle extension. Peut-être que le débogage s'est bien passé sans cela, il a donc été reporté à «un jour».
13) Dactylographie. Le jouet était si vieux que certains des programmeurs d'aujourd'hui n'étaient même pas nés. Il a été écrit en ActionScript2, avec un typage dynamique et un héritage via des prototypes disponibles directement au moment de l'exécution. Parmi les langages modernes entendus, seul Python fonctionne de cette façon. Cependant, lier à cette idée n'est pas particulièrement difficile. Je le ferais en utilisant le symbole de clé ':' comme ceci: "$ X: int" mais cela peut être délicat si la première occurrence de la variable n'avait aucun du type spécifié. Et en plus, il peut y avoir confusion avec l'opérateur ternaire.
Comme on dit, c'était lisse sur le papier, mais l'utilisation pratique nécessitait un certain nombre de béquilles différentes. Voici ceux dont je me souviens:
14) Un seul et même nœud pourrait être vérifié non pas par un, mais par plusieurs conditions. Par exemple, une telle condition vérifiait d'abord qu'il y avait plus de 20 monnaie, puis spécifiait la variable dans laquelle cette somme était représentée. Le symbole de service '@' s'il n'est pas au début de la ligne signifiait une rentrée dans le nœud, l'identifiant de rentrée allant plus loin n'était en aucun cas utile. Peut-être qu'un symbole de service a été utilisé et un autre, mais rien, à mon avis, ne vous empêche d'utiliser celui-ci:
{
"player":{
"$X":{"gold":"<20", "gold@cnt":"$COUNT"}
}
}15) Il a fallu des opérations arithmétiques qui pouvaient être effectuées sans utiliser aucun nœud du tout. Selon la tradition du prologue, ils ont été désignés `` _ '' et il peut y en avoir beaucoup:
{
"_":"$SUM=$A+$B",
"_@check":"@SUM <20"
}16) Puisqu'il y a une passe de vérification dans l'arbre, il a également fallu une descente vers le bas via le mot-clé "@parent". Ceci, bien sûr, n’a pas amélioré la lisibilité, mais cela ne fonctionnait pas sans cela. Ici, bien sûr, un analogue de la fonction path se suggère directement, qui redirigerait vers l'endroit spécifié dans l'arbre, mais je ne me souviens pas si j'ai réussi à l'implémenter à la fin ou non:
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":{
"$X":{"rules":[
{
"condition":{
"@parent":{"@parent":{"…":"…"}}
}
]},
}
}17) L'action a maintenant la capacité d'extraire directement une méthode de classe. C'est un tel coup de pied dans l'estomac de la lisibilité, et je préférerais une sorte d'analogue de #include, mais tel quel, vous ne pouvez pas jeter les mots de la chanson. Je me demande si je peux me passer de cela en pratique si je réanime la bibliothèque maintenant en C #?
18) La règle dispose désormais d'un paramètre supplémentaire pour répéter l'action non pas pour toutes les concrétions trouvées, mais uniquement pour la première. Je ne me souviens plus comment cela s'appelait, mais pour une raison quelconque, cette béquille était utile pour certaines règles.
Résultats d'utilisation
Dès que la bibliothèque a commencé à être activement utilisée, tous les AI-shki y ont été rapidement transférés, ce qui a permis d'avoir une IA deux fois plus intelligente tout en dépensant trois fois moins de ressources de programmation. Le fait que les données intermédiaires de l'échelle AI aient été stockées directement dans l'arbre a beaucoup aidé. En particulier, les règles elles-mêmes écrivaient des informations sur les cartes de chaque couleur qui avaient quitté le jeu directement dans l'arbre d'état du jeu.
Déjà dans le prochain projet, vérifier les règles du jeu et faire des mouvements possibles de chaque position déplacée vers le même moteur. Et en général, non seulement pour le prototypage rapide, mais aussi pour les jeux dans lesquels il existe simplement de nombreuses règles, ce serait une chose très utile. En fin de compte, les JSON téléchargeables avec logique peuvent remplacer la moitié de ce que les programmeurs font avec du code et gagner en flexibilité.
Bien sûr, en termes de vitesse d'exécution, tout cela était nettement inférieur au désordre des ifs, en particulier dans la mise en œuvre sur AS2 avec ses prototypes et ses objets dynamiques, mais pas au point qu'il ne puisse pas être déployé en production.
L'étape suivante consistait à transférer la vérification des règles et à déterminer l'action de l'IA sur l'ordinateur client. Pour que les joueurs se vérifient. Et j'ai même proposé un tel algorithme pour faire cela malgré le fait que les valeurs des cartes ennemies ne nous soient pas connues, mais c'était une histoire complètement différente.
De nombreuses années ont passé, j'ai changé d'emploi une dizaine de fois, et chaque fois que j'ai mis à jour mon CV, je suis allé sur toox.com et j'ai été surpris de trouver mon emploi toujours en service. Je me suis même arrêté pour jouer à un autre match. Et une fois à Belot, je suis tombé par hasard sur un jeu de cartes donnant le maximum de points possible. La probabilité d'obtenir un tel ensemble est de un sur trois millions.
Un jour, je rassemblerai ma volonté dans une poignée et ferai un remake moderne de Logrus pour C # et Unity3d, par exemple, pour le stratège hexagonal dont je rêve. Mais ce ne sera pas aujourd'hui, je vais me coucher aujourd'hui. Le devoir de diffuser des idées qui valent la peine d'être diffusées a été rempli avec succès.
En conclusion, quelques anecdotes
Nous étions situés dans le Novosibirsk Academgorodok. Nous avons loué un bureau à l'institut. Et le client est français, totalement méconnu des coutumes locales. Et ainsi, au troisième ou quatrième mois de travail en commun, il vient nous rendre visite, faire connaissance. Je suis arrivé le week-end à l'hôtel local "Zolotaya Dolina" et le lundi, dit-il au directeur, retrouvons-moi dans un taxi à dix heures du matin, nous irons avec les programmeurs pour faire connaissance. Et prenez Vovchik et venez à 10. En général, ils conduisent à l'institut, frappent à la porte, et de l'autre côté vient la grand-mère du gardien et les regarde complètement sans comprendre derrière la porte verrouillée. À une date aussi précoce, aucun scientifique ou programmeur ne louait de bureaux dans le bâtiment. Ils l'ont littéralement réveillée.
Et voici un autre cas. D'une manière ou d'une autre, notre Sebastian Pereira appelle le directeur et dit qu'ils ont miraculeusement réussi à s'introduire à la télévision et que nous serons bientôt montrés à la télévision avec notre site Web. Après environ 8 heures. Alors, que faites-vous là-bas pour que cela fonctionne de manière plus fiable ... Au compteur le 2 janvier ... Peu importe l'heure ... Et donc Vovchik prend un taxi, commence à rassembler les programmeurs dans les dortoirs et les appartements, complètement en état de charbon, et les emmène au bureau. Ce jour-là, j'ai vu notre administrateur système pour la première fois de ma vie. Jusque-là, il faisait tout exclusivement à distance. Et donc nous avons tordu chacun qui pouvait. En particulier, j'ai cassé tout ce système en remettant un tas de ifs à sa place et nous y voilà, en regardant le graphique de fréquentation et tout à coup nous voyons comment cela commence à augmenter. Quelque part à la marque x15, le serveur s'est écrasé. Mais l'administrateur a dit que tout allait bien, est tombé doucement,maintenant il se lèvera. Le serveur s'est écrasé trois fois de plus ce jour-là.