Wie genau funktioniert die Minimax-Rekursion?

StackOverflow https://stackoverflow.com//questions/11703846

Frage

Also habe ich nach Mini-max für ein Tic-Tac-Toe-Spiel gesucht, konnte aber nicht verstehen, wie die Rekursion funktioniert?Okay, im Grunde sind hier meine Fragen:

  1. Woher weiß Minimax, wer an der Reihe ist?Was ist der beste Weg, um den Spieler anzuzeigen, dessen Zug es generiert?
  2. Wie generieren Sie mögliche Züge?
  3. Woher wissen Sie, wann Sie sich an einem Endknoten befinden, und wie generieren Sie die Endknoten?

Zum Beispiel in diesem Pseudocode

function integer minimax(node, depth)
if node is a terminal node or depth <= 0:
    return the heuristic value of node
α = -∞
for child in node: # evaluation is identical for both players
    α = max(α, -minimax(child, depth-1))
return α

A node ist ein Board richtig?Und ist die Tiefe, wie viele Schichten der Code bei der Rekursion durchlaufen muss?Auch was ist das max Funktion und woher werden die Knoten generiert?

Bisher habe ich diesen Code zum Erstellen eines Boards:

class Board{
    public:
        Board();
        ~Board(){};
    public: // The board
        // In the board, 1 is x, 2 is o, 0 is empty square.
        int board[3][3];
};

Aber woher soll ich wissen, wer an der Reihe ist?Und wie erstelle ich die untergeordneten Knoten für das Board?

War es hilfreich?

Lösung

Wir verwenden zunächst Ihr Tic-Tac-Toe als Beispiel.

  • Ein Minimax-Algorithmus eignet sich am besten für Spiele, bei denen die Spieler abwechselnd an der Reihe sind, kann aber an Spiele angepasst werden, bei denen die Spieler möglicherweise mehrere Züge pro Zug ausführen.Der Einfachheit halber gehen wir von Ersterem aus.In diesem Fall müssen Sie nicht bei jedem Knoten „X zum Verschieben“ oder „O zum Verschieben“ speichern, da dies einfach durch die Parität der Knotentiefe bestimmt werden kann (ob ich eine gerade oder ungerade Anzahl von Schritten habe). Anzahl der Schritte, von oben).
  • Um mögliche Züge von jeder Position aus zu generieren, müssen Sie wissen, um wessen Zug es sich handelt (was wie zuvor bestimmt werden kann) und die Regeln für legale Züge von einer bestimmten Position aus kennen.Für ein einfaches Spiel wie Tic-Tac-Toe reicht es bei gegebener Position aus, alle Zustände aufzuzählen, die aus einer Kopie der aktuellen Position und einer neuen Figur des aktuellen Spielers bestehen, die der Reihe nach auf jedem leeren Feld platziert wird.Bei Spielen wie Othello müssen Sie außerdem jede Platzierung überprüfen, um sicherzustellen, dass sie den Regeln entspricht, und die endgültige Position entsprechend den Konsequenzen der Regel aktualisieren (bei Othello das Vertauschen der Farben einer Reihe von Spielsteinen).Im Allgemeinen zählen Sie von jeder gültigen Position aus, die Sie verfolgen, alle möglichen Platzierungen eines neuen Stücks auf und prüfen, welche durch den Regelsatz zulässig sind.
  • Im Allgemeinen generieren Sie NIEMALS den gesamten Baum, da die Größe der Wildbäume leicht die Speicherkapazität der Erde überschreiten kann.Sie legen immer eine maximale Iterationstiefe fest.Ein Endknoten ist also einfach ein Knoten in der maximalen Tiefe oder ein Knoten, von dem aus keine legalen Bewegungen möglich sind (für Tic-Tac-Toe ein Brett, auf dem jedes Feld gefüllt ist).Sie generieren die Endknoten nicht vorher;Sie werden auf natürliche Weise während der Spielbaumkonstruktion erzeugt.Tic-Tac-Toe ist so einfach, dass Sie dürfen Generieren Sie den gesamten Spielbaum, aber versuchen Sie dann nicht, Ihren Tic-Tac-Toe-Code z. B. für Spiele zu verwenden.Othello.

Schauen Sie sich Ihren Pseudocode an:

  • max(a, b) ist jede Funktion, die den größeren von zurückgibt a oder b.Dies wird normalerweise von einer Mathematikbibliothek oder ähnlichem bereitgestellt.
  • Der depth ist die maximale Tiefe, bis zu der Sie suchen werden.
  • Der heuristische Wert, den Sie berechnen, ist ein numerischer Wert, der den Wert des Boards beschreibt.Für ein Spiel wie Tic-Tac-Toe, das so einfach ist, dass Sie den gesamten Spielbaum aufzählen KÖNNEN, können Sie eine Bezeichnung festlegen 1 für eine Brettposition, die für den Spieler, der die Analyse durchführt, gewinnt, -1 für eine Brettposition, die für den anderen Spieler gewinnt, und 0 für jede nicht schlüssige Position.Im Allgemeinen müssen Sie selbst eine Heuristik ausarbeiten oder eine allgemein akzeptierte verwenden.
  • Sie generieren die Knoten während Ihrer Analyse spontan auf der Grundlage ihrer übergeordneten Knoten.Ihr Wurzelknoten ist immer die Position, von der aus Sie die Analyse durchführen.

Wenn Sie noch nicht mit Diagrammen oder Bäumen gearbeitet haben, empfehle ich Ihnen, dies zunächst zu tun.Insbesondere das Baumprimitiv ist essentiell zu diesem Problem.

Als Antwort auf einen Kommentar in diesem Thread, in dem nach einem Beispiel für die Bestimmung gefragt wird, wer für einen bestimmten Knoten an der Reihe ist, biete ich dieses Pseudo-Python an:

who_started_first = None

class TreeNode:
    def __init__(self, board_position = EMPTY_BOARD, depth = 0):
        self.board_position = board_position
        self.children = []
        self.depth = depth
    def construct_children(self, max_depth):
        # call this only ONCE per node!
        # even better, modify this so it can only ever be called once per node
        if max_depth > 0:

            ### Here's the code you're actually interested in.
            if who_started_first == COMPUTER:
                to_move = (COMPUTER if self.depth % 2 == 0 else HUMAN)
            elif who_started_first == HUMAN:
                to_move = (HUMAN if self.depth % 2 == 0 else COMPUTER)
            else:
                raise ValueError('who_started_first invalid!')

            for position in self.board_position.generate_all(to_move):
                # That just meant that we generated all the valid moves from the
                # currently stored position. Now we go through them, and...
                new_node = TreeNode(position, self.depth + 1)
                self.children.append(new_node)
                new_node.construct_children(max_depth - 1)

Jeder Knoten ist in der Lage, seine absolute Tiefe vom „Wurzel“-Knoten aus zu verfolgen.Wenn wir versuchen zu bestimmen, wie wir Brettpositionen für den nächsten Zug generieren sollen, überprüfen wir anhand der Parität unserer Tiefe (dem Ergebnis von), wessen Zug er ist self.depth % 2) und unsere Aufzeichnung, wer zuerst umgezogen ist.

Andere Tipps

1) Woher weiß Minimax, wer an der Reihe ist?Was ist der beste Weg, um den Spieler anzuzeigen, dessen Zug es generiert?

Du hast das depth Streit.Wenn die Tiefe gerade ist, ist ein Spieler am Zug, ist sie ungerade, ist der andere Spieler am Zug.

2) Wie generieren Sie mögliche Züge?

Die Spielregeln anwenden.Bei Tic Tac Toe bedeutet ein möglicher Zug, dass man sein Zeichen in ein freies Feld setzt.

3) Woher wissen Sie, wann Sie sich an einem Endknoten befinden, und wie generieren Sie die Endknoten?

Ein Endknoten ist ein Knoten, an dem jemand gewonnen hat.Sie generieren sie durch Rekursion.Bei jedem rekursiven Aufruf sollte der aktuelle Zustand des Boards angegeben werden.Ich schätze, das ist das node Und child Parameter in Ihrem Pseudocode.Wenn also in dieser Situation jemand gewonnen hat, dann ist das tödlich, andernfalls versucht man alle legalen Schritte und rekursiert.

Ich kann Ihnen eine kleine Vorstellung davon geben, wonach Sie suchen, da ich einen Minimax-Algorithmus für Tic-Tac-Toe geschrieben habe.

Um Ihre Fragen direkt zu beantworten:

  1. Mein Minimax-Algorithmus hat das nicht festgestellt.Es akzeptierte ein Argument, das festlegte, welchen Spieler der Algorithmus verwendete.

  2. Wenn Sie den Spieler kennen, der sich bewegen soll, durchlaufen Sie alle leeren Felder auf dem Spielbrett und erzeugen für jedes Feld einen Knoten mit dem Spielstein des aktuellen Spielers in diesem Feld.Fahren Sie von dort aus rekursiv fort.

  3. Ich habe eine Funktion verwendet, die einen Wert zurückgab, der angab, ob das Spiel vorbei war und ob es ein Unentschieden oder ein Sieg war.

Mein grundlegender Algorithmus hat Folgendes getan:

  • Eingang:der Spieler, der sich bewegen soll, und der Zustand des Spielbretts.
  • Finden Sie alle Leerstellen auf der Tafel.
    • Erzeuge ein neues Spielbrett mit dem Zug des Spielers in diesem Feld.
    • Wenn das Spiel vorbei ist, generieren Sie einen Knoten mit dem Ergebnis des Spiels.
    • Andernfalls führen Sie den Algorithmus aus, übergeben den anderen Spieler und das neue Spielfeld und generieren einen Knoten mit dem Ergebnis des idealen Zugs des Gegners.
  • Bestimmen Sie, welcher Knoten (Bewegung) zum bestmöglichen Worst Case führt.
  • Ausgabe:Der beste Zug und Informationen über das Ergebnis der Partie.
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top