Künstliche Intelligenz des Brettspiels: der Minimax-Algorithmus - Gunook

2024 Autor: John Day | [email protected]. Zuletzt bearbeitet: 2024-01-30 07:18

Haben Sie sich jemals gefragt, wie die Computer, gegen die Sie beim Schach oder Dame spielen, hergestellt werden? Suchen Sie nicht weiter als dieses Instructable, denn es zeigt Ihnen, wie Sie mit dem Minimax-Algorithmus eine einfache, aber effektive künstliche Intelligenz (KI) erstellen! Durch die Verwendung des Minimax-Algorithmus macht die KI gut geplante und durchdachte Bewegungen (oder ahmt zumindest einen Denkprozess nach). Jetzt könnte ich Ihnen einfach den Code für die KI geben, die ich erstellt habe, aber das würde keinen Spaß machen. Ich werde die Logik hinter den Entscheidungen des Computers erklären.

In diesem Instructable werde ich Sie durch die Schritte führen, wie Sie eine KI für Othello (AKA Reversi) in Python erstellen. Sie sollten ein mittleres Verständnis des Programmierens in Python haben, bevor Sie dieses Projekt in Angriff nehmen. Hier sind ein paar gute Websites, um Sie auf dieses Instructable vorzubereiten: w3schools oder learnpython. Am Ende dieses Instructable sollten Sie eine KI haben, die berechnete Bewegungen macht und in der Lage sein sollte, die meisten Menschen zu besiegen.

Da sich dieses Instructable in erster Linie damit befassen wird, wie man eine KI erstellt, werde ich nicht erklären, wie man ein Spiel in Python entwirft. Stattdessen werde ich den Code für das Spiel geben, bei dem ein Mensch gegen einen anderen Menschen spielen kann, und ihn so ändern, dass Sie ein Spiel spielen können, bei dem ein Mensch gegen die KI spielt.

Ich habe in einem Sommerprogramm bei Columbia SHAPE gelernt, wie man diese KI erstellt. Ich hatte eine gute Zeit dort, also schau dir ihre Website an, um zu sehen, ob du interessiert bist.

Jetzt, da wir die Logistik aus dem Weg geräumt haben, können wir mit dem Programmieren beginnen!

(Ich habe ein paar Notizen in die Bilder eingefügt, also schaut sie euch unbedingt an)

Lieferungen

Das ist einfach:

1) Computer mit einer Python-Umgebung wie Spyder oder IDLE

2) Laden Sie die Dateien für das Othello-Spiel von meinem GitHub herunter

3) Dein Gehirn mit installierter Geduld

Schritt 1: Laden Sie die erforderlichen Dateien herunter

Wenn Sie in meinen GitHub gehen, sollten Sie 5 Dateien sehen. Laden Sie alle 5 herunter und legen Sie sie alle in denselben Ordner. Bevor wir das Spiel ausführen, öffnen Sie alle Dateien in der Spyder-Umgebung.

Hier ist, was die Dateien tun:

1) othello_gui.py Diese Datei erstellt das Spielbrett, auf dem die Spieler spielen können (egal ob Mensch oder Computer)

2) othello_game.py diese Datei spielt zwei Computer ohne Spielbrett gegeneinander und zeigt nur den Punktestand und die Zugpositionen an

3) ai_template.py Hier werden Sie Ihren gesamten Code einfügen, um Ihre KI zu erstellen

4) randy_ai.py Dies ist eine vorgefertigte KI, die ihre Züge zufällig auswählt

5) othello_shared.py eine Reihe vorgefertigter Funktionen, mit denen Sie Ihre KI erstellen können, z. B. nach verfügbaren Zügen, der Punktzahl oder dem Brettzustand

6) Die drei anderen Dateien: Puma.py, erika_5.py und nathan.py, erstellt von mir, Erika bzw. Nathan aus dem SHAPE-Programm, das sind drei verschiedene KIs mit einzigartigen Codes

Schritt 2: So öffnen und spielen Sie Python Othello

Sobald Sie alle Dateien geöffnet haben, geben Sie in der unteren rechten Ecke des Bildschirms "run othello_gui.py" ein und drücken Sie die Eingabetaste in der IPython-Konsole. Oder geben Sie im Mac-Terminal "python othello_gui.py" ein (natürlich nachdem Sie sich im richtigen Ordner befinden). Dann sollte eine Tafel auf Ihrem Bildschirm erscheinen. Dieser Modus ist der Mensch-gegen-Mensch-Modus. Licht wird an zweiter Stelle und dunkel zuerst. Schauen Sie sich mein Video an, wenn Sie verwirrt sind. iOben befindet sich die Punktzahl jedes Farbplättchens. Um zu spielen, klicken Sie auf ein gültiges Bewegungsfeld, um dort eine Kachel zu platzieren, und geben Sie den Computer dann Ihrem Gegner, der dasselbe tut und wiederholt.

Wenn Sie nicht wissen, wie man Othello spielt, lesen Sie diese Regeln auf der Ultra Boards-Website:

Schwarz zieht immer zuerst. Ein Zug wird ausgeführt, indem eine Scheibe der Farbe des Spielers auf dem Brett in einer Position platziert wird, die eine oder mehrere Scheiben des Gegners "überflankt". Eine Scheibe oder Scheibenreihe ist überflügelt, wenn sie an den Enden von Scheiben der anderen Farbe umgeben ist. Eine Scheibe kann beliebig viele Scheiben in einer oder mehreren Reihen in beliebiger Richtung (horizontal, vertikal, diagonal) überflügeln…. (Lesen Sie auf ihrer Website zu Ende)

Der Unterschied zwischen dem Originalspiel und diesem Python-Spiel besteht darin, dass das Spiel endet, wenn für einen Spieler keine gültigen Züge mehr vorhanden sind

Jetzt, da Sie das Spiel mit einem Freund spielen können, erstellen wir eine KI, mit der Sie spielen können.

Schritt 3: Minimax-Algorithmus: Generieren von Szenarien

Bevor wir darüber sprechen, wie man dies in Code schreibt, lassen Sie uns die Logik dahinter durchgehen. Der Minimax-Algorithmus ist ein Entscheidungs-, Back-Tracking-Algorithmus und wird typischerweise in rundenbasierten Spielen für zwei Spieler verwendet. Das Ziel dieser KI ist es, den nächstbesten Zug und die folgenden besten Züge zu finden, bis sie das Spiel gewinnt.

Wie würde der Algorithmus nun bestimmen, welcher Zug der beste Zug ist? Halten Sie inne und überlegen Sie, wie Sie den nächsten Zug wählen würden. Die meisten Leute würden den Zug wählen, der ihnen die meisten Punkte bringt, oder? Oder wenn sie vorausdenken würden, würden sie den Zug wählen, der eine Situation schaffen würde, in der sie noch mehr Punkte sammeln könnten. Die letztere Denkweise ist die Denkweise des Minimax-Algorithmus. Es blickt auf alle zukünftigen Board-Setups voraus und macht den Zug, der zu den meisten Punkten führen würde.

Ich habe dies einen Backtracking-Algorithmus genannt, weil er damit beginnt, zuerst alle zukünftigen Board-Zustände mit ihren zugehörigen Werten zu erstellen und auszuwerten. Dies bedeutet, dass der Algorithmus das Spiel so oft spielt, wie er benötigt (die Züge für sich selbst und den Gegner ausführen), bis jedes Szenario des Spiels gespielt wurde. Um den Überblick über alle Boardzustände (Szenarien) zu behalten, können wir einen Baum zeichnen (siehe Bilder). Der Baum im Bild oben ist ein einfaches Beispiel für ein Spiel von Connect 4. Jede Board-Konfiguration wird als Board-Zustand bezeichnet und ihr Platz im Baum wird als Knoten bezeichnet. Alle Knoten am unteren Rand des Baums sind die endgültigen Brettzustände, nachdem alle Züge ausgeführt wurden. Offensichtlich sind einige Board-States für einen Spieler besser als für den anderen. Jetzt müssen wir also die KI wählen lassen, in welchen Board-Zustand sie gelangen möchte.

Schritt 4: Minimax: Platinenkonfigurationen auswerten

Um den Board-States Werte zu geben, müssen wir die Strategien des Spiels lernen, das wir spielen: in diesem Fall die Strategien von Othello. Da es sich bei diesem Spiel um einen Kampf um das Umdrehen der gegnerischen und Ihrer Scheiben handelt, sind die besten Scheibenpositionen diejenigen, die stabil sind und nicht umgedreht werden können. Die Ecke ist beispielsweise die Stelle, an der eine eingelegte Disc nicht in die andere Farbe geändert werden kann. Daher wäre dieser Ort äußerst wertvoll. Andere gute Positionen sind die Seiten des Bretts, die es Ihnen ermöglichen, viele Steine zu nehmen. Es gibt mehr Strategien auf dieser Website.

Jetzt können wir den Positionen für jedes Board State Board Werte zuweisen. Wenn eine Stellung von der Figur der KI besetzt ist, dann vergibt man je nach Stellung eine bestimmte Punktzahl. Zum Beispiel, ein Brettzustand, in dem die Figur der KI in der Ecke liegt, können Sie einen Bonus von 50 Punkten geben, aber wenn sie sich an einer ungünstigen Stelle befindet, kann die Figur einen Wert von 0 haben. Nach Berücksichtigung aller Werte von den Positionen weisen Sie dem Board-Zustand einen Wert zu. Wenn die KI beispielsweise eine Figur in der Ecke hat, kann der Brettzustand eine Punktzahl von 50 haben, während ein anderer Tafelzustand mit der Figur der KI in der Mitte eine Punktzahl von 10 hat.

Es gibt viele Möglichkeiten, dies zu tun, und ich habe drei verschiedene Heuristiken, um die Brettstücke auszuwerten. Ich ermutige Sie, Ihre eigene Art von Heuristik zu erstellen. Ich habe drei verschiedene KIs von drei verschiedenen Herstellern mit drei verschiedenen Heuristiken auf meinen Github hochgeladen: Puma.py, erika5.py, nathanh.py.

Schritt 5: Minimax-Algorithmus: Auswahl des besten Zugs

Nun wäre es schön, wenn die KI einfach alle Züge auswählen könnte, um in den Brettzustand mit der höchsten Punktzahl zu gelangen. Aber denken Sie daran, dass die KI auch die Züge für den Gegner auswählte, als sie alle Brettzustände generierte, und wenn der Gegner schlau ist, wird sie der KI nicht erlauben, die höchste Brettpunktzahl zu erreichen. Stattdessen würde ein kluger Gegner den Schritt unternehmen, um die KI in den niedrigsten Board-Zustand zu bringen. Im Algorithmus nennen wir die beiden Spieler einen Maximierungsspieler und einen Minimierungsspieler. Die KI wäre der maximierende Spieler, da sie die meisten Punkte für sich selbst erzielen möchte. Der Gegner wäre der minimierende Spieler, da der Gegner versucht, den Zug dort zu machen, wo die KI die wenigsten Punkte bekommt.

Nachdem alle Platinenzustände generiert und den Platinen Werte zugewiesen wurden, beginnt der Algorithmus mit dem Vergleich der Platinenzustände. In den Bildern habe ich einen Baum erstellt, um darzustellen, wie der Algorithmus seine Züge auswählen würde. Jede Aufteilung in den Zweigen ist ein anderer Zug, den die KI oder der Gegner spielen kann. Links neben den Knotenreihen habe ich geschrieben, ob der maximierende oder der minimierende Spieler geht. Die untere Reihe enthält alle Boardzustände mit ihren Werten. In jedem dieser Nodes befindet sich eine Zahl und das sind die Punkte, die wir jedem der Boards zuordnen: Je höher sie sind, desto besser ist es für die KI.

Definitionen: Elternknoten – ein Knoten, der darunter liegende Knoten ergibt oder erzeugt; der Ursprung der Kinderknoten - die Knoten, die vom gleichen Elternknoten stammen

Die leeren Knoten stellen dar, welche Bewegung die KI ausführen wird, um den besten Board-Zustand zu erreichen. Es beginnt mit dem Vergleich der Kinder des Knotens ganz links: 10, -3, 5. Da der maximierende Spieler den Zug machen würde, würde er den Zug wählen, der ihm die meisten Punkte bringt: 10. Also wählen wir diesen aus und speichern ihn Bewegen Sie sich mit der Brettpunktzahl und schreiben Sie sie in den übergeordneten Knoten. Da sich nun 10 im übergeordneten Knoten befindet, sind nun die Minimierungsspieler an der Reihe. Der Knoten, mit dem wir 10 vergleichen würden, ist jedoch leer, daher müssen wir diesen Knoten zuerst auswerten, bevor der minimierende Spieler wählen kann. Wir gehen also zurück zum Zug des maximierenden Spielers und vergleichen die Kinder des benachbarten Knotens: 8, -2. Maximieren wählt 8 und wir schreiben das in den leeren Elternknoten. Nachdem der Algorithmus nun die leeren Räume für die Kinder eines darüber liegenden Knotens ausgefüllt hat, kann der minimierende Spieler diese Kinder vergleichen – 10 und 8 und 8. Der Algorithmus wiederholt diesen Vorgang dann, bis der gesamte Baum ausgefüllt ist. Am Ende dieses Beispiels haben wir die Punktzahl 8. Das ist der höchste Brettzustand, den die KI spielen kann, wenn der Gegner optimal spielt. Die KI wählt also den ersten Zug, der zum Brettzustand 8 führt, und wenn der Gegner optimal spielt, sollte die KI alle Züge spielen, um zum Brettzustand 8 zu gelangen. (Befolgen Sie die Hinweise auf meinen Bildern)

Ich weiß, das war viel. Wenn Sie zu den Typen gehören, die jemanden brauchen, der mit Ihnen spricht, um etwas zu verstehen, hier sind ein paar Videos, die ich mir angesehen habe, um die Idee dahinter zu verstehen: 1, 2, 3.

Schritt 6: Minimax-Algorithmus: Pseudocode

Nachdem Sie die Logik hinter dem Minimax-Algorithmus verstanden haben, werfen Sie einen Blick auf diesen Pseudocode (die Funktionen, die für alle Codes universell sind) von Wikipedia:

Funktion Minimax (Knoten, Tiefe, MaximizingPlayer) ist

wenn Tiefe = 0 oder Knoten ein Endknoten ist, dann

den heuristischen Wert von node. zurückgeben

wenn maximingPlayer dann

Wert:= −∞

für jedes Kind des Knotens do

Wert:= max(Wert, minimax(Kind, Tiefe − 1, FALSE))

Rückgabewert

sonst (* Spieler minimieren *)

Wert:= +∞

für jedes Kind des Knotens do

Wert:= min(Wert, Minimax(Kind, Tiefe − 1, WAHR))

Rückgabewert

Dies ist eine rekursive Funktion, was bedeutet, dass sie sich selbst immer wieder aufruft, bis sie einen Stopppunkt erreicht. Erstens nimmt die Funktion drei Werte an, den Knoten, die Tiefe und wer an der Reihe ist. Der Knotenwert ist die Stelle, an der das Programm mit der Suche beginnen soll. Die Tiefe gibt an, wie weit das Programm suchen soll. In meinem Baumbeispiel hat es zum Beispiel eine Tiefe von 3, weil es nach 3 Zügen alle Brettzustände durchsucht hat. Natürlich möchten wir, dass die KI jeden Boardstatus überprüft und einen gewinnenden Gewinn auswählt, aber in den meisten Spielen, in denen es Tausende, wenn nicht sogar Millionen von Boardkonfigurationen gibt, kann Ihr Laptop zu Hause nicht alle diese Konfigurationen verarbeiten. Also begrenzen wir die Suchtiefe der KI und lassen sie auf den besten Board-Zustand gehen.

Dieser Pseudocode reproduziert den Prozess, den ich in den vorherigen beiden Schritten erklärt habe. Lassen Sie uns nun einen Schritt weitergehen und dies im Python-Code korrigieren.

Schritt 7: Erstellen Sie Ihre KI mit Ai_template.py

Bevor Sie sich meinen Minimax-KI-Code ansehen, versuchen Sie, mit der Datei ai_template.py und dem Pseudo-Code, über den wir im letzten Schritt gesprochen haben, Ihre eigene KI zu erstellen. Es gibt zwei Funktionen im ai-Template namens: def minimax_min_node(board, color) und def minimax_max_node(board, color). Anstatt dass sich die Minimax-Funktion selbst rekursiv aufruft, haben wir zwei verschiedene Funktionen, die sich gegenseitig aufrufen. Um die Heuristik zur Auswertung von Platinenzuständen zu erstellen, müssen Sie eine eigene Funktion erstellen. Es gibt eine vorgefertigte Funktion in der Datei othello_shared.py, mit der Sie Ihre KI erstellen können.

Sobald Sie Ihre KI haben, versuchen Sie, sie gegen randy_ai.py auszuführen. Um zwei Ais gegeneinander auszuführen, geben Sie "python othello_gui.py (Insert ai file name).py (insert file name).py" in das Mac-Terminal ein oder geben Sie "run othello_gui.py (insert ai file name).py" ein (Dateinamen einfügen).py" und stellen Sie sicher, dass Sie sich im richtigen Verzeichnis befinden. Sehen Sie sich auch mein Video an, um die genauen Schritte zu erfahren.

Schritt 8: Zeit, KI zum Kampf zu bringen

Holen Sie sich jetzt einen Haufen Ihrer Computerfreunde und lassen Sie sie ihre eigene KI entwerfen! Dann kannst du einen Wettbewerb machen und deine KI duellieren lassen. Auch wenn Sie keine eigene KI erstellen konnten, konnten Sie hoffentlich verstehen, wie der Minimax-Algorithmus funktioniert. Wenn Sie Fragen haben, können Sie diese gerne in den Kommentaren unten posten.