title: Chess AI: MinMax on object implementation
body: <p>I'm writing an AI for a game similar to chess.
  The board is 10x10 with 15 pieces for each side
  which all have chess similar moves.</p>
  
  <p>Everything in the game is organized in objects.
  Tile[][] tiles; 10x10, every Tile has a piece-pointer to a piece or null.</p>
  
  <p>I've implemented a MinMax algorithm with no pruning so far.
  Possible moves each round are on average twice as many as in a chess game.</p>
  
  <p>The algorithm works but it's very slow. On average it can check 
  40000 moves/pr sec. So with a depth of 4 my game uses around 4-5 seconds to
  calculate all possible moves. I will implement pruning later, but could need
  some feedback on my implementation first. </p>
  
  <p><strong>Question:
  Do i have to convert to char-arrays/bit-board or similar to speed up the 
  calculation or am i doing something horribly wrong?</strong></p>
  
  <p>Implementation: (sudo)
  To avoid lots of double for-loops i keep track of myPieces and opponentPieces
  in Lists of Tiles. Board evaluation is also done once and then only updates 
  and only updated by adding and subtracting the value of a move.
  In my implementation of the minMax algorithm i use a GameState class that
  holds the current gameState. </p>
  
  <pre><code>GameState {
   Tile[][] board
   List&lt;Tile&gt; myPieces;
   List&lt;Tile&gt; otherPieces;
   int[][] evaluatedBoard
   int evaluatedValue
   Piece moveFrom, moveTo //used to save pointer when applying move
   int moveFromValue, moveToValue //used to save evaluationValue when applying move
  
  
   void applyMove(Tile from, Tile to)
   void undoMove(Tile from, Tile to)
   GameState createCopy()
  }
  </code></pre>
  
  <p>ApplyMove only updates the evaluatedValue and does not go through
   the whole array.myPieces and otherPieces are also updated by apply/undo.</p>
  
  <p>MinMax:</p>
  
  <pre><code>maxMove(GameState state, int depth) {
   for(Tile from : state.getMyPieces().clone()) { //list will be changed
     for(Tile to : from.getPiece().getPossibleMoves()) {
         if(depth == 0)
           //find best move and so forth
         else {
          state.applyMove(from, to);
          minMove(state.createCopy(), depth - 1) //similar to maxMove except it uses otherPieces
          state.undoMove(from, to)
         }
     }
   }
   //return best move
  }
  </code></pre>
  
  <p>Edit:
  Added information about applyMove and Profiler</p>
  
  <pre><code>Profiler:          instructions
  applyMove()     3200ms  11 430 000 
  undoMove()      1800ms  11 430 000
  evaluateTile()  1400ms  22 400 000
  minMove()       1700ms  315 493 
  </code></pre>
  
  <p>applyMove and undoMove only store/reverse pointers to the old
  value off from and to and replace them with the new ones from
  the move. Then calls evaluateTile which returns a number from 1-10
  depending on a enum Type in piece.</p>