Whisthub

Waarom er een fout zat in de AI van hartenjagen op iOS

Enkele maanden geleden kreeg ik een e-mail van iemand die zei dat er een fout zat in de AI van hartenjagen. Volgens de gebruiker in kwestie werd de schoppendame ♠Q altijd gespeeld door de AI de eerste keer dat schoppen ♠ uitgekomen werd, los van of dit een goede strategie was of niet. Wanneer ik zulke meldingen binnenkrijg, ga ik steeds na of ik de fout kan reproduceren. Bij het debuggen is het immers belangrijk om de fout te kunnen reproduceren, anders is het zo goed als onmogelijk om ze te kunnen oplossen.

Wanneer ik echter een paar spelletjes hartenjagen speelde, viel het nooit op dat de AI steeds ♠Q zou spelen wanneer schoppen werd uitgekomen. Het maakte niet uit hoevel spelletjes ik speelde, ik kon de fout niet reproduceren, dus helaas moest ik de gebruiker in kwestie vertellen dat ik de fout niet kon reproduceren en dat het zo dus moeilijk was om er iets aan te doen.

Enkele dagen geleden kreeg ik echter opnieuw een e-mail van dezelfde gebruiker die zei dat het probleem nog steeds aanwezig was. Ik speelde opnieuw een paar spelletjes, en deze keer was het wel prijs: ik kon het probleem wél reproduceren! De situatie waar de fout zich voordeed is hieronder weergegeven. In deze spelsituatie speelde de AI ♠Q, terwijl het duidelijk is dat dit geen goed idee is omdat Monica zeer waarschijnlijk nog een lagere kaart kan spelen, en de AI op die manier dus de 13 strafpunten van ♠Q aangesmeerd krijgt. De juiste kaart om te spelen hier is ♠10, of eventueel ♠A.

Nu dat ik eindelijk een geval had waar de fout kon gereproduceerd worden, kon ik beginnen met debuggen. Opgelet: de rest van deze blogpost is nogal technisch, dus als dit niet echt uw ding is, kunt u hier stoppen met lezen en gewoon onthouden dat de fout nu opgelost is.

Nog steeds hier? Leuk! Als u de blogpost over hoe de AI werkt hebt gelezen, dan weet u dat er een heleboel testen zijn voor de AI, dus nam ik de log van het spel in kwestie en maakte er een test van, wat er ongeveer zo uitziet

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');
});

Doordat ik wist dat de AI ♠Q zou spelen in dit geval, was de verwachting dat deze test zou falen, maar tot mijn grote verbazing gebeurde dit niet en speelde de AI correct ♠10! Dit is de nachtmerrie van elke programmeur: bugs die voorkomen "in het wild", maar die onmogelijk na te bootsen zijn onder gecontroleerde omstandigheden. Wanneer zoiets gebeurt, is het duidelijk dat er een leuke debugsessie zit aan te komen. En jazeker, dat was ook hier het geval!

Het spel uit de test was gespeeld op mijn iPhone, dus dat was mijn eerste reflex: voer de test ook eens uit op iPhone in plaats van op een computer, en jawel, daar gebeurde het: de test faalde op iPhone, maar slaagde op mijn computer. Het was echter wel een grote stap voorwaarts omdat ik nu toch op een betrouwbare manier de fout kon reproduceren, maar het nadeel is dat debuggen op een iPhone een echte nachtmerrie is omdat er geen toegang is tot de normale manier van debuggen die gebruikt kan worden op een computer. Als u bekend bent met JavaScript: dit betekende dat ik moest debuggen op mijn gsm met alert(). Pijnlijk!

Na wat speurwerk in de code, bleek dat er op een bepaald moment de waarde NaN werd geïntroduceerd in het algoritme van de AI, maar enkel op iPhone. NaN staat voor Not a Number en is een waarde die je in JavaScript krijgt bijvoorbeeld door te delen door nul, alsook in een aantal andere gevallen. Het probleem met NaN is dat eender welke wiskundige operatie met NaN opnieuw resulteert in NaN, en vergelijkingen zoals value > NaN zijn plots waardeloos omdat deze altijd als false worden aanschouwd. In minder technische termen betekent dit dat eens NaN ergens voorkomt in de AI, het gedrag van de AI foutief wordt en niet langer te voorspellen valt, dus dat was wat er inderdaad gebeurde.

Na wat meer onderzoek bleek dat de NaNs geïntroduceerd werden door een functie die binomiaalcoëfficiënten berekent. Zoals u zich misschien nog herinnert uit de wiskunde van vroeger, worden binomiaalcoëfficiënten berekend met faculteiten als

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

Binomiaalcoëfficiënten worden gebruikt op veel plaatsen in de AI, maar doordat de berekening van faculteiten veel tijd in beslag kan nemen, werden de meest gebruikte faculteiten op voorhand berekend zodat ze simpelweg uit een cache gelezen konden worden in plaats van telkens opnieuw berekend te moeten worden. Meer specifiek komt het nauwelijks voor in de AI dat er faculteiten groter dan 13!13! nodig zijn doordat er maximum 13 kaarten van elke kleur zijn, dus het is logisch om alle faculteiten te cachen tot 13!13!.

De waardes van deze faculteiten werden opgeslagen in een Uint32Array, hetgeen een datastructuur is in JavaScript die de waarden opslaat als unsigned 32-bit integers, en deze werd aangemaakt als

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

Merk echter op dat de cache enkel waarden bevat tot 12!12!, omdat 13!=6 227 020 80013! = 6\ 227\ 020\ 800 groter is dan de grootste unsigned 32-bit integer 232−1=2 147 483 6472^{32}-1 = 2\ 147\ 483\ 647. De functie die effectief gebruikt werd om de faculteiten te berekenen was

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

Wat er hier gebeurt is dat de waardes uit de cache worden gelezen, tenzij ze niet bestaan, in welk geval er wordt teruggegrepen naar de recursieve aanpak.

Moderne JavaScript engines voeren echter een hoop optimalisaties uit achter de schermen, en dat is trouwens waarom er een Uint32Arraywerd gebruikt voor de cache, omdat op die manier de JavaScript engine intern de faculteiten als 32-bit integers kan voorstellen en op deze manier de berekeningen versnellen, zelfs al kunnen getallen in JavaScript waardes bevatten groter dan 232−12^{32}-1 doordat ze geïmplementeerd zijn volgens het double-precision 64-bit IEEE 754 formaat.

Dus, wat er op iOS gebeurde - tenminste zo vermoed ik - is dat eens de factorial() functie een paar keer aangeroepen werd, de JavaScript engine deze optimaliseert. Deze optimalisatie gebeurt echter waarschijnlijk zonder dat de functie ooit waarden groter dan 232−12^{32}-1 heeft gezien, en dus wordt de functie geoptimaliseerd in de veronderstelling dat alle getallen erin kunnen voorgesteld worden als 32-bit integers. Echter, eens de factorial() functie aangeroepen wordt met x=13x = 13, dan kan de output niet langer voorgesteld worden als 32-bit integer, en dus wordt er incorrect 0 geretourneerd door de functie. Dit betekent op zijn beurt dan weer dat er verderop in de AI door 0 gedeeld wordt, et voilà: dat is waar de NaN vandaan kwam!

Wat interessant is, is dat andere JavaScript engines - zoals bijvoorbeeld de V8 engine van Google Chrome - dit randgeval wel correct behandelen, en daarom kon de fout in de AI hier dus niet gereproduceerd worden. Het lijkt er dus op dat het eigenlijk een fout in Safari was op iOS! Wat ook interessant is, is dat zolang Safari de factorial() functie niet optimaliseert, deze wél het correcte resultaat oplevert voor 13!13!. Bijvoorbeeld

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 zoals het moet
let value = factorial(13);

levert wél het verwachte resultaat op, maar als we de functie "opwarmen" met enkel waardes onder 12!12!

// Warm de factorial functie op zodat deze geoptimaliseerd wordt.
for (let i = 1; i <= 12; i++) {
  for (let j = 0; j < 1e5; j++) {
    factorial(i);
  }
}
let value = factorial(13);

dan wordt de factorial() functie geoptimaliseerd door de JavaScript engine en levert dit 13!=013! = 0 op, wat uiteraard niet correct is!

Nog verwarrender is dat wanneer ik de factorial() functie herschreef als

function factorial(x) {
  // Bemerk de <= in plaats van <
  if (x <= 0) return 1;
  return cache[x] || factorial(x-1)*x;
}

alles werkte zoals verwacht! Mogelijk is dit omdat de functie op die manier niet geoptimaliseerd werd, hetgeen alleen maar aantoont dat hoe JavaScript engines code optimaliseren complex is, en in het geval van Safari zelfs fouten bevat!

Ik heb ook geprobeerd om de fout te reproduceren op een webpagina die niets anders doet dan de faculteit van 13 te berekenen, maar het was onmogelijk om het probleem hier te reproduceren. Ik vermoed dat dit is omdat er niet genoeg JavaScript uitgevoerd wordt om het voor de engine de moeite waard te maken om te gaan optimaliseren. De Whisthub AI is echter volledig in JavaScript geschreven, dus vooraleer de faculteiten berekend worden is er al een hoop JavaScript uitgevoerd, wat er wellicht voor zorgt dat de engine de factorial() functie wél gaat optimaliseren!

Maar goed, uiteindelijk heb ik de fout opgelost door te herschrijven hoe de binomiaalcoëfficiënten berekend worden. In plaats van faculteiten te gebruiken, is er ook een manier om dit te doen zonder faculteiten en hun bijbehorende hoge numerieke waarden. De implementatie hiervan wordt overgelaten als een oefening voor de lezer.

Dus, de fout zou niet langer aanwezig mogen zijn, en daarbij komt ook nogeens dat ik nu eindelijk ook een verklaring heb waarom ik de fout initieel niet kon reproduceren: de eerste keer probeerde ik dit op mijn computer met Google Chrome, hetgeen ervoor zorgde dat alles normaal werkte. Het was pas toen ik ook begon te spelen tegen de AI op iPhone dat het duidelijk was dat er inderdaad een fout was! Het was puur geluk dat ik het de tweede keer probeerde op iPhone en zo de fout tegenkwam, anders had ik het wellicht nooit gevonden.

Oef!