Journal Sortie de Bim! en version 16, avec des bots

Sommaire

• Animations des flammes et des caisses
• Somme de contrôle de l'état du jeu
  • Tentative d’implémentation avec les instructions dédiées
  • Implémentation de la vérification de sommes de contrôle
• Système de karma
• Introduction des bots
  • Ce que le bot voit
  • Ce que le bot veut faire.
• La triste parenthèse LLM
• Statistiques
• Pistes pour la suite

Cher journal,

J'espère que tu vas bien. J'ai sorti deux versions de Bim! depuis le dernier journal, pleines d'améliorations que je vais te présenter ici. Au programme : de nouvelles animations, une détection de désynchronisation qui ne s'est pas passée comme prévu, un système de karma, des bots, et comme d'habitude des stats au sujet du jeu et des joueurs.

Pour rappel, Bim! est un jeu libre (code AGPL3 et assets CC-by-sa 4.0) multijoueur de type dernier survivant, et qui se joue uniquement en ligne. Il n’est disponible que pour les systèmes Android.

En plus du PlayStore, le jeu est disponible sur GitHub, F-Droid, et d’autres magasins alternatifs.

Animations des flammes et des caisses

J'ai ajouté quelques animations des éléments de jeu dans la version 15, à commencer par les flammes produites par les bombes :

Comme tu peux le voir, le style a changé. La raison est que je n'ai simplement pas réussi à reprendre le style original (d'Aryeom) et après quelques essais je me suis résigné à repartir d'un canevas vierge. Mais même comme ça j'ai souffert, c'est tellement difficile de trouver une palette de couleurs qui vont bien ensemble !

La seconde animation est celle des caisses qui brûlent :

Là encore, grosse galère de couleurs mais aussi de mouvement. La première animation partait du centre vers les côtés et ce n'est qu'une fois dans le jeu que j'ai vu que ce n'était pas top. J'ai donc repris toutes les frames pour faire un mouvement de bas en haut. Je crois que je l'ai faite cinq fois cette animation, à retravailler les couleurs et le mouvement. Mais bon, j'imagine que c'est le lot de l'animation bitmap, amplifié par le fait que je n'ai qu'un petit niveau d'illustrateur-animateur.

En tout cas au final ça me semble très bien et ça donne de la vie dans les parties :)

Somme de contrôle de l'état du jeu

Il s'agit là d'un point technique qui me trottait dans la tête depuis un moment. Pour comprendre le problème il faut se souvenir que dans une partie de Bim! tout le monde fait tourner la simulation. Le serveur le fait en appliquant les actions de tous les joueurs, et les joueurs le font avec ce qu'ils ont sous la main ; c'est à dire les actions des autres si elles sont connues, ou une prédiction de ces actions sinon.

J'ai quelques tests qui font tourner ce système, ce qui me donne un minimum de garanties, et il y a régulièrement des joueurs de n'importe où dans le monde qui font des parties. En gros, je suis plutôt confiant sur le fait que cela fonctionne bien. Cependant, il reste malgré tout un doute : si quelque chose se passe mal, le détecterai-je ? Si un client ne voit plus la simulation dans le même état que le serveur, ça ne l'empêchera pas de jouer mais il va avoir une expérience bizarre.

Un moyen de surveiller que la simulation se déroule bien est de faire une somme de contrôle de son état sur le client et sur le serveur, d'envoyer le résultat obtenu du premier au second, et de vérifier que ça correspond. Fastoche ! En plus j'utilise déjà le système de snapshot d'EnTT pour sérialiser l'état du jeu dans le système de rollback networking, j'aurais juste à appliquer un CRC32 sur le buffer et c'est bon. Ça va être vite plié cette affaire.

Double bonus, j’eus ouï dire que les processeurs relativement récents avaient des instructions pour accélérer le calcul de CRC32. C'est l'occasion de voir ce qu'elles valent.

Tentative d’implémentation avec les instructions dédiées

J'ai commencé par utiliser
boost::crc_32_type et je me suis documenté sur ce qui se faisait sur le sujet. Mon attention s'est arrêtée sur le dépôt komrad36/CRC qui décrit le process en détail et propose des implémentations à différents degrés d'optimisation. C'est très fourni donc j'ai un peu zappé la présentation générale du concept et je suis allé directement aux implémentations. La première chose qui me vient à l'esprit est de vérifier si je reproduis ses résultats.

Et c'est un gros oui. Clairement, chaque implémentation apporte des gains par rapport à la précédente, jusqu'à 98% de gains pour un buffer de 64 KB par rapport à l'implémentation de Boost. La meilleure implémentation utilise bien les instructions CRC32 du processeur qui, j'en profite pour l'apprendre, font partie de SSE 4.2 et sont donc disponibles depuis longtemps. Une petite note au passage, j'ai pris cette taille de buffer en référence car c'est l'ordre de grandeur d'un snapshot de l'état du jeu par EnTT.

Ces gains étant acquis j'ai donc commencé à intégrer leur implémentation dans des tests. Et là, c'est le drame. Je découvre qu'il existe plusieurs versions de CRC32 et en particulier que celle du processeur est CRC32c, distincte de celle de Boost. Bon ce n'est qu'un léger contre-temps, il me suffit d'utiliser un autre paramétrage de Boost pour obtenir le même résultat.

Je me mets ensuite à réfléchir au moyen d'intégrer proprement l'implémentation de CRC32c avec les intrinsèques dans le build de Bim!. Cette implémentation est valide pour les builds x86_64 (utile pour le serveur et quelques appareils Android) mais ne pourra pas être utilisée sur les appareils ARM (la plupart des Android). J'ai commencé par chercher une lib qui ferait la sélection de l'implémentation pour moi mais je n'ai pas trouvé grand chose. Le dépôt cité précédemment n'est pas intégrable tel quel, il faut en extraire les implémentations, et les autres dépôts que je trouve sont du même acabit ou bien n'ont pas les variantes optimisées. Je bricole donc un truc et je m'en vais me documenter sur les instructions CRC32 ARM.

Et là, c'est le drame. J'apprends que les instructions CRC32 pour ARM n'utilisent pas le même polynôme que les instructions SSE ! Impossible d'avoir une implémentation optimisée pour chaque plate-forme et qui effectuerait le même calcul. Pire, il y a des appareils ARM qui sont censés supporter les instructions spécifiques sur le papier mais qui ne le font pas en pratique (quelques iPhones notamment). Je ne peux donc même pas bêtement utiliser les intrinsèques au moins sur le client. Quelle déception.

Il resterait éventuellement les versions optimisées sans intrinsèques, à bases de tables, mais j'ai des doutes sur leur validité sur une architecture big-endian. Et puis je suis trop dépité. Je fais donc ce que j'aurais dû faire depuis le début : j'utilise l'implémentation de Boost et j’implémente la fonctionnalité, et seulement ensuite je m'intéresserai à la perf.

Implémentation de la vérification de sommes de contrôle

Et là… En gros rien n'a fonctionné.

Premier truc auquel je n'avais pas pensé : le serveur va devoir faire une somme de contrôle à chaque itération du jeu, et conserver le résultat pour le comparer avec ce qu'envoient les clients. Le serveur est le premier à connaître l'état de tous les joueurs, et il doit attendre que les clients aient été informés de l'état des autres pour qu'ils puissent eux-même calculer le CRC32, pour enfin faire la comparaison.

J'ai eu un mal fou à mettre ça en place sur le serveur. En réalité avant même de pouvoir mettre la somme de contrôle j'ai dû faire une revue en détail de mon implémentation de la synchro côté serveur, constater qu'il y avait beaucoup d'erreurs, et les corriger. Typiquement je m'étais mélangé entre divers compteurs tels que l'itération de la simulation commune du point de vue du serveur, l'itération commune confirmée par chaque client, et l'itération atteinte par chaque joueur individuellement (en supposant les actions des autres). De même, parfois j'utilisais une variable comme un compteur et parfois comme un indice. Franchement je suis surpris de ne pas avoir eu de problèmes en prod avec les versions précédentes. C'est je pense l'algo le plus difficile à suivre que j'ai implémenté dans ma carrière.

Enfin bon, j'ai quand même réussi à assembler le tout et je suis passé à l'implémentation côté client. Et là, c'est le drame. Les sommes de contrôle ne correspondent pas ! Enfin parfois ça marche et soudain ça se décale. Pourtant les états sont identiques visuellement et dans les dumps (ha ! ha ! trop marrant le débogage d'une app client-serveur ; c'est encore pire qu'un problème multi-thread). Alors évidemment j'ai un problème de décalage de 1 sur une variable (indice ou quantité, il faut choisir) mais ce n'est pas le gros du problème. Après de longues recherches et des discussions sur les forums d'EnTT je comprends : le snapshot n'est pas stable. Le snapshot est exactement ce qu'il annonce en fait, une sérialisation de l'état interne de la lib, donc forcément quand le client fait son rollback et rejoue des actions, ça diverge en interne par rapport au serveur, même si conceptuellement le résultat est le même. J'ai donc dû implémenter une sérialisation reproductible et tout est tombé en marche.

Enfin presque, parce qu'évidemment il restait encore un problème (c'eut été trop facile). Apparemment dès lors que le brouillard est activé, les sommes de contrôle divergent. Pourquoi ? Et bien tout simplement parce que, malin que je suis, j'avais forcé la désactivation du brouillard côté serveur, vu que c'est un effet visuel qui n'a aucun impact sur la logique du jeu. Comme le serveur n'a pas d'yeux, il n'a pas besoin de s'occuper du brouillard.

Et voilà, ça marche ! Comme quoi, ce n'était pas si compliqué. La bonne nouvelle c'est que depuis que c'est en place j'ai très peu de logs indiquant une divergence de sommes de contrôle ; 16 à l'heure où j'écris ces lignes, sur 3400 parties. Aucune idée en revanche de ce qui peut causer la divergence.

Niveau perf, ce n'est pas excellent. Le calcul du CRC32 est 5 fois plus long que la boucle de jeu par exemple. Après ça reste de l'ordre de quelques microsecondes quand même, donc ce n'est pas bloquant, mais c'est dommage sachant qu'il existe une version 98% plus performante de l'algo.

Système de karma

Depuis la version 15 un ingénieux système de karma est appliqué pour filtrer les comportements problématiques. Le karma est un concept robuste utilisé par les meilleurs sites du oueb afin d'évaluer les utilisateurs. Le serveur de Bim! aura dorénavant sa propre version.

La question de gérer d'éventuels comportements problématiques se pose depuis le début du projet, notamment par exemple pour des joueurs qui ne valident jamais sur l'écran de matchmaking ou qui quittent en pleine partie. En pratique ces problèmes seraient noyés dans la masse, donc je n'avais pas d'incitation à m'y intéresser. Cependant j'ai remarqué il y a quelque temps des joueurs qui faisaient des parties très courtes. Ils lancent un match et perdent intentionnellement. Je me doute que l'idée est de s'organiser avec un groupe de joueurs pour faire monter les compteurs de pièces des uns et des autres en les faisant gagner. Au fond ce n'est pas un problème tant que les joueurs sont consentants, mais si un joueur externe au groupe se retrouve dans la même partie, son expérience sera décevante.

J'ai donc mis en place un système de points que les joueurs perdent s'ils se comportent d'une manière qui dégrade l'expérience des autres. Quand les points tombent à zéro, le joueur est banni pour une durée paramétrable.

Introduction des bots

Grosse nouveauté de la version 16 : le serveur instanciera dorénavant un bot en guise d'adversaire si aucun humain n'est disponible. C'en est fini de l'attente interminable sur l'écran de recherche d'adversaire !

Si j'avais déjà expérimenté avec des IA de jeu dans le passé, c'était principalement pour des jeux combinatoires et de petite taille (morpion, puissance 4, tetris, ce genre de choses). C'est donc la première fois que je m'intéresse à une IA pour un jeu avec un terrain, pour laquelle il ne suffira pas de tester toutes les actions possibles et de simuler les étapes suivantes.

J'ai cherché un peu de documentation sur des IA de game play à la Bomberman, sans grand succès. À part ce très intéressant article d'un dénommé Jean-Francois Geyelin qui a développé Bomber Dude pour TI-89 en 2004, malgré un clavier qui se blo

Mon approche sera similaire à celle de l'article sur l'aspect des données utilisées par le bot : il va se faire plein de des cartes du niveau. Une carte est juste un tableau à deux dimensions qui représente un aspect de chaque case du jeu : est-ce un danger, est-ce un bloc destructible, est-ce un bonus, etc.

Pour le reste, je vais diverger de l'article. L'auteur a implémenté son bot pour qu'il ait des objectifs court terme, c'est à dire qu'il va cibler une case voisine et cherchera un nouvel objectif quand il y sera. L'idée étant que la topologie du niveau pouvant changer il est inutile de stocker un chemin long terme. De plus, son bot pose des bombes de manière aléatoire. J'ai choisi de prendre l'approche opposée. Mon bot se fixe un objectif et vérifie en chemin si l'objectif est toujours faisable. De plus il pose des bombes dès lors que cela lui semble pertinent.

Durant l'implémentation de cette fonctionnalité j'ai plusieurs fois cru que j'avais terminé, pour ensuite tomber sur une partie où le bot fait soudain n'importe quoi. C'est très amusant de le voir évoluer tout seul même s'il arrive qu'on ait envie de lui dire d'ouvrir les yeux. « Tu vois bien que c'est dangereux là ! »

Ci-dessous je vais décrire les structures de données utilisées par le bot ainsi que sa stratégie.

Ce que le bot voit

Lorsqu'on demande au bot de progresser d'une étape, il commence par faire un bilan de l'état du jeu sous la forme de cartes :

• visibilité : voit-il le contenu de la case ;
• caisses : la case contient-elle une caisse ;
• solides : la case contient-elle un élément bloquant (mur, caisse, bombe) ;
• bonus : la case contient-elle un bonus ;
• létalité : la case cause-t-elle une mort immédiate (flammes) ;
• danger imminent : la case est-elle sur le point d'être mortelle (zones couvertes par les futures flammes des bombes sur le point d'exploser) ;
• danger long-terme : la case va-t-elle devenir dangereuse (zones qui seront couvertes par l'explosion d'une bombe).
• distances : tout simplement la plus courte distance de la position courante vers la case.
• chemins : un plus court chemin pour atteindre la case.

Par précaution les cases sur lesquelles on n'a pas de visibilité sont aussi létales.

De plus, pour simplifier, les cartes de danger plus fort sont inclues dans celles des dangers plus faibles. Une case létale est un danger imminent et un danger imminent est aussi un danger long-terme.

Le bot en profite aussi pour noter la position et la puissance de feu des autres joueurs, sauf si ceux-ci sont invisibles ou masqués par le brouillard.

Ce que le bot veut faire.

Le bot n'a que deux états : le mode conquête et le mode protection. Une fois récoltées les informations sur l'état du jeu, il fait le point sur sa situation. Il commence par regarder si sa case est marquée comme danger imminent. Si c'est le cas et qu'il est en mode conquête, il change d'objectif en passant en mode protection. S'il est déjà en mode protection il regarde s'il peut atteindre un lieu sûr plus rapidement que prévu, sinon il maintient son plan. Si sa case n'est pas un danger et qu'il est en mode conquête, il continue aussi avec son plan, mais s'il est en mode protection il passe en mode conquête.

Une fois traité l'état de la case en cours, il est temps de s'occuper du plan. D'abord il regarde si son objectif est toujours réalisable. Par exemple s'il a prévu d'exploser une caisse et que celle-ci n'est plus là, le plan tombe à l'eau. De même, si un obstacle a été posé devant lui et qu'il ne peut plus avancer, alors son plan n'est plus réalisable. Si le plan est annulé ou qu'il n'y avait simplement pas de plan, il est temps d'en trouver un nouveau.

Le plan le plus simple est sans doute en mode protection. Le bot est en danger, il va scanner la table des distances pour trouver une case la plus proche dans laquelle il n'y a pas de danger imminent. Son but va être d'atteindre cette case.

En mode conquête c'est un peu plus compliqué. S'il ne reste plus de caisses ni de brouillard à découvrir, le bot attaque. Il va alors vers le joueur pour lui mettre une bombe sous le nez. S'il reste des caisses ou du brouillard, il va tenter d'en enlever. Pour cela il donne un score à chaque case qu'il peut atteindre puis sélectionne une case avec le score le plus élevé. Ce score augmente si :

• on prend un bonus bombe ou flamme.
• on prend un bouclier alors qu'on en n'a pas déjà un.
• il existe un chemin vers un autre joueur et on prend un bonus d'invisibilité (aucun intérêt à devenir invisible si les autres ne peuvent nous atteindre).
• on découvre des cases couvertes par du brouillard.
• on casse des caisses.
• on met des adversaires en danger.

À l'inverse, on perd des points si on brûle des bonus ou que la cible est marquée comme un danger.

Le score est dégressif à mesure que la distance de la cible augmente. De plus, c'est un poil plus compliqué dans les détails. Par exemple quand on compte les caisses qui vont être détruites, il faut vérifier qu'elles ne sont pas déjà la cible de bombes en place ; autrement on risque de brûler un bonus qui va apparaître.

Et voilà, une fois que la cible est choisie le bot bouge petit à petit le long du chemin pour y aller. À chaque déplacement il regarde bien sûr s'il n'est pas en train d'entrer dans une case dangereuse, auquel cas il attend que le danger passe, et si ça ne serait pas une bonne idée de poser une bombe sur le chemin pour casser plus de caisses ou embêter les autres joueurs.

Il y a encore des points améliorables bien sûr mais en l'état le bot me semble suffisamment bon pour que les parties soient sympa. Sur le long terme j'aimerais le rendre meilleur, évidemment, mais aussi lui donner un mouvement plus souple. Un autre défaut est qu'il sait trop de choses, on le voit donc s'arrêter à la limite des explosions alors qu'un humain aurait tendance à garder de la marge. À l'heure où j'écris ces lignes le bot a remporté 67% de ses 2900 parties contre de vrais joueurs.

La triste parenthèse LLM

Il y a quelques semaines j'ai eu une très mauvaise expérience en tentant de contribuer à Axmol, un des outils que j'utilise pour le jeu. J'avais envoyé un patch et celui-ci est resté longtemps sans réponse. Un mois et demi, pour être précis, avant que je demande s'il y avait une raison pour ne pas intégrer le patch. Le responsable du dépôt a alors activé un bot Gemini pour faire une revue… C'est sans doute une des pires revues que j'ai subi. Des banalités et « recommandations » d'un niveau consultant, sans considérations pratiques ni discussions. Évidemment qu'il n'y a pas de discussion, puisque c'est un bot. Imagine, c'est comme si tu appelais un service client et qu'au lieu d'échanger avec un humain tu devais parler à une machine. Quel enfer, personne n'accepterait ça.

En plus de cela j'ai eu le droit à une synthèse insipide typique d'une IA, en quatre points, gras au début de chaque point, et développement en listes à puces.

Pour être tout à fait clair, c'est insultant. Quel mépris d'accueillir les contributeurs avec des robots. Peut-être que le responsable du dépôt ne se sentait pas de juger le patch et qu'il lui a semblé pertinent d'utiliser Gemini pour l'aider à comprendre, mais il aurait dû garder cela pour lui, justement pour guider son jugement, et sûrement pas rediriger le bousin vers son interlocuteur. Il faut bien comprendre que pour chaque commentaire laissé par Gemini, je reçois un mail. Si l'intention pour le responsable était de se faire accompagner dans la revue, ça ne devrait pas me polluer.

J'en ai discuté sur le chat du projet et personne d'autre ne trouve cela anormal. La conclusion semble être « peut-être qu'on pourrait mettre dans la doc que les PR seront revues par Gemini pour éviter les surprises ? ». Pour ma part je me mets en retrait. Je veux bien revoir mon patch et débattre de l'implémentation mais il est hors de question que je me prenne la tête à « discuter » d'une PR avec des robots ; et je regrette du coup d'avoir choisi cet outil pour mon jeu.

Statistiques

Je te copie ci-dessous deux graphiques fournis par les stats en ligne :

Nombre de parties par heure au moment où j'écris ces lignes.

Nombre de sessions par heure au moment où j'écris ces lignes.

On voit bien sur ces graphes une hausse d'activité dans les jours qui suivent la sortie d'une nouvelle version (la 15 vers le 17 mars, la 16 vers le 21 avril). Sur le graphe des sessions ces deux versions donnent la même tendance, par contre sur le graphe des parties jouées on voit une claire hausse d'activité avec la dernière version, qui propose les bots. En résumé, les joueurs jouent plus quand ils ont un adversaire. Merci Captain Obvious.

En termes de répartition du nombre de joueurs par partie, en agrégeant les parties depuis la version 14, du dernier journal, jusqu'à aujourd'hui (environ 3 mois) on en est à peu près à :

Nombre de joueurs	Nombre de parties
1	2912
2	4150
3	916
4	293

Bien que le bot ne soit disponible que depuis quelques jours, il y a déjà plus de parties avec lui qu'à trois ou quatre joueurs.

Et enfin, pour la répartition des joueurs par pays, on a :

L'Allemagne remonte de la quatrième place à la première et le Japon passe devant la France. Mais si on regarde la map monde de PostHog, la tendance est différente, donc c'est à prendre avec des pincettes :

Pour les dernières stats on va parler argent. C'est la seule métrique stable de version en version : le revenu lié au jeu reste un bon gros zéro. Mais vous pouvez y remédier facilement, il suffit d'envoyer des sioux. Je n'ai besoin que d'un seul million, après ça roule tout seul :)

Pistes pour la suite

Le jeu est dans un état qui me semble assez plaisant. Il n'est pas trop moche et on peut jouer quand on veut. Je pense que c'est le bon moment pour ouvrir de nouvelles possibilités.

Les éléments les plus simples à mettre en place sont sans doute les modifications de gameplay (quoi que maintenant qu'il faut mettre le bot dans l'équation ça va demander plus de boulot). J'ai une petite liste de choses à essayer sur ce sujet.

D'autre part, avec l'arrivée des bots j'ai pu pousser les tests un peu plus loin en simulant plusieurs parties concurrentes. C'est bien mais maintenant j'ai des tests très longs (un des workflows GitHub actions prend jusqu'à deux heures). Ce serait une bonne chose de travailler là dessus pour réduire ces temps, sinon ça va être intenable.

Cependant je pense qu'aujourd'hui il manque surtout un moyen de faire de l'administration. Par exemple la config du client est un fichier JSON sur mon serveur et je l'édite à la main quand je veux faire évoluer les choses. Il y a un gros risque d'introduire des erreurs (c'est déjà arrivé). Je voudrais donc mettre en place un serveur business pour gérer cela, qui me permettrait de configurer l'ensemble avec un peu plus de rigueur.

Une fois ce serveur en place j'ai l'impression que ce serait une bonne chose qu'il gère l'inventaire des joueurs aussi, ainsi que les stats de jeu. Déjà parce que ça compliquera la triche, mais aussi parce que ça me permettrait d'avoir une vue d'ensemble et un peu de contrôle. Je suis encore un peu hésitant là dessus parce que ça va me demander plus de travail alors qu'au fond la triche ne va pas changer grand chose pour moi ; ce n'est pas parce que le joueur ne peut pas tricher qu'il va payer. Par contre pour les stats de jeu c'est important qu'elles soient stockées sur le serveur si je veux que les joueurs puissent voir les stats de leurs adversaires.

Avoir des stats de joueurs implique aussi que les joueurs aient un profil, et je pourrais alors aussi proposer des leaderboards. Cela dit je suis quand même inquiet de l'effort de modération pour filtrer les pseudos. Enfin je voudrais aussi mettre un système de salons privés pour pouvoir jouer uniquement avec des personnes informées. C'est dispo sur le serveur de jeu mais il manque des outils d'administration.

Bref, l'existence d'un serveur business ouvre des possibilités. Dès qu'il sera en place je pense que je pourrai passer le jeu d'alpha a beta :)