Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra MCTS og stokastiske spill, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En søkemetode som bygger søketreet gradvis og anslår verdien av stillinger med simulerte partier i stedet for en evalueringsfunksjon. Hver iterasjon har fire faser: seleksjon, ekspansjon, simulering og tilbakepropagering (Monte Carlo tree search, MCTS).
Et raskt simulert parti fra en stilling helt til spillet er slutt, der resultatet brukes som anslag på verdien av stillingen (playout).
Regelen som velger trekkene i en utspilling. Den må være rask og er ofte tilfeldig, eller enkel med litt tilfeldighet (playout policy).
Regelen som velger barn fra roten og nedover i seleksjonsfasen, og som balanserer utforsking mot utnyttelse. UCB1 er den vanligste (selection policy).
Seleksjonsformelen : gevinstandelen pluss et utforskingsledd som er stort for barn som er lite prøvd (upper confidence bound).
Avveiningen mellom å bruke ressursene der det har gått bra (utnyttelse) og å prøve alternativer som kan være bedre enn de ser ut (utforsking) (exploration vs. exploitation).
Fasen der resultatet av en simulering sendes opp langs stien til roten: hver node får økt med 1 og resultatet lagt til , sett fra spilleren som gjorde trekket inn i noden (back-propagation).
En node i spilltreet for et tilfeldig utfall, som et terningkast, med én kant per utfall og sannsynligheten på kanten. Verdien er forventet verdi av barna (chance node).
Minimax utvidet med sjansenoder: MAX- og MIN-noder regnes som før, og en sjansenode får summen av barnas verdier vektet med sannsynlighetene (expectiminimax value).
Et spill der spillerne ikke ser hele tilstanden, som et kortspill med skjulte kort. Agenten må resonnere om mengden tilstander som passer med det den har sett (partially observable game).
Å trekke mange mulige skjulte tilstander, løse hver som et spill med full informasjon og velge trekket som er best i snitt. Metoden antar feilaktig at du kjenner den skjulte tilstanden når du tar senere valg (averaging over clairvoyance).
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
UCB1-formelen
Seleksjonen velger barnet med høyest verdi i hver node på vei ned. Første ledd er gevinstandelen, andre ledd utforskingen, og teorien gir . Vanlige feil er å bruke barnets i logaritmen og å glemme at er regnet for spilleren som trekker i forelderen.
Expectiminimax-verdien
Regnes nedenfra som minimax. I en sjansenode vektes hver barneverdi med sannsynligheten for utfallet; et vanlig gjennomsnitt er feil når utfallene ikke er like sannsynlige. Regn med brøker.
Tidsbruken til expectiminimax
Hvert halvtrekk med et tilfeldig utfall ganger arbeidet med både og , så søket rekker bare få halvtrekk ned. Forklarer hvorfor spill med terninger søkes grunt.
Trekkvalget i MCTS
Når tiden er ute, spiller MCTS trekket med flest utspillinger, ikke det med høyest gevinstandel: et lite prøvd trekk kan ha høy andel ved flaks.
Kodesnutter
Kodesnutter fra kapittelet, vist literal.
UCB1 på tre trekk med ukjent vinnersjanse
import mathimport random C = 1.40 # @param 0.00..3.00 0.05iterasjoner = 200 # @param 10..1000 10random.seed(4)vinnersjanse = {"A": 0.45, "B": 0.60, "C": 0.35} # ukjent for søketU = {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)")Prøv: sett C til 0 og se at linja Besøk trekk C: står på 1, fordi søket aldri prøver det trekket igjen etter ett tap; med C på 3 blir besøkene jevnere fordelt.
Trygt trekk eller sats på en sekser
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'}")Prøv: øk p_seks fra 0.17 til 0.30 og se at linja Valgt trekk: bytter fra A til B når Verdi trekk B: passerer 5.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Beskriv de fire fasene i Monte Carlo-tresøk og oppdater U og N etter én simulering
- 02Regn ut UCB1 for et barn og avgjør hvilket barn seleksjonen velger
- 03Regn ut expectiminimax-verdier i et tre med sjansenoder og vis den vektede summen
- 04Forklar hvorfor evalueringsfunksjonen må være en positiv lineær transformasjon av vinnersjansen når sjanse er med
- 05Forklar hvorfor gjennomsnitt over klarsyn kan velge feil i delvis observerbare spill