Tic Tac Toe auf Arduino mit AI (Minimax-Algorithmus) - Gunook

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

In diesem Instructable werde ich Ihnen zeigen, wie Sie ein Tic Tac Toe-Spiel mit einer KI mit einem Arduino bauen. Sie können entweder gegen den Arduino spielen oder zusehen, wie der Arduino gegen sich selbst spielt.

Ich verwende einen Algorithmus namens "Minimax-Algorithmus", der nicht nur zum Erstellen einer KI für Tic Tac Toe verwendet werden kann, sondern auch für eine Vielzahl anderer Spiele wie Vier in einer Reihe, Dame oder sogar Schach. Spiele wie Schach sind sehr komplex und erfordern viel verfeinerte Versionen des Algorithmus. Für unser Tic Tac Toe-Spiel können wir die einfachste Version des Algorithmus verwenden, die dennoch ziemlich beeindruckend ist. Tatsächlich ist die KI so gut, dass es unmöglich ist, das Arduino zu schlagen!

Das Spiel ist einfach zu bauen. Sie brauchen nur ein paar Komponenten und die Skizze, die ich geschrieben habe. Ich habe auch eine detailliertere Erklärung des Algorithmus hinzugefügt, wenn Sie verstehen möchten, wie er funktioniert.

Schritt 1: Bauen und spielen

Um das Tic Tac Toe-Spiel zu bauen, benötigen Sie die folgenden Komponenten:

• Ein Arduino Uno
• 9 WS2812 RGB-LEDs
• 9 Druckknöpfe
• einige Draht- und Überbrückungskabel

Verdrahten Sie die Komponenten wie in der Fritzing-Skizze gezeigt. Laden Sie dann den Code auf Ihren Arduino hoch.

Standardmäßig nimmt der Arduino die erste Runde. Um die Sache etwas interessanter zu machen, wird der erste Zug zufällig gewählt. Nach dem ersten Zug verwendet der Arduino den Minimax-Algorithmus, um den bestmöglichen Zug zu bestimmen. Sie starten ein neues Spiel, indem Sie das Arduino zurücksetzen.

Sie können das Arduino "denken" beobachten, indem Sie den Serial Monitor öffnen. Für jeden möglichen Zug berechnet der Algorithmus eine Wertung, die angibt, ob dieser Zug zu einem Gewinn (Wert 10) oder einem Verlust (Wert -10) für den Arduino oder einem Unentschieden (Wert 0) führt.

Sie können auch zusehen, wie das Arduino gegen sich selbst spielt, indem Sie die Zeile "#define DEMO_MODE" ganz am Anfang des Sketches auskommentieren. Wenn Sie die modifizierte Skizze hochladen, macht der Arduino den ersten Zug zufällig und verwendet dann den Minimax-Algorithmus, um den besten Zug für jeden Spieler in jeder Runde zu bestimmen.

Beachten Sie, dass Sie gegen das Arduino nicht gewinnen können. Jedes Spiel endet entweder unentschieden oder Sie verlieren, wenn Sie einen Fehler machen. Dies liegt daran, dass der Algorithmus immer den bestmöglichen Zug wählt. Wie Sie vielleicht wissen, endet eine Partie Tic Tac Toe immer unentschieden, wenn beide Spieler keinen Fehler machen. Im Demo-Modus endet jedes Spiel unentschieden, denn Computer machen bekanntlich keine Fehler;-)

Schritt 2: Der Minimax-Algorithmus

Der Algorithmus besteht aus zwei Komponenten: einer Bewertungsfunktion und einer Suchstrategie. Die Bewertungsfunktion ist eine Funktion, die Platinenpositionen einen numerischen Wert zuweist. Wenn die Position eine Endposition ist (dh eine Position, bei der entweder der blaue Spieler oder der rote Spieler gewonnen hat oder keiner der Spieler gewonnen hat), ist die Bewertungsfunktion sehr einfach: Nehmen wir an, der Arduino spielt blau und der menschliche Spieler spielt rot. Wenn die Position eine Gewinnposition für Blau ist, weist die Funktion dieser Position einen Wert von 10 zu; wenn es sich um eine Gewinnposition für Rot handelt, weist die Funktion der Position einen Wert von -10 zu; und wenn die Position ein Unentschieden ist, weist die Funktion den Wert 0 zu.

Wenn der Arduino an der Reihe ist, möchte er einen Zug wählen, der den Wert der Bewertungsfunktion maximiert, da die Maximierung des Wertes bedeutet, dass er einen Gewinn gegenüber einem Unentschieden (10 ist größer als 0) bevorzugt und ein Unentschieden dem Verlieren vorzieht (0 ist größer als -10). Durch ein analoges Argument möchte die Gegnerin so spielen, dass sie den Wert der Bewertungsfunktion minimiert.

Für eine nicht endgültige Position berechnet der Algorithmus den Wert der Bewertungsfunktion durch eine rekursive Suchstrategie. Ausgehend von der aktuellen Position simuliert es abwechselnd alle Züge, die der blaue Spieler und der rote Spieler ausführen können. Dies kann wie im Diagramm als Baum visualisiert werden. Wenn es eine Endposition erreicht, beginnt es zurückzutreten und den Wert der Bewertungsfunktion von der niedrigeren Rekursionsebene auf die höhere Rekursionsebene zu übertragen. Sie ordnet das Maximum (wenn im entsprechenden Rekursionsschritt der blaue Spieler am Zug ist) oder das Minimum (wenn im entsprechenden Rekursionsschritt der rote Spieler an der Reihe ist) der Werte der Bewertungsfunktion von der unteren Rekursionsebene an die Position auf der höhere Rekursionsstufe. Wenn der Algorithmus schließlich mit dem Zurücktreten fertig ist und wieder an der aktuellen Position angekommen ist, nimmt er den Zug (oder einen der Züge) mit dem maximalen Bewertungsfunktionswert.

Das mag etwas abstrakt klingen, ist aber eigentlich gar nicht so schwer. Betrachten Sie die Position oben im Diagramm. Im ersten Rekursionsschritt kann Blau drei verschiedene Züge ausführen. Blau versucht, den Wert der Bewertungsfunktion zu maximieren. Für jeden Zug, den Blau ausführen kann, gibt es zwei Züge, die Rot ausführen kann. Rot versucht, den Wert der Bewertungsfunktion zu minimieren. Betrachten Sie den Zug, bei dem Blau in der oberen rechten Ecke spielt. Wenn Rot im Mittelfeld spielt, hat Rot gewonnen (-10). Spielt dagegen Rot im mittleren unteren Kasten, gewinnt Blau im nächsten Zug (10). Wenn also Blau in der oberen rechten Ecke spielt, wird Rot in der mittleren Box gespielt, da dies den Wert der Bewertungsfunktion minimiert. Wenn Blau in der mittleren unteren Box spielt, wird analog auch Rot in der mittleren Box spielen, da dies die Bewertungsfunktion minimiert. Spielt Blau hingegen im Mittelfeld, spielt es keine Rolle, welchen Zug Rot nimmt, Blau gewinnt immer (10). Da Blau die Bewertungsfunktion maximieren möchte, spielt es in der mittleren Box, da diese Position zu einem größeren Wert der Bewertungsfunktion führt (10) als die anderen beiden Züge (-10).

Schritt 3: Fehlerbehebung und weitere Schritte

Wenn Sie eine Taste drücken und eine andere LED als die der Taste entsprechende aufleuchtet, haben Sie wahrscheinlich entweder die Drähte an den Pins A0-A2 oder 4-6 vertauscht oder Sie haben die LEDs in der falschen Reihenfolge angeschlossen.

Beachten Sie auch, dass der Algorithmus nicht unbedingt immer einen Zug wählt, der den Arduino so schnell wie möglich gewinnen lässt. Tatsächlich habe ich einige Zeit damit verbracht, den Algorithmus zu debuggen, weil der Arduino keinen Zug gewählt hat, der ein Gewinnzug gewesen wäre. Es dauerte einige Zeit, bis mir klar wurde, dass er stattdessen einen Zug gewählt hatte, der garantierte, dass er einen Zug später gewinnen würde. Wenn Sie möchten, können Sie versuchen, den Algorithmus so zu ändern, dass er immer einen Gewinnzug einem späteren Gewinn vorzieht.

Eine mögliche Erweiterung dieses Projekts wäre, den Algorithmus zu verwenden, um eine KI für einen 4x4 oder sogar einen 5x5 Tic Tac Toe zu bauen. Beachten Sie jedoch, dass die Anzahl der Positionen, die der Algorithmus untersuchen muss, sehr schnell wächst. Sie müssen Wege finden, die Bewertungsfunktion intelligenter zu gestalten, indem Sie Positionen, die nicht endgültig sind, Werte zuordnen, basierend auf der Wahrscheinlichkeit, dass die Position für den fraglichen Spieler gut oder schlecht ist. Sie können auch versuchen, die Suche intelligenter zu gestalten, indem Sie die Rekursion frühzeitig stoppen, wenn sich herausstellt, dass ein Zug weniger lohnenswert ist als alternative Züge.

Der Arduino ist aufgrund seines begrenzten Speichers wahrscheinlich nicht die beste Plattform für solche Erweiterungen. Rekursion lässt den Stack während der Programmausführung wachsen, und wenn der Stack zu stark anwächst, kann es den Programmspeicher beschädigen, was zu Abstürzen oder unregelmäßigem Verhalten führt. Ich habe das Arduino für dieses Projekt hauptsächlich gewählt, weil ich sehen wollte, ob es machbar ist, und zu Bildungszwecken, nicht weil es die beste Wahl für diese Art von Problem ist.