C ++ Funktion Minimax

Question

Ich habe gesucht Google und Stackoverflow für diese Frage, aber ich immer noch nicht verstehen, wie eine Minimax-Funktion funktioniert.

fand ich den Wikipedia-Eintrag eine Pseudo-Code-Version der Funktion hat:

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 α

Mehrere andere Minimax-Funktionen, die ich mit Google sind im Grunde die gleiche Sache gefunden; Ich versuche, dies in C ++ zu implementieren, und das ist, was ich bin gekommen, sich mit so weit:

double miniMax(Board eval, int iterations)
{
    //I evaluate the board from both players' point of view and subtract the difference
    if(iterations == 0)
        return boardEval(eval, playerNumber) - boardEval(eval, opponentSide());

    /*Here, playerTurn tells the findPossibleMoves function whose turn it is;
    I mean, how do you generate a list of possible moves if you don't even know
    whose turn it's supposed to be? But the problem is, I don't see where I can
    get playerTurn from, as there are only 2 parameters in all the examples of
    minimax I've seen*/
    vector<int> moves = eval.findPossibleMoves(playerTurn);

    //I'm assuming -∞ in the wikipedia article means a very low number?
    int result = -999999999;

    //Now I run this loop to evaluate each possible move
    /*Also, the Lua example in the wiki article has
      alpha = node.player==1 and math.max(alpha,score) or math.min(alpha,score)
      Is alpha a boolean there?!*/
    for(int i = 0; i * 2 < moves.size(); i++)
    {
        //I make a copy of the board...
        Board temp = eval;

        /*and make the next possible move... once again playerTurn crops up, and I
        don't know where I can get that variable from*/
        temp.putPiece(moves[i * 2], moves[i * 2 + 1], playerTurn);

        /*So do I create a function max that returns the bigger of two doubles?*/
        result = max(result, -miniMax(temp, iterations - 1));
    }

    return result;
    /*So now I've returned the maximum score from all possible moves within a certain
    # of moves; so how do I know which move to make? I have the score; how do I know
    which sequence of moves that score belongs to?*/
}

Wie Sie sehen können, bin ich ziemlich verwirrt über diese Minimax-Funktion. Bitte an den allerwenigsten geben Sie mir einige Hinweise zu helfen mir dabei.

Danke! :)

Answer 1

Das Beispiel von Wikipedia tut NegaMax mit Alpha / Beta Pruning .

Sie können, indem sie die Namensgebung gerade geholfen werden:

• Basis ist Minimax eine wörtliche Umsetzung 2 Verfahren umfassen würde, die abwechselnd (wechselseitig rekursive), 1 für jede Seite.

• Faule Programmierer machen diese zu NegaMax, ein Verfahren mit einem strategisch platzierten - Betreibern.

• Alpha / Beta Pruning ist die Verfolgung eines Fensters besten Züge (über mehrere Tiefen) tote Äste zu erkennen.

Ihr playerTurn verwendet, um zu bestimmen, der am Zug ist. In NegaMax können Sie dies aus der Tiefe (Iterationen) ableiten gerade oder ungerade ist. Aber es wäre einfacher, 2 Parameter zu verwenden (myColor, otherColor) und schalten Sie sie auf jeder Ebene.

Answer 2

Ihre miniMax () -Funktion sollte den besten Zug erinnern sie bisher gefunden. Also statt diesem Code:

  /*So do I create a function max that returns the bigger of two doubles?*/
  result = max(result, -miniMax(temp, iterations - 1));

Sie sollten etwas tun:

  /*So do I create a function max that returns the bigger of two doubles?*/
  double score = -miniMax(temp, iterations - 1);
  if (score > result)
  {
     result = score;
     bestMove = i;
  }

Natürlich müssen Sie eine Variable „bestMove“ und eine Möglichkeit, die beste Bewegung für den Anrufer gefunden zurückzukehren.

Answer 3

Fügen Sie die playerTurn Variable als Argument an miniMax und Anruf miniMax, die den aktuellen Spielers Bewegung zunächst und rekursiv.

Auch opponentSide Bedarf eine Funktion von playerTurn sein.

Answer 4

Ein guter Ort, um mit Spielbaum Suche zu starten, ist die Schachprogrammierung Wiki . Für Ihre Frage über den Umzug: Ich denke, es am häufigsten ist zwei Max-Funktionen zu haben. Der Unterschied zwischen den beiden max Funktionen ist, dass eine Rückkehr nur die Partitur und die anderen kehrt der Partitur und der beste Zug. Eine rekursive Aufrufreihenfolge wie folgt aussehen würde:

maxWithBestMoveReturn(...) --> min(...) --> max(...) --> min(...)

Es gibt einige guten Papiere mit Pseudo-Code für den Alpha-Beta-Algorithmus:

• TA Marsland - Computer Schach und Suchen
• J Schaeffer - Spielen Sie die Spiele Computer (und Menschen)

Um Ihre Frage im Kommentar:?! und Math.max (alpha, score) oder Math.min (alpha, score) Ist Alpha ein boolean dort

Kein alpha ist ein Fenster in einem Alpha-Beta-Algorithmus gebunden. Der Alpha-Wert wird mit einem neuen Wert aktualisiert. Da Alpha und Beta sind mit dem rekursiven Aufruf der negamax-Funktion des Alpha-Variable bezieht sich auf das Beta-Variable in dem nächsten rekursiven Aufruf vertauscht.

Ein Hinweis auf die playerTurn Variable: Der Minimax-oder Alpha-Beta-Algorithmus diese Informationen nicht benötigen. Also ich würde die Informationen geben - wer als nächstes kommt -, in die Board-Struktur. Die Funktionen findPossibleMoves und boardEval erhalten Sie alle Informationen, die sie aus dem Board-Struktur benötigen.

Ein Hinweis auf die rekursive Abbruchbedingung: Wenn ich Ihren Code richtig verstehen, dann nur Sie das mit iterations == o haben. Ich denke, das bedeutet der Algorithmus die gewünschte Tiefe erreicht hat. Aber was, wenn es keine möglichen Bewegungen vor dem Algorithmus links erreicht diese Tiefe. Vielleicht sollten Sie schreiben folgendes:

vector<int> moves = findPossibleMoves(...);
if (!moves.size())
    return boardEval(...);

Answer 5

In Ihrem Pseudo-Code weist die Knotenvariable alle die Informationen über die aktuelle Board Position enthalten (oder was auch immer). Diese Informationen würden an der Reihe, sich zu bewegen.