title: A Simple Chess Minimax
body: <p>I have problem with my own Chess Engine using minimax algorithm to search for chess moves I use a 5 plies depth search and with only material/bonus/mobility evaluation , but it also make dumb moves and sacrifices valuable pieces even when I give to them infinity (which is sure a search problem), I'm not using any types of pruning and gives a 5 depth search result in few seconds.</p>
  
  <p>I'm stuck in this problem for a week, I am sure the Problem is with the Backtracking not the Chess Logic (so anyone with no chess background would solve this :)) and I searched a lot this is my first Question in Stack Overflow and I hope you guys won't Disappoint me :)</p>
  
  <p>Here is the simple search code</p>
  
  <pre><code>int GameControl::Evaluate(ChessBoard _B)
  {
  
      int material=0,bonus=0,mobility=0;
      for(int i=0;i&lt;8;i++)
          for(int j=0;j&lt;8;j++)
          {
  
              if(_B.Board[i][j]!=EMPTY)
              {
                  if(_B.Board[i][j]-&gt;pieceColor==WHITE){
                      material+=-_B.Board[i][j]-&gt;Weight;
                      bonus+=-_B.Board[i][j]-&gt;bonusPosition[i][j];
                      mobility+=-_B.Board[i][j]-&gt;getPossibleMovesList(i,j,B).size();
                  }
                  else {
                      material+=_B.Board[i][j]-&gt;Weight;
                      bonus+=_B.Board[i][j]-&gt;bonusPosition[i][j];             
                  mobility+=_B.Board[i][j]-&gt;getPossibleMovesList(i,j,B).size();
                  }
              }
          }
          return material+bonus/10+mobility/20;
  }
  
  
  pair&lt;pair&lt;int,int&gt;,pair&lt;int,int&gt;&gt; GameControl::minimax( int depth , ChessBoard _B )
  {
      short int i,j;
  
      int bestValue = -INFINITY;
  
      pair&lt;pair&lt;int,int&gt;,pair&lt;int,int&gt;&gt; bestMove;
  
      vector&lt; pair&lt;int,int&gt; &gt; ::iterator it;
  
      vector&lt; pair&lt;int,int&gt; &gt; Z;
  
      for( i = 0; i &lt; 8; i++ )
  
          for( j = 0; j &lt; 8; j++ )
          {
              if(_B.Board[i][j]!=EMPTY &amp;&amp; _B.Board[i][j]-&gt;pieceColor==BLACK )
              {
                  Z=_B.Board[i][j]-&gt;getPossibleMovesList(i,j,_B);
                  for(it=Z.begin();it!=Z.end();it++)
                  {
                      pair&lt;int,int&gt; temp;
                      temp.first=i,temp.second=j;
                      ChessPieces* DestinationPiece;
                      DestinationPiece=_B.Board[(*it).first][(*it).second];
                      //Moving
                      _B.Board[(*it).first][(*it).second]=_B.Board[i][j];
                      _B.Board[i][j]=EMPTY;
                      //
                      int value = minSearch( depth-1 , _B );
                      if( value &gt; bestValue )
                      {
                          bestValue = value;
                          bestMove.first.first = i;
                          bestMove.first.second = j;
                          bestMove.second.first = (*it).first;
                          bestMove.second.second = (*it).second;
  
                      }
                      //Undo Move
                      _B.Board[i][j]=_B.Board[((*it).first)][(*it).second];
                      _B.Board[(*it).first][(*it).second]=DestinationPiece;
                  }
  
              }
          }
  
          return bestMove;
  }
  
  
  int GameControl::minSearch( int depth , ChessBoard _B )
  {
  
      short int i;
      short int j;
      if(depth==0)
          return Evaluate(_B);
  
      int bestValue = INFINITY;
      for( i = 0; i &lt; 8; i++ )
          for( j = 0; j &lt; 8; j++ )
          {
              vector&lt; pair&lt;int,int&gt; &gt; ::iterator it;
              vector&lt; pair&lt;int,int&gt; &gt; Z;
              if(_B.Board[i][j]!=EMPTY &amp;&amp; _B.Board[i][j]-&gt;pieceColor==WHITE  &amp;&amp; !_B.Board[i][j]-&gt;V.empty())
              {
  
                  Z=_B.Board[i][j]-&gt;getPossibleMovesList(i,j,_B);
                  for(it=Z.begin();it!=Z.end();it++)
                  {
  
                      pair&lt;int,int&gt; temp;
                      temp.first=i;
                      temp.second=j;
                      ChessPieces* DestinationPiece;
                      DestinationPiece=_B.Board[(*it).first][(*it).second];
                      // Moving
                      _B.Board[(*it).first][(*it).second]=_B.Board[i][j];
                      _B.Board[i][j]=EMPTY;
                      //
                      int value = maxSearch( depth-1 , _B );
                      if( value &lt; bestValue )
                          bestValue = value;  
                      //Undo Move
                      _B.Board[i][j]=_B.Board[(*it).first][(*it).second];     
                      _B.Board[(*it).first][(*it).second]=DestinationPiece;
                      //
                  }
  
              }
          }
          return bestValue;
  }
  
  
  int GameControl::maxSearch( int depth , ChessBoard _B )
  {
  
  
      short int i;
      short int j;
      if(depth==0)
          return Evaluate(_B);
      vector&lt; pair&lt;int,int&gt; &gt; ::iterator it;
      vector&lt; pair&lt;int,int&gt; &gt; Z;
      int bestValue = -INFINITY;
      for( i = 0; i &lt; 8; i++ )
          for( j = 0; j &lt; 8; j++ )
          {
  
              if(_B.Board[i][j]!=EMPTY &amp;&amp; _B.Board[i][j]-&gt;pieceColor==BLACK )
              {
                  Z=_B.Board[i][j]-&gt;getPossibleMovesList(i,j,_B);
                  for(it=Z.begin();it!=Z.end();it++)
                  {
                      pair&lt;int,int&gt; temp;
  
                      temp.first=i,temp.second=j;
                      ChessPieces* DestinationPiece;
                      DestinationPiece=_B.Board[(*it).first][(*it).second];
                      //Moving
                      _B.Board[(*it).first][(*it).second]=_B.Board[i][j];
                      _B.Board[i][j]=EMPTY;
                      //
                      int value = minSearch( depth-1 , _B );
                      if( value &gt; bestValue )     
                          bestValue = value;
  
                      //Undo Move
                      _B.Board[i][j]=_B.Board[((*it).first)][(*it).second];   
                      _B.Board[(*it).first][(*it).second]=DestinationPiece;
                  }
  
              }
          }
          return bestValue;
  }
  </code></pre>