MCTS og stokastiske spill

Alfa-beta trenger en evalueringsfunksjon og en forgreningsfaktor som ikke er altfor stor. I go er det hundrevis av lovlige trekk i hver stilling, og det er vanskelig å se på en stilling hvem som leder. Monte Carlo-tresøk (Monte Carlo tree search, MCTS) klarer seg uten evalueringsfunksjon. Verdien av en stilling anslås i stedet med en utspilling (playout): et raskt parti fra stillingen helt til slutt, med trekk valgt av en utspillingspolicy (playout policy) som er billig og gjerne litt tilfeldig. Andelen seire over mange utspillinger er anslaget.

MCTS lagrer to tall i hver node: $N(n)$, antall utspillinger som har gått gjennom noden, og $U(n)$, samlet nytte for spilleren som gjorde trekket inn i noden, med seier som 1 og tap som 0. Én iterasjon har fire faser:

1. 1.Seleksjon. Fra roten velger en seleksjonspolicy (selection policy) barn etter barn til søket når en node med trekk som ikke er prøvd.
2. 2.Ekspansjon. Søket legger til ett nytt barn under den noden.
3. 3.Simulering. En utspilling kjøres fra det nye barnet til spillet er slutt.
4. 4.Tilbakepropagering. Resultatet sendes opp langs stien (tilbakepropagering, back-propagation): $N$ øker med 1 i alle nodene på stien, og resultatet legges til $U$, sett fra spilleren som gjorde trekket inn i hver node.

Treet under er bygd opp av tolv utspillinger. B har vunnet alle sine fire, og under B har motspilleren prøvd to svar.

Iterasjonene gjentas så lenge det er tid. Til slutt spiller MCTS trekket med flest utspillinger, ƒtrekkvalget i MCTS, og ikke trekket med høyest gevinstandel, fordi et trekk med få utspillinger kan ha høy andel ved flaks.

Seleksjonen må balansere to ønsker. Utnyttelse (exploitation) betyr å bruke simuleringene der det har gått bra, slik at anslaget for det beste trekket blir sikrere. Utforsking (exploration) betyr å prøve trekk med få simuleringer, fordi de kan være bedre enn de ser ut. Denne avveiningen, utforsking mot utnyttelse (exploration vs. exploitation), dukker opp overalt der en agent lærer mens den handler. UCB1 er seleksjonspolicyen de fleste MCTS-programmer bruker, ƒUCB1-formelen:

Her er $p=\text{Parent}(n)$, forelderen til $n$.

Første ledd er gevinstandelen, utnyttelsesleddet. Andre ledd er utforskingsleddet: det er stort når barnet har få simuleringer sammenlignet med forelderen, og krymper etter hvert som barnet blir prøvd. Et barn som aldri er prøvd, har $N=0$ og regnes som uendelig, så alle barn prøves minst én gang. Konstanten $C$ styrer balansen; teorien gir $C=\sqrt{2}$, og i praksis justeres den ved å prøve flere verdier. Seleksjonen tar barnet med høyest UCB1 i hver node på vei ned. Siden $U$ i et barn er regnet for spilleren som trekker i forelderen, velger hver spiller det som er best for seg.

Navnet kommer fra statistikken: UCB står for upper confidence bound, en øvre konfidensgrense for gevinstandelen. Formelen er optimistisk når den er usikker. Et barn med få simuleringer får en høy øvre grense og dermed en sjanse til å vise seg fram. Etter hvert som simuleringene samler seg, krymper grensen mot den faktiske gevinstandelen, og et barn som bare var heldig i starten, faller tilbake.

Koden under lar UCB1 fordele simuleringer mellom tre trekk med vinnersjanser søket ikke kjenner.

import math
import random

C = 1.40  # @param 0.00..3.00 0.05
iterasjoner = 200  # @param 10..1000 10
random.seed(4)
vinnersjanse = {"A": 0.45, "B": 0.60, "C": 0.35}  # ukjent for søket
U = {t: 0 for t in vinnersjanse}
N = {t: 0 for t in vinnersjanse}

for n in range(iterasjoner):
    uprovd = [t for t in N if N[t] == 0]
    if uprovd:
        t = uprovd[0]
    else:
        t = max(N, key=lambda m: U[m] / N[m] + C * math.sqrt(math.log(n) / N[m]))
    N[t] += 1
    U[t] += 1 if random.random() < vinnersjanse[t] else 0

print(f"Besøk trekk A: {N['A']} (gevinstandel {U['A'] / N['A']:.2f})")
print(f"Besøk trekk B: {N['B']} (gevinstandel {U['B'] / N['B']:.2f})")
print(f"Besøk trekk C: {N['C']} (gevinstandel {U['C'] / N['C']:.2f})")
print(f"Valgt trekk: {max(N, key=N.get)} (flest besøk)")

I mange spill avgjør terninger eller kort hvilke trekk som er mulige. I terningspillet «først til 10» kaster spilleren én terning og velger så hvilken brikke som skal flyttes så mange felt. MAX vet hvilke trekk hun har etter kastet, men ikke hva motstanderen kommer til å slå. Spilltreet får derfor et tredje slags nivå: en sjansenode (chance node) før hvert trekk, med én kant per mulig utfall og sannsynligheten skrevet på kanten.

Verdien i en sjansenode er forventet verdi: summen av barnas verdier vektet med sannsynlighetene. MAX- og MIN-noder regnes som før. Det gir expectiminimax-verdi (expectiminimax value), ƒexpectiminimax-verdien:

• •terminaltilstand: $\text{EMM}(s)=\text{Utility}(s)$
• •MAX trekker: $\text{EMM}(s)={\max }_a\text{EMM}(s_a)$
• •MIN trekker: $\text{EMM}(s)={\min }_a\text{EMM}(s_a)$
• •sjansenode: $\text{EMM}(s)={\sum }_{r}P(r)\text{EMM}(s_r)$

Her er $s_a=\text{Result}(s,a)$ tilstanden etter trekket $a$, og $s_r$ tilstanden etter utfallet $r$.

Regn med brøker når sannsynlighetene er tredjedeler eller sjettedeler, og skriv ut den vektede summen. Det er der regnefeilene skjer.

MAX velger under mellom to trekk som begge fører til et tilfeldig utfall. Trekket til B gir MIN et svar etterpå, mens trekket til C avgjør partiet med én gang.

Expectiminimax er verken forsiktig eller dristig i seg selv: den maksimerer forventet verdi. Om MAX burde foretrekke det sikre eller det usikre trekket, avhenger av hvordan tallene i bladene er målt, og det er tema i neste steg.

Sjansenoder gjør treet mye større. Med $n$ ulike utfall per kast blir tiden ƒtidsbruken til expectiminimax:

For hvert halvtrekk ganges arbeidet med både antall trekk og antall utfall, så selv et raskt program kommer bare noen få halvtrekk ned. Ideen bak alfa-beta kan brukes med sjansenoder bare når nytten er begrenset, for eksempel mellom 0 og 10: da kan søket sette en grense for gjennomsnittet før alle utfallene er sett.

Evalueringsfunksjonen må også oppfylle et strengere krav. I et deterministisk spill holder det at Eval rangerer stillingene riktig. Å bytte Eval med $2\cdot \text{Eval}$ eller ${\text{Eval}}^3$ endrer ikke hvilket trekk minimax velger, fordi max og min bare ser på rekkefølgen. En sjansenode regner gjennomsnitt, og et gjennomsnitt kan snu når noen verdier strekkes mer enn andre. Kravet er derfor at Eval er en positiv lineær transformasjon av sannsynligheten for å vinne, eller av forventet nytte: $a\cdot P(\text{seier})+c$ med $a>0$.

En annen vei er å la simuleringer erstatte evalueringsfunksjonen, slik MCTS gjør. Programmet spiller hundrevis av raske partier fra stillingen med tilfeldige terningkast og bruker andelen seire som verdi. Da er verdien en sannsynlighet, og kravet til skala er oppfylt av seg selv.

Koden under regner ut et valg mellom et trygt trekk og et trekk som trenger en sekser på neste kast. Sannsynligheten for en sekser kan endres.

p_seks = 0.17  # @param 0.00..1.00 0.01

# Du velger trekk nå, og neste kast avgjør om satsingen lykkes.
# Trekk A: flytt én brikke trygt. Motspilleren (MIN) svarer, og stillingene er verdt 6 eller 5.
verdi_A = min(6, 5)
# Trekk B: sats på en sekser i neste kast. Sekser gir seier (10). Ellers svarer MIN med 4 eller 3.
verdi_B = p_seks * 10 + (1 - p_seks) * min(4, 3)

print(f"Verdi trekk A: {verdi_A:.2f}")
print(f"Verdi trekk B: {verdi_B:.2f}")
print(f"Valgt trekk: {'A' if verdi_A >= verdi_B else 'B'}")

I kortspill ser du ikke motspillerens kort, og i brettspill med skjulte brikker ser du ikke hele brettet. Et delvis observerbart spill (partially observable game) krever at agenten resonnerer om en oppfatningstilstand: mengden stillinger som passer med det den har sett. Et naturlig triks er å trekke mange mulige kortfordelinger, løse hver av dem som et vanlig spill med full informasjon og velge trekket som er best i snitt. Det kalles gjennomsnitt over klarsyn (averaging over clairvoyance), fordi hvert delproblem later som om du ser alle kortene. Fordelingene trekkes ikke blindt: de må passe med kortene som allerede er spilt, og fordelinger som stemmer godt med det motspilleren har gjort, får større vekt.

Hvor går det galt? Hvert delproblem regner som om kortene ligger åpne fra og med neste trekk. Et trekk som bare er godt hvis du senere vet hvilket kort motspilleren har, blir derfor regnet som godt, selv om du aldri får vite det. Eksempelet under viser hvor mye det kan koste. Den samme blindsonen gir to bivirkninger. Et trekk som bare avslører noe, for eksempel et kort du spiller for å se hva motspilleren svarer med, er verdiløst når alle delproblemene allerede ser alt. Og fordi alle ser alt, er det heller ingen gevinst i å skjule hva du selv har, eller i å late som du har noe annet.

Sammenlign til slutt spilltresøk med en erfaren menneskelig spiller. Hun tenker i planer, som «bytt dronninger og vinn sluttspillet», og regner bare på de få trekkene som tjener planen. Søket kjenner bare enkelttrekk, og uten kunnskap om hvilke grener som er verdt å se på, bruker det like mye tid på håpløse trekk som på lovende. Og der spilleren kan stoppe opp når magefølelsen virker usikker, stoler søket fullt på evalueringsfunksjonen i bladene. Et feil anslag der kan bli båret helt opp til roten og avgjøre trekket.