Voordat de AI speelt, moet het zijn zet vinden in een hooiberg van honderdvijftigduizend woorden, en dan stoppen met zoeken.
Geef een persoon een WordChess-rack en de instructie "speel een goed woord", en hij verkleint het probleem zonder te beseffen dat hij dat doet. De computer beschikt niet over zo'n intuïtie. Op een 25×25 bord, met toegang tot de volledige pool van honderd tegels, kan het bijna elk van de 148,941 woorden uit de woordenlijst proberen, en elk woord kan op duizenden legale coördinaten en oriëntaties worden neergelegd. Erger nog, een plaatsing is alleen legaal als every het nieuwe letter dat het introduceert ook een echt woord voltooit waar het kruist met wat al op het bord ligt. Vermenigvuldig de woorden met de plaatsingen en met die kruisingsbeperking en je hebt een zoekruimte die geen speler, of die nu van silicium is of niet, volledig kan opsommen en rangschikken.
Dit is de reden waarom serieuze woordspelmotoren, Quackle, waaronder de open-source referentieimplementatie, nooit de woordenlijst brute-forcen.4 Steven Gordon's 1994 GADDAG structure, and the DAWG ervóór, laat een programma woorden naar buiten groeien vanaf tegels die al op het bord liggen en controleer kruisingen tijdens het proces, zodat illegale takken vroeg sterven in plaats van te worden gescoord en verworpen.1 De taak is niet "elk woord opsommen". Het is "alleen de zetten genereren die mogelijk legaal kunnen zijn, en dat snel doen."
Zelfs een slanke generator levert meer kandidaat-zetten op dan diep geëvalueerd kunnen worden, dus het tweede probleem is tijd. Het sterkste Scrabble-programma dat ooit is gebouwd, Brian Sheppard's Maven, stond precies voor dit probleem en beantwoordde het in twee fasen: een snelle heuristiek sorteert de ruwe zetten in een grove volgorde van kwaliteit, en alleen een shortlist van de meest belovende kandidaten wordt zorgvuldig bestudeerd door het spel vele malen vooruit te simuleren om te zien welke kandidaat daadwerkelijk het beste presteert.2 Sheppard leende de naam van het idee uit andere spellen, wat backgammon een rollout noemt en Go een playout, noemde hij simulatie.
WordChess werkt in dezelfde geest, maar onder een strengere beperking: een vast zoekbudget per zet. Wanneer het budget op is, gaat de AI over op het beste woord dat hij tot dusver heeft gevonden. Dit is geen compromis waar de ingenieurs spijt van hebben; het is het hele ontwerp. Een speler die voor eeuwig nadenkt, is geen betere tegenstander, slechts een langzamere. De klok dwingt de machine om te doen wat mensen instinctief doen: kiezen voor een zet die duidelijk goed is, in plaats van bewijsbaar de beste.
De woordenlijst is niet de geest van de tegenstander. De klok is dat wel.
De luie manier om een spel-AI makkelijker te maken, is hem willekeurig dom te maken, hem een zet te laten missen die hij duidelijk zag. Spelers merken dit op, en ze zijn er boos over. De ontwerper Sid Meier wordt vaak aangehaald voor het schrappen van Civilization functies waarmee de computer spelers in onderhandelingen kon verslaan, omdat het effect, zoals een beschrijving van het ontwerp van AI-tegenstanders het stelt, zou "spelers achterlaten met het gevoel dat ze niet konden winnen omdat de computer bedrogen speelde."3 Moeilijkheid die als oneerlijk wordt ervaren, vergiftigt het spel, en daarom bezigden zich de onderzoekspublicaties over dynamische moeilijkheidsaanpassing met het afstemmen van wat de AI in staat is, in plaats van 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. Elk niveau verschilt in hoe lang het mag zoeken, hoe diep in de zeldzame woordenlijst zijn vocabulaire reikt, en welke woordlengtebanden het favoriet heeft. Een makkelijk de tegenstander speelt aannemelijk zwakke woorden, echte, zinnige, korte, geen rommel. Een grootmeester heeft het hele obscure lexicon en de tijd om het te ontginnen. De speler verliest van iets dat lijkt op een betere woordenschat en scherpere lezing, omdat dat precies wat het is.
| Niveau | Reikwijdte woordenschat | Zoekbudget | Lengtevoorkeur |
|---|---|---|---|
| Makkelijk | Alleen gangbaar | Kortste | Kort |
| Normaal | Gangbaar + midden | Kort | Gemengd |
| Moeilijk | Breed | Lang | Langer |
| Grootmeester | Volledig zeldzaam | Langste | Onbeperkt |
Een rekenmachine geeft elke keer hetzelfde antwoord; een tegenstander verrast je. WordChess voegt een bewuste, gerandomiseerde, anti-kopieer-stap toe aan de selectie, zodat bijna gelijke zetten niet altijd op dezelfde manier worden opgelost en de AI niet simpelweg je laatste zet spiegelt. In combinatie met per-niveau woordgrenzen zorgt dit voor variatie, het gevoel dat er iemand aan de overkant van het bord zit die keuzes maakt, waarvan sommige jij ook had kunnen maken.
Dat is de stille kunst ervan. Een geloofwaardige tegenstander heeft evenveel terughoudendheid nodig als kracht: de bereidheid om een slechts goed woord te spelen, punten op tafel te laten liggen, en op een manier verslaanbaar te zijn die verdiend voelt. Het moeilijkste ingenieursprobleem van de machine was het zoeken in de hooiberg. Het subtielste was leren wanneer te stoppen met zoeken, wat te weten, en hoeveel terug te houden.