Verbessern Minimax-Algorithmus für Gomoku AI mit Transposition Tabelle?

Question

Ich baue eine KI für Gomoku (16x16) mit Minimax und Alpha-Beta-Beschneidung, aber es ist sehr langsam. Bis jetzt habe ich versucht, die Reihenfolge der Züge vorzusortieren und anstatt das Brett tief zu kopieren, die Züge hinzuzufügen und später zu entfernen. Außerdem benutze ich eine Arraylist von relevanten Moves (die sich in einem Radius von 2 zu bereits platzierten Stücken befinden), um das Suchboard zu verkleinern. Dennoch kämpft die KI immer noch bei einer Tiefensuche von 3.
Edit: Ich habe etwas über Transpositionstabelle herausgefunden, aber ich weiß nicht, wo ich anfangen soll. Jede Hilfe wäre großartig!

private double minimax(Board node, String player, int depth, double lowerBound, double upperBound){ 
    if (depth==3){ 
     return node.evaluate(); 
    } 

    if (player.equals(humanPiece)) {// min node 
     // sort setup 
     ArrayList<int[]> relevantMoves = node.relevantMoves(); 
     HashMap<int[], Double> moveValueTable = new HashMap<>(); 

     for (int[] move: relevantMoves){ 
      node.addMove(move[0], move[1], player); 
      double val = node.evaluate(); 
      moveValueTable.put(move, val); 
      node.retractMove(move[0], move[1]); 
     } 
     // insertion sort from small to big (alpha-beta optimization) 
     insertionSort(relevantMoves, moveValueTable); 
     result = Double.POSITIVE_INFINITY; 
     // minimax 
     for (int[] move : relevantMoves) { // y first, x second 
      node.addMove(move[0], move[1], player); 
      double score = minimax(node, node.getEnemy(player), depth+1, lowerBound, upperBound); 
      node.retractMove(move[0], move[1]); 
      if (score < upperBound) { 
       upperBound = score; 
      } 
      if (score < result) result = score; 
      if (lowerBound > upperBound) { 
       break; 
      } 
     } 
     return result; 
    } 

    else{// max node 
     // sort setup 
     ArrayList<int[]> relevantMoves = node.relevantMoves(); 
     HashMap<int[], Double> moveValueTable = new HashMap<>(); 

     for (int[] move: relevantMoves){ 
      node.addMove(move[0], move[1], player); 
      double val = node.evaluate(); 
      moveValueTable.put(move, val); 
      node.retractMove(move[0], move[1]); 
     } 
     // insertion sort from big to small (alpha-beta optimization) 
     reversedInsertionSort(relevantMoves, moveValueTable); 
     result = Double.NEGATIVE_INFINITY; 
     // minimax 
     for (int[] move : relevantMoves) { // y first, x second 
      node.addMove(move[0], move[1], player); 
      double score = minimax(node, node.getEnemy(player), depth+1, lowerBound, upperBound); 
      node.retractMove(move[0], move[1]); 
      if (score > lowerBound) { 
       lowerBound = score; 
      } 
      if (score > result) result = score; 
      if (lowerBound > upperBound) { 
       break; 
      } 
     } 
     return result; 
    } 
} 

Answer 1

ist hier eine sehr gute Erklärung, wie Umsetzungstabellen arbeiten: TT

Es Ihre Suchgeschwindigkeit durch die Beseitigung der Umsetzung von dem Suchbaum verbessern. Transpositionen sind Positionen, die durch zwei oder mehr verschiedene Bewegungsfolgen erreicht werden können. Manche Spiele, wie Schach oder Dame, haben viele Umstellungen, andere haben sehr wenig oder gar keine.

Sobald Sie die Transpositionstabelle an Ort und Stelle haben, ist es einfach, weitere Geschwindigkeitsoptimierungen hinzuzufügen, die darauf basieren.