Minimax Algoritme Med Alpha-beta beskjæring

helt siden advent Av Kunstig Intelligens (AI), har spillet vært en AV DE mest interessante anvendelser AV AI.

de første sjakkprogrammene ble skrevet Av Claude Shannon og Av Alan Turing i 1950, nesten så snart datamaskinene ble programmerbare.

Spill som sjakk, tic-tac-toe og Go er interessante fordi De tilbyr en ren abstraksjon av konkurransen mellom de to hærene.

det er denne abstraksjonen som gjør spillet til et attraktivt område FOR AI-forskning.

i denne artikkelen vil vi gå gjennom grunnleggende Om Minimax-algoritmen sammen med algoritmens funksjon.

Vi vil også ta en titt på optimalisering av minimax algoritmen, alpha-beta beskjæring.

Hva Er Minimax-algoritmen?

Minimax Er en rekursiv algoritme som brukes til å velge et optimalt trekk for en spiller forutsatt at den andre spilleren også spiller optimalt.

Den brukes i spill som tic-tac-toe, go, chess, Isola, dam, og mange andre to-player spill.

Slike spill kalles spill av perfekt informasjon fordi det er mulig å se alle mulige trekk av et bestemt spill.

det kan være to-spiller spill som ikke er av perfekt informasjon som Scrabble fordi motstanderens trekk ikke kan forutsies.

det ligner på hvordan vi tenker når vi spiller et spill :» hvis jeg gjør dette trekket, kan motstanderen min bare gjøre bare disse trekkene, » og så videre.

Minimax kalles så fordi det bidrar til å minimere tapet når den andre spilleren velger strategien som har maksimalt tap.

Terminologi

• Spilltre: Det er en struktur i form av et tre som består av alle mulige trekk som lar deg flytte fra en tilstand av spillet til neste tilstand.

et spill kan defineres som et søkeproblem med følgende komponenter:

• Initial state: den består av styrets posisjon og viser hvem som beveger seg.
• Etterfølger funksjon: Det definerer hva de juridiske trekk en spiller kan gjøre er.
• Terminal state: Det er plasseringen av brettet når spillet kommer over.
• Utility function: Det er en funksjon som tildeler en numerisk verdi for utfallet av et spill. For eksempel, i sjakk eller tic-tac-toe, er utfallet enten en seier, et tap eller en uavgjort, og disse kan representeres av verdiene +1, -1 eller 0, henholdsvis. Det er spill som har et mye større utvalg av mulige utfall; for eksempel varierer verktøyene i backgammon fra +192 til -192. En bruksfunksjon kan også kalles en utbetalingsfunksjon.

hvordan fungerer algoritmen?

det er to spillere involvert I et spill, KALT MIN OG MAX. Spilleren MAX prøver å få høyest mulig poengsum og MIN prøver å få lavest mulig poengsum, dvs. min OG MAX prøver å handle motsatt av hverandre.

Den generelle prosessen Med Minimax-algoritmen er som følger:

Trinn 1: først genererer du hele spilltreet med den nåværende posisjonen til spillet helt opp til terminalstatene. Dette er hvordan spillet treet ser ut for spillet tic-tac-toe.

La oss forstå den definerte terminologien i form av diagrammet ovenfor.

1. den opprinnelige tilstanden er det første laget som definerer at brettet er tomt, DET ER MAXS tur til å spille.
2. Etterfølger-funksjonen viser alle mulige etterfølgerbevegelser. Det er definert for alle lagene i treet.
3. Terminalstatus er det siste laget av treet som viser den endelige tilstanden, dvs. om SPILLEREN MAKS vinner, taper eller bånd med motstanderen.
4. Verktøy i dette tilfellet for terminaltilstandene er 1, 0 og -1 som diskutert tidligere, og de kan også brukes til å bestemme verktøyene til de andre nodene.

Trinn 2: Bruk verktøyfunksjonen for å få verktøyverdiene for alle terminaltilstandene.
Trinn 3: Bestem verktøyene til de høyere noder ved hjelp av verktøyene til terminalnodene. For eksempel, i diagrammet nedenfor, har vi verktøyene for terminalstatene skrevet i rutene.

la oss beregne verktøyet for venstre node(rød) av laget over terminalen. Siden det er flyttingen av spilleren MIN, vil vi velge minimum av alle verktøyene. FOR dette tilfellet må VI evaluere MIN{3, 5, 10}, som vi vet er absolutt 3. Så verktøyet for den røde noden er 3.

På samme måte, for den grønne noden i samme lag, må VI evaluere MIN{2,2} som er 2.

Trinn 4: Beregn bruksverdiene ved hjelp av blader vurderer ett lag om gangen til roten av treet.
Trinn 5: til Slutt kommer alle sikkerhetskopierte verdier til roten av treet, det vil si det øverste punktet. PÅ DET tidspunktet MÅ MAX velge den høyeste verdien.

i vårt eksempel har vi bare 3 lag, så vi nådde umiddelbart til roten, men i faktiske spill vil det være mange flere lag og noder. SÅ VI må evaluere MAX{3,2} som er 3.

derfor er den beste åpningsflyten FOR MAX den venstre noden(eller den røde). Dette trekket kalles minimax-avgjørelsen, da det maksimerer verktøyet etter antagelsen om at motstanderen også spiller optimalt for å minimere den.

for å oppsummere,

Minimax Avgjørelse = MAKS{MIN{3,5,10}, MIN{2,2}}
= MAKS{3,2}
= 3

Psuedokode:

function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue

Optimalisering

Spilltrær er generelt svært tidkrevende å bygge, og det er bare for enkle spill at det kan genereres på kort tid.

hvis det er \(b\) lovlige trekk, dvs.,\ (b\) noder på hvert punkt og maksimal dybde av treet er \(m\), tidskompleksiteten til minimax-algoritmen er av rekkefølgen \(b^m(O (b^m))\).

for å dempe denne situasjonen, er det noen optimaliseringer som kan legges til algoritmen.

Heldigvis er Det levedyktig å finne den faktiske minimax-avgjørelsen uten å se på hver knutepunkt i spilltreet. Derfor eliminerer vi noder fra treet uten å analysere, og denne prosessen kalles beskjæring.

Alpha-beta beskjæring

metoden som vi skal se i denne artikkelen kalles alpha-beta beskjæring.

hvis vi bruker alfa-beta beskjæring til en standard minimax algoritme, returnerer den samme trekk som standard en, men det fjerner (svisker) alle noder som muligens ikke påvirker den endelige avgjørelsen.

La oss forstå intuisjonen bak dette først, og da vil vi formalisere algoritmen. Anta at vi har følgende spilltre:

i dette tilfellet
Minimax Beslutning = MAX{MIN{3,5,10}, MIN{2, a, b}, MIN{2,7,3}}
= MAX{3, c,2}
= 3

Du ville bli overrasket!

Hvordan kan vi beregne maksimumet med en manglende verdi? Her er trikset. MIN{2, a, b} ville sikkert være mindre enn eller lik 2, dvs. c<=2 OG DERMED MAX{3,c,2} må være 3.

spørsmålet nå er om vi virkelig trenger å beregne c? Selvsagt ikke.

Vi kunne ha kommet til en konklusjon uten å se på disse nodene. Og det er her alpha-beta beskjæring kommer inn i bildet.

noen få definisjoner:

Alpha: Det er det beste valget så langt FOR spilleren MAKS. Vi ønsker å få høyest mulig verdi her.
Beta: Det er det beste valget så langt FOR MIN, og det må være lavest mulig verdi.

Merk: hver node må holde oversikt over alfa-og beta-verdiene. Alpha kan oppdateres bare NÅR DET ER MAX tur og, tilsvarende, beta kan oppdateres bare når DET ER MIN sjanse.

hvordan fungerer alpha-beta beskjæring?

1. Initialiser alpha = -infinity og beta = infinity som de verste tilfellene. Betingelsen for å beskjære en node er når alfa blir større enn eller lik beta.
2. Begynn med å tilordne de opprinnelige verdiene for alfa og beta til rot, og siden alfa er mindre enn beta beskjærer vi ikke den.
3. Bær disse verdiene av alfa og beta til underordnet node til venstre. Og nå fra bruksverdien til terminalstaten, vil vi oppdatere verdiene til alpha og be, så vi trenger ikke å oppdatere verdien av beta. Igjen, vi beskjærer ikke fordi tilstanden forblir den samme. Tilsvarende er den tredje barneknuten ogsa. Og så backtracking til roten setter vi alpha = 3 fordi det er minimumsverdien som alpha kan ha.
   
4. nå, alpha = 3 og beta=uendelig ved roten. Så vi beskjærer ikke. Ved å bære dette til senternoden, og beregne MIN{2, uendelig}, får vi alfa=3 og beta=2.
5. Beskjær andre og tredje underordnede noder fordi alfa nå er større enn beta.
6. Alfa ved roten forblir 3 fordi Den er større enn 2. Bære dette til høyre barnnode, vurder MIN{uendelig, 2}=2. Oppdater beta til 2 og alfa forblir 3.
7. Beskjær andre og tredje underordnede noder fordi alfa nå er større enn beta.
8. Derfor får vi 3, 2, 2 til venstre, senter og høyre MIN noder, henholdsvis. Og ved Å beregne MAKS{3,2,2}, får vi 3. Derfor, uten å se på fire blader, kunne vi riktig finne minimax-beslutningen.

Pseudokode (Kilde: NPTEL Kurs):

evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha

Konklusjon

Spill er veldig tiltalende og skrive spill-spiller programmer er kanskje enda mer spennende. Hva Grand Prix racing er til bilindustrien, er spill å AI.

Akkurat som vi ikke forventer at en racerbil skal kjøre perfekt på en humpete vei, bør vi ikke forvente at spillspillalgoritmer skal være perfekte for enhver situasjon.

så er minimax-algoritmen. Det kan ikke være den beste løsningen på alle typer dataspill som MÅ HA AI.

men gitt en god implementering, kan det skape en tøff konkurrent.