Wie kann ich meinen Minimax-Suchbaum so anpassen, dass kein laufzeitbasiertes Spiel verwendet wird?

Question

Ich muss ein Projekt machen, wo wir Mancalabrettspiel implementieren müssen, und dann auch die KI dafür implementieren.

Wir wurden angewiesen, dass wir einen Minimax-Baum ändern oder ändern müssen, um mit Mancala arbeiten zu können, da es im Spiel möglich ist, dass ein Spieler mehrere Züge hintereinander hat.

Ich habe meine Spiellogik und GUI bereits implementiert, aber jetzt, bevor ich mit der KI beginne, möchte ich versuchen, eine Idee über die Theorie dahinter zu bekommen. Ich habe im Internet nach nicht-drehbaren Mini-Max-Bäumen gesucht und ich kann anscheinend nichts finden. Aber ich habe viele Leute gesehen, die über die Verwendung von Minimax für Mancala sprechen.

Jetzt verstehe ich den normalen Minimax-Baum und wie jede Ebene zwischen einem minimalen Knoten und einem maximalen Knoten wechselt. Mit dem Baum, den ich jetzt brauche, würde ich sagen: min > max > max > min > max, wenn der 2. Spieler ZWEI Drehungen bekommen hat?

Wir müssen auch in der Lage sein, die gegebene Tiefe des Minimax-Baumes anzugeben. Wir müssen auch Alpha-Beta-Beschneidung machen, aber das ist für später, sobald ich tatsächlich einen Baum habe.

Answer 1

Wenn eine Seite in einer Runde mehrere Züge haben kann, muss es eine Möglichkeit geben, dies zu erkennen. Wenn erkannt, erzeugt der Bewegungsgenerator für den Gegner eine Liste, die nur eine Nullbewegung enthält, d.h. eine Bewegung, die nichts tut. Der Gegner wird gezwungen, diesen Zug zu spielen (nichts tun) und der erste Spieler kann dann seinen nächsten Zug berechnen.

Answer 2

Soweit ich es verstanden habe, ist dein Hauptproblem folgendes: dir wurde gezeigt, wie man minimax in einer Situation benutzt, in der max/min im Zyklus läuft und du jetzt ein Spiel hast, in dem manchmal ein Spieler mehrere Züge machen kann eine Reihe.

Ich werde Ihnen den allgemeinen Ansatz erklären, der für praktisch jedes Spiel funktioniert, und dann werde ich ein paar Dinge hinzufügen, die für Mancala anders gemacht werden können.

So der allgemeine Ansatz

Standard-Minimax geht so:

function minimax(node, depth, maximizingPlayer) 
    if depth = 0 or node is a terminal node 
     return the heuristic value of node 
    if maximizingPlayer 
     bestValue := -∞ 
     for each child of node 
      val := minimax(child, depth - 1, FALSE) 
      bestValue := max(bestValue, val) 
     return bestValue 
    else 
     bestValue := +∞ 
     for each child of node 
      val := minimax(child, depth - 1, TRUE) 
      bestValue := min(bestValue, val) 
     return bestValue 

Wo Sie die Minimax-Aufruf mit max/min initialisieren und dann ändert sich ständig. In Ihrem Fall müssen Sie nur einen winzigen Scheck hinzufügen.

function minimax(node, depth, maximizingPlayer) 
    if depth = 0 or node is a terminal node 
     return the heuristic value of node 
    if maximizingPlayer 
     bestValue := -∞ 
     for each child of node 
      # here is a small change 
      if freeTurn(child): 
       isMax := TRUE 
      else: 
       isMax := FALSE 
      val := minimax(child, depth - 1, isMax) 
      bestValue := max(bestValue, val) 
     return bestValue 
    else 
     bestValue := +∞ 
     for each child of node 
      # here is a small change 
      if freeTurn(child): 
       isMax := FALSE 
      else: 
       isMax := TRUE 
      val := minimax(child, depth - 1, isMax) 
      bestValue := min(bestValue, val) 
     return bestValue 

Wo Ihre Funktion freeTurn gelangen Sie, ob Sie eine kostenlose Turn nach der aktuellen Bewegung haben. Beachten Sie, dass es für diesen Algorithmus keinen Unterschied gibt, ob Sie nur 2 Züge hintereinander oder 5 Züge hintereinander ausführen können.

In Bezug auf Mancala

Es gibt viele Variationen von mancala, aber der Verzweigungsfaktor des Spiels ist ziemlich klein (in dem einen, den ich kenne < = 6). Angenommen, Sie haben drei Züge A, B, C, und bewegen Sie C können Sie noch einmal spielen. Von der Position C können Sie Bewegungen C1, C2 tun. So können Sie sie kombinieren (C + C1, C + C2) und behandeln sie als nur einen Zug (kleine Buchhaltung sollte getan werden, um daran zu erinnern, dass dies tatsächlich zwei Züge ist).Jetzt haben Sie am Ende Ihre min max Iterationen, wo Sie nicht 4, sondern 5 Züge haben: A, B, C + C1, C + C2, D. Eigentlich ist es nicht falsch, diesen Ansatz für Spiele mit einem größeren Verzweigungsfaktor zu verwenden.