De Wiskunde Achter Wordfeud | helpmetwordfeud.nl

Wordfeud lijkt simpel: leg letters, scoor punten. Maar achter elke computerspeler draait een verrassend samenspel van datastructuren, zoekalgoritmen en wiskunde. Hoe vindt een computer in een fractie van een seconde de beste zet uit honderdduizenden mogelijkheden? Ik vond dat leuk om uit te zoeken, dus ik schreef het op.

Waarom brute-force niet werkt

Een Wordfeud-bord heeft 225 vakjes. Bij elke lege positie kun je horizontaal of verticaal een woord beginnen. Met een rek van 7 letters zijn er al $7! = 5{,}040$ permutaties per startpunt, en dan moet elk woord ook nog in een woordenboek staan en aansluiten op bestaande letters.

Naief alle combinaties proberen zou biljoenen checks kosten. Er is een slimmere aanpak nodig: een compacte datastructuur die razendsnel vertelt of een reeks letters een geldig woord vormt, gecombineerd met een algoritme dat alleen kansrijke posities bekijkt.

De Datastructuur: Trie en DAWG

De basis is een Trie (uitgesproken als "try"), ook wel een voorvoegselboom genoemd. Elk knooppunt in de boom stelt een letter voor, en paden van wortel naar blad vormen woorden. Zo delen woorden als boom, boor en boot dezelfde stam boo-.


      (wortel)
       ├── B
       │   └── O
       │       └── O
       │           ├── M ✓
       │           ├── R ✓
       │           └── T ✓
       └── K
           ├── A
           │   ├── T ✓
           │   └── N
           │       └── S ✓
           └── O
               └── P ✓

Het opzoeken van een woord kost $O(n)$ stappen, waarbij $n$ de woordlengte is, onafhankelijk van het aantal woorden in het woordenboek. Voor een typisch Wordfeud-woord van 6 letters betekent dit precies 6 stappen, of het woordenboek nu 1.000 of 1.000.000 woorden bevat.

Een DAWG (Directed Acyclic Word Graph) is een geoptimaliseerde variant die identieke suffixen samenvoegt. "BOOM" en "ROOM" delen niet alleen het pad voor "OOM", maar ook het eindknooppunt. Dit reduceert het geheugengebruik drastisch.

Zelf gebruik ik een compacte Trie, opgeslagen in een Uint32Array. Elke knoop neemt 27 geheugenposities in: 26 voor de kindknopen (A tot Z) en 1 voor een vlag die aangeeft of hier een geldig woord eindigt. Voor 340.000 Nederlandse woorden past de hele structuur in 20 tot 40 MB.

Het Appel & Jacobson Algoritme

In 1988 publiceerden Andrew Appel en Guy Jacobson een baanbrekend algoritme voor het vinden van alle geldige zetten in een kruiswoordspel. Hun methode is tot op de dag van vandaag de standaard in computerspelers voor Scrabble en Wordfeud. Het werkt in vier stappen.

Stap 1: Ankerpunten

Een ankerpunt is elk leeg vakje dat grenst aan een reeds gevuld vakje. Op een halfvol bord zijn er meestal 20 tot 60 ankerpunten, een fractie van de 225 vakjes. Het algoritme hoeft alleen deze posities te onderzoeken, omdat elk nieuw woord minstens één bestaande letter moet raken.

Stap 2: Kruiscontroles (Cross-checks)

Voor elk leeg vakje berekent het algoritme welke letters er mogen staan zonder een ongeldig kruiswoord te vormen. Dit wordt opgeslagen als een bitmask van 26 bits, één bit per letter van het alfabet. Een 1 op positie 4 betekent dat de letter E hier mag.

Voorbeeld: vakje met K erboven en N eronder

Alleen letters die K_N tot een geldig woord maken zijn toegestaan:

A (KAN) ✓ I (KIN) ✓ O (KON) ✓ U (KUN) ✓

Bitmask: 0000010001000001000000100000

Stap 3: Linkerdeel genereren

Vanuit elk ankerpunt genereert het algoritme alle mogelijke voorvoegsels (linkergedeelten) door tegelijkertijd de Trie af te lopen en letters uit het rek te gebruiken. De maximale lengte van een linkerdeel wordt begrensd door de afstand tot het vorige ankerpunt en het aantal beschikbare rekstenen.

Stap 4: Naar rechts uitbreiden

Elk geldig voorvoegsel wordt naar rechts uitgebreid door de Trie te volgen. Bij elke stap controleert het algoritme de kruiscontroles van het huidige vakje. Als we bij een terminal knooppunt komen (een knooppunt waar een geldig woord eindigt) en minstens één nieuwe tegel hebben gelegd, is er een geldige zet gevonden.

Dit hele proces wordt twee keer uitgevoerd: één keer voor horizontale zetten en één keer voor verticale (door het bord te transponeren).

GADDAG-variant: Een alternatieve datastructuur, de GADDAG, slaat woorden op in alle mogelijke prefix/suffix-combinaties. Dit maakt het linkerdeel overbodig, je loopt simpelweg vanuit elk ankerpunt de GADDAG af. Het nadeel: een GADDAG voor 340.000 woorden neemt 150 tot 300 MB in beslag, te veel voor mobiele apparaten. Daarom hou ik het bij de klassieke Trie-aanpak.

De Wiskundige Scoreberekening

De score van een Wordfeud-zet is een optelsom van drie onderdelen: het hoofdwoord, eventuele kruiswoorden, en een bingobonus.

Het hoofdwoord

Elke letter heeft een vaste puntwaarde $L_i$ . Op een bonusvakje wordt de letterwaarde vermenigvuldigd met een lettermultiplier $M_{L,i}$ (2 voor DL, 3 voor TL), en de totale woordscore met een woordmultiplier $M_{W,j}$ (2 voor DW, 3 voor TW). Let op: bonussen gelden alleen voor nieuw gelegde tegels.

\text{HoofdwoordScore} = \left(\sum_{i=1}^{n} L_i \times M_{L,i}\right) \times \prod_{j=1}^{k} M_{W,j}

Waar:

$L_i$ = puntwaarde van letter $i$ (joker = 0)
$M_{L,i}$ = lettermultiplier (1, 2 of 3), alleen voor nieuwe tegels
$M_{W,j}$ = woordmultiplier (2 of 3), alleen voor nieuwe tegels op DW/TW
$n$ = totaal aantal letters in het woord
$k$ = aantal DW/TW-vakjes met nieuwe tegels

Kruiswoorden

Elke nieuw gelegde tegel die een kruiswoord vormt (loodrecht op de speelrichting) levert extra punten op. Het kruiswoord wordt onafhankelijk gescoord, inclusief de bonus van het vakje waar de nieuwe tegel ligt:

\text{KruiswoordScore}_j = \left(\sum_{i=1}^{m} V_i + L_{\text{nieuw}} \times M_{L}\right) \times M_W

Hier is $V_i$ de waarde van de bestaande letters in het kruiswoord (zonder bonus, want die zijn al eerder gebruikt) en $L_{\text{nieuw}}$ de waarde van de nieuw gelegde letter, eventueel vermenigvuldigd met DL/TL.

Bingobonus

Gebruik je alle 7 stenen uit je rek in één beurt, dan krijg je een bingobonus van 40 punten. De totaalscore wordt dus:

\text{TotaalScore} = \text{HoofdwoordScore} + \sum_{j=1}^{k} \text{KruiswoordScore}_j + B

Waar $B = 40$ als alle 7 rekstenen zijn gebruikt, anders $B = 0$ .

Rekenvoorbeeld

Stel: je legt WATER horizontaal. De A valt op een DL-vakje, de T op een DW-vakje. Alle 5 letters zijn nieuw.

Letterwaardes: W=5, A=1, T=2, E=1, R=2

Met bonussen: W=5, A=1×2=2 (DL), T=2, E=1, R=2

Basissom: 5 + 2 + 2 + 1 + 2 = 12

Woordmultiplier: T staat op DW → ×2

Hoofdwoordscore: 12 × 2 = 24 punten

Waarom de hoogste score niet altijd de beste zet is

Tot nu toe ging het over het maximaliseren van de score per beurt. Maar in een echt spel speelt er meer mee. Professionele Scrabble- en Wordfeudspelers denken in termen van Expected Value (EV): de verwachte netto-opbrengst op langere termijn.

\text{EV} = \text{Score}_{\text{beurt}} + \text{Leave} - \text{Tegenstander Kans}

Rack Leave

Het rack leave is de waarde van de letters die na je beurt op je rek overblijven. Sommige letters (zoals veelvoorkomende klinkers en de S) zijn waardevoller dan andere (zoals de Q of X) omdat ze meer combinatiemogelijkheden bieden.

Een zet die 35 punten scoort maar je opzadelt met QXY op je rek, kan slechter zijn dan een zet van 28 punten die STER op je rek achterlaat.

Bordcontrole

Een ander strategisch element is bordcontrole: het beperken van de mogelijkheden voor je tegenstander. Een woord dat een TW-vakje opent voor de tegenstander kan kostbaar zijn, zelfs als het zelf hoog scoort. Omgekeerd kan een defensieve zet die minder scoort, maar geen bonusvakjes openlegt, op langere termijn meer opleveren.

Monte Carlo-simulatie

De meest geavanceerde computerspelers gebruiken Monte Carlo-simulatie om de EV te schatten. Voor elke kandidaat-zet simuleren ze honderden willekeurige verdere spelverloop-scenario's:

Speel de kandidaat-zet
Trek willekeurige letters voor de tegenstander (uit de resterende pool)
Laat de tegenstander de beste zet spelen
Herhaal voor meerdere beurten
Middel de nettoscores over alle simulaties

De zet met de hoogste gemiddelde nettoscore wint. Dit is een stochastische aanpak: geen garantie op het optimum, maar in de praktijk buitengewoon effectief.

Mijn helper richt zich op het vinden van de hoogst scorende zet, de eerste en belangrijkste stap. Voor recreatieve spelers is dat ruim voldoende: de hoogste score is in veruit de meeste situaties ook de beste zet. Rack leave en Monte Carlo-simulatie komen pas in beeld op het allerhoogste competitieve niveau.

Tot zover onder de motorkap

Zelf denk ik echt niet aan formules als ik zit te spelen, maar ik vind het leuk om te weten wat er gebeurt zodra je op “zoeken” drukt. De Trie zorgt voor razendsnelle lookups, het Appel & Jacobson algoritme vindt alle geldige zetten, en de scoreberekening telt bonusvakjes en kruiswoorden bij elkaar op.

En als je nog dieper wilt graven: rack leave, bordcontrole en Monte Carlo-simulatie laten zien dat het hoogst scorende woord vinden pas het begin is van strategisch spel. Veel plezier met je volgende potje.