Whisthub

Retour

Comment l'IA de la dame de pique était buguée sur iOS

Il y a quelques mois, j'ai reçu un e-mail de quelqu'un m'informant qu'il y avait un bug dans l'IA de la dame de pique. Selon cet utilisateur, la dame de pique ♠Q était systématiquement jouée par l'IA dès la première fois que pique ♠ était demandé, que ce soit une bonne idée ou non. Chaque fois que je reçois un signalement de ce genre, je vérifie d'abord si je parviens à reproduire le bug. C'est en effet la règle numéro un du débogage : il faut être capable de reproduire le bug, sinon il est tout simplement impossible de le corriger.

Cependant, en jouant plusieurs parties de dame de pique, je n'ai jamais remarqué que l'IA jouait ♠Q au premier pli alors qu'elle n'aurait pas dû. Peu importe le nombre de parties jouées, je ne parvenais pas à reproduire le problème, donc j'ai dû répondre à l'utilisateur que je n'avais malheureusement trouvé aucun problème avec l'IA et que je ne pouvais donc rien y faire.

Il y a quelques jours cependant, j'ai reçu un nouvel e-mail du même utilisateur, m'indiquant que le problème était toujours présent. J'ai rejoué quelques parties, et cette fois, j'ai effectivement réussi à reproduire le bug. Le cas précis que j'ai trouvé est illustré ci-dessous. Dans cette situation, l'IA jouait ♠Q, alors que ce n'est clairement pas une bonne idée puisque Monica peut probablement jouer une carte plus basse, ce qui fait que l'IA récolte les 13 points de pénalité de ♠Q. La bonne carte à jouer ici serait ♠10, ou éventuellement ♠A.

Maintenant que j'avais enfin un cas reproduisant le bug, je pouvais réellement commencer à déboguer. Attention : le reste de cet article est un peu technique, donc si ce n'est pas votre truc, vous pouvez vous arrêter ici et simplement retenir que le bug est désormais corrigé.

Toujours là ? Super ! Si vous avez lu l'article de blog sur le fonctionnement de l'IA, vous savez qu'il existe un grand nombre de cas de test pour l'IA, donc j'ai récupéré le journal de la partie ci-dessus et j'en ai fait un cas de test, qui ressemble à ceci

it('does not play ♠Q when not needed', function() {
  this.log = `
    # 0
    1: ♥AQ4 ♦K7 ♣Q963 ♠AQ86
    2: ♥873 ♦Q852 ♣K104 ♠1093
    3: ♥K102 ♦A9643 ♣87 ♠K54
    0: ♥J965 ♦J10 ♣AJ52 ♠J72
    0: [♣2 ♣5 ♦J]
    1: [♣Q ♠Q ♠A]
    2: [♣K ♣10 ♣4]
    3: [♣8 ♣7 ♠K]
    # 1: ♥AQ4 ♦KJ7 ♣96532 ♠86
    # 2: ♥873 ♦Q852 ♣Q ♠AQ1093
    # 3: ♥K102 ♦A9643 ♣K104 ♠54
    # 0: ♥J965 ♦10 ♣AJ87 ♠KJ72
    1: ♣2 ♣Q ♣K ♣A
    0: ♠J ♠8
  `;
  let card = this.decide();
  expect(card).to.not.equal('♠Q');
});

Comme je savais que l'IA jouerait ♠Q dans ce cas, je m'attendais à ce que le test échoue, mais à ma grande surprise, il a réussi, et l'IA jouait correctement ♠10 ! C'est le cauchemar de tout programmeur : des bugs qui apparaissent « en pleine nature », mais qui sont impossibles à recréer dans des conditions contrôlées. Quand ce genre de chose arrive, on sait qu'on est parti pour une belle session de débogage. Et effectivement, ça l'a été !

Le cas de test ci-dessus avait été trouvé sur mon iPhone, alors mon premier réflexe a été d'exécuter le test sur un iPhone plutôt que sur mon ordinateur, et effectivement, c'était bien ça : le test échouait sur iPhone, mais réussissait sur mon ordinateur. C'était une avancée importante puisque je pouvais désormais reproduire le bug de manière fiable, mais l'inconvénient est que déboguer sur un iPhone est un véritable cauchemar, car on n'a pas accès aux outils de débogage habituels de l'ordinateur. Si vous connaissez JavaScript : cela signifiait que je devais déboguer sur mon téléphone à coups de alert(). Aïe !

Après avoir creusé un moment dans le code, j'ai découvert qu'à un certain point, une valeur NaN était introduite dans l'IA, mais uniquement sur iPhone. NaN signifie Not a Number, et c'est une valeur que l'on obtient en JavaScript en divisant par zéro, entre autres cas. Le problème avec NaN, c'est que toute opération numérique impliquant NaN donne également NaN, et des comparaisons comme value > NaN deviennent absurdes puisqu'elles sont toujours fausses. En des termes moins techniques : dès que NaN apparaît quelque part dans l'IA, son comportement devient indéfini et imprévisible, ce qui était exactement ce qui se passait ici.

Après quelques recherches supplémentaires, j'ai découvert que les NaN étaient introduits par une fonction qui calcule des coefficients binomiaux. Comme vous vous en souvenez peut-être de vos cours de mathématiques, les coefficients binomiaux se calculent à l'aide de factorielles, comme suit :

(nk)=n!(n−k)! k!\binom{n}{k} = \frac{n!}{(n-k)!\ k!}

Les coefficients binomiaux sont utilisés à de nombreux endroits dans l'IA, mais comme le calcul des factorielles peut prendre du temps, les factorielles les plus utilisées avaient été précalculées afin de pouvoir simplement les lire depuis un cache. Plus précisément, l'IA n'a quasiment jamais besoin d'une factorielle plus grande que 13!13!, puisqu'une couleur ne compte que 13 cartes, donc il est logique de mettre en cache toutes les factorielles jusqu'à 13!13!.

Les valeurs de ces factorielles mises en cache étaient stockées dans un Uint32Array, une structure de données JavaScript qui stocke les valeurs sous forme d'entiers non signés sur 32 bits, et qui se crée comme ceci :

const cache = new Uint32Array(13);
cache[0] = 1;
for (let i = 1; i <= 12; i++) {
  cache[i] = cache[i-1]*i;
}

Notez toutefois que le cache ne contient des valeurs que jusqu'à 12!12!, car 13!=6 227 020 80013! = 6\ 227\ 020\ 800 est plus grand que le plus grand entier non signé sur 32 bits, 232−1=2 147 483 6472^{32}-1 = 2\ 147\ 483\ 647. La fonction qui calculait réellement les factorielles ressemblait alors à ceci :

function factorial(x) {
  if (x < 0) return 1;
  return cache[x] || x*factorial(x-1);
}

Ce qui se passe ici, c'est que l'on lit la valeur depuis le cache, sauf si elle n'existe pas, auquel cas on se rabat sur l'approche récursive.

Or, les moteurs JavaScript modernes effectuent de nombreuses optimisations, et c'est justement pour cela qu'un Uint32Array est utilisé pour le cache : cela permet au moteur JavaScript de stocker les nombres en interne comme des entiers 32 bits et d'accélérer les calculs, même si les nombres en JavaScript sont en réalité implémentés au format double précision 64 bits IEEE 754, ce qui signifie qu'ils peuvent contenir des valeurs plus grandes que 232−12^{32}-1.

Donc, ce qui se passe sur iOS - du moins c'est ce que je suppose - c'est qu'une fois que la fonction factorial() a été appelée plusieurs fois, le moteur JavaScript l'optimise. Cependant, cette optimisation se produit sans que le moteur n'ait jamais vu de valeurs supérieures à 232−12^{32}-1, et il l'optimise donc en partant du principe qu'il ne verra jamais que des valeurs représentables comme des entiers 32 bits. Or, dès que la fonction factorial() est appelée avec x=13x = 13, elle suppose à tort que le résultat pourra encore être représenté sur 32 bits, ce qui n'est en réalité pas le cas ! Résultat : elle retourne incorrectement 0, ce qui signifie que plus loin dans le calcul des coefficients binomiaux, on divise par zéro, et - boum - voilà d'où vient notre NaN !

Ce qui est intéressant, c'est que les autres moteurs JavaScript - comme le moteur V8 de Chrome - gèrent correctement ce cas particulier, et le bug ne peut donc pas y être reproduit. Il semble donc bien s'agir d'un véritable bug de Safari sur iOS ! Ce qui est également intéressant, c'est que tant que Safari n'optimise pas la fonction factorial(), celle-ci produit le résultat attendu. Par exemple,

function factorial(x) {
  if (x < 0) return 1;
  return cache[x] || factorial(x-1)*x;
}
const cache = new Uint32Array(13);
cache[0] = 1;
for (let i = 1; i <= 12; i++) {
  cache[i] = cache[i-1]*i;
}

// Value is 6 227 020 800 as expected
let value = factorial(13);

cela produit le résultat attendu, mais si l'on « préchauffe » la fonction factorial avec uniquement des valeurs inférieures à 12!12!

// Warm up the factorial function
for (let i = 1; i <= 12; i++) {
  for (let j = 0; j < 1e5; j++) {
    factorial(i);
  }
}
let value = factorial(13);

alors la fonction factorial() se fait optimiser par le moteur JavaScript et calcule 13!=013! = 0, ce qui est incorrect !

Ce qui est encore plus déroutant, c'est qu'en réécrivant la fonction factorial() comme suit

function factorial(x) {
  // Notice the <= instead of <
  if (x <= 0) return 1;
  return cache[x] || factorial(x-1)*x;
}

alors tout fonctionne comme prévu ! C'est peut-être parce que de cette façon, le moteur JavaScript ne l'optimise pas, ce qui montre simplement à quel point la manière dont les moteurs JavaScript optimisent le code est complexe, et dans le cas de Safari, carrément buguée !

J'ai également essayé de reproduire le bug en créant une page web qui ne fait rien d'autre que calculer la factorielle de 13, mais là, je n'ai pas réussi à reproduire le problème. Je suppose que c'est parce qu'il n'y a pas assez de JavaScript exécuté pour que le moteur juge que ça vaille la peine de l'optimiser. Cependant, comme la logique de l'IA de Whisthub est écrite en JavaScript, il y a déjà énormément de JavaScript exécuté, donc je suppose que l'optimisation s'y déclenche parce qu'il y a plus à y gagner !

Quoi qu'il en soit, j'ai fini par résoudre le bug en revoyant la façon dont les coefficients binomiaux sont calculés. Au lieu d'utiliser des factorielles pour les coefficients binomiaux, il existe en fait une méthode qui permet d'éviter les factorielles et leurs grandes valeurs associées. L'implémentation de cette méthode est laissée en exercice au lecteur.

Le bug ne devrait donc plus être présent, et j'ai en plus maintenant une explication pour laquelle je n'étais initialement pas parvenu à le reproduire : quand je jouais contre l'IA sur mon ordinateur avec Google Chrome, tout fonctionnait parfaitement bien. Ce n'est qu'en jouant contre l'IA sur iOS que le bug s'est manifesté ! C'est un pur coup de chance si j'ai retenté ma chance sur mon iPhone la seconde fois et que j'ai donc rencontré le bug, sinon je ne l'aurais probablement jamais découvert.

Ouf !