Bordspel Kunstmatige Intelligentie: het Minimax-algoritme - Ajarnpa

2024 Auteur: John Day | [email protected]. Laatst gewijzigd: 2024-01-30 11:16

Heb je je ooit afgevraagd hoe de computers waar je tegen speelt bij schaken of dammen worden gemaakt? Zoek niet verder dan dit Instructable, want het laat je zien hoe je een eenvoudige maar effectieve kunstmatige intelligentie (AI) kunt maken met behulp van het Minimax-algoritme! Door het Minimax-algoritme te gebruiken, maakt de AI goed geplande en doordachte bewegingen (of bootst op zijn minst een denkproces na). Ik zou je de code kunnen geven voor de AI die ik heb gemaakt, maar dat zou niet leuk zijn. Ik zal de logica achter de keuzes van de computer uitleggen.

In deze Instructable zal ik je door de stappen leiden voor het maken van een AI voor Othello (AKA Reversi) in python. U moet een gemiddeld begrip hebben van hoe u in python moet coderen voordat u dit project aanpakt. Hier zijn een paar goede websites om naar te kijken om je voor te bereiden op deze Instructable: w3schools of learnpython. Aan het einde van deze Instructable zou je een AI moeten hebben die berekende bewegingen maakt en de meeste mensen zou moeten kunnen verslaan.

Aangezien dit Instructable voornamelijk gaat over het maken van een AI, zal ik niet uitleggen hoe je een spel in Python ontwerpt. In plaats daarvan zal ik de code geven voor het spel waarin een mens tegen een ander mens kan spelen en deze aanpassen zodat je een spel kunt spelen waarin een mens tegen de AI speelt.

Ik heb geleerd hoe ik deze AI kan maken via een zomerprogramma bij Columbia SHAPE. Ik heb er een leuke tijd gehad, dus neem een kijkje op hun website om te zien of je interesse hebt.

Nu we de logistiek uit de weg hebben geruimd, gaan we beginnen met coderen!

(Ik heb een paar aantekeningen in de afbeeldingen geplaatst, dus zorg ervoor dat je ze bekijkt)

Benodigdheden

Dit is makkelijk:

1) Computer met een python-omgeving zoals Spyder of IDLE

2) Download de bestanden voor het Othello-spel van mijn GitHub

3) Je hersenen met geduld geïnstalleerd

Stap 1: Download de benodigde bestanden

Als je naar mijn GitHub gaat, zou je 5 bestanden moeten zien. Download ze alle 5 en plaats ze allemaal in dezelfde map. Voordat we het spel starten, opent u alle bestanden in de spyder-omgeving.

Dit is wat de bestanden doen:

1) othello_gui.py dit bestand creëert het spelbord waarop de spelers kunnen spelen (mens of computer)

2) othello_game.py dit bestand speelt twee computers tegen elkaar zonder het bord en toont alleen de score en zetposities

3) ai_template.py dit is waar je al je code gaat plaatsen om je AI te maken

4) randy_ai.py dit is een vooraf gemaakte AI die zijn bewegingen willekeurig kiest

5) othello_shared.py een heleboel vooraf gemaakte functies die u kunt gebruiken om uw AI te maken, zoals het controleren op beschikbare zetten, de score of bordstatus

6) De drie andere bestanden: Puma.py, erika_5.py en nathan.py, respectievelijk gemaakt door mij, Erika en Nathan uit het SHAPE-programma, dit zijn drie verschillende AI's met unieke codes

Stap 2: Hoe Python Othello te openen en te spelen

Zodra u alle bestanden hebt geopend, typt u in de rechterbenedenhoek van het scherm "run othello_gui.py" en drukt u op enter in de IPython-console. Of typ in de Mac-terminal "python othello_gui.py" (nadat u zich in de juiste map bevindt natuurlijk). Dan zou er een bord op je scherm moeten verschijnen. Deze modus is de modus mens versus mens. Licht gaat op de tweede plaats en donker eerst. Kijk naar mijn video als je in de war bent. iBovenaan staat de score van elke kleurtegel. Om te spelen, klikt u op een geldig verplaatsingsvak om daar een tegel te plaatsen en geeft u de computer aan uw tegenstander die hetzelfde zal doen en herhalen.

Als je niet weet hoe je Othello moet spelen, lees dan deze regels van de ultra boards-website:

Zwart zet altijd eerst. Een zet wordt gedaan door een schijf in de kleur van de speler op het bord te plaatsen in een positie die een of meer van de schijven van de tegenstander "over-flankt". Een schijf of rij schijven wordt omsingeld wanneer deze aan de uiteinden wordt omgeven door schijven van de tegenovergestelde kleur. Een schijf mag een willekeurig aantal schijven in een of meer rijen in elke richting (horizontaal, verticaal, diagonaal)… omcirkelen. (beëindig het lezen op hun website)

Het verschil tussen het originele spel en dit pythonspel is dat wanneer er geen geldige zetten meer zijn voor één speler, het spel eindigt

Nu je de game met een vriend kunt spelen, gaan we een AI maken waarmee je kunt spelen.

Stap 3: Minimax-algoritme: scenario's genereren

Voordat we het hebben over hoe dit in code te schrijven, laten we de logica erachter bekijken. Het minimax-algoritme is een besluitvormings-, back-tracking-algoritme en wordt meestal gebruikt in turn-based games voor twee spelers. Het doel van deze AI is om de volgende beste zet en de volgende beste zetten te vinden totdat hij het spel wint.

Hoe zou het algoritme nu bepalen welke zet de beste zet is? Stop en bedenk hoe je de volgende zet zou kiezen. De meeste mensen zouden de zet kiezen die hen de meeste punten zou opleveren, toch? Of als ze vooruit dachten, zouden ze de zet kiezen die een situatie zou creëren waarin ze nog meer punten zouden kunnen behalen. De laatste manier van denken is de manier waarop het Minimax-algoritme denkt. Het kijkt vooruit naar alle toekomstige bordopstellingen en maakt de zet die tot de meeste punten zou leiden.

Ik noemde dit een backtracking-algoritme, omdat het begint met het maken en evalueren van alle toekomstige bordstatussen met hun bijbehorende waarden. Dit betekent dat het algoritme het spel zo vaak zal spelen als nodig is (de zetten voor zichzelf en de tegenstander doen) totdat elk scenario van het spel is gespeeld. Om alle bordstatussen (scenario's) bij te houden, kunnen we een boom tekenen (kijk in de afbeeldingen). De boom in de afbeelding hierboven is een eenvoudig voorbeeld van een spel van Connect 4. Elke bordconfiguratie wordt een bordstatus genoemd en zijn plaats in de boom wordt een knooppunt genoemd. Alle knooppunten onderaan de boom zijn de laatste bordstatussen na het maken van alle zetten. Het is duidelijk dat sommige bordstatussen beter zijn voor de ene speler dan voor de andere. Dus nu moeten we de AI laten kiezen naar welke bordstatus het wil gaan.

Stap 4: Minimax: bordconfiguraties evalueren

Om waarden aan de bordstaten te geven, moeten we de strategieën leren van het spel dat we spelen: in dit geval de strategieën van Othello. Omdat dit spel een gevecht is tussen het omdraaien van de schijven van de tegenstander en jouw schijven, zijn de beste schijfposities die welke stabiel zijn en niet kunnen worden omgedraaid. De hoek is bijvoorbeeld de plaats waar wanneer een schijf wordt geplaatst deze niet in de andere kleur kan worden veranderd. Die plek zou dus zeer waardevol zijn. Andere goede posities zijn de zijkanten van het bord, waardoor je veel stenen kunt nemen. Er zijn meer strategieën op deze website.

Nu kunnen we waarden toewijzen aan de posities voor elk bordstatusbord. Wanneer een positie wordt ingenomen door het stuk van de AI, dan geef je een bepaald aantal punten afhankelijk van de positie. Bijvoorbeeld, een bord staat waar het stuk van de AI in de hoek staat, je kunt een bonus van 50 punten geven, maar als het op een ongunstige plek zou staan, kan het stuk een waarde van 0 hebben. Na rekening te hebben gehouden met alle waarden van de posities, kent u de bordstatus een waarde toe. Als de AI bijvoorbeeld een stuk in de hoek heeft, kan de bordstatus een score van 50 hebben, terwijl een andere bordstatus met het stuk van de AI in het midden een score van 10 heeft.

Er zijn veel manieren om dit te doen, en ik heb drie verschillende heuristieken om de bordstukken te evalueren. Ik moedig je aan om je eigen soort heuristiek te maken. Ik heb drie verschillende AI's naar mijn github geüpload door drie verschillende makers, met drie verschillende heuristieken: Puma.py, erika5.py, nathanh.py.

Stap 5: Minimax-algoritme: de beste zet kiezen

Nu zou het mooi zijn als de AI gewoon alle zetten zou kunnen kiezen om bij de bordstatus met de hoogste score te komen. Maar onthoud dat de AI ook de zetten voor de tegenstander koos toen het alle bordstatussen genereerde en als de tegenstander slim is, zal het de AI niet toestaan om de hoogste bordscore te halen. In plaats daarvan zou een slimme tegenstander de zet doen om de AI naar de laagste bordstatus te laten gaan. In het algoritme noemen we de twee spelers een maximaliserende speler en een minimaliserende speler. De AI zou de maximale speler zijn, omdat hij de meeste punten voor zichzelf wil krijgen. De tegenstander zou de minimaliserende speler zijn, aangezien de tegenstander de zet probeert te maken waar de AI de minste punten krijgt.

Zodra alle bordstatussen zijn gegenereerd en waarden zijn toegewezen aan de borden, begint het algoritme de bordstatussen te vergelijken. In de afbeeldingen heb ik een boom gemaakt om weer te geven hoe het algoritme zijn bewegingen zou kiezen. Elke splitsing in de takken is een andere zet die de AI of de tegenstander kan spelen. Links van de rijen knooppunten schreef ik of de maximaliserende of minimaliserende speler gaat. De onderste rij bevat alle bordstaten met hun waarden. Binnenin elk van die knooppunten bevindt zich een nummer en dat zijn de scores die we aan elk van de borden toewijzen: hoe hoger ze zijn, hoe beter het is voor de AI.

Definities: bovenliggend knooppunt - een knooppunt dat eronder resulteert of knooppunten maakt; de oorsprong van de onderliggende knooppunten - de knooppunten die afkomstig zijn van hetzelfde bovenliggende knooppunt

De lege knooppunten geven aan welke beweging de AI zal maken om de beste bordstatus te bereiken. Het begint met het vergelijken van de kinderen van de meest linkse knoop: 10, -3, 5. Aangezien de speler die de maximale zet zou doen, de zet zou kiezen die hem de meeste punten zou opleveren: 10. Dus selecteren en bewaren we die zet. verplaats met de bordscore en schrijf deze in het bovenliggende knooppunt. Nu 10 zich in het bovenliggende knooppunt bevindt, zijn nu de minimaliserende spelers aan de beurt. Het knooppunt waarmee we 10 zouden vergelijken is echter leeg, dus we moeten dat knooppunt eerst evalueren voordat de minimaliserende speler kan kiezen. We gaan dus terug naar de beurt van de maximaliserende speler en vergelijken de kinderen van de aangrenzende knoop: 8, -2. Maximaliseren zal 8 kiezen en dat schrijven we in het lege bovenliggende knooppunt. Nu het algoritme klaar is met het invullen van de lege ruimtes voor de kinderen van een knooppunt erboven, kan de minimaliserende speler die kinderen vergelijken - 10 en 8 en 8 kiezen. Het algoritme herhaalt dit proces totdat de hele boom is ingevuld. Aan het einde van dit voorbeeld hebben we de score 8. Dat is de hoogste bordstatus die de AI kan spelen, ervan uitgaande dat de tegenstander optimaal speelt. Dus de AI zal de eerste zet kiezen die leidt naar de 8-bordstatus, en als de tegenstander optimaal speelt, moet de AI alle zetten spelen om in bordstatus 8 te komen. (Volg de opmerkingen op mijn foto's)

Ik weet dat dat veel was. Als je een van die types bent die iemand met je moet laten praten om iets te begrijpen, zijn hier een paar video's die ik heb bekeken om me te helpen het idee hierachter te begrijpen: 1, 2, 3.

Stap 6: Minimax-algoritme: pseudocode

Nadat je de logica achter het minimax-algoritme hebt begrepen, bekijk je deze pseudocode (de functies die universeel zijn voor alle codes) van wikipedia:

functie minimax (knooppunt, diepte, maximizingPlayer) is

als diepte = 0 of knooppunt een eindknooppunt is, dan

retourneer de heuristische waarde van node

als je Player maximaliseert dan

waarde:=

voor elk kind van knoop do

waarde:= max(waarde, minimax(kind, diepte − 1, ONWAAR))

winstwaarde

else (*minimaliseren speler *)

waarde:= +∞

voor elk kind van knoop do

waarde:= min(waarde, minimax(kind, diepte − 1, WAAR))

winstwaarde

Dit is een recursieve functie, wat betekent dat het zichzelf keer op keer aanroept totdat het een stoppunt bereikt. Ten eerste neemt de functie drie waarden in, het knooppunt, de diepte en wiens beurt het is. De node-waarde is de plaats waar u wilt dat het programma begint te zoeken. De diepte is hoe ver je wilt dat het programma zoekt. In mijn boomvoorbeeld heeft het bijvoorbeeld een diepte van 3, omdat het alle bordtoestanden na 3 zetten heeft doorzocht. Natuurlijk willen we dat de AI elke bordstatus controleert en een winnende overwinning kiest, maar in de meeste spellen met duizenden, zo niet miljoenen bordconfiguraties, kan je laptop thuis niet al die configuraties verwerken. Dus we beperken de zoekdiepte van de AI en laten deze naar de beste bordstatus gaan.

Deze pseudocode reproduceert het proces dat ik in de vorige twee stappen heb uitgelegd. Laten we nu een stap verder gaan en dit rechtzetten in python-code.

Stap 7: Uw AI maken met Ai_template.py

Voordat je mijn Minimax AI-code bekijkt, moet je eerst proberen om je eigen AI te maken met het bestand ai_template.py en de pseudo-code waar we het in de laatste stap over hadden. Er zijn twee functies in de ai-sjabloon genaamd: def minimax_min_node(bord, kleur) en def minimax_max_node(bord, kleur). In plaats van dat de minimax-functie zichzelf recursief aanroept, hebben we twee verschillende functies die elkaar aanroepen. Om de heuristiek te creëren om bordstatussen te evalueren, moet u uw eigen functie maken. Er zijn vooraf gemaakte functies in het bestand othello_shared.py die u kunt gebruiken om uw AI te bouwen.

Als je eenmaal je AI hebt, probeer het dan uit te voeren tegen randy_ai.py. Om twee ais tegen elkaar uit te voeren, typt u "python othello_gui.py (voeg ai-bestandsnaam).py (voeg bestandsnaam in).py" in de mac-terminal in of typt u "run othello_gui.py (voeg ai-bestandsnaam).py in). (bestandsnaam invoegen).py" en zorg ervoor dat u zich in de juiste map bevindt. Bekijk ook mijn video voor de exacte stappen.

Stap 8: Tijd om AI te laten vechten

Haal nu een aantal van je computervrienden bij elkaar en laat ze hun eigen AI ontwerpen! Dan kun je een wedstrijd maken en je AI het laten uitvechten. Hopelijk kon je, zelfs als je je eigen AI niet kon bouwen, begrijpen hoe het minimax-algoritme werkt. Als u vragen heeft, kunt u deze in de onderstaande opmerkingen plaatsen.