De AI van kingen heeft vals gespeeld

Zaterdag 20 januari 2024

Kingen is al een hele tijd beschikbaar op Whisthub. Op 1 april 2024 is het exact twee jaar geleden dat het gelanceerd werd - en dat was geen grap! In die tijd is kingen uitgegroeid tot een van de meest geliefde kaartspellen op Whisthub, naast de eeuwige klassiekers kleurenwiezen en manillen.

Onlangs kreeg ik echter een e-mail van iemand die me vertelde dat de AI vals gespeeld had. "Onmogelijk!" dacht ik. Ik heb de AI zelf geschreven, en ik heb hem absoluut niet geprogrammeerd om vals te spelen. De AI speelt altijd met dezelfde informatie als een menselijke speler: hij weet niet welke kaarten de andere spelers in handen hebben. "De gebruiker moet zich vergist hebben, de AI is al die jaren niet veranderd, dus het zou vreemd zijn als niemand dit ooit gemeld had!" was mijn eerste, natuurlijke reactie.

Toch was mijn nieuwsgierigheid geprikkeld, dus probeerde ik het valsspeelgedrag dat de gebruiker meldde te reproduceren. En, wauw, wat was ik verrast. Het bleek dat de AI inderdaad vals speelde, en dat zonder dat ik het wist! Betekent dit misschien dat computers eindelijk bewustzijn hebben gekregen, in deze tijd waar AI overal opduikt? Wel nee, maar laten we eens kijken wat er precies gebeurd is!

Het valsspelen deed zich voor in een spelsituatie die er als volgt uitzag

Bert koos voor een troefspelletje en koos ♦ als troef, waarna Chris ♦10 speelde op Rachels ♦2. Wij hebben ♦K, ♦Q en ♦8, dus idealiter spelen we onze ♦8, aangezien Bert waarschijnlijk ♦A heeft, want hij is degene die ♦ als troef koos. Dit is bijvoorbeeld wat u normaal gezien zou doen bij kleurenwiezen. Volgens de regels van kingen moeten we echter overtroeven indien mogelijk, dus zijn we verplicht om ofwel ♦K ofwel ♦Q te spelen.

Hier gaat het mis bij de AI. Als de AI in deze situatie terechtkomt, speelt hij toch ♦8, ook al is dat volgens de regels niet toegelaten! Aanvankelijk was ik daar behoorlijk door verrast. ♦8 is immers, zoals u kan zien, correct uitgegrijsd, en als menselijke speler kunt u ze niet spelen. Waar kwam dat verschil dan vandaan?

Om te beginnen moet u weten dat de server een onderscheid maakt tussen kaarten die door mensen en kaarten die door de AI gespeeld kunnen worden. Voor menselijke spelers volstaat het niet om ongeldige kaarten grijs te maken in de interface. Als u namelijk een technische achtergrond heeft, kunt u nog steeds een ongeldige kaart naar de server sturen, en daar valt niets tegen te doen. Daarom wordt elke menselijke kaart die op de server toekomt eerst gecontroleerd om na te gaan of het geen ongeldige kaart is. De code hiervoor op de server ziet er ongeveer zo uit

// Zoek de speler en kaart voor het binnenkomende bericht.
let player = game.findPlayer(request.id);
let { move } = request.body;

// Als de kaart ongeldig is, zorg voor een foutmelding
if (!game.isValidMove(move)) {
  throw new Error(`Invalid move ${move}!`);
}

// Geen foutmelding? Cool, speel de kaart.
player.move(move);

Kaarten van de AI zijn echter anders. Er is volledige controle over hoe de AI speelt, dus kan deze ook gewoon geprogrammeerd worden om de regels te volgen. Daardoor is het niet nodig om de beslissingen van de AI te controleren, wat de AI ook sneller maakt.

Hoewel het niet echt de bedoeling was, heeft het niet verifiëren van de kaarten van de AI eigenlijk nog een ander voordeel: als er een bug in de AI zit en de AI een ongeldige kaart zou kiezen, dan crasht het spel niet, maar faalt het gewoon stilletjes. Als u erover nadenkt, is dat eigenlijk best positief! Stel u voor dat dit niet het geval was, dan zou het spel blijven hangen als de AI per ongeluk een ongeldige kaart kiest, want we kunnen de AI niet gewoon zeggen om "het nog eens te proberen": de AI speelt deterministisch, dus hij zou telkens opnieuw diezelfde - ongeldige - kaart kiezen!

Het blijkt ook dat de bug zich niet altijd voordoet. Als de hand er als volgt had uitgezien

met andere woorden, met maar één kaart die Chris' ♦10 overtroeft, dan speelt de AI netjes ♦Q, zoals het hoort. De reden hiervoor is dat de AI een kortere weg neemt: als er maar één geldige optie is om te spelen, kiezen we gewoon die optie. Er is dan geen reden om de volledige AI-logica te doorlopen als er toch maar één geldige optie is. Dat maakt de AI een pak sneller. Dit verklaart waarschijnlijk ook waarom de bug zo lang onopgemerkt is gebleven, want meestal is er maar één kaart die overtroeft wat er al gespeeld is, en in dat geval volgt de AI dankzij deze kortere weg wel de regels.

Enkel wanneer er meerdere kaarten zijn om mee te overtroeven, doet de bug zich voor. De reden hiervoor is dat de logica om te beslissen wat er gespeeld moet worden in dit soort situaties grotendeels gebaseerd is op de AI van kleurenwiezen. Bij kleurenwiezen zijn de regels een stuk minder streng, en is de enige regel eigenlijk dat u de gespeelde kleur moet volgen.

Dit betekent dat de logica om in dit geval te beslissen wat er gespeeld moet worden geen rekening hield met het feit dat er beperkingen konden zijn op wat er gespeeld mag worden, en de code evalueerde gewoon alle kaarten van de kleur die gespeeld was. Iets in de trant van:

// Rangschik de kaarten, en kies dan de "beste" om te spelen.
function decide(player, trick) {
  let { suit } = trick;
  let cards = player.hand.suit(suit);
  let sorted = cards.sort(rankCards);
  return sorted[0];
}

Dit was een fout van mijn kant, en ik had dit moeten opmerken tijdens het testen van de AI. Gelukkig is Whisthub intussen bijgewerkt, en is de bug nu verholpen. De AI mag niet langer vals spelen!

Ik weet al wat sommigen onder u nu gaan zeggen:

Schaf toch gewoon die onnozele regel af dat je moet overtroeven, en laat ons gewoon ♦8 spelen! Dat had deze bug voorkomen.

Ik snap dat, en eerlijk gezegd heb ik dat zelf ook liever, maar ik heb beslist om exact dezelfde regels te gebruiken als IWWA, omwille van de consistentie en eenvormigheid. U kan ze hier opnieuw nalezen. Als zij deze regel ooit zouden aanpassen, dan volg ik natuurlijk graag. De regels zijn immers voor iedereen gelijk, nu ook inclusief de AI!

Wat hebben we vandaag geleerd? Wel, de belangrijkste les is dat ik er bij het ontwikkelen van de AI voor een nieuw spel voortaan voor moet zorgen dat de zetten van de AI tijdens simulaties tegen de spelregels geverifieerd worden. In de toekomst volgt er wellicht nog een blogpost over hoe de AI ontwikkeld is, maar het uitvoeren van simulaties - waarbij de AI tegen zichzelf speelt - is daar een fundamenteel onderdeel van. Het is ook zo dat ik heb kunnen verifiëren dat de valsspeelbug nu niet langer aanwezig is: na 200.000 gesimuleerde partijen volgden alle zetten van de AI de regels.

Mensheid vs AI: de mensen staan nog steeds op voorsprong!