Eksempel: Et parti bondesjakk

Maxine og Minnie er hekta på spill, spesielt brettspill for to personer slik som bondesjakk og sjakk. En dag spiller de bondesjakk. Maxine, eller Max blant venner, spiller med X, mens Minnie, eller Min blant venner, spiller med O. Min har nettopp valgt sitt trekk og brettet ser da slik ut:

Max stirrer konsentrert på brettet og pønsker ut neste trekk. Plutselig begraver hun fortvilet ansiktet i hendene, litt på samme måte som Garry Kasparov da han spilte mot Deep Blue i 1997.

Min har snart tre O-er på rad på den øverste raden, men Max kan enkelt forhindre det. Hvorfor blir da Max så ute av seg?

Spilltre

For å løse spill ved hjelp av kunstig intelligens skal vi introdusere konseptet spilltre. De forskjellige tilstandene i spillet er representert med noder i spilltreet. Nodene tilsvarer dermed tilstandene i planleggingsproblemene vi omtalte i eksemplet med robåten. De fungerer bare på litt forskjellige måter. I et spilltre er nodene fordelt på forskjellige nivåer som korresponderer med hver spillers tur, slik at «rotnoden» på treet (vanligvis på toppen av diagrammet) er startposisjonen i spillet. I bondesjakk er startposisjonen et tomt rutenett uten X eller O. Under roten, på andre nivå, finner vi alle de mulige spill-tilstandene som kan være resultatet av trekket til den første spilleren, enten det nå er X eller O. Vi kaller disse nodene «barna» til rotnoden.

Hver node på det andre nivået har igjen barnenoder som forestiller situasjonen hvor motstanderen har gjort sitt trekk. Slik fortsetter det, nivå etter nivå, til spillet er over. I bondesjakk har da en av spillerne fått tre på rad og vinner, eller rutenettet er fullt og spillet ender uavgjort.

Minimering og maksimering av verdi

For å utvikle kunstig intelligens slik at den får som mål å vinne spillet, gir vi hvert sluttresultat en numerisk verdi. I spillsituasjoner der det finnes tre X på rad og Max vinner, tilordner vi verdien +1. På samme måte tilordner vi verdien -1 til de spillsituasjonene der det er tre O-er på rad og Min vinner. Blir det uavgjort, setter vi verdien til 0. I utgangspunktet spiller det ingen rolle hvilke verdier vi velger, så lenge de er ordnet slik at Max forsøker å maksimere verdien og Min forsøker å minimere den.

Et eksempel på et spilltre

Vi skal se på et bondesjakkeksempel som begynner midt i et spill isteden for et tomt rutenett (ellers ville ikke spilltreet fått plass på skjermen). Dette er altså ikke det samme eksempelet som i begynnelsen av kapittelet. Nodene i spilltreet er nummerert med 1, 2, ..., 14.

Spilltreet består av vekslende nivåer, hvor det er enten Mins tur til å sette O på ett av de ledige feltene, eller Max sin tur til å sette X. Hvem sin tur det er, vises til venstre for spilltreet.

Rotnoden som er markert med tallet 1, viser oss den aktuelle spillsituasjonen: Det er Mins tur til å sette O i en av de tre ledige rutene. Nodene 2-4 viser posisjonene på spillebrettet for hvert av de tre alternativene. I neste omgang har hver node to alternativer hvor Max kan sette X, og treet forgrener seg igjen.

Med utgangspunkt i node 1, ender spillet alltid med tre på rad: i nodene 7 og 9 vinner Max med sine X, og i nodene 11-14 er det Min med O-ene som er vinneren.

Merk at siden spillet går etter tur, kan nivåene også merkes som Min-nivåer og Max-nivåer.

Strategisk spill

La oss se litt på situasjonen ved nodene 5-10 på det andre nivået nedenfra. I nodene 7 og 9 er spillet over, og Max vinner med tre på rad. Verdien på disse spillsituasjonene er +1. I de andre nodene 5, 6, 8 og 10 er spillet i praksis også avgjort fordi Min ikke har andre muligheter enn å sette O i den eneste ledige ruten og vinne spillet. Med andre ord vet vi hvordan spillet slutter ved hver av nodene på nest siste nivå. Vi kan derfor si at verdien på nodene 5, 6, 8 og 10 er -1.

Nå kommer vi til den mest interessante delen. La oss se på verdien av nodene på nivået over, altså nodene 2-4. Siden vi nå vet at begge barnenodene 5 og 6 i node 2 fører til at Min vinner, kan vi også sette verdien -1 til node 2. Ved node 3 er det barnet til venstre, node 7, som fører til at Max vinner med verdien +1. Barnet til høyre, derimot, altså node 8, gir Min seier med verdien -1. Hva er da verdien av node 3? Ta deg tid til å tenke på det, og tenk også på hvem av spillerne som har tur i node 3.

Ettersom det er Max sin tur, velger hun naturligvis barnenoden til venstre, node 7. Det er altså slik at hver gang spillet leder til en node 3-situasjon, kan Max sikre seieren, og vi kan legge verdien +1 til node 3.

Det samme gjelder node 4. Max kan igjen bestemme hvilken av de ledige rutene hun setter X i og dermed sikre seg seieren. Derfor kan vi legge verdien +1 til node 4.

Å avgjøre seieren på forhånd

Når man bruker logikkrekken beskrevet ovenfor, er det altså mulig å forutse hvem av spillerne som vinner i en hvilken som helst spillsituasjon.

Så langt har vi regnet ut at verdien av node 2 er -1, som betyr at Min kan gå av med seieren dersom spillet befinner seg i den posisjonen. Situasjonen er det motsatte i nodene 3 og 4 fordi deres verdi er +1, og da vinner Max hvis hun velger smart.

I tillegg kan vi regne ut at Min, siden hun er en erfaren spiller, har trukket samme konklusjon. Da har hun i realiteten bare ett alternativ: å sette ringen O i midten. I diagrammet under ser du verdien for alle nodene og de optimale trekkene for Min helt fra rot-noden.

Verdien på roten angir vinneren

Verdien på rotnoden, også kalt spillverdien, forteller oss hvem som vinner spillet (og hvor stor seieren blir dersom resultatet ikke bare blir målt i seier eller tap). Max vinner dersom verdien på spillet er +1, Min vinner om verdien er -1. Om verdien er 0, er spillet uavgjort. I andre spill kan spillverdien være noe annet, for eksempel pengeverdien til sjetongene som ligger på pokerbordet.

Alt baseres på antakelsen om at begge spillerne alltid velger det optimale alternativet. Det som er best for den ene, er samtidig verst for den andre – også kalt nullsumspill.

Minimax-algoritmen

Vi kan benytte oss av spillverdikonseptet for å forstå algoritmen som kalles minimax-algoritmen. I teorien garanterer den et optimalt spill i ethvert deterministisk nullsumspill, dvs. spill med to spillere, der begge spillerene har fullstendig informasjon om spillet. For enhver spilltilstand beregner algoritmen barnas verdier i den gitte tilstanden og velger maksimal verdi når det er Max sin tur, og minimal verdi når det er Mins tur.

Algoritmen kan implementeres ved hjelp av bare noen få kodelinjer. På dette tidspunktet nøyer vi oss likevel med å forstå den grunnleggende ideen. Om du er interessert i å ta en titt på selve algoritmen (her er det en fordel å kunne litt om programmering!), kan du for eksempel søke på Minimax i Wikipedia.

Ok, kan vi gå hjem nå?

Som vi konstaterte tidligere, løser minimax-algoritmen optimale spilltrekk i hvilket som helst deterministisk nullsumspill med to spillere og med fullstendig informasjon. Eksempler på slike spill er bondesjakk, fire på rad, sjakk og Go. Stein-saks-papir hører ikke med i denne gruppen, siden det inneholder informasjon som er skjult for den andre spilleren. Det gjør heller ikke Monopol og backgammon, i og med at flaksen her spiller en vesentlig rolle, og disse spillene ikke er deterministiske av natur. Er vi da «ferdig snakka» om dette temaet og kan gå hjem? I prinsippet, ja, men i praksis, nei.

Flere triks for å behandle enorme spilltrær

Det krever noen ekstra triks for å behandle enorme spilltrær. Mange av dem ble brukt i IBMs sjakkdatamaskin Deep Blue da den vant over verdensmesteren Garry Kasparov i 1997.

Fordi vi bare kan undersøke en liten del av spilltreet, trenger vi en måte å avslutte minimax-gjentakelsen på før vi kommer frem til sluttnoden. Det vil si noden hvor spillet er over og vinneren er kåret. Dette oppnås ved å bruke en såkalt heuristisk evalueringsfunksjon. Den tar utgangspunkt i en spillsituasjon, inkludert informasjon om hvem av spillerne som står for tur, og gir en vurdering av det sannsynlige utfallet dersom spillet fortsetter fra denne spillsituasjonen.

Minimax-algoritmen vi har vist her krever bare minimale endringer for å bli en versjon der dybden begrenses , slik at heuristikkverdien fra nodene på denne dybden brukes, istedenfor å fortsette søket nedover. Med dybde mener man det nivået som noden befinner seg på i treet.