En minimax-algoritme er en matematisk fremgangsmåte for å estimere sluttresultat av enkelte typer spill.

Minimax-algoritmer brukes til å analysere mange typer spill og spillignende prosesser, for eksempel sjakk.

Spillene må ha disse egenskapene:

  • Det må være to spillere som trekker annenhver gang.
  • Hvert trekk må lede til en ny tilstand.
  • Spillet må være konstruert slik at det før eller siden stopper opp.
  • Spillet må ende opp med en poengsum for hver av spillerne.
  • Hensikten med spillet må være å få så høy poengsum som mulig.
  • Poengsummen for hver av spillerne må tildeles på en slik måte at totalt antall poeng alltid er konstant.

Det finnes mange utvidelser og tilpasninger som løser på disse betingelsene. 

Når man analyserer denne algoritmen er det vanlig å kalle den ene spilleren for A og den andre for B.

Siden totalt antall poeng er konstant, vil en økning av poengsummen til A alltid innebære tilsvarende reduksjon av poengsummen til B. Derfor er det bare nødvendig å beregne poengsummen til A. Målsettingen for A er å maksimere denne summen, mens B alltid vil forsøke å minimere den.

Minimax-verdien for en tilstand er den poengsummen A vil ende opp med hvis både A og B spiller optimalt i resten av spillet. Av og til går det an å regne seg frem til denne verdien, men i mange tilfeller, for eksempel i sjakk, vil dette være alt for ressurskrevende.

I slike situasjoner kan man istedet bruke en minimax-algoritme  til å estimere denne verdien. Målsettingen er å regne seg frem til en verdi som ligger så nært den virkelige minimax-verdien som mulig.

En viktig komponent i en miminax-algoritme er en evalueringsfunksjon som estimerer verdien av en tilstand ut fra egenskaper ved selve tilstanden. Uformingen av denne vil variere fra spill til spill. Det er også vanlig å benytte forskjellige evalueringsmetoder i forskjellige faser av spillet.

Kvaliteten på denne funksjonen er avgjørende for hvor godt algoritmen vil fungere. Det å bygge opp slike funksjoner er derfor et interessant tema innenfor spillteori. Utfordringen er å definere funksjoner som både er effektive og treffsikre. De må være effektive fordi de som regel vil bli benyttet svært mange ganger under en analyse. De må også være treffsikre fordi det estimatet man kommer frem til alltid er et resultat av en slik evaluering. I tillegg brukes de til å gjøre prioriteringer og veivalg underveis i analysen.

Derfor gjelder det å finne frem til egenskaper som har mye å si for utfallet samtidig som de er enkle å beregne. I sjakk er det for eksempel vanlig å legge stor vekt på totalverdien av brikkene spillerne disponerer. Denne egenskapen er enkel å beregne samtidig som den ofte har stor betydning for utfallet. Den spilleren som har flest og best brikker vil som regel vinne spillet til slutt.

Den andre hovedkomponenten er en søkemekanisme som kan brukes til å tenke flere trekk fremover i tid. Algoritmen tenker ett trekk fremover på denne måten:

  • Den går igjennom alle lovlige trekk i utgangstilstanden.

  • For hvert av disse trekkene bruker den evalueringsfunksjonen til å beregne verdien av den nye tilstanden som oppstår etter at trekket er utført.

  • Det antatt optimale trekket vil være det som leder til den beste verdien for spilleren, det vil si høyeste verdi hvis det er A som trekker og laveste verdi hvis det er B sin tur.

  • Den beste verdien vil også utgjøre det mest nøyaktige estimatet for minimax-verdien av utgangstilstanden.

Den kan også tenke to trekk fremover. I stedet for å bruke evalueringsfunksjonen til å analysere tilstandene etter første trekk, kan den gå videre og analysere hver av tilstandene på samme måte som ovenfor. Algoritmen vil da velge det trekket hvor motstanderen får de dårligste valgmulighetene i neste trekk. Hvis det er A som trekker vil den velge det trekket hvor B sitt beste trekk i neste runde har så høy verdi som mulig. Den vil med andre ord minimalisere motstanderens maksimale verdi. Derfor kalles dette for en minimax-algoritme.

En datamaskin vil fortsette på denne måten og analysere flere trekk fremover, helt til den går tom for tid.

Prosessen kan beskrives som et søk i et tre som beskriver alle mulige utviklinger i spillet:

  • Forgreningene i treet representerer tilstander.

  • Den nederste forgreningen representerer starttilstanden.

  • Grenene representerer trekk som leder til nye tilstander.

  • Ytterpunktene representerer sluttilstander.

I noen tilfeller er spilltreet såpass lite at det går an å søke helt frem til slutten av spillet. Andre ganger er treet er alt for stort. Da må algoritmen gjøre noen vanskelige valg underveis for å utnytte tiden best mulig. Hver gang den har behov for å analysere en tilstand, må den velge om den skal nøye seg med bruke evalueringsfunksjonen eller om den skal søke videre utover i treet.

Evnen til å velge om man skal søke videre i treet eller ikke, er den andre avgjørende faktoren som bestemmer kvaliteten på algoritmen. Det gjelder å bruke den verdifulle tiden så effektivt som mulig.

Det finnes heldigvis en logisk sammenheng i slike trær som begrenser behovet for søk. Hvis man under analysen av en tilstand oppdager et trekk som gir dårligere verdi for motspilleren enn en tilstand som er oppdaget lavere i treet, kan man avbryte analysen. Spilleren vil ikke velge et trekk som er bedre for motspilleren en dette og siden motspilleren allerede har funnet et trekk som vil gi bedre verdi, vil tilstanden aldri kunne være med i en optimal strategi for motspilleren.

For å oppdage slike situasjoner så fort som mulig, er det viktig å analysere de mest lovende tilstandene først. Det vil øke sannsynligheten for at man raskt finner de beste trekkene for motstanderen og at man tidlig finner et trekk som er dårligere for motstanderen enn disse på neste nivå i treet.

Dette kan man få til ved beregne foreløpige verdier med evalueringsfunksjonen og så sortere tilstandene før man går i gang med søket. Det går også an å lage en egen funksjon som bare brukes til å rangere tilstandene.

Dette kalles også for alpha beta cutoff.

Beskjæring av lite lovende tilstander

En annen teknikk er å ganske enkelt la være å analysere de minst lovende tilstandene. Dette kan imidlertid føre til at man går glipp av trekk som ser dårlige ut i første omgang, men som senere i spillet kan vise seg å være gode. Dette kalles for pruning.

Algoritmen kjenner bare de tilstandene den har evaluert. Den har ingen magefølelse som gjør den i stand til å oppdage eventuelle overraskelser i neste trekk. De ytterste tilstandene i søketreet utgjør en horisont den ikke kan se forbi. Dette kan motvirkes med et fredfullhetssøk (quiescence search). Dette er et kort søk 1-2 trekk frem i tid som brukes til å forebygge overraskelser før man avslutter analysen av en tilstand.

Som regel vil det være nødvendig å gjennomføre en fredfullhetsevaluering som avgjør hvorvidt man skal gjennomføre et slikt søk eller ikke.

  • John von Neumann: Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 1928
  • Tinne Hoff Kjeldsen: John von Neumann's Conception of the Minimax Theorem: A Journey Through Different Mathematical Contexts. Archive for History of Exact Sciences. Springer, 2001.
  • Donald E. Knuth, Ronald W. Moore: An analysis of alpha-beta pruning. Artificial Intelligence 1975.

Foreslå endringer i tekst

Foreslå bilder til artikkelen

Kommentarer

Har du spørsmål om artikkelen? Skriv her, så får du svar fra fagansvarlig eller redaktør.

Du må være logget inn for å kommentere.