title: Improving minimax algorithm for Gomoku AI with transposition table?
body: <p>I'm building an AI for Gomoku (16x16) with minimax and alpha-beta pruning but it's very slow. So far, I have tried pre-sorting the order of moves and instead of deep copying the board, adding and later removing the moves. Also, I use an arraylist of relevant moves(which are within a radius of 2 to already placed pieces) to reduce the search board. Yet the AI still struggles even at a depth search of 3.<br>
  Edit: I have found out about something called transposition table, but I don't know where to start. Any help would be great!</p>
  
  <pre><code>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&lt;int[]&gt; relevantMoves = node.relevantMoves();
          HashMap&lt;int[], Double&gt; moveValueTable = new HashMap&lt;&gt;();
  
          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 &lt; upperBound) {
                  upperBound = score;
              }
              if (score &lt; result) result = score;
              if (lowerBound &gt; upperBound) {
                  break;
              }
          }
          return result;
      }
  
      else{// max node
          // sort setup
          ArrayList&lt;int[]&gt; relevantMoves = node.relevantMoves();
          HashMap&lt;int[], Double&gt; moveValueTable = new HashMap&lt;&gt;();
  
          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 &gt; lowerBound) {
                  lowerBound = score;
              }
              if (score &gt; result) result = score;
              if (lowerBound &gt; upperBound) {
                  break;
              }
          }
          return result;
      }
  }
  </code></pre>