title: How can this Java tree be 1000 x faster?
body: <p>I am programming an AI for a chess-like game, based on two types of pieces on a 8 x 8 grid.</p>
  
  <p>I want to build a kind of minmax tree, which represents each possible move in a game, played by white players in first, and by black players in second.</p>
  
  <p>I have this generate() method which is call recursively. I need to be able to display about 8 levels of possible moves. Without optimization, this three has 8^8 leafs.</p>
  
  <p>I implemented a simple system which determinate if a grid has actually ever been calculated and if its the case, system just points a child to the ever-calculated child reference.</p>
  
  <p>I don't know if my explanations are clear, I will join a part of code that you should be able to understand.</p>
  
  <p>The problem is that actually, I am able to generate about 3 or 4 levels of all possibilities. I am far of 8.</p>
  
  <p>I would like to be able to calculate it in less than 5 seconds..</p>
  
  <p>So guys, do you see a solution for optimize my algorithm ?</p>
  
  <p>This is the generate function:
  leftDiagonalMove(), rightDiagonalMove() and frontMove() return false if a move is illegal or move the piece in the grid and return true, if the move is legal.</p>
  
  <p>clone() creates a new instance with the same properties of it's "parent" and backMove() just step back to last Move.</p>
  
  <pre><code>public void generate(Node root, boolean white, int index) {
  
      Grid grid = root.getGrid();
  
      Stack&lt;Piece&gt; whitePieces = grid.getPiecesByColor(WHITE);
      Stack&lt;Piece&gt; blackPieces = grid.getPiecesByColor(BLACK);
      Node node;
  
      String serial = "";
      // white loop
      for (int i = 0; i &lt; whitePieces.size() &amp;&amp; white; i++) {
          Piece wPiece = whitePieces.get(i);
  
          if (grid.leftDiagonalMove(wPiece)) {
              serial = grid.getSerial();
              if(!allGrids.containsKey(serial)){
                  node = new Node(grid.clone());
                  node.setMove(grid.getLastMove());
                  root.addChild(node); // add modified grid
                  allGrids.put(serial, node);
                  //actualGrid.display();
                  if (index &lt; 5 &amp;&amp; grid.getPosition(wPiece).x &gt; 0)
                      generate(node, !white, index + 1);
                  actualGrid.backMove(); // back step to initial grid
              }
              else{
                  root.addChild(allGrids.get(serial));
              }
          }
  
          if (grid.frontMove(wPiece)) {
              // same code as leftMove
          }
  
          if (grid.rightDiagonalMove(wPiece)) {
              // same code as leftMove
          }
  
      }
  
      // black loop
      for (int i = 0; i &lt; blackPieces.size() &amp;&amp; !white; i++) {
          Piece bPiece = blackPieces.get(i);
  
          if (grid.leftDiagonalMove(bPiece)) {
              // same code as white loop and replacing wPiece by bPiece
          }
  
          if (grid.frontMove(bPiece)) {
              // same code as white loop and replacing wPiece by bPiece
          }
  
          if (grid.rightDiagonalMove(bPiece)) {
              // same code as white loop and replacing wPiece by bPiece
          }
  
      }
  
  }
  </code></pre>