Vertakkingsfactor & knooppuntentelling
Een zoekboom modelleert elke mogelijke reeks zetten vanaf een beginpositie. Elk knooppunt vertegenwoordigt een bordstatus. Elke rand vertegenwoordigt één legale zet. De structuur van de boom bepaalt of zoeken haalbaar blijft.
Belangrijkste parameters
Vertakkingsfactor b: aantal legale zetten beschikbaar op een typische positie.
Diepte d: aantal ply's (halve zetten) waaruit vooruit te zoeken.
Knooppuntentelling op diepte d: b^d
Totaal aantal knooppunten over alle dieptes: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Voor grote b en d benadert het totaal ≈ b^d (gedomineerd door het bladniveau).
4×4×4 Tic-Tac-Toe
De volledige zoekboom: b ≈ 64 (legale velden), d = 64 (totaal zetten). Volledig aantal knooppunten ≈ 64^64 ≈ 10^115. Het waarneembare universum bevat ongeveer 10^80 atomen. Brute-force zoeken is fysiek onmogelijk.
Zoekboomgrootte berekenen
Schaken voorziet in realistischere getallen. Gemiddelde vertakkingsfactor b ≈ 35. Een 6-ply zoeking (3 zetten per kant) vereist ongeveer 35^6 knooppunten.
Alpha-Beta Snoei: de exponent verminderen
Alpha-beta snoei elimineert subbomen die het minimax-resultaat niet kunnen beïnvloeden. Het belangrijkste inzicht: als je al weet dat één tak waarde V geeft, kun je elke zustertак pruimen wiens waarde aantoonbaar onder V (voor de maximaliseringssspeler) of boven V (voor de minimaliseringssspeler) valt.
Beste-geval geometrie
Bij optimale zet-ordening (beste zetten eerst doorzocht), reduceert alpha-beta de effectieve vertakkingsfactor van b naar √b. Zoekdiepte verdubbelt effectief voor dezelfde knooppunt-begroting:
Volledige zoeking: b^d knooppunten
Alpha-beta beste geval: b^(d/2) knooppunten
Voorbeeld: b=35, d=6. Volledig: 35^6 ≈ 1,84 × 10^9. Alpha-beta: 35^3 = 42.875. Reductiefactor: ~43.000.
In de praktijk is zet-ordening niet perfect. Typische reductie: b^(d×0,75) — equivalente vertakkingsfactor ≈ b^0,75.
Dualiteit tussen centrum en hoeken
Hamming merkt een geometrische dualiteit op in de 4×4×4 kubus: er bestaat een inversie die de 8 hoekposities naar de 8 middenpunten (de binnenste 2×2×2 kubus) en omgekeerd stuurt, terwijl alle 76 winnende lijnen behouden blijven.
Lijnen door een positie tellen
In een 4×4×4 kubus verschillen posities in hoeveel winnende lijnen er doorheen gaan:
Hoekposities: elk 7 lijnen (4 vlaksdiagonalen, 2 randlijnen, 1 ruimtediagonaal)
Middenpunten van randen: elk 4 lijnen
Middenpunten van vlakken: elk 6 lijnen
Middenpunten van lichaam (binnenste 2×2×2): elk 7 lijnen
De dualiteit brengt hoeken (7 lijnen) in kaart naar middenpunten van lichaam (7 lijnen). Beide sets vormen 'hete punten'.
Waarom hete punten geometrisch belangrijk zijn
Een speler die meer posities met veel lijnen controleert, controleert meer potentiële winnende lijnen. Dit is een direct geometrisch argument: maximalisering van lijndekking leidt zet-selectie zonder enige zoeking.
Evaluatiefuncties
Elk spelprogramma heeft een evaluatiefunctie nodig: een functie die bordstatussen toewijst aan numerieke waarden (positief = goed voor de maximaliseringssspeler, negatief = goed voor de minimaliseringssspeler). De evaluatiefunctie voorziet in de grensvoorwaarde bij de bladeren van de zoekboom.
Lineaire evaluatiefuncties
Een lineaire evaluatiefunctie wijst een gewicht w_i toe aan elk kenmerk f_i van de positie:
E(positie) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
Voor 4×4×4 tic-tac-toe kunnen kenmerken open lijnen onder controle, posities in vierkanten met veel lijnen, bedreigde vorken omvatten. Voor schaken: materiaalwaarde, centrumcontrole, veiligheid van de koning, pionnierstructuur.
Dit is een lineaire functie in kenmerkruimte — een hypervlak in ℝ^n. Twee posities met dezelfde kenmerkwaarden krijgen dezelfde evaluatie ongeacht alle andere verschillen. De geometrie van de evaluatiefunctie bepaalt wat het programma 'ziet'.
Samuels dammaprogramma verbeterde door de gewichtsvector w aan te passen — gradiëntdaling in de ruimte van lineaire evaluatiefuncties.
Meetkunde & de grens van formalisering
De zoekboom heeft een schone geometrische structuur: exponentiële groei op diepte d, reduceerbaar tot b^(d/2) door alpha-beta, verder reduceerbaar door zich tot hoog-waardige posities te beperken (hete punten verminderen effectieve b). De evaluatiefunctie definieert een hypervlak in kenmerkruimte.
Dit alles is schoon, nauwkeurig, formeel volledig. Het beschrijft het centrum van het spelprobleem — het gebied waar wiskundige structuur duidelijke begeleiding biedt.
De grens — waar u van regeltoepassing naar verkenning overschakelt, wanneer u positioneel voordeel voor tactische kansen inruilt, hoe u opkomende patronen voorbij de evaluatiefunctie herkent — weerstaat deze formalisering. Hammings impliciete kennis leeft op die grens.
De meetkunde laat je berekenen hoeveel zoeking je je kunt permitteren. Het vertelt je niet wat je moet zoeken.