Motstandersøk: minimax og alfa-beta

Et søkeproblem fra kapittel 2 har én agent som styrer alt. I et brettspill for to deler agenten makta med en motstander, og da kalles søket motstandersøk (adversarial search). Vi ser på den mest studerte typen: to spillere trekker etter tur, begge ser hele brettet, ingen terninger avgjør noe, og det den ene vinner, taper den andre. Et slikt nullsumspill (zero-sum game) beskrives med seks deler:

• •$S_0$: starttilstanden.
• •$\text{To-Move}(s)$: hvem som trekker i $s$, MAX eller MIN.
• •$\text{Actions}(s)$: de lovlige trekkene i $s$.
• •$\text{Result}(s,a)$: tilstanden etter trekket $a$.
• •$\text{Is-Terminal}(s)$: terminaltesten, sann når spillet er slutt.
• •$\text{Utility}(s,p)$: en nyttefunksjon (utility function) som gir tallverdien av sluttilstanden $s$ for spilleren $p$.

MAX er spilleren vi regner for, og MIN er motstanderen. I sjakk er nytten $1$, $0$ eller $\frac{1}{2}$ for seier, tap og remis, og summen for de to spillerne er alltid 1. Strengt tatt er det konstantsum, men det regnes som nullsum.

Starttilstanden, trekkene og resultatfunksjonen gir sammen et spilltre (game tree): roten er $S_0$, hver kant er et trekk, og bladene er terminaltilstander med nytte. Ett trekk av én spiller kalles et halvtrekk (ply), så to halvtrekk er én runde. Treet vokser fort. Med $b$ lovlige trekk per stilling og partier på $m$ halvtrekk har det rundt $b^m$ blader, og i sjakk er $b$ omtrent 35. Ingen kan søke gjennom hele det treet, og resten av kapitlet handler om hvordan søket slipper.

Hvordan skal MAX velge trekk når MIN svarer? Svaret er å regne baklengs fra bladene. Minimax-verdi (minimax value) til en node er nytten MAX får hvis begge spiller optimalt derfra. I et blad er den nytten selv. I en MAX-node er den den største av barnas verdier, fordi MAX velger. I en MIN-node er den den minste, fordi MIN velger det som er verst for MAX. Det er ƒminimax-verdien:

• •terminaltilstand: $\text{MM}(s)=\text{Utility}(s)$
• •MAX trekker: $\text{MM}(s)={\max }_a\text{MM}(s_a)$
• •MIN trekker: $\text{MM}(s)={\min }_a\text{MM}(s_a)$

Her er $s_a=\text{Result}(s,a)$, og nytten er regnet for MAX.

Algoritmen er et dybde-først-søk: den går helt ned til et blad, leser nytten og sender verdien opp når alle barna til en node er ferdige. Tiden er $O(b^m)$ og minnet $O(bm)$, som for dybde-først-søk i et tre med dybde $m$. Trekket MAX velger i roten, er barnet med høyest verdi.

I treet under har MAX og MIN tre valgnivåer til sammen. To av partiene slutter tidlig: E og F er terminaltilstander allerede etter to halvtrekk.

Minimax er pessimistisk med vilje. Verdien er det MAX er garantert mot en motstander som aldri gjør feil. Gjør MIN en feil, får MAX minst like mye, men en strategi som regnet med feilen, kunne ha utnyttet den bedre.

Med tre eller flere spillere holder ikke ett tall per node. Hver node får i stedet en vektor med én nytte per spiller, for eksempel $(u_1,u_2,u_3)$. Regelen er en direkte utvidelse av minimax: i en node der spiller $i$ trekker, velges barnet med høyest $u_i$, og hele vektoren til det barnet kopieres opp. Hver spiller maksimerer sin egen komponent og bryr seg ikke om de andres.

Legg merke til bladet $(7,0,4)$, som er det beste for spiller 1. Det blir aldri nådd, fordi spiller 3 heller tar $(1,1,6)$, og spiller 2 da heller avslutter med $(5,4,2)$. Noen partier slutter tidligere enn andre, og da står vektoren rett i bladet. Spill med flere deltakere åpner også for allianser: to spillere som hver for seg ligger dårlig an, kan tjene på å angripe den som leder, uten at noen avtale er nødvendig. Et tospillers nullsumspill er spesialtilfellet der vektoren er $(u,-u)$, og da blir regelen minimax igjen.

Minimax besøker hver node i treet, men mange av dem kan ikke endre svaret. Anta at MAX vet at ett trekk gir 6, og at et annet trekk fører til en MIN-node der første barn gir 4. Da kan MIN holde MAX på 4 eller lavere i den grenen, og MAX velger den aldri. Resten av barna der trenger ikke ses. Alfa-beta-beskjæring (alpha–beta pruning) bruker denne logikken systematisk med to grenser som følger med nedover stien:

• •Alfa (α) er den beste verdien MAX allerede har sikret et sted langs stien fra roten. Den starter på $-\infty$.
• •Beta (β) er den beste verdien MIN har sikret langs stien. Den starter på $+\infty$.

En MAX-node setter $v=\max (v,\text{barn})$ og deretter $\alpha =\max (\alpha ,v)$. En MIN-node setter $v=\min (v,\text{barn})$ og $\beta =\min (\beta ,v)$. Kuttet skjer etter ƒkuttregelen i alfa-beta:

Det kuttes også ved likhet, fordi en like stor verdi heller ikke kan endre valget over. Det som kuttes, er resten av barna i noden med hele undertrærne. I svar oppgir du den øverste noden som aldri blir besøkt, ikke bladene under den. Rotverdien og trekket blir de samme som med minimax, men verdiene i noder der det er kuttet i eller under, er bare grenser.

1alfabeta(node, alfa, beta):2    hvis node er terminal:3        returner nytte(node)4    hvis cutoff(node):5        returner eval(node)6    hvis MAX trekker i node:7        v = -uendelig8        for barn i barna(node):                  # venstre mot høyre9            v = max(v, alfabeta(barn, alfa, beta))10            hvis v >= beta:11                returner v                       # kutt: MIN over vil aldri slippe hit12            alfa = max(alfa, v)13    ellers:14        v = +uendelig15        for barn i barna(node):16            v = min(v, alfabeta(barn, alfa, beta))17            hvis v <= alfa:18                returner v                       # kutt: MAX over har noe minst like godt19            beta = min(beta, v)20    returner v21 22# start: alfabeta(rot, -uendelig, +uendelig)

I treet under har MAX tre trekk, og hvert av dem gir MIN tre svar.

Koden under kjører alfa-beta på et lite tre med to MIN-noder, der verdien til bladet F styres med en glidebryter.

blad_F = 3  # @param -10..10

# Roten A er MAX. B og C er MIN-noder, og bladene leses fra venstre mot høyre.
barn = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F", "G", "H"]}
blad = {"D": 3, "E": 7, "F": blad_F, "G": 8, "H": 6}
er_max = {"A": True, "B": False, "C": False}
evaluert, kuttet = [], []

def alfabeta(node, alfa, beta):
    if node in blad:
        evaluert.append(node)
        return blad[node], None
    v, valgt = (float("-inf") if er_max[node] else float("inf")), None
    for i, b in enumerate(barn[node]):
        w, _ = alfabeta(b, alfa, beta)
        if (er_max[node] and w > v) or (not er_max[node] and w < v):
            v, valgt = w, b
        if (er_max[node] and v >= beta) or (not er_max[node] and v <= alfa):
            kuttet.extend(barn[node][i + 1:])  # kutt også ved likhet
            break
        if er_max[node]:
            alfa = max(alfa, v)
        else:
            beta = min(beta, v)
    return v, valgt

verdi, trekk = alfabeta("A", float("-inf"), float("inf"))
print(f"Minimax-verdi i roten: {verdi}")
print(f"Valgt trekk: {trekk}")
print(f"Blader evaluert med alfa-beta: {len(evaluert)} av {len(blad)}")
print(f"Kuttede noder: {', '.join(kuttet) if kuttet else 'ingen'}")

Hvor mye alfa-beta sparer, avhenger av rekkefølgen barna besøkes i. I treet i forrige steg ga det første trekket (B) MAX en høy garanti med en gang, så de to andre MIN-nodene kunne avvises tidlig. Med det dårligste trekket først og bladene i verst mulig rekkefølge må alle ni bladene evalueres: α holder seg lav, og ingenting blir kuttet. Trekkordning (move ordering) er rekkefølgen søket prøver trekkene i, og den ideelle rekkefølgen er «beste trekk først».

Med perfekt ordning trenger alfa-beta bare omtrent $b^{m/2}$ blader i stedet for $b^m$, og med tilfeldig ordning omtrent $b^{3m/4}$. Det er ƒtidsbruken til alfa-beta:

Den effektive forgreningsfaktoren blir $\sqrt{b}$, så med samme tid kan søket gå omtrent dobbelt så dypt. Perfekt ordning er umulig i praksis, for da ville vi ikke trengt å søke. Enkle tiltak kommer likevel nær: prøv slag før rolige trekk, prøv trekk som ga kutt andre steder i treet tidligere, og bruk iterativ fordypning, der resultatene fra dybde $d$ ordner trekkene på dybde $d+1$.

Mange stillinger kan nås via ulike trekkrekkefølger. En transposisjonstabell (transposition table) er en hashtabell med verdiene til stillinger som allerede er evaluert, slik at søket slipper å regne dem ut på nytt når de dukker opp igjen.

Her er bladene fra forrige figur sortert slik at det beste barnet står først i hver node.

Selv med perfekt ordning er sjakktreet altfor stort til å søkes til bunns. Løsningen er å stoppe på en fast dybde og anslå verdien der. En evalueringsfunksjon (evaluation function) $\text{Eval}(s)$ gir et anslag på nytten fra en stilling som ikke er terminal, og en cutoff-test (cutoff test) avgjør når søket skal stoppe. Det gir ƒminimax med cutoff:

Ellers regnes noden som i minimax, med ${\max }_a\text{H-MM}(s_a,d+1)$ når MAX trekker og ${\min }_a\text{H-MM}(s_a,d+1)$ når MIN trekker.

Is-Cutoff er sann i terminaltilstander og når dybden $d$ har nådd grensen. I terminaltilstander må Eval rangere stillingene på samme måte som nyttefunksjonen. Den vanligste formen er en vektet sum av egenskaper ved stillingen, ƒlineær evalueringsfunksjon:

Hver $f_i$ teller noe som henger sammen med vinnersjansen, og vekten $w_i$ sier hvor mye det teller. En god evalueringsfunksjon er rask å regne ut og følger den faktiske vinnersjansen tett. Tabellen viser en slik funksjon for fire på rad på et brett med 5 kolonner og 4 rader.

Å stoppe på fast dybde har en kjent svakhet, horisonteffekt (horizon effect): et uunngåelig tap som ligger rett bak søkedybden, er usynlig, og programmet kan velge trekk som bare skyver tapet ut av syne. Et rosøk (quiescence search) demper problemet ved å søke videre fra urolige stillinger, der et slag eller en trussel henger i lufta, til stillingen er rolig nok til at Eval er til å stole på. Foroverbeskjæring (forward pruning) går motsatt vei og dropper trekk som ser dårlige ut, uten å søke dem. Det sparer mye tid, men kan kutte det beste trekket. Til slutt bruker sterke programmer oppslagstabeller for åpninger og sluttspill, der riktig trekk er regnet ut på forhånd.