Spellen en zoeken met tegenstanders

Zoeken in een spel begint met een toestand: genoeg informatie om te bepalen wat er vervolgens kan gebeuren. Bij boter-kaas-en-eieren betekent dat het bord en de speler die aan zet is. Het bord alleen is onvolledig, omdat het volgende teken afhangt van wie aan de beurt is.

Definieer de zes onderdelen

Een spelmodel bevat:

• Een begintoestand, $S_0$.
• Een functie, $\text{Aan-zet}(s)$, die de speler aanwijst die in toestand $s$ handelt.
• De toegestane zetten, $\text{Acties}(s)$.
• Een overgangsmodel, $\text{Resultaat}(s,a)$, dat de toestand na actie $a$ geeft.
• Een eindtoestandstest, $\text{Is-eindtoestand}(s)$, die het einde van het spel vaststelt.
• Een nutsfunctie, $\text{Nut}(s,p)$, die speler $p$ in een eindtoestand een numerieke opbrengst geeft.

Bij boter-kaas-en-eieren begin je met een leeg bord van 3×3 en X aan zet. Een actie kiest een leeg vakje. De overgang plaatst het teken van de huidige speler en wisselt de beurt. Het spel eindigt zodra iemand een rij, kolom of diagonaal van drie maakt, of als een vol bord gelijkspel oplevert. Geef vanuit het perspectief van X winst de score +1, gelijkspel 0 en verlies −1. De eindtoestandstest moet worden uitgevoerd voordat nog een teken wordt geplaatst: na winst gaat het spel niet verder.

Deel het spel langs afzonderlijke dimensies in

Deze dimensies zijn onafhankelijk. Dobbelstenen maken backgammon stochastisch, ook al is het bord zichtbaar. Verborgen kaarten gaan over informatie, niet over de vraag of een actie zelf willekeurig is. In een spel met verborgen informatie redeneert een speler over de mogelijke toestanden die overeenkomen met zijn waarnemingen; dit heet een kennistoestand.

Houd het perspectief voor de opbrengst vast

In een nulsomspel met twee spelers is de winst van de ene speler het verlies van de andere. Scores met een constante som gedragen zich op dezelfde manier: winst 1, verlies 0 en gelijkspel ½ voor elk tellen altijd op tot 1. Eén getal volstaat om de tegenstelling uit te drukken. Noem de speler die een grotere waarde wil MAX en de speler die een kleinere waarde wil MIN. Dit zijn rollen; MAX hoeft niet altijd wit of X te zijn.

Bij gewoon zoeken kan elke actie langs een pad worden gekozen. Een spelende agent moet reageren op zetten die hij niet bepaalt. Zijn oplossing is een strategie, die aangeeft wat hij moet doen in elke situatie waarmee hij te maken kan krijgen. Een plan dat alleen werkt als de tegenstander een gunstig antwoord geeft, is niet genoeg.

Een spelboom begint bij de huidige toestand. Elke uitgaande tak stelt één toegestane zet voor en de bijbehorende kindknoop is de resulterende toestand. Geef elke niet-terminale knoop de speler die daar handelt als label. In een spel met twee spelers die om de beurt spelen, wisselen MAX- en MIN-niveaus elkaar af.

Tel afzonderlijke beurten

Een halve zet is één zet van één speler. Bij schaken omvat een volledige zet meestal één beurt van wit en één van zwart, dus twee halve zetten. Een zoekactie tot diepte 4 vanaf de beurt van wit bereikt posities nadat wit, zwart, wit en zwart hebben gehandeld. Tel de takken vanaf de wortel, waarvan de diepte nul is.

Laat $b$ de vertakkingsfactor en $m$ de maximale diepte zijn. Een uniforme boom heeft $b^d$ knopen op diepte $d$ en $b^m$ bladeren. Het totale aantal knopen is:

Voor $b>1$ overheersen de diepste niveaus, wat exponentiële groei oplevert. Met vier zetten per positie heeft diepte 3 64 bladeren; diepte 4 heeft er 256. Eén extra halve zet vermenigvuldigt het aantal bladeren met vier, niet met één.

Onderscheid partijen van posities

Boter-kaas-en-eieren heeft maximaal $9!=362.880$ volgorden om het bord te vullen. Veel volgorden zouden doorgaan na een eerdere overwinning en zijn geen volledige toegestane partijen. Als het spel direct stopt bij winst, zijn er 255.168 volledige partijen: 131.184 keer winst voor X, 77.904 keer winst voor O en 46.080 keer gelijkspel. In toegestane spelverlopen zijn er slechts 5.478 verschillende bordposities, inclusief het lege bord.

Het verschil komt deels door zetverwisselingen: verschillende zetvolgorden die dezelfde toestand bereiken. X kan een hoek spelen, O het midden en X de tegenoverliggende hoek, of X kan die twee hoeken in omgekeerde volgorde spelen. Beide paden eindigen met hetzelfde bord en dezelfde speler aan zet. Een boom bewaart beide paden; een spelgraaf kan hun gedeelde toestand eenmaal opslaan. Om werk te hergebruiken moet je volledige toestanden herkennen, niet alleen borden die er hetzelfde uitzien.

Zie waarom volledig zoeken vastloopt

Schaken wordt vaak gemodelleerd met ongeveer 35 toegestane zetten per positie en een partij van 100 halve zetten, ofwel 50 zetten per speler. Dat geeft bij benadering de grootteorde:

Werkelijke takken eindigen op verschillende diepten en hebben verschillende aantallen zetten, maar deze schatting verklaart al waarom het onpraktisch is om een volledige schaakspelboom te enumereren. Op een leeg gobord van 19×19 heeft alleen de eerste steen al 361 mogelijke punten.

De zoekboom is wat een algoritme daadwerkelijk genereert. Gewone minimax genereert de volledige spelboom onder de toestand voor een eindig spel dat volledig wordt doorzocht. Snoeien, dieptelimieten en selectieve simulatie genereren minder. Een blad waar het zoeken wordt afgebroken kan daarom een onvoltooide positie zijn, terwijl een blad van de volledige spelboom een eindtoestand is.

Stel je een strategie binnen de boom voor

Een strategiedeelboom voor MAX behoudt één gekozen tak bij elke MAX-knoop en elke toegestane tak bij elke MIN-knoop. MAX kiest zijn eigen actie, maar moet een antwoord behouden op elke zet van de tegenstander. Eén pad van wortel naar blad beschrijft slechts één mogelijk spelverloop. Het kan niet laten zien dat het gekozen plan ook tegen de andere antwoorden standhoudt.

Minimax kiest het beste resultaat dat MAX tegen optimaal tegenspel kan veiligstellen. Elk bladnut wordt voor MAX gemeten. Een groot getal is gunstig voor MAX, ook wanneer de geëvalueerde knoop bij MIN hoort.

Werk van de bladeren naar de wortel

Geef bij een eindknoop het nut terug. Geef bij een MAX-knoop de grootste waarde van de kindknopen terug. Geef bij een MIN-knoop de kleinste terug. Ga door totdat de wortel een waarde krijgt:

Een waarde van een kindknoop vat het optimale vervolg vanaf die kindknoop al samen. Daarom vergelijkt een ouderknoop de teruggegeven waarden in plaats van elk onderliggend blad opnieuw te bekijken. De recursie werkt door een willekeurig aantal afwisselende niveaus heen.

Doorloop een beslissing van twee halve zetten

MAX heeft drie zetten, die elk naar een MIN-knoop leiden:

Neem eerst het minimum binnen elke rij. MIN kan A 4 waard maken, B 2 en C 5. Daarna neemt MAX het maximum van die drie resultaten:

De minimaxwaarde is 5. De minimaxbeslissing is de zet naar C. Het ene is een getal dat de positie beschrijft; het andere is een actie die het programma kan spelen.

Het grootste blad, 15, ligt onder B, maar MAX bepaalt niet welk antwoord dat blad bereikt. MIN zou 2 kiezen. Het gemiddelde van de bladeren van B is 10, wat er ook aantrekkelijk uitziet, maar middelen modelleert een willekeurige keuze met passende kansen. Optimaal tegenspel vraagt om een minimum.

Lees de hoofdvariant af

De hoofdvariant is het spelverloop dat wordt gevolgd wanneer de spelers optimale zetten kiezen. Hier speelt MAX C en kiest MIN zijn blad met waarde 5. Volg in een diepere boom op elk niveau het gekozen maximum of minimum. Het eindnut op dat pad komt overeen met de wortelwaarde. Als meerdere zetten gelijk eindigen, kan meer dan één optimaal spelverloop bestaan.

Begrijp de garantie

Voor een eindig deterministisch nulsomspel met twee spelers en volmaakte informatie garandeert het volgen van de minimaxstrategie ten minste de wortelwaarde. Een optimale tegenstander beperkt MAX tot die waarde. Een fout van de tegenstander kan een beter resultaat mogelijk maken, dus 5 is een ondergrens, geen voorspelling dat elke partij op precies 5 moet eindigen.

Een programma kan zwakte uitbuiten en die ondergrens behouden. Als twee zetten allebei minimaxwaarde 5 hebben, kan het de voorkeur geven aan de zet die de tegenstander meer kansen op een fout biedt. Een zet met minimaxwaarde 2 kiezen omdat daar een verleidelijke 15 onder ligt, geeft de garantie van 5 op. Het verschil is of de zet de beste waarde voor het slechtste geval behoudt.

De minimaxdefinitie is al een recursief programma. Een waardefunctie neemt een toestand en geeft een getal terug. Een zoekfunctie vergelijkt de mogelijke eerste zetten en geeft de te spelen actie terug.

Scheid zetkeuze van waardeberekening

De volgende pseudocode gaat ervan uit dat MAX bij de wortel handelt en dat de beurten afwisselen:

MINIMAX-SEARCH(s):
    if Is-Terminal(s): return no action
    bestMove = no action
    bestValue = -infinity
    for a in Actions(s):
        value = MIN-VALUE(Result(s, a))
        if value > bestValue:
            bestValue = value
            bestMove = a
    return bestMove

MAX-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a)))
    return v

MIN-VALUE(s):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a)))
    return v

Initialiseer MAX met min oneindig zodat elke kindknoop die waarde verbetert; initialiseer MIN met plus oneindig. Test of het spel is geëindigd voordat je opvolgers genereert. Een vol bord bij boter-kaas-en-eieren zonder rij van drie is gelijkspel, geen niet-terminale positie waarvan de beste zet uit een lege lijst moet worden gekozen.

Volg wat de recursie ontdekt

Bekijk dit bord voor boter-kaas-en-eieren, met X aan zet en een punt voor een leeg vakje:

X O X
. O .
. . .

O dreigt de middelste kolom te vullen. Als X ergens anders dan middenonder speelt, kan O de volgende beurt winnen. Die zetten hebben waarde −1 voor X. Middenonder spelen blokkeert de onmiddellijke winst en maakt gelijkspel mogelijk bij optimaal spel, met waarde 0. De wortel geeft middenonder terug. Het algoritme heeft geen afzonderlijke instructie nodig die deze dreiging benoemt: de einduitkomsten bepalen de waarden.

Begroot tijd en geheugen

Diepte-eerstminimax bekijkt $O(b^m)$ knopen bij vertakkingsfactor $b$ en maximale diepte $m$. Het opslaan van alle gegenereerde knopen met dezelfde ouder op elk actief niveau vereist $O(bm)$ geheugen. Opvolgers één voor één genereren vermindert de opslag voor het actieve zoeken tot $O(m)$, afgezien van de toestandsrepresentatie. Exponentiële tijd, niet de recursiestapel, is meestal het grootste obstakel.

Behoud de scoreconventie

In MAX/MIN-code geeft elke aanroep het nut van MAX terug. Draai het teken niet om alleen omdat MIN daarna handelt. Negamax gebruikt een andere conventie: elke waarde is vanuit het perspectief van de huidige speler, zodat een waarde van een kindknoop wordt ontkend voordat de ouderknoop die maximaliseert:

Voor een spel dat in minder dan 100 halve zetten eindigt, kan de timing worden meegenomen door winst voor MAX op diepte $d$ te scoren als $100-d$, verlies als $-100+d$ en gelijkspel als 0. Snellere winst scoort dan hoger en uitgesteld verlies is minder negatief. De strikte dieptelimiet houdt elke winst positief en elk verlies negatief.

Zo scoren overwinningen bij halve zet 3 en 7 respectievelijk 97 en 93, zodat de snellere winst de voorkeur krijgt. Verliezen op die diepten scoren −97 en −93, waardoor het latere verlies de voorkeur krijgt terwijl beide slechter blijven dan gelijkspel.

Eén nutswaarde voor MAX werkt wanneer de belangen van twee spelers strikt tegengesteld zijn. Bij meerdere spelers of overlappende belangen houd je een nutsvector bij. Voor spelers A, B en C geeft de vector (1, 2, 6) hun opbrengsten in die volgorde.

Selecteer op basis van het element van de actieve speler

Vergelijk bij een knoop waar C handelt de derde elementen van de kindvectoren. Geef de volledige vector terug van de kindknoop die C verkiest. Vergelijk bij een B-knoop de tweede elementen van die teruggegeven vectoren; vergelijk bij een A-knoop de eerste.

Maximaliseer niet elk element onafhankelijk. Als de beschikbare uitkomsten (1, 2, 6) en (4, 2, 3) zijn, kiest C (1, 2, 6). De combinatie (4, 2, 6) is geen beschikbare uitkomst en kan niet worden teruggewerkt.

Werk terug door drie spelers

A zet eerst, dan B en dan C. Na de linkerzet van A kiest B tussen twee C-knopen:

• De eerste heeft bladeren (1, 2, 6) en (4, 2, 3). C kiest (1, 2, 6).
• De tweede heeft bladeren (6, 1, 2) en (7, 4, 1). C kiest (6, 1, 2).

B vergelijkt de tweede elementen 2 en 1, dus de linkertak geeft (1, 2, 6) terug.

Na de rechterzet van A:

• C kiest (5, 4, 5) boven (2, 5, 4), omdat 5 groter is dan 4 in het derde element.
• C kiest (5, 2, 4) boven (7, 7, 1), omdat 4 groter is dan 1 in het derde element.

B vergelijkt de tweede elementen 4 en 2, dus de rechtertak geeft (5, 4, 5) terug. Ten slotte vergelijkt A de eerste elementen 1 en 5 en kiest rechts. De wortel krijgt de volledige vector (5, 4, 5).

Geef aan hoe gelijke waarden worden afgehandeld

Als C (2, 3, 4) of (6, 1, 4) kan kiezen, leveren beide C 4 op. De uiteindelijke opbrengst van A kan 2 of 6 zijn. Een voorspelling vereist een keuzeregel bij gelijke waarden of een model van de keuze van C. Dat een andere speler geen voorkeur heeft, hoeft voor de speler bij de wortel niet onschadelijk te zijn.

Als twee achtervolgers allebei willen dat MAX wordt gevangen, heeft een ronde één MAX-laag en een MIN-laag voor elke achtervolger. Met twee achtervolgers is één ronde drie halve zetten. Dit model verschilt van drie onafhankelijke spelers die hun eigen beloningen nastreven.

Laat belangen overlappen

In een spel met variabele som kunnen beide spelers de voorkeur geven aan (100, 100) boven lagere gezamenlijke opbrengsten. Spelers kunnen ook tijdelijk voordeel hebben bij het aanvallen van een gemeenschappelijke koploper. Zulk gedrag dat op een bondgenootschap lijkt, kan uit hun eigen voorkeuren volgen en veranderen wanneer de positie verandert.

Gewone alfa-bèta-afbrekingen berusten op tegengestelde belangen en zijn niet direct overdraagbaar op nutsvectoren. Het paranoïde model herstelt een tegenstelling tussen twee spelers, waardoor alfa-bètazoeken mogelijk is, maar kan gecoördineerde vijandigheid voorspellen waarvoor de andere spelers in werkelijkheid niet zouden kiezen.

Alfa-bètasnoei geeft dezelfde wortelwaarde als minimax op dezelfde boom met dezelfde bladwaarden. De methode bespaart werk door te bewijzen dat sommige takken de keuze niet kunnen verbeteren. Optimale zetten met gelijke waarden kunnen in een andere volgorde worden teruggegeven.

Geef een zoekvenster langs het pad door

Twee grenzen beschrijven de beschikbare keuzes boven de huidige knoop:

• $\alpha$ is de beste beschikbare waarde voor MAX langs het pad: MAX kan al ten minste deze waarde behalen.
• $\beta$ is de beste beschikbare waarde voor MIN langs het pad: MIN kan MAX al tot hoogstens deze waarde beperken.

Begin bij de wortel met min en plus oneindig. Elke recursieve kindknoop ontvangt de huidige grenzen. Het zijn lokale argumenten, geen globale getallen die tussen onafhankelijke zoekacties in knopen met dezelfde ouder worden gedeeld.

Houd bij een MAX-knoop de grootste waargenomen waarde van de kindknopen bij. Stop wanneer die bèta bereikt of overschrijdt: MIN hoger in de boom heeft al een alternatief dat niet groter is dan bèta. Verhoog anders alfa wanneer MAX een verbetering vindt. Houd bij een MIN-knoop de kleinste waargenomen waarde van de kindknopen bij. Stop wanneer die alfa bereikt of daaronder komt: MAX hoger in de boom heeft al een alternatief dat minstens even goed is. Verlaag anders bèta.

MAX-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = -infinity
    for a in Actions(s):
        v = max(v, MIN-VALUE(Result(s, a), alpha, beta))
        if v >= beta: return v
        alpha = max(alpha, v)
    return v

MIN-VALUE(s, alpha, beta):
    if Is-Terminal(s): return Utility(s, MAX)
    v = +infinity
    for a in Actions(s):
        v = min(v, MAX-VALUE(Result(s, a), alpha, beta))
        if v <= alpha: return v
        beta = min(beta, v)
    return v

De wortel vergelijkt acties en behoudt alfa tussen de acties:

ALPHA-BETA-SEARCH(s):
    if Is-Terminal(s): return no action
    alpha = -infinity
    beta = +infinity
    bestMove = no action
    for a in Actions(s):
        v = MIN-VALUE(Result(s, a), alpha, beta)
        if v > alpha:
            alpha = v
            bestMove = a
    return bestMove

Doorloop een afbreking bij MIN

Doorzoek de MIN-takken A = (4, 9, 6), B = (2, 15, 13) en C = (5, 8, 10), van links naar rechts. A moet alle drie de bladeren bekijken en geeft 4 terug. De wortel heeft nu alfa 4. Het eerste blad van B is 2. Het uiteindelijke minimum kan alleen op 2 blijven of dalen, dus B kan A niet overtreffen. Sla de twee resterende bladeren van B over. C bekijkt alle drie de bladeren en geeft 5 terug. De wortel kiest C na zeven van de negen bladeren te hebben bekeken.

Doorloop een afbreking bij MAX

Stel dat een MIN-ouderknoop al een kindknoop met waarde 3 heeft, waardoor bèta op 3 staat. Zijn volgende MAX-kindknoop vindt een blad met waarde 6. De waarde van die kindknoop is minstens 6, dus MIN geeft de voorkeur aan de al gevonden 3. Sla de resterende kindknopen van die MAX-knoop over. De redenering voor de afbreking gebruikt het alternatief van MIN, ook al is de huidige knoop een MAX-knoop.

Een gesnoeide MIN-knoop kan een bovengrens teruggeven; een gesnoeide MAX-knoop kan een ondergrens teruggeven. Hun exacte waarden blijven onbekend. De voltooide wortelwaarde is exact voor de doorzochte boom. Ook gelijkheid staat een afbreking toe, omdat een tak die hoogstens gelijk kan eindigen de huidige beste waarde niet kan verbeteren.

Alfa-bètasnoei bespaart het meeste werk wanneer sterke zetten vroeg worden doorzocht. De waarden veranderen niet met de zetvolgorde; het moment waarop de zoekmethode een afbreking kan bewijzen wel.

Vergelijk twee volgorden

Voor de drie MIN-takken A = (4, 9, 6), B = (2, 15, 13) en C = (5, 8, 10) worden bij een begin met A zeven bladeren bekeken. Begin in plaats daarvan met C. Zijn drie bladeren stellen alfa 5 vast. A vindt dan direct 4 en breekt af; B vindt direct 2 en breekt af. Slechts vijf bladeren worden geëvalueerd en het antwoord blijft C met waarde 5.

Voor een uniforme boom met volmaakte ordening is het aantal bladeren:

Dit is ongeveer $O(b^{m\mathrm{/}2})$ in plaats van de $O(b^m)$ van minimax. De effectieve vertakkingsfactor daalt tot ongeveer $\sqrt{b}$, waardoor bij een vergelijkbaar budget ongeveer tweemaal de diepte mogelijk is. Bij $b=35$ evalueert een zoekactie tot diepte 8 met volmaakte ordening 3.001.249 bladeren; gewone minimax tot diepte 4 heeft 1.500.625 bladeren. De vergelijking gaat over de grootteorde, niet over een identieke looptijd.

Bij de slechtste volgorde kan alfa-bètasnoei elk minimaxblad bekijken. De extra grenscontroles kosten tijd, ook als ze geen bladeren besparen.

Gebruik goedkope aanwijzingen voor de ordening

De exacte beste zet is vóór het zoeken onbekend. Programma's gebruiken snelle schattingen. Bij schaken kunnen ze slagzetten proberen, dan dreigingen en dan rustige zetten. Een killerzet veroorzaakte elders op dezelfde zoekdiepte een afbreking en wordt vroeg in een andere positie geprobeerd. Deze aanwijzingen beïnvloeden de efficiëntie; ze rechtvaardigen niet dat de andere toegestane zetten worden weggegooid.

Iteratieve verdieping zoekt tot diepte 1, dan 2, dan 3 enzovoort. Een sterke zet uit de vorige iteratie wordt een vroege kandidaat in de volgende. Het diepste voltooide resultaat ligt ook klaar als de tijd verstrijkt.

Het herhaalde werk heeft verschillende kosten afhankelijk van het snoeien. Bij ongesnoeid uniform zoeken met vertakkingsfactor 35 voegen alle ondiepere iteraties ongeveer $1\mathrm{/}(35-1)\approx \mathrm{2,9}\mathrm{\%}$ toe aan de laatste zoekactie. Bij alfa-bètasnoei met volmaakte ordening evalueren diepten 1 tot en met 7 samen 1.677.159 bladeren, ongeveer 56% van het aantal op diepte 8. Betere ordening kan het totale proces nog steeds de moeite waard maken.

Sla posities op met hun betekenis

Een transpositietabel slaat resultaten op met de volledige speltoestand als sleutel. Als een andere zetvolgorde die toestand bereikt, kan het programma een geschikt item hergebruiken. Sla de doorzochte diepte op en of het resultaat exact is, een ondergrens of een bovengrens. Een ondiep item vervangt niet de informatie die een diepere zoekactie vereist. Een grens kan een venster versmallen of een afbreking rechtvaardigen, maar mag niet als exacte waarde worden behandeld.

Een evaluatiefunctie schat hoe gunstig een onvoltooide positie voor MAX is. Ze maakt zoeken met een dieptelimiet mogelijk: het zoekfront krijgt geschatte waarden die door minimax of alfa-bètasnoei kunnen worden teruggewerkt.

Maak scores bruikbaar voor het zoeken

Een goede evaluator is snel, komt overeen met de ordening van werkelijke einduitkomsten en hangt bij niet-terminale posities samen met succes. Eindtoestanden zelf moeten hun exacte nut krijgen. Een overwinning van MAX moet hoger scoren dan elke niet-terminale schatting, zodat stukken verzamelen niet aantrekkelijker kan worden dan winnen.

Een manier om naar evaluatie te kijken is posities te groeperen op gedeelde kenmerken. Als zo'n groep 72% winst, 8% gelijkspel en 20% verlies oplevert, met nutswaarden 1, ½ en 0, is het gemiddelde nut:

Deze interpretatie hangt af van hoe posities en voortzettingen zijn geselecteerd. Het is een schatting van de kwaliteit van de uitkomst, geen bewijs van een afgedwongen overwinning.

Tel gewogen kenmerken op

Een veelgebruikt ontwerp is een gewogen som:

Elk kenmerk $f_i(s)$ meet een eigenschap van de positie; elk gewicht $w_i$ geeft aan hoeveel het bijdraagt. Verschillen tussen de spelers houden het perspectief helder. Een positief materiaalverschil betekent dat MAX meer materiaal heeft.

Traditionele schaakwaarden zijn pion 1, paard 3, loper 3, toren 5 en dame 9. Aan de koning wordt geen materiaalwaarde als te slaan stuk toegekend. Stel dat MAX wit is. Wit heeft een dame, twee torens, een loper en zes pionnen:

Zwart heeft twee torens, twee paarden, een loper en zeven pionnen:

Het materiaalkenmerk is daarom $28-26=2$. Als wit 30 toegestane zetten heeft en zwart 24, is het mobiliteitsverschil 6. Met materiaalgewicht 1 en mobiliteitsgewicht 0,1:

Die 2,6 is een kenmerkscore, geen winstkans van 260%. De gewichten bepalen de schaal ervan.

Houd rekening met kenmerken die op elkaar inwerken

Een eenvoudige lineaire som geeft elk kenmerk een vaste bijdrage onafhankelijk van de andere. De werkelijke spelwaarde kan afhangen van combinaties: een paar lopers kan meer waard zijn dan de som van hun afzonderlijke effecten, en het belang van een pion kan in een eindspel veranderen. Gecombineerde kenmerken, gewichten die afhangen van de spelfase of niet-lineaire evaluatoren kunnen deze effecten vastleggen. Gewichten kunnen op basis van een inschatting worden gekozen of worden aangepast aan uitkomsten van vastgelegde partijen.

Meer kenmerken kosten ook tijd. Een uitgebreide evaluator die een extra nuttige halve zoekzet verhindert, kan de beslissing verslechteren, zelfs als de afzonderlijke schattingen beter worden.

Stem de schaal af op de regel voor terugwerken

Bij deterministische minimax behouden consequent toegepaste strikt stijgende transformaties de ordening via maxima en minima. Als alle scores positief zijn, behoudt kwadrateren bijvoorbeeld hun volgorde. Willekeurige scores met een positief of negatief teken kwadrateren doet dat niet. Bij toevalsknopen zijn de werkelijke afstanden tussen nutswaarden van belang omdat de waarden worden gemiddeld. Een score die alleen is ontworpen om posities te rangschikken, moet worden gekalibreerd voordat die verwacht nut kan weergeven.

Heuristische minimax stopt voordat het spel eindigt. Het antwoord is optimaal voor de doorzochte boom met de toegekende scores aan het zoekfront. De methode kan in het werkelijke spel toch een verliezende zet kiezen als die schattingen missen wat er daarna gebeurt.

Onderscheid eindtoestanden van afbreekpunten

Een eindtoestand heeft een bekende uitkomst. Bij een afbreking op de dieptelimiet is het spel nog niet afgelopen en is een schatting nodig. Test ze in die volgorde:

H-MINIMAX(s, d):
    if Is-Terminal(s): return Utility(s, MAX)
    if Is-Cutoff(s, d): return Eval(s)
    if To-Move(s) == MAX:
        return max over a of H-MINIMAX(Result(s, a), d + 1)
    return min over a of H-MINIMAX(Result(s, a), d + 1)

De afbreektest controleert meestal of de diepte een limiet heeft bereikt. Alfa-bètasnoei kan deze heuristische boom op dezelfde manier snoeien. Het snoeien blijft exact ten opzichte van die waarden aan het zoekfront; het verandert schattingen niet in werkelijke speluitkomsten.

Binnen een tijdslimiet behoudt iteratieve verdieping de actie uit de diepste voltooide iteratie. Bij een gedeeltelijk doorzochte diepere wortel kan de eerste tak de voorkeur krijgen, alleen doordat de alternatieven nog niet zijn geëvalueerd.

Maak een tactische slagwisseling af

Een rustige positie is rustig genoeg dat een korte gedwongen voortzetting de evaluatie waarschijnlijk niet sterk verandert. Rustzoeken gaat in onrustige posities voorbij de normale diepte door, meestal door slagzetten te volgen totdat de slagwisseling voorbij is.

Stel dat de witte dame precies op de dieptelimiet een pion slaat. De materiaalscore verbetert met 1. Maar zwart kan de dame in de volgende halve zet terugslaan. De nettoverandering in materiaal is:

Stoppen na de eerste slagzet meldt +1; een korte zoekverdieping met slagzetten onthult −8. Het probleem is evalueren midden in een slagwisseling, niet een tekortkoming van de regel waarmee minimax waarden terugwerkt.

Herken uitgesteld verlies

Het horizoneffect treedt op wanneer een programma een onvermijdelijk verlies uitstelt tot voorbij de zoekdiepte. Een ingesloten loper kan na enkele schaakzetten met pionnen alsnog verloren gaan. Als de zoekmethode de schaakzetten ziet maar stopt voordat de loper wordt geslagen, kan het programma pionnen weggeven om dat toekomstige verlies te verhullen.

Een singuliere zoekverdieping zoekt dieper langs een zet die duidelijk boven de alternatieven uitsteekt. Programma's zoeken ook verder na dwingende schaakzetten of terugslagen. Zoekverdiepingen besteden extra diepte aan geselecteerde spelverlopen; ze vereisen een budget zodat een zoekactie nog kan worden voltooid.

Voorwaarts snoeien, zoals alleen enkele beste zetten behouden, kan de winnende zet weggooien. De besparing gaat niet gepaard met de garantie van alfa-bètasnoei.

Vervang zoeken door exact opgeslagen kennis

Een openingsboek levert bestudeerde openingszetten. Eindspeldatabases werken met retrograde analyse terug vanaf bekende uitkomsten. Schaakeindspeldatabases voor zeven stukken omvatten de twee koningen en leveren exacte resultaten voor de eindspelen die ze bestrijken. De regels en toestandsinformatie van een opzoekresultaat moeten overeenkomen met het gespeelde spel.

Een toevalsknoop stelt een toevalsgebeurtenis voor. De takken geven mogelijke uitkomsten en hun kansen weer, die optellen tot 1. Geen enkele speler kiest de gunstigste tak.

Gebruik de regel die bij elke knoop hoort

Voor uitkomsten $r$ heeft een toevalsknoop de waarde:

Expectiminimax combineert alle vier de regels. Expectimax gebruikt MAX en toeval wanneer er geen minimaliserende speler is. Een kansmodel van een willekeurig spelende tegenstander kan zelfs in een spel met deterministische zetregels toevalstakken opleveren.

Werk terug door toeval en tegenspel

MAX kiest L of R. Elke zet leidt tot een toevalsgebeurtenis, gevolgd door een keuze van MIN.

Na L levert een zuivere muntworp twee MIN-knopen op. Hun bladeren zijn (3, 7) en (8, 4). MIN geeft 3 en 4 terug. De toevalsknoop geeft dan:

Na R leiden kansen 0,25 en 0,75 naar MIN-knopen met bladeren (10, 1) en (6, 5). Hun waarden zijn 1 en 5, dus:

MAX kiest R omdat 4 groter is dan 3,5. Als je eerst de oorspronkelijke eindbladeren zou middelen, zou toeval de beslissing van MIN vervangen. Verwerk elke knoop nadat de kindknopen zijn afgehandeld.

Ken de juiste kansen toe

Twee zuivere dobbelstenen hebben 36 even waarschijnlijke geordende uitkomsten. Backgammon groepeert omgekeerde volgorden, zoals 3–5 en 5–3, als dezelfde worp. Dat geeft 21 verschillende worpen: zes dubbele worpen met elk kans 1/36 en 15 niet-dubbele worpen met elk kans 1/18. De controle is:

Alle 21 worpen kans 1/21 geven zou dubbele worpen te zwaar en niet-dubbele worpen te licht laten meetellen. Takken die er gelijk uitzien, hoeven geen gelijke kansen te hebben.

Als elke beslissingsfase $b$ toegestane zetten en een toevalsgebeurtenis met $n$ uitkomsten heeft, kost het doorzoeken van $m$ zulke fasen ongeveer $O(b^m{n}^m)$. De diepteconventie moet rekening houden met hoe vaak toeval optreedt. Met ongeveer 20 toegestane zetten en 21 worpen beperken de extra toevalstakken bij backgammon al snel hoe ver volledig vooruit kan worden gekeken.

Zo leveren twee fasen met elk 21 toevalsuitkomsten en 20 acties $(21\times 20{)}^2=176.400$ paden op. Tel de toevalsgebeurtenissen afzonderlijk van de halve zetten van spelers wanneer je die kosten schat.

Snoei alleen als ongeziene uitkomsten begrensd zijn

Een gedeeltelijk gemiddelde is geen minimaxgrens. Als nutswaarden tussen 0 en 10 liggen en de eerste van twee even waarschijnlijke uitkomsten 2 waard is, ligt de waarde van de hele knoop tussen 1 en 6. In het bijzonder:

Als MAX al een andere zet met waarde 7 heeft, kan deze toevalsknoop die niet overtreffen en kan de resterende uitkomst worden overgeslagen. Zonder een geschikte grens voor ongeziene waarden kan een extreme uitkomst het gemiddelde nog genoeg veranderen om de keuze om te keren.

Minimax vraagt welk resultaat een tegenstander kan afdwingen. Expectimax vraagt welk gemiddeld nut uit een kansmodel volgt. Hun beslissingen kunnen zelfs op dezelfde boom verschillen, omdat ze verschillend gedrag weergeven.

Vergelijk optimaal en willekeurig tegenspel

Voor MIN-takken A = (4, 9, 6), B = (2, 15, 13) en C = (5, 8, 10) kiest minimax C met een garantie van 5. Als de tegenstander daarentegen elk antwoord uniform willekeurig kiest, zijn de verwachtingswaarden ongeveer 6,33, 10 en 7,67. Expectimax kiest B.

Dat is verstandig volgens het uniforme model, maar een vaardige tegenstander kan B met 2 beantwoorden. Expectimax neemt niet aan dat de tegenstander een gemiddelde minimaliseert. Het gebruikt de opgegeven kansen. Met een correct model maximaliseert het het verwachte nut; de bescherming in het slechtste geval is zwakker dan die van minimax. De gemiddelde prestatie kan gelijk zijn aan die van minimax wanneer beide dezelfde zet aanbevelen.

Een boom kan modellen combineren. De knoop van een vijandige agent neemt een minimum, terwijl de knoop van een willekeurig spelende agent een gewogen gemiddelde neemt. Gebruik de regel voor de agent die bij die knoop handelt, niet één regel voor elke laag die geen MAX-laag is.

Zie waarom alleen de volgorde niet volstaat

Stel dat zet A 2 geeft met kans 0,6 en 3 met kans 0,4. Zet B geeft 1 met kans 0,6 en 4 met kans 0,4:

A heeft de grotere verwachtingswaarde. Verhef nu elke eindwaarde tot de derde macht. Hun rangorde blijft hetzelfde, maar de verwachtingswaarden worden:

B wint nu de vergelijking. Getransformeerde uitkomsten middelen is iets anders dan hun gemiddelde transformeren. Verheffen tot de derde macht versterkt het voordeel van de hoge uitkomst van B genoeg om de beslissing te veranderen.

Behoud beslissingen met de juiste transformaties

Een positieve affiene transformatie vermenigvuldigt elke verwachtingswaarde met hetzelfde positieve getal en telt dezelfde constante op. Toepassing van $10x+5$ geeft A waarde 29 en B waarde 27, zodat A de voorkeur houdt.

Als A en B MIN-knopen waren, zouden hun waarden 2 en 1 zijn vóór het verheffen tot de derde macht en 8 en 1 daarna. Hun volgorde zou ongewijzigd zijn. Maxima en minima selecteren een waarde van een kindknoop; gemiddelden combineren de grootte van meerdere waarden.

Een evaluator die bij toeval wordt gebruikt, moet daarom het bedoelde verwachte nut op een consistente schaal schatten, zoals de winstkans of een positieve affiene transformatie daarvan. Een niet-lineaire rangschikkingsscore kan geschikt zijn voor deterministische minimax, maar bij toeval tot verkeerde afwegingen van risico leiden.

Monte-Carlo-boomzoeken, of MCTS, schat zetten op basis van gesimuleerde spellen en bouwt daarbij een boom die toekomstige simulaties stuurt. Een gesimuleerde voortzetting tot het einde is een spelsimulatie of gesimuleerde partij. Het simulatiebeleid kan willekeurige toegestane zetten kiezen of goedkope kennis gebruiken om verstandiger spel te produceren.

Sla bij elke knoop gegevens op

Houd een bezoekaantal $N(n)$ en een cumulatieve beloning $U(n)$ bij. Gebruik in een spel met twee spelers en winst of verlies de overwinningen voor de speler die de zet naar knoop $n$ maakte. Een gelijkspel telt meestal als een halve overwinning. Dan schat $U(n)\mathrm{/}N(n)$ het succespercentage van die speler.

De wortel heeft geen inkomende zet. Zijn bezoeken tellen nog steeds elke iteratie; overwinningen bij de wortel kunnen zo nodig vanuit het perspectief van de speler bij de wortel worden bijgehouden. Scores van kindknopen, die de selectie sturen, moeten steeds het perspectief gebruiken van de speler die de inkomende zet maakte.

Herhaal de vier fasen

1. Selectie: volg vanaf de wortel een selectiebeleid door bestaande kindknopen totdat je een eindknoop of een knoop met een niet-uitgeprobeerde zet bereikt.
2. Expansie: voeg bij een niet-terminale knoop één kindknoop toe voor een niet-uitgeprobeerde toegestane zet.
3. Simulatie: voer vanaf die kindknoop een spelsimulatie uit tot een einduitkomst.
4. Terugkoppeling van simulatieresultaten: werk bezoeken en beloningen bij voor knopen op het geselecteerde pad.

Als selectie een eindknoop bereikt, sla je expansie en simulatie over. De bekende uitkomst kan direct worden teruggewerkt. De tijdelijke voortzetting van een spelsimulatie hoeft niet als nieuwe boomknopen te worden opgeslagen: gewone expansie voegt één kindknoop per iteratie toe.

Volg een bijwerking van de beloning

Wit handelt bij de wortel. Selectie en expansie volgen:

• n1, bereikt met een zet van wit;
• n2, bereikt met een zet van zwart;
• n3, bereikt met een zet van wit.

De spelsimulatie eindigt met winst voor zwart. Verhoog het aantal bezoeken met één bij de wortel en bij n1, n2 en n3. Verhoog van deze drie kindknopen alleen bij n2 het aantal overwinningen, omdat zwart de inkomende zet naar n2 maakte. De kindknopen van wit krijgen geen extra overwinning. Als je bij de wortel het perspectief van de speler bij de wortel gebruikt, blijft ook het eigen winsttotaal van de wortel ongewijzigd.

Een gelijkspel zou 0,5 toevoegen aan de beloning van elke kindknoop. De overwinning van zwart bij elke knoop als succes tellen zou wit zetten laten kiezen die zwart helpen.

Laat de boom ongelijkmatig groeien

Herhaalde iteraties concentreren simulaties op veelbelovende of onzekere takken. Zetten die sterk lijken krijgen doorgaans grotere deelbomen, terwijl slechte zetten minder werk krijgen. De zoekmethode legt niet één vaste diepte op aan elk spelverloop. Zodra een toegestane zet beschikbaar is, kan de methode bij een tijdslimiet stoppen en de verzamelde statistieken gebruiken.

De uiteindelijke actie is meestal de kindknoop van de wortel met de meeste bezoeken. Een zet met twee overwinningen uit twee simulaties heeft een volmaakt waargenomen percentage, maar weinig bewijs. Een vaak bezochte zet weerspiegelt veel meer onderzoek door de zoekmethode.

Zuiver Monte-Carlo-zoeken geeft zetten bij de wortel onafhankelijke spelsimulaties zonder een beslissingsboom op te bouwen. Het kan herhaaldelijk één sterk antwoord van de tegenstander missen, omdat latere zetten door het simulatiebeleid bepaald blijven. MCTS leert waar het dieper moet vertakken naarmate het gegevens verzamelt, al kan een zeldzame tactische weerlegging nog steeds tijd kosten om te ontdekken.

MCTS moet beslissen waar een extra simulatie het nuttigst is. Exploitatie bezoekt zetten die er al sterk uitzien opnieuw. Exploratie onderzoekt zetten waarvoor minder gegevens beschikbaar zijn en die beter kunnen blijken. Altijd het grootste waargenomen winstpercentage najagen kan het zoeken vastzetten op een vroeg resultaat dat door geluk ontstond.

Bereken een UCB1-score

De score voor de bovengrens van het betrouwbaarheidsinterval voor kindknoop $n$ is:

De eerste term is het waargenomen winstpercentage. De tweede is een exploratiebonus. Die groeit naarmate de ouderknoop meer bezoeken verzamelt en krimpt naarmate de kindknoop meer bezoeken krijgt. De logaritme is natuurlijk. Kies tijdens de selectie de kindknoop met de grootste gecombineerde score.

Behandel een niet-bezochte kindknoop alsof die oneindige prioriteit heeft in plaats van door nul te delen. Elke toegestane zet bij een knoop wordt geprobeerd voordat selectie herhaaldelijk de voorkeur geeft aan bezochte alternatieven. MCTS met deze selectieregel heet UCT, bovengrenzen van betrouwbaarheidsintervallen toegepast op bomen.

Vergelijk drie kindknopen

Een ouderknoop heeft 50 bezoeken. Zijn kindknopen hebben winst- en bezoekaantallen 21/30, 7/12 en 3/8. Met $C=\sqrt{2}$ en $\ln 50\approx \mathrm{3,912}$:

De tweede kindknoop wordt geselecteerd. Het huidige winstpercentage is lager dan dat van de eerste kindknoop, maar de onzekerheidsbonus is groter. De derde is nog minder bezocht, maar door het lagere winstpercentage blijft het totaal iets onder dat van de tweede.

Met $C=\mathrm{0,5}$ worden dezelfde totalen ongeveer 0,881, 0,869 en 0,725. De selectie geeft nu de voorkeur aan de eerste kindknoop. Er zijn geen uitkomsten veranderd; het programma heeft veranderd hoe sterk het onzekerheid beloont.

Interpreteer de exploratieconstante

Een grotere positieve $C$ geeft meer gewicht aan exploratie. Als je die op nul zet, verdwijnt de bonus en wordt uitsluitend op basis van het waargenomen gemiddelde gekozen. De formulering van het bandietprobleem met beloningen tussen 0 en 1 motiveert $C=\sqrt{2}$ in deze vorm van de vergelijking; praktische spelprogramma's stellen de constante af. Een andere beloningsschaal verandert ook de verhouding tot de exploratieterm.

Bij elke ouderknoop registreren de kindknopen overwinningen voor de speler die daar kiest. Daardoor is UCB1 maximaliseren bij de beurten van beide spelers zinvol. Als je in de hele boom alleen overwinningen van wit opslaat en elke score maximaliseert, zou zwart het succes van wit bevorderen.

Onderscheid zoekprioriteit van zetkwaliteit

UCB1 kiest waaraan de volgende simulatie wordt besteed. Een grote onzekerheidsbonus kan een weinig onderzochte zet het onderzoeken waard maken. Kies aan het einde van de zoekactie de meest bezochte kindknoop van de wortel, niet de hoogste huidige UCB1-score. Onder de voorwaarden van UCT voor eindige spellen en bij voortdurende exploratie convergeert onbeperkt zoeken naar minimaxgedrag; een eindig budget laat nog steeds steekproefonzekerheid over.

Een zoekmethode past bij de grootte van de ruimte van mogelijke zetten, de kwaliteit van de beschikbare evaluatie en het soort onzekerheid in het spel. Hetzelfde tijdbudget kan tot heel verschillende beslissingen leiden, afhankelijk van wat de methode onderzoekt.

Vergelijk tactische dekking en simulatie

Alfa-bètasnoei kan binnen de zoekdiepte één tactische weerlegging vinden. MCTS kan aanvankelijk de voorkeur geven aan een zet die de meeste willekeurige spelsimulaties wint maar door één precies antwoord verliest. Naarmate de boom groeit, kan MCTS dat antwoord ontdekken, maar bij een klein simulatiebudget kan het worden gemist. Een hoog winstpercentage uit spelsimulaties is daarom geen garantie voor het slechtste geval.

Verbind methoden aan baanbrekende programma's

In 1997 gebruikte Deep Blue van IBM alfa-bètazoeken, gespecialiseerde hardware en schaakevaluatie om wereldkampioen Garry Kasparov met 3½–2½ te verslaan over zes partijen. Het succes liet zien hoeveel sterk zoeken en spelspecifieke evaluatie samen konden bereiken.

Go maakte die combinatie moeilijker. Een leeg bord van 19×19 biedt 361 plaatsen voor een steen, en een positie beoordelen op basis van eenvoudige kenmerken is moeilijk. MCTS werd een sterke aanpak omdat het uitkomsten kon schatten door te spelen en een selectieve boom kon laten groeien zonder een handgeschreven statische evaluator nodig te hebben.

AlphaGo combineerde MCTS met neurale netwerken die zetten voorstellen en posities beoordelen. De beschrijving in Nature uit 2016 ging vooraf aan de overwinning met 4–1 op Lee Sedol in maart 2016. AlphaZero gebruikte later evaluatie met een neuraal netwerk in plaats van willekeurige spelsimulaties en bereikte een bovenmenselijk spelniveau in schaken, shogi en go. Deze programma's laten zien dat een zoekmethode verschillende bronnen voor positiewaarden kan gebruiken.

Onderscheid sterk spel van een spel oplossen

Een programma kan een kampioen verslaan zonder de waarde van de beginpositie te bewijzen. In 2007 gebruikte het team van Jonathan Schaeffer zoekmethoden en grote eindspeldatabases om vast te stellen dat Amerikaans dammen bij volmaakt spel in gelijkspel eindigt. Een spel oplossen stelt een uitkomst vast tegen elke mogelijke strategie van de tegenstander, niet alleen tegen de tegenstanders die in wedstrijden zijn getest.

Stem de methode af op het model

Trek in een stochastisch spel tijdens het doorlopen van de boom en tijdens spelsimulaties toevalsuitkomsten volgens hun werkelijke kansen. Een gebeurtenis met kans 0,8 moet over veel trekkingen ongeveer vier keer zo vaak voorkomen als een gebeurtenis met kans 0,2. Dit schat dezelfde gewogen verwachtingswaarde die expliciet terugwerken bij toeval berekent.

Elke aanpak blijft afhankelijk van correcte regels en toestandsovergangen. Alfa-bètasnoei met een dieptelimiet hangt af van de evaluator; MCTS hangt af van het simulatie- of evaluatiebeleid en het eindige steekproefbudget. Een vijandige tegenstander als willekeurig modelleren kan kostbaar zijn, ongeacht de zoekmethode waarmee het antwoord van dat model wordt berekend.