Brætspil Kunstig intelligens: Minimax -algoritmen: 8 trin

2024 Forfatter: John Day | [email protected]. Sidst ændret: 2024-01-30 08:27

Har du nogensinde spekuleret på, hvordan de computere, du spiller mod i skak eller brikker, er lavet? Se ikke længere end denne Instructable, for den viser dig, hvordan du laver en simpel, men effektiv kunstig intelligens (AI) ved hjælp af Minimax -algoritmen! Ved at bruge Minimax -algoritmen laver AI godt planlagte og gennemtænkte træk (eller efterligner i det mindste en tankeproces). Nu kunne jeg bare give dig koden til den AI, jeg lavede, men det ville ikke være sjovt. Jeg forklarer logikken bag computerens valg.

I denne instruks vil jeg guide dig gennem trinene til, hvordan du laver en AI til Othello (AKA Reversi) i python. Du bør have en mellemliggende forståelse af, hvordan du koder i python, før du tackler dette projekt. Her er et par gode websteder at se på for at forberede dig på denne Instructable: w3schools eller learnpython. I slutningen af denne instruktive skal du have en AI, der vil foretage beregnede træk og skal kunne besejre de fleste mennesker.

Da denne Instructable primært vil beskæftige sig med, hvordan man laver en AI, vil jeg ikke forklare, hvordan man designer et spil i python. I stedet vil jeg give koden til spillet, hvor et menneske kan spille mod et andet menneske og ændre det, så du kan spille et spil, hvor et menneske spiller mod AI.

Jeg lærte at oprette denne AI gennem et sommerprogram på Columbia SHAPE. Jeg havde det godt der, så tag et kig på deres hjemmeside for at se, om du ville være interesseret.

Nu hvor vi fik logistikken af vejen, lad os begynde at kode!

(Jeg lagde et par noter i billederne, så sørg for at se dem)

Forbrugsvarer

Dette er let:

1) Computer med et python -miljø som Spyder eller IDLE

2) Download filerne til Othello -spillet fra min GitHub

3) Din hjerne med tålmodighed installeret

Trin 1: Download de nødvendige filer

Når du går ind på min GitHub, skal du se 5 filer. Download alle 5 og placer dem alle i den samme mappe. Inden vi kører spillet, skal du åbne alle filerne i spyder -miljøet.

Her er hvad filerne gør:

1) othello_gui.py denne fil opretter spillebrættet for spillerne at spille på (uanset om det er menneske eller computer)

2) othello_game.py denne fil spiller to computere mod hinanden uden spillepladen og viser kun scoren og flytte positioner

3) ai_template.py det er her, du vil lægge al din kode for at lave din AI

4) randy_ai.py dette er en præfabrikeret AI, der vælger sine bevægelser tilfældigt

5) othello_shared.py en flok præfabrikerede funktioner, som du kan bruge til at lave din AI, f.eks. For at kontrollere, om der er tilgængelige træk, score eller bordstat

6) De tre andre filer: Puma.py, erika_5.py og nathan.py, lavet af henholdsvis mig, Erika og Nathan fra SHAPE -programmet, disse er tre forskellige AI'er med unikke koder

Trin 2: Sådan åbnes og afspilles Python Othello

Når du har alle filerne åbne, skal du skrive "kør othello_gui.py" i nederste højre hjørne af skærmen og trykke på enter i IPython-konsollen. Eller i Mac -terminal skal du skrive "python othello_gui.py" (efter at du selvfølgelig er i den rigtige mappe). Derefter skulle et bord dukke op på din skærm. Denne tilstand er den menneskelige mod den menneskelige tilstand. Lys går andet og mørkt først. Se min video, hvis du er forvirret. iOverst er der point for hver farveflise. For at spille skal du klikke på en gyldig flytteplads for at placere en flise der og derefter give computeren til din modstander, der vil gøre det samme og gentage.

Hvis du ikke ved, hvordan du spiller Othello, skal du læse disse regler fra ultra boards -webstedet:

Sort bevæger sig altid først. Et træk foretages ved at placere en skive med spillerens farve på brættet i en position, der "out-flankerer" en eller flere af modstanderens skiver. En disk eller en række diske flankeres, når den i enderne er omgivet af diske med den modsatte farve. En disk kan flankere et vilkårligt antal diske i en eller flere rækker i en hvilken som helst retning (vandret, lodret, diagonal)…. (læs færdig på deres hjemmeside)

Forskellen mellem det originale spil og dette python -spil er, at når der ikke er gyldige træk tilbage for en spiller, slutter spillet

Nu hvor du kan spille spillet med en ven, lad os lave en AI, som du kan spille med.

Trin 3: Minimax -algoritme: Generering af scenarier

Før vi taler om, hvordan man skriver dette i kode, lad os gå over logikken bag det. Minimax-algoritmen er en beslutningstagende, back-tracking-algoritme og bruges typisk i to-spiller, turn-baserede spil. Målet med denne AI er at finde det næstbedste træk og de følgende bedste træk, indtil det vinder spillet.

Nu hvordan ville algoritmen bestemme hvilket træk der er det bedste træk? Stop og tænk, hvordan du ville vælge det næste træk. De fleste mennesker ville vælge det træk, der ville give dem flest point, ikke? Eller hvis de tænkte fremad, ville de vælge det træk, der ville skabe en situation, hvor de kunne få endnu flere point. Sidstnævnte tankegang er den måde, hvorpå Minimax -algoritmen tænker. Det ser frem til alle de fremtidige bestyrelsesopsætninger og foretager det træk, der ville føre til flest point.

Jeg kaldte dette en backtracking -algoritme, fordi den starter med først at oprette og evaluere alle de fremtidige bestyrelsesstater med deres tilhørende værdier. Det betyder, at algoritmen vil spille spillet så mange, som det skal (foretage træk for sig selv og modstanderen), indtil hvert scenarie i spillet har spillet. For at holde styr på alle bestyrelsestilstande (scenarier) kan vi tegne et træ (se på billederne). Træet på billedet ovenfor er et simpelt eksempel på et spil Connect 4. Hver bordkonfiguration kaldes en board -tilstand, og dens sted på træet kaldes en node. Alle knuderne i bunden af træet er de sidste tavler efter at have foretaget alle træk. Nogle bestyrelsesstater er naturligvis bedre for den ene spiller end den anden. Så nu skal vi få AI til at vælge, hvilken bestyrelsesstat den ønsker at komme til.

Trin 4: Minimax: Evaluering af bordkonfigurationer

For at give værdier til brætstaterne skal vi lære strategierne for det spil, vi spiller: i dette tilfælde Othellos strategier. Fordi dette spil er en kamp om at vende modstanderens og dine diske, er de bedste diskplaceringer dem, der er stabile og ikke kan vendes. Hjørnet er for eksempel det sted, hvor en disk ikke kan ændres til den anden farve, når en disk placeres. Således ville dette sted være yderst værdifuldt. Andre gode positioner inkluderer siderne af brættet, som giver dig mulighed for at tage en masse sten. Der er flere strategier på dette websted.

Nu kan vi tildele værdier til positionerne for hver bestyrelsesstatsbestyrelse. Når en position er besat af AI's brik, giver du et bestemt antal point afhængigt af positionen. For eksempel kan en brætstat, hvor AI's brik er i hjørnet, give en bonus på 50 point, men hvis det var på et ugunstigt sted, kan stykket have en værdi på 0. Efter at have taget alle værdierne i betragtning positionerne, tildeler du bestyrelsen en værdi. For eksempel, hvis AI har et stykke i hjørnet, kan boardstaten have en score på 50, mens en anden board state med AI's brik i midten har en score på 10.

Der er mange måder at gøre dette på, og jeg har tre forskellige heuristikker til at evaluere tavlestykkerne. Jeg opfordrer dig til at lave din egen type heuristik. Jeg uploadede tre forskellige AI'er til min github af tre forskellige producenter med tre forskellige heuristikker: Puma.py, erika5.py, nathanh.py.

Trin 5: Minimax -algoritme: Valg af det bedste træk

Nu ville det være rart, hvis AI bare kunne vælge alle træk for at komme til bestyrelsesstaten med den højeste score. Men husk, at AI også valgte bevægelserne for modstanderen, da den genererede alle brætstaterne, og hvis modstanderen er smart, tillader den ikke AI at nå den højeste brætscore. I stedet ville en smart modstander tage skridtet til at få AI til at gå til den laveste brætstat. I algoritmen kalder vi de to spillere en maksimeringsspiller og en minimeringsspiller. AI ville være den maksimerende spiller, da den ønsker at få flest point for sig selv. Modstanderen ville være den minimerende spiller, da modstanderen forsøger at foretage trækket, hvor AI får færrest point.

Når alle brættilstande er genereret og værdier er blevet tildelt tavlerne, begynder algoritmen at sammenligne tavlestaterne. På billederne skabte jeg et træ for at repræsentere, hvordan algoritmen ville vælge sine træk. Hver splittelse i grenene er et andet træk AI eller modstanderen kan spille. Til venstre for noderækkerne skrev jeg, om maksimaliserings- eller minimeringsspilleren kører. Den nederste række er alle bestyrelsesstaterne med deres værdier. Inde i hver af disse noder er et tal, og det er de score, vi tildeler hvert af tavlerne: Jo højere de er, jo bedre er det for AI at have.

Definitioner: forældreknudepunkt - en knude, der resulterer eller opretter noder under den; børneknudernes oprindelse - de knuder, der kommer fra den samme forældreknude

De tomme knuder repræsenterer hvilken bevægelse AI vil foretage for at komme til den bedste tavletilstand. Det starter med at sammenligne børnene i den knude til venstre: 10, -3, 5. Da den maksimerende spiller ville foretage træk, ville den vælge det træk, der ville give det flest point: 10. Så vi vælger og gemmer det flytte med brættet score og skrive det i forældreknudepunktet. Nu hvor 10 er i forældreknudepunktet, er det nu minimeringsspillernes tur. Noden, som vi ville sammenligne 10 med, er imidlertid tom, så vi er nødt til at evaluere den node først, før den minimerende spiller kan vælge. Så vi går tilbage til den maksimerende spillers tur og sammenligner børnene i den tilstødende knude: 8, -2. Maksimering vælger 8, og vi skriver det i den tomme forældreknude. Nu hvor algoritmen er færdig med at udfylde de tomme rum for børn i en node over den, kan den minimerende spiller sammenligne disse børn - 10 og 8 og vælge 8. Algoritmen gentager derefter denne proces, indtil hele træet er udfyldt. I slutningen af dette eksempel har vi scoren 8. Det er den højeste brætstat, AI kan spille for at antage, at modstanderen spiller optimalt. Så AI vil vælge det første træk, der fører til 8 -bordets tilstand, og hvis modstanderen spiller optimalt, bør AI spille alle træk for at komme til board -tilstand 8. (Følg noterne på mine billeder)

Jeg ved, det var meget. Hvis du er en af de typer, der skal have nogen til at tale med dig for at forstå noget, her er et par videoer, som jeg så for at hjælpe mig med at forstå ideen bag dette: 1, 2, 3.

Trin 6: Minimax -algoritme: Pseudokode

Når du forstår logikken bag minimax -algoritmen, skal du kigge på denne pseudokode (de funktioner, der er universelle for alle koder) fra wikipedia:

funktion minimax (node, dybde, maximizingPlayer) er

hvis dybde = 0 eller node er en terminal knude derefter

returnere den heuristiske værdi af node

hvis maximering af Spiller derefter

værdi: = −∞

for hvert nodebarn

værdi: = max (værdi, minimax (barn, dybde - 1, FALSK))

returværdi

andet (* minimering af afspiller *)

værdi: = +∞

for hvert nodebarn

værdi: = min (værdi, minimax (barn, dybde - 1, SAND))

returværdi

Dette er en rekursiv funktion, hvilket betyder, at den kalder sig selv igen og igen, indtil den når et stoppunkt. Først indtager funktionen tre værdier, noden, dybden, og hvis tur det er. Nodeværdien er det sted, hvor du vil have programmet til at begynde at søge. Dybden er, hvor langt du vil have programmet til at søge. For eksempel har det i mit træeksempel en dybde på 3, fordi det søgte i alle brætstaterne efter 3 træk. Selvfølgelig vil vi gerne have, at AI kontrollerer hver bestyrelsesstat og vælger en vindende gevinst, men i de fleste spil, hvor der er tusinder, hvis ikke millioner af bordkonfigurationer, vil din bærbare computer derhjemme ikke kunne behandle alle disse konfigurationer. Så vi begrænser AI's søgedybde og får den til at gå til den bedste bestyrelsesstat.

Denne pseudokode gengiver den proces, som jeg forklarede i de to foregående trin. Lad os nu tage dette et skridt videre og rette dette i python -kode.

Trin 7: Lav din AI med Ai_template.py

Inden du kigger på min Minimax AI-kode, skal du prøve at lave din egen AI med filen ai_template.py og pseudokoden, vi talte om i det sidste trin. Der er to funktioner i ai -skabelonen kaldet: def minimax_min_node (board, color) og def minimax_max_node (board, color). I stedet for at minimax -funktionen kalder sig selv rekursivt, har vi to forskellige funktioner, som kalder hinanden. For at skabe det heuristiske for at evaluere bestyrelsestilstande, bliver du nødt til at oprette din egen funktion. Der er en forhåndsdefineret funktion i othello_shared.py -filen, som du kan bruge til at bygge din AI.

Når du har din AI, kan du prøve at køre den mod, randy_ai.py. Hvis du vil køre to ais mod hinanden, skal du indtaste "python othello_gui.py (indsæt ai -filnavn).py (indsæt filnavn).py" i mac -terminalen eller indtaste "run othello_gui.py (indsæt ai -filnavn).py (indsæt filnavn).py "og sørg for, at du er i det rigtige bibliotek. Se også min video for de nøjagtige trin.

Trin 8: Tid til at få AI til at kæmpe

Få nu en flok af dine computervenner og få dem til at designe deres egen AI! Derefter kan du lave en konkurrence og få din AI hertug det ud. Forhåbentlig, selvom du ikke kunne bygge din egen AI, var du i stand til at forstå, hvordan minimax -algoritmen fungerer. Hvis du har spørgsmål, er du velkommen til at sende spørgsmål i kommentarerne herunder.