Spille strategispill med Minimax-algoritmen

I denne leksjonen vil vi utforske en populær algoritme kalt minimax . Vi lærer også noen av de vennlige tilleggsfunksjonene i nabolaget som heuristiske poeng , iterativ utdyping og alfa-beta-beskjæring . Ved å bruke disse teknikkene kan vi skape en mer fleksibel og kraftig agent for spill. Det vil være i stand til å konkurrere i mange utfordringer, inkludert strategispillet Isolation.

I mitt forrige innlegg How To Win Sudoku lærte vi hvordan vi lærte datamaskiner å løse puslespillet Sudoku. Hvis du ikke har lest den, kan du lese den raskt. Men det var egentlig bare en måte å få føttene våte før vi dykket inn i mer sofistikerte metoder for å spille agenter. Spesielt de metodene som kan gjøre strategiske grep mot en motstander!

Ikke bli strandet

Isolation (eller Isola) er et turbasert strategi brettspill der to spillere prøver å begrense motstanderen på et 7x7 brikkelignende brett. Til slutt kan de ikke lenger gjøre et trekk (og dermed isolere dem).

Hver spiller har ett stykke, som de kan bevege seg rundt som en dronning i sjakk - opp-ned, venstre-høyre og diagonal. Det er tre forhold der brikkene kan flyttes -

  1. De kan ikke plassere stykket sitt på et allerede besøkt torg.
  2. De kan ikke krysse over allerede besøkte firkanter (å klemme dem diagonalt er OK).
  3. De kan ikke krysse hverandres brikke.

På bildet ovenfor kan du se fra de svarte rutene at begge spillerne har plassert brikkene sine på forskjellige deler av brettet. Men etter hvert som spillet utviklet seg, viser det at den gule spilleren fortsatt har tre mulige trekk. Opp og til høyre, høyre en firkant og høyre to firkanter. Men den blå spilleren er ute av muligheter. Derfor er den gule spilleren vinneren her.

Nå kan dette virke som et enkelt spill - og for å være ærlig, det er det. Det er ikke slik at vi spiller poker eller Starcraft. Likevel er det fremdeles en enorm mengde mulige trekk hver spiller kan gjøre når som helst i løpet av spillet.

I gåter som Sudoku er det et “svar” som vi ønsker å løse for. Men det er ikke noe svar når det gjelder strategispill.

Vi spiller mot en annen motstander - som en person, en datamaskin eller en kattedetektiv. Dette krever strategi og litt tanke på hvordan spillet kan bli når det ruller sammen.

Slike spill kan utvikle seg og gi en absurd mengde mulige resultater. Så vi må tenke på hvordan vi kan velge et best mulig trekk, uten å bruke den tiden det tok for katter å befolke jorden.

Ok, ikke flere katter!

Mighty Minimax And Friends

Nå som du vet hvordan du skal spille Isolation, la oss ta en titt på hvordan vi kan bruke minimax- algoritmen; en stift i AI-samfunnet. Vi vil også se på heuristiske poeng , iterativ utdyping og alfa-beta beskjæring . Sammen med disse kan vi bygge en konkurransedyktig AI-agent.

Minimax

Minimax-algoritmen er veldig populær for å lære AI-agenter hvordan de skal spille turbaserte strategispill. Årsaken er at det tar hensyn til alle mulige trekk som spillerne kan ta til enhver tid i løpet av spillet. Med denne informasjonen prøver den å minimere motstanderens fordel mens den maksimerer agentens hver gang AI-agenten får spille.

Nå, hvordan ser dette ut?

Vel, i likhet med hvordan en AI-agent ville spille et spill som Sudoku, kan vi modellere de neste mulige trekkene hver spiller kan gjøre via et søketre . Vi må imidlertid bruke et søketre med variabel bredde - eller med andre ord bredden på et trenivå. Årsaken er at det er et variabelt antall trekk hver spiller kan gjøre til enhver tid i løpet av spillet.

Treet vist ovenfor representerer de neste trekkene som er tilgjengelige under et spill av Isolation. Den har et 2x3 rutenett, med den nedre høyre firkanten som ikke kan nås. Som du kan se er de to spillerne en blå sirkel og et rødt kors.

Toppen av treet (rotnoden) illustrerer et trekk gjort av den røde spilleren. Midtnivået illustrerer neste mulige trekk av den blå spilleren. Og det tredje nivået illustrerer mulige trekk fra den røde spilleren, gitt det forrige trekket som ble gjort av den blå spilleren.

Hver spilltilstand eller node i treet har informasjon om hvilken spiller som har mest å tjene på potensielle trekk.

Nå lurer du kanskje på, hva pokker er de trekantene under hvert trekk?

Den nedadgående trekanten representerer et sted i treet der minimax vil minimere motstanderens fordel. Mens de oppadgående trekanter er stedene hvor minimax maksimerer agentens fordel.

Men minimax kan bare kjenne begge spilleres fordel hvis den kjenner banene i treet som fører til seier for begge spillere. Dette betyr at minimax må krysse helt til bunnen av treet for hver mulige serie trekk. Deretter må den tildele noe poengsum (f.eks. +1 for seier og -1 for tap), og forplante tallene opp gjennom treet. På denne måten har hver spilltilstand eller node i treet informasjon om hvilken spiller som har mest å tjene på et potensielt trekk.

På dette bildet kan vi gjøre et par observasjoner. Første minimax tildeler et nummer til de endelige spillresultatene på bladnodene . Deretter forplanter den dem oppover gjennom treet, og utfører minimeringer og maksimeringer på veien. Når minimax er ferdig med å fylle ut treet, vet det hvilke bevegelser som sannsynligvis vil føre til seier eller tap, når det er AI-agentens tur.

Det andre nivået etter rotnoden viser neste mulige trekk for den blå spilleren (vår AI-agent). Agenten vår vil maksimere tilgjengelige poeng i løpet av sin tur. Så det ville valgt trekket representert i den noden som ligger rett etter rotnoden. Superkul!

Men er det fornuftig å bare tilordne +1 eller -1 til spillresultatene? Bør ikke denne poengsummen ta hensyn til hvordan spillet blir vunnet eller tapt?

Spoilervarsel: svaret er ja!

Heuristiske poeng

I en verden av strategispill er en heuristisk poengsum egentlig en subjektiv verdi vi tildeler en eller annen spilltilstand. Denne verdien er basert på vår forståelse av hvordan spillet blir vunnet og tapt. Ved å velge en gjennomtenkt heuristisk poengsum kan vi lære AI-agenten vår hvordan vi best velger de neste trekkene mens vi spiller spillet Isolation.

Nå er det sannsynligvis et ubegrenset antall heuristiske poeng vi kan komme med. Men her vil vi bare se på noen få av dem, bortsett fra den naive poengsummen (NS) på +1 og -1.

En idé kan være å telle alle de neste mulige trekkene hver spiller har til enhver tid, siden flere mulige trekk betyr mindre sjanse for å bli isolert. Vi vil kalle dette Open Move Score (OMS) .

En annen idé kan være å bruke verdien oppnådd fra OMS og trekke antallet neste mulige trekk motstanderen har. Årsaken er at hver spiller vil øke antall trekk mens de reduserer motstanderens. Vi vil kalle dette forbedret poengsum (IS) .

Ovennevnte figur viser gevinstratene for mange simulerte isolasjonsspill spilt mellom AI-agenter ved bruk av forskjellige heuristiske poeng. Nå kan du se hvor forskjellige poengene våre gjorde under det faktiske spillet. Men det var noen heuristiske poeng som overgikk de vi kom på

Interessant, de to beste er nesten nøyaktig det samme som forbedret poengsum. Vi vil kalle dem aggressiv forbedret score (AIS) og super aggressiv forbedret score (SAIS) . Men det er en liten forskjell mellom disse partiturene og originalen. De to øverste poengene bruker en faktor på to og tre til verdien du trekker fra (antall trekk tilgjengelig for motstanderen) når du beregner den forbedrede poengsummen.

Du kan oppdage en optimal “aggressiv faktor” du kan bruke når du beregner denne poengsummen!

Nok et spoilervarsel - det finnes bedre verdier.

Men hva om vi kommer med en heuristisk poengsum som det tar mye tid å beregne? Hva om treet er stort? Vil vår AI-agent ha nok tid til å finne de neste beste trekkene, mens de fremdeles er lydhøre nok under spillet?

Iterativ fordypning

Nå vet vi at vår AI-agent kan modellere alle mulige trekk ved hjelp av et søketre og dets noders tilsvarende heuristiske poengsum. Men dessverre, når du spiller Isolation, vil treet vårt være massivt. Det ville ta mer tid å søke i treet og beregne disse verdiene enn det er år siden big bang!

Gå inn i iterativ utdyping - strategien for tidsstyring for spillagenter. Ved å bruke denne metoden kan vi kutte beregningstiden og søketiden ned til en maksimal tid vi velger. På denne måten kan vår AI-agent svare minst så raskt som et menneske kunne.

Men hvordan fungerer iterativ utdyping?

Det tillater minimax å bevege seg nivå for nivå og beregne heuristiske poeng til en viss tidsgrense. Når denne tidsgrensen er nådd, blir AI-agenten tvunget til å bruke det beste trekket den oppdaget mens han har beveget seg dypere og dypere nedover treet.

Nå gir dette litt innsikt i hvor vanskelig det kan være. Å lage en AI-agent som er smart og responsiv nok til strategispill, kan være ganske vanskelig, selv for AI-veivisere. Spesielt hvis slike spill inneholder en verden av muligheter.

Dessverre er antallet bevegelser AI-agenten kan "forestille seg" fremover begrenset. Så det er mulig det kan ta en beslutning som fører til at den er død. Dette er et kjent fenomen som kalles horisonteffekten . Men vi må fremdeles se på uten tvil den mest effektive algoritmen for tidsskjæring som brukes når du søker i trær.

Alpha-Beta Beskjæring

Ok, det er rosiner og ikke svisker, men likevel - hvordan var dette noen gang en ting? Jeg mener, seriøst, en rosinbluesgruppe?

Du har kanskje allerede gjettet alfa-beta-beskjæring har ingenting å gjøre med svisker, og mer om å redusere størrelsen (beskjæring) på søketreet vårt. Når vi har et veldig stort søketre, viser det seg at det ikke alltid er nødvendig å krysse hver node når vi bruker minimax.

Vi må gi minimax muligheten til å slutte å søke i en bestemt region av treet når den finner det garanterte minimum eller maksimum for det bestemte nivået.

Hvis vi kan gjøre det, kan dette redusere AI-agentens responstid og forbedre ytelsen.

Hvordan fungerer alfa-beta beskjæring?

Minimax-algoritmen beveger seg gjennom treet ved hjelp av første dybdesøk. Det betyr at den går gjennom treet fra venstre mot høyre, og alltid går dypest mulig. Den oppdager deretter verdier som må tildeles noder rett over den, uten å se på andre grener av treet.

Beskjæring med Alpha-beta gjør at minimax kan ta like gode beslutninger som minimax kunne gjøre alene, men med et høyere ytelsesnivå.

Tenk på følgende bilde, der vi har et tre med forskjellige poeng tildelt hver node. Noen noder er skyggelagt med rødt, noe som indikerer at du ikke trenger å gjennomgå dem.

Nederst til venstre på treet ser minimax på verdiene 5 og 6 på det nederste maksnivået. Den bestemmer at 5 må tilordnes min-nivået rett over det. Gir mening.

Men etter å ha sett på 7 og 4 i den rette maksnivågrenen, innser den at den ovennevnte min-nivånoden må tildeles en maksimumsverdi på 4. Siden det andre maksnivået rett over det første min-nivået vil ta maksimalt mellom 5 og på det meste 4 er det klart at det vil velge 5. Etter dette vil det fortsette å krysse treet for å utføre samme eksakte sett med operasjoner innenfor treets andre grener.

Nedenfor er den algoritmiske representasjonen av minimax med alfa-beta beskjæring.

Å bruke denne metoden gir en enkel måte å kutte ned på AI-agentens søkeplass. På denne måten tillater alfa-beta beskjæring minimax å ta gode avgjørelser som minimax kan gjøre alene, men med et høyere ytelsesnivå.

Isola-ter

Vi har utforsket hvordan vi bygger vår egen AI-agent som kan spille spillet Isolation på et ganske konkurransedyktig nivå. Ved å bruke minmax-algoritmen så vi hvordan AI-agenten kan modellere spillet og kan ta beslutninger basert på en heuristisk poengsum. Vi lærte også å bestemme en veldefinert heuristikk for vår gitte oppgave (Isolation).

Men vi oppdaget også at det ville være altfor beregningsintensivt å la minimax løpe vilt. Så vi måtte bruke teknikker som iterativ utdyping og alfa-beta beskjæring. Disse vil tvinge vår AI-agent til å komme med neste trekk innen rimelig tid. Men hva om vi vil at vår AI-agent skal ha en høyere gevinst, mens vi i det minste er like responsive som et menneske?

Vel, det er andre teknikker vi kan utforske for å øke agentens gevinstrate samt responstid. Vi berørte ideen om å justere parametrene til heuristiske poengsummer (husker du den “aggressive faktoren”?). Vi kan til og med komme med en heuristisk poengsum bedre skreddersydd for å spille Isolation.

Det er også reflekterende egenskaper relatert til mulige trekk på isolasjonskortet. Disse blir tydelige når vi analyserer det fullbefolkede søketreet, noe som gjør at vi potensielt kan kutte mange grener fra søketreet. Også, hvis vi oppgraderte maskinvaren vår, ville vår AI-agent være raskere - og dermed kunne utforske flere muligheter.

Hvis du vil komme inn på detaljene for hvordan du implementerer dette selv, kan du ta en titt på koden jeg skrev for å løse dette problemet for min Udacity Artificial Intelligence Nanodegree. Du finner den på GitHub-repoen min.

Hei, jeg er Grant! Jeg er frilansutvikler og kvant. Sjekk ut nettstedet mitt på //freelancequant.com. Jubel!