Afspilning af strategispil med Minimax-algoritmen

I denne lektion udforsker vi en populær algoritme kaldet minimax . Vi lærer også nogle af dens venlige tilføjelsesfunktioner i kvarteret som heuristiske scores , iterativ uddybning og alfa-beta-beskæring . Ved hjælp af disse teknikker kan vi skabe en mere fleksibel og stærk spilagent. Det vil være i stand til at konkurrere i mange udfordringer, herunder strategispil Isolation.

I mit tidligere indlæg Sådan vinder du Sudoku lærte vi, hvordan man lærer computere at løse puslespillet Sudoku. Hvis du ikke har læst det, skal du læse det hurtigt. Men det var virkelig bare en måde at få vore fødder på, inden vi dykkede ned i mere sofistikerede metoder til at spille agenter. Især de metoder, der kan foretage strategiske træk mod en modstander!

Bliv ikke strandet

Isolation (eller Isola) er et turbaseret strategi brætspil, hvor to spillere forsøger at begrænse deres modstander på et 7x7 brik-lignende bræt. Til sidst kan de ikke længere tage et skridt (og dermed isolere dem).

Hver spiller har et stykke, som de kan bevæge sig som en dronning i skak - op-ned, venstre-højre og diagonal. Der er tre betingelser, hvorunder stykkerne kan flyttes -

  1. De kan ikke placere deres stykke på en allerede besøgt plads.
  2. De kan ikke krydse allerede besøgte firkanter (at klemme diagonalt igennem er OK).
  3. De kan ikke krydse hinandens stykke.

På billedet ovenfor kan du se fra de sorte firkanter, at begge spillere har placeret deres brikker på forskellige dele af brættet. Men efterhånden som spillet skred frem, viser det, at den gule spiller stadig har tre mulige træk. Op og til højre, højre en firkant og højre to firkanter. Men den blå spiller er ude af muligheder. Derfor er den gule spiller vinder her.

Nu kan dette virke som et simpelt spil - og for at være ærlig er det. Det er ikke som om vi spiller poker eller Starcraft. Alligevel er der stadig en enorm mængde mulige træk, som hver spiller kan foretage på ethvert tidspunkt under spillet.

I gåder som Sudoku er der et “svar”, som vi vil løse. Men der er ikke noget svar, når det kommer til strategispil.

Vi spiller mod en anden modstander - som en person, en computer eller en katdetektiv. Dette kræver strategi og noget overvejelser om, hvordan spillet kan blive, når det ruller sammen.

Sådanne spil kan udvikle sig og producere en absurd mængde mulige resultater. Så vi er nødt til at tænke på, hvordan vi kan vælge den bedst mulige bevægelse uden at bruge den tid, det tog for katte at befolke jorden.

Okay, ikke flere katte!

Mighty Minimax And Friends

Nu hvor du ved, hvordan du spiller Isolation, skal vi se på, hvordan vi kan bruge minimax- algoritmen; et dagligt syn i AI-samfundet. Vi ser også på heuristiske scores , iterativ uddybning og alfa-beta-beskæring . Sammen med disse kan vi opbygge en konkurrencedygtig AI-agent.

Minimax

Minimax-algoritmen er meget populær til at lære AI-agenter, hvordan man spiller turbaserede strategispil. Årsagen er, at det tager højde for alle de mulige træk, som spillerne kan tage på et hvilket som helst tidspunkt i løbet af spillet. Med disse oplysninger forsøger den derefter at minimere modstanderens fordel, mens den maksimerer agentens hver gang AI-agenten spiller.

Hvordan ser det nu ud?

I lighed med hvordan en AI-agent ville spille et spil som Sudoku, kan vi modellere de næste mulige træk, som hver spiller kan foretage via et søgetræ . Vi skal dog bruge et søgetræ med variabel bredde - eller med andre ord et træniveaus bredde. Årsagen er, at der er et variabelt antal træk, som hver spiller kan foretage på et hvilket som helst tidspunkt under spillet.

Træet vist ovenfor repræsenterer de næste træk tilgængelige under et spil Isolation. Det har et 2x3 gitter, hvor nederste højre firkant ikke kan nås. Som du kan se, er de to spillere en blå cirkel og et rødt kors.

Toppen af ​​træet (rodnoden) illustrerer et træk foretaget af den røde spiller. Det midterste niveau illustrerer de næste mulige træk fra den blå spiller. Og det tredje niveau illustrerer de mulige træk fra den røde spiller, givet den tidligere træk foretaget af den blå spiller.

Hver spiltilstand eller knudepunkt i træet har information om, hvilken spiller der har mest at vinde på ethvert potentielt træk.

Nu spekulerer du måske på, hvad pokker er disse trekanter under hvert træk?

Den nedadgående trekant repræsenterer en placering i træet, hvor minimax minimerer modstanderens fordel. Mens de opadgående trekanter er de steder, hvor minimax maksimerer agentens fordel.

Men minimax kan kun kende begge spilleres fordel, hvis den kender stierne i træet, der fører til sejr for begge spillere. Dette betyder, at minimax skal krydse bunden af ​​træet for hver mulig række bevægelser. Derefter skal den tildele noget score (f.eks. +1 for en sejr og -1 for et tab) og sprede disse tal op gennem træet. På denne måde har hver spiltilstand eller knude i træet information om, hvilken spiller der har mest at vinde på ethvert potentielt træk.

På dette billede kan vi lave et par observationer. Første minimax tildeler et nummer til de endelige spilresultater ved bladknudepunkterne . Derefter formerer det dem opad gennem træet og udfører minimeringer og maksimeringer undervejs. Når minimax er færdig med at udfylde træet, vil det vide, hvilke bevægelser der sandsynligvis vil føre til sejr eller tab, når det er AI-agentens tur.

Det andet niveau efter rodnoden viser de næste mulige træk for den blå afspiller (vores AI-agent). Vores agent ønsker at maksimere de tilgængelige scores under sin tur. Så det ville vælge det træk, der er repræsenteret i den højeste knude efter rodknudepunktet. Super sejt!

Men giver det mening at blot tildele et +1 eller -1 til spilresultaterne? Bør denne score ikke tage højde for, hvordan spillet vindes eller tabes?

Spoiler alarm: svaret er ja!

Heuristiske score

I en verden af ​​strategispil er en heuristisk score i det væsentlige en subjektiv værdi, som vi tildeler en eller anden spiltilstand. Denne værdi er baseret på vores forståelse af, hvordan spillet vindes og tabes. Ved at vælge en gennemtænkt heuristisk score er vi i stand til at lære vores AI-agent, hvordan man bedst vælger de næste træk, mens vi spiller spillet Isolation.

Nu er der sandsynligvis et ubegrænset antal heuristiske scores, vi kunne komme med. Men her ser vi kun på nogle få af dem bortset fra den naive score (NS) på +1 og -1.

En idé kan være at tælle alle de næste mulige træk, hver spiller har til enhver tid, da flere mulige træk betyder mindre chance for at blive isoleret. Vi kalder dette det åbne træk-score (OMS) .

En anden idé kan være at bruge værdien opnået fra OMS og trække antallet af næste mulige træk, som modstanderen har. Årsagen er, at hver spiller ønsker at øge deres antal træk, mens den mindsker deres modstanders. Vi kalder dette den forbedrede score (IS) .

Ovenstående figur viser vinderaterne over mange simulerede isolationsspil, der spilles mellem AI-agenter ved hjælp af forskellige heuristiske scores. Nu kan du se, hvor forskellige vores scores gjorde under det aktuelle spil. Men der var nogle heuristiske scores, der overgik dem, vi kom på

Interessant nok er de to øverste næsten nøjagtigt de samme som forbedret score. Vi kalder dem aggressiv forbedret score (AIS) og super aggressiv forbedret score (SAIS) . Men der er en lille forskel mellem disse scores og originalen. De to øverste scorer anvender en faktor på to og tre på den værdi, du trækker med (antallet af tilgængelige træk for modstanderen), når du beregner den forbedrede score.

Du kan finde en optimal "aggressiv faktor", der skal anvendes, når du beregner denne score!

Endnu en spoileralarm - der findes bedre værdier.

Men hvad hvis vi kommer med en heuristisk score, der tager meget tid at beregne? Hvad hvis træet er stort? Vil vores AI-agent have tid nok til at finde de næste bedste træk, mens de stadig er lydhøre nok under spillet?

Iterativ uddybning

Nu ved vi, at vores AI-agent kan modellere alle mulige bevægelser ved hjælp af et søgetræ og dets noder 'tilsvarende heuristiske score. Men desværre, når vi spiller Isolation, vil vores træ være massivt. Det ville tage mere tid at søge i træet og beregne disse værdier, end der er år siden big bang!

Indtast iterativ uddybning - strategien til tid til styring af spilagenter. Ved at bruge denne metode kan vi skære beregningstiden og søgetiden ned til det maksimale tidspunkt, vi vælger. På denne måde kan vores AI-agent reagere mindst lige så hurtigt som et menneske kunne.

Men hvordan fungerer iterativ uddybning?

Det giver minimax mulighed for at bevæge sig niveau for niveau og beregne heuristiske scores indtil en bestemt tidsgrænse. Når denne tidsgrænse er nået, er AI-agenten tvunget til at bruge det bedste træk, det opdagede, mens han har bevæget sig dybere og dybere ned ad træet.

Nu giver dette et indblik i, hvor svært det kan være. Oprettelse af en AI-agent, der er smart og lydhør nok til strategispil, kan være ret vanskelig, selv for AI-guider. Især hvis sådanne spil indeholder en verden af ​​muligheder.

Desværre er antallet af bevægelser, som AI-agenten kan "forestille sig" fremad, begrænset. Så det er muligt, at det kan tage en beslutning, der fører til dens død. Dette er et velkendt fænomen kaldet horisonteffekten . Men vi er stadig nødt til at se på uden tvivl den mest effektive tidsskæringsalgoritme, der bruges til at søge i træer.

Beskæring af Alpha-Beta

Okay, det er rosiner og ikke svesker, men stadig - hvordan var det nogensinde en ting? Jeg mener alvorligt en rosinbluesgruppe?

Du har måske allerede gættet alfa-beta beskæring har intet at gøre med svesker, og mere om at reducere størrelsen (beskæring) af vores søgetræ. Når vi har et meget stort søgetræ, viser det sig, at det ikke altid er nødvendigt at krydse hver node, når vi bruger minimax.

Vi er nødt til at give minimax muligheden for at stoppe med at søge i en bestemt region af træet, når det finder det garanterede minimum eller maksimum for det bestemte niveau.

Hvis vi kan gøre det, kan dette i høj grad reducere vores AI-agents responstid og forbedre ydelsen.

Hvordan fungerer alfa-beta beskæring?

Minimax-algoritmen bevæger sig gennem træet ved hjælp af dybde-første søgning. Det betyder, at det krydser gennem træet, der går fra venstre mod højre, og altid går den dybeste, det kan gå. Derefter opdager det værdier, der skal tildeles knuder direkte over det uden nogensinde at se på andre grene af træet.

Beskæring med Alpha-beta gør det muligt for minimax at træffe lige så gode beslutninger som minimax kunne gøre alene, men med et højere ydeevne.

Overvej følgende billede, hvor vi har et træ med forskellige scorer tildelt hver node. Nogle noder er skyggelagt med rødt, hvilket indikerer, at der ikke er behov for at gennemgå dem.

Nederst til venstre på træet ser minimax på værdierne 5 og 6 på det nederste maksimumniveau. Det bestemmer, at 5 skal tildeles min-niveauet lige over det. Giver mening.

Men efter at have set på 7 og 4 i den rigtige max-niveau-gren, indser den, at ovenstående min-niveau-knude skal tildeles en maksimumsværdi på 4. Da det andet max-niveau lige over det første min-niveau vil tage det maksimale mellem 5 og højst 4 er det klart, at det vælger 5. Efter dette vil det fortsætte med at krydse træet for at udføre det samme nøjagtige sæt operationer inden for træets andre grene.

Nedenfor er den algoritmiske repræsentation af minimax med alfa-beta beskæring.

Brug af denne metode giver en nem måde at skære ned på vores AI-agents søgerum. På denne måde giver alfa-beta beskæring minimax mulighed for at træffe gode beslutninger, som minimax kunne gøre alene, men med et højere niveau af ydeevne.

Isola-ter

Vi har undersøgt, hvordan vi bygger vores egen AI-agent, der kan spille spillet Isolation på et ret konkurrencedygtigt niveau. Ved at bruge minmax-algoritmen så vi, hvordan AI-agenten kan modellere spillet og kan træffe beslutninger baseret på en heuristisk score. Vi lærte også at bestemme en veldefineret heuristik til vores givne opgave (Isolation).

Men vi opdagede også, at det ville være alt for beregningsintensivt at lade minimax løbe vildt. Så vi var nødt til at bruge teknikker som iterativ uddybning og alfa-beta beskæring. Disse vil tvinge vores AI-agent til at komme med det næste skridt inden for en rimelig tid. Men hvad hvis vi vil have vores AI-agent til at have en højere gevinstprocent, mens vi i det mindste er så lydhøre som et menneske?

Der er andre teknikker, vi kunne udforske for at øge vores agents gevinstprocent samt svartid. Vi berørte ideen om at tilpasse vores heuristiske scores parametre (husker du den “aggressive faktor”?). Vi kunne endda komme med en heuristisk score, der var bedre skræddersyet til at spille Isolation.

Der er også reflekterende egenskaber relateret til de mulige bevægelser på isolationskortet. Disse bliver tydelige, når vi analyserer det fuldt udfyldte søgetræ, hvilket gør det muligt for os at skære mange grene fra søgetræet. Hvis vi opgraderede vores hardware, ville vores AI-agent også være hurtigere - og dermed være i stand til at udforske flere muligheder.

Hvis du vil komme ind i de detaljerede detaljer om, hvordan du selv implementerer dette, skal du kigge på koden, jeg skrev for at løse dette problem til min Udacity Artificial Intelligence Nanodegree. Du kan finde det på min GitHub repo.

Hej, jeg er Grant! Jeg er freelance udvikler og kvant. Tjek min hjemmeside på //freelancequant.com. Skål!