Voordat de AI speelt, moet hij zijn zet vinden in een hooiberg van honderdvijftigduizend woorden, en daarna ophouden met zoeken.
In het Engels geschreven en geredigeerd. Deze Nederlandse versie is met machinevertaling gemaakt; waar precisie ertoe doet, is het Engelse origineel leidend. Lees het origineel in het Engels →
Geef iemand een volledige set WordChess-tegels en de opdracht “speel een goed woord”, en hij verkleint het probleem zonder te merken dat hij dat doet. De computer heeft zo’n intuïtie niet. Op een bord van 25×25, met een eigen volledige set van honderd tegels, kan hij bijna elk van 148.941 woorden uit het woordenboek proberen, en elk woord kan op duizenden geldige coördinaten en in verschillende richtingen worden neergelegd. Erger nog: een plaatsing is alleen geldig als elke nieuwe letter die ze toevoegt ook een echt woord vormt waar ze kruist met wat al op het bord ligt. Vermenigvuldig de woorden met de plaatsingen en met die kruisingseis, en je krijgt een zoekruimte die geen enkele speler, van silicium of niet, volledig kan opsommen en rangschikken.
Daarom brute-forcen serieuze woordspelengines, waaronder Quackle, de opensource-referentie-implementatie, nooit het hele woordenboek. 4 Met de GADDAG-structuur van Steven Gordon uit 1994, en de DAWG daarvoor, kan een programma woorden naar buiten laten groeien vanuit tegels die al op het bord liggen en onderweg de kruisingen controleren, zodat ongeldige takken vroeg afsterven in plaats van eerst gescoord en dan weggegooid te worden. 1 De opdracht is niet “noem elk woord”. Ze luidt: “genereer alleen de zetten die mogelijk geldig zijn, en doe dat snel”.
Zelfs een zuinige generator levert meer kandidaatzetten op dan grondig kunnen worden beoordeeld, dus het tweede probleem is tijd. Maven van Brian Sheppard, het eerste programma dat menselijke topspelers aftroefde, stond precies hiervoor en loste het in twee fasen op: een snelle heuristiek zet de ruwe zetten grofweg op volgorde van kwaliteit, en alleen een shortlist van de veelbelovendste wordt zorgvuldig bestudeerd door het spel vele malen vooruit te simuleren en te zien welke kandidaat het echt het best doet. 2 Andere spellen kennen hetzelfde idee onder andere namen, de rollout bij backgammon en de playout van go-programma’s; in Maven heet het simulatie.
WordChess werkt in dezelfde geest, maar onder een strengere voorwaarde: een vast zoektijdbudget per zet. Als het budget op is, legt de AI zich vast op het beste woord dat hij tot dan toe heeft gevonden. Dat is geen compromis waar de ontwikkelaars spijt van hebben; het is het hele ontwerp. Een speler die eindeloos nadenkt is geen betere tegenstander, alleen een tragere. De klok dwingt de machine te doen wat mensen instinctief doen: genoegen nemen met een zet die duidelijk goed is in plaats van aantoonbaar de beste.
Het woordenboek kennen is het makkelijke deel. Weten wanneer je moet ophouden met erin zoeken is het moeilijke.
De luie manier om een spel-AI makkelijker te maken is hem willekeurig dom te laten zijn, hem een zet te laten verprutsen die hij duidelijk zag. Spelers merken dat, en ze nemen het kwalijk. Ontwerper Sid Meier wordt vaak aangehaald omdat hij bondgenootschapsfuncties uit Civilization schrapte, omdat de computer die bijna even goed kon uitbuiten als een speler; het effect zou, in Meiers woorden zoals geciteerd in een beschrijving van het ontwerp van AI-tegenstanders, gamers achterlaten met “het gevoel dat ze niet konden winnen omdat de computer vals speelde”. 3 Moeilijkheid die als oneerlijkheid overkomt vergiftigt het spel, en daarom houdt het onderzoek naar dynamische moeilijkheidsaanpassing zich bezig met afstemmen waartoe de AI in staat is, niet met wat hij mag zien. 5
WordChess stemt zijn vier niveaus af langs assen die een mens zou herkennen, nooit door de AI verborgen informatie te geven. De niveaus verschillen in hoe lang ze mogen zoeken, hoe diep hun woordenschat in het zeldzame deel van het woordenboek reikt en welke woordlengtes ze verkiezen. Een makkelijke tegenstander speelt geloofwaardig zwakke woorden: echt, verstandig, kort, geen onzin. Een grootmeester deelt het hele obscure lexicon met het moeilijke niveau, en heeft de meeste tijd om het uit te pluizen. De speler verliest van iets wat eruitziet als een grotere woordenschat en een scherpere blik, omdat het precies dat is.
| Niveau | Bereik woordenschat | Zoekbudget | Voorkeur woordlengte |
|---|---|---|---|
| Makkelijk | Alleen gangbaar | Kortst | Kort |
| Normaal | Gangbaar + middel + helft van zeldzaam | Kort | Gemengd |
| Moeilijk | Volledig | Lang | Langer |
| Grootmeester | Volledig | Langst | Onbegrensd |
Een rekenmachine geeft elke keer hetzelfde antwoord; een tegenstander verrast je. WordChess voegt bij het kiezen bewust een willekeurige stap toe, zodat vrijwel gelijkwaardige zetten niet altijd op dezelfde manier worden beslist en de AI niet elke keer hetzelfde woord opnieuw speelt. Samen met de woordenschatplafonds per niveau levert dat afwisseling op: het gevoel dat er iemand tegenover je aan het bord zit die keuzes maakt, waarvan je sommige zelf ook had kunnen maken.
Dat is de stille kunst ervan. Een geloofwaardige tegenstander heeft evenveel terughoudendheid nodig als kracht: de bereidheid een gewoon goed woord te spelen, punten te laten liggen, verslaanbaar te zijn op een manier die verdiend aanvoelt. Het lastigste technische probleem van de machine was het doorzoeken van de hooiberg. Het subtielste was leren wanneer te stoppen met zoeken, wat te weten en hoeveel achter te houden.