Gomoku AIのminimaxアルゴリズムを転置テーブルで改良しましたか？

Question

私はminimaxとalpha-betaプルーニングを使ってGomoku（16x16）のAIを構築していますが、非常に遅いです。これまでは、移動の順序を事前にソートしようとしましたが、ボードを深くコピーし、移動を追加して後で削除しました。また、私は検索ボードを減らすために、関連する動きのarraylistを使用しています（すでに配置されている部分の半径が2以内です）。しかし、AIはまだ3の深さ検索でも苦労しています。
編集：私は転置テーブルと呼ばれるものについて知りましたが、どこから始めるべきか分かりません。どんな助けも素晴らしいだろう！ここで

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

は転置テーブルがどのように働くかの非常に良い説明です：TT

それは探索木から転置を排除することで、検索速度を向上させることができます。移調は、2つ以上の異なる移動シーケンスによって達成され得る位置である。チェスやチェッカーのようないくつかのゲームは、多くの転置を持ち、他のゲームはほとんどまたはまったくありません。

転置テーブルを配置すると、それに依存する速度最適化を追加するのは簡単です。