Wie ein Minimax-Position Baum in JavaScript bauen

Question

Für ein Connect4 Spiel ich diesen Alpha-Algorithmus auf den AlphaBetaWithMemory Algorithmus von Aske Plaat in seinem MTD (f) Algorithmus erklärt konvertieren müssen: https://people.csail.mit.edu/plaat/mtdf.html#abmem

Deshalb brauche ich einige Hinweise wie ich eine Minimax-Tree-Board-Position der möglichen Moves erstellen kann, um in der Lage zu sein, seine Kindknoten auf die gleiche Weise wie AlphaBetaWithMemory zu durchlaufen.

Ich hoffe wirklich, dass Sie mir einige Ratschläge geben können, bitte.

Vielen Dank.

Game.prototype.alphabeta = function(board, depth, alpha, beta, maximizingPlayer) { 

    // Call score of our board 
    var score = board.score(); 

    // Break 
    if (board.isFinished(depth, score)) return [null, score]; 

    if(maximizingPlayer) 
    { 
     // Column, Score 
     var max = [null, -99999]; 

     // POSSIBLE MOVES 
     for (var column = 0; column < that.columns; column++) 
     { 
      var new_board = board.copy(); // Create new board 

      if (new_board.place(column)) { 

       that.iterations++; // Debug 

       var next_move = that.alphabeta(new_board, depth-1, alpha, beta, false); // Recursive calling 

       // Evaluate new move 
       if (max[0] == null || next_move[1] > max[1]) { 
        max[0] = column; 
        max[1] = next_move[1]; 
        alpha = next_move[1]; 
       } 

       if (alpha >= beta) return max; 
      } 
     } 

     return max; 
    } 
    else 
    { 
     // Column, score 
     var min = [null, 99999]; 

     // POSSIBLE MOVES 
     for (var column = 0; column < that.columns; column++) { 
      var new_board = board.copy(); 

      if (new_board.place(column)) { 

       that.iterations++; 

       var next_move = that.alphabeta(new_board, depth-1, alpha, beta, true); 

       if (min[0] == null || next_move[1] < min[1]) { 
        min[0] = column; 
        min[1] = next_move[1]; 
        beta = next_move[1]; 
       } 

       if (alpha >= beta) return min; 
      } 
     } 
     return min; 
    } 
} 

Answer 1

Der AlphaBetaWithMemory Algorithmus ist ein Standard-Alpha Beta-Algorithmus, der ein Transposition Table verwendet.

Wenn also Ihr Alpha Beta-Algorithmus funktioniert, müssen Sie nur eine Transpositionstabelle hinzufügen, um Informationen aus früheren Suchen zu speichern. Ohne eine Umsetzungstabelle wird MTD (f) immer noch korrekt, aber nicht sehr effizient sein.