Body: <p>I've done implementing alpha-beta, and transpositional table on my search tree algorithm so I decided to implement move-ordering next. But once I implemented it, it's way more longer to respond than before?</p>
  <p>Here's my code so far:</p>
  <pre><code>function sortMoves(chess)
  {
      const listA = [], listB = chess.moves({ verbose: true });
      const scores = [];
  
      // calc best moves
      const moves = [...listB];
      for (const move of moves)
      {
          const state = chess.move(move, {
              promotion: 'q'
          });
          scores.push(evaluate(chess.board()));
          chess.undo();
      }
      
      // sort move
      for (var i = 0; i &lt; Math.min(5, moves.length); i++)
      {
          let maxEval = -Infinity;
          let maxIndex = 0;
          
          for (var j = 0; j &lt; scores.length; j++)
          {
              if (scores[j] &gt; maxEval)
              {
                  maxEval = scores[j];
                  maxIndex = j;
              }
          }
          
          scores[maxIndex] = -Infinity;
          listA.push(moves[maxIndex]);
          listB.splice(maxIndex, 1);
      }
      
      const newList = listA.concat(listB);
      return newList;
  }
  </code></pre>
  <p>I am expecting for this to respond quicker than before but it turns out it's not. So my question is am I actually sorting the moves correctly? or should I write some code for the alpha-beta pruning related to the sorted moves?</p>
  <p>Here's my <code>negamax</code> function:</p>
  <pre><code>function negamax(chess, depth, depthOrig, alpha, beta, color)
  {
      // transposition table look up
      const alphaOrig = alpha;
      const hashKey = zobrist.hash(chess);
      const lookup = transposition.get(hashKey);
      if (lookup)
      {
          if (lookup.depth &gt;= depth)
          {
              if (lookup.flag === EXACT)
                  return lookup.score;
              else if (lookup.flag === LOWERBOUND)
                  alpha = Math.max(alpha, lookup.score);
              else if (lookup.flag === UPPERBOUND)
                  beta = Math.min(beta, lookup.score);
              
              if (alpha &gt;= beta)
                  return lookup.score;
          }
      }
  
  
      if (depth === 0 || chess.game_over())
      {
          // if current turn is checkmated,
          // remove the king on the board
          // so the AI knows if the move
          // will lead to checkmate or not, if
          // it's remove on the board, 
          // the checkmated team will
          // reduce the king's value leading
          // the AI to move in checkmate
          const kingPos = getPiecePos(chess, 'k', chess.turn());
          if (chess.in_checkmate())
              chess.remove(kingPos);
          
          const evaluation = evaluate(chess.board());
          chess.put({ type: chess.KING, color: chess.turn() }, kingPos);
  
          return color * evaluation;
      }
  
      
      /* let moves = chess.moves();
      if (lookup)
      {
          console.log(moves, depth)
          const bestMove = lookup.move;
          const moveIndex = moves.indexOf(bestMove);
          const arr = moves.splice(moveIndex, 1);
          moves = arr.concat(moves);
          console.log(moves, depth)
      } */
      const moves = sortMoves(chess);
      /* const moves = chess.moves({ verbose: true }); */
  
  
      let count = 0;
      let score = -Infinity;
      let bestMove = null;
      if (lookup)
          bestMove = lookup.move;
  
      
      for (const move of moves)
      {
          const state = chess.move(move, {
              promotion: 'q'
          });
          searchedMoves++;
          if (count === 0)
              score = -negamax(chess, depth-1, depthOrig, -beta, -alpha, -color);
          else
          {
              score = -negamax(chess, depth-1, depthOrig, -alpha-1, -alpha, -color);
              if (alpha &lt; score &lt; beta)
                  score = -negamax(chess, depth-1, depthOrig, -beta, -score, -color);
          }
          chess.undo();
  
          if (score &gt; alpha)
          {
              alpha = score;
              bestMove = move;
          }
  
          // do I add something on this part?
          count++;
          if (alpha &gt;= beta)
              break;
      }
  
      
      // transposition table store
      const key = zobrist.hash(chess);
      keyArr.push(key);
      const entry = new Transposition();
      entry.score = score;
      entry.depth = depth;
      entry.move = bestMove;
      if (score &lt;= alphaOrig)
          entry.flag = UPPERBOUND;
      else if (score &gt;= beta)
          entry.flag = LOWERBOUND;
      else
          entry.flag = EXACT;
      transposition.set(key, entry);
  
  
      return alpha;
  }
  <span class="math-container">```</span>
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-27T11:55:38.723Z
Comments.Text: Are you saying that it's taking too long to sort the moves?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-27T14:53:43.207Z
Comments.Text: Yes, when I sort moves, it takes longer than before (which has no sorted moves).
Comments.UserDisplayName: James Urian
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-27T15:59:32.243Z
Comments.Text: No, my question was: what is taking too long: 1. sorting the moves, 2. minimax after sorting the moves? Also, I didn't look at your code and it's been a while I had to deal with minimax, but what would it mean to apply minimax after having sorted the moves? Can you explain a little bit what your idea is? Also, how long does it take?
Comments.UserDisplayName: nbro
Tags: <chess><alpha-beta-pruning>
Title: How to implement very simple move-ordering for alpha-beta pruning
UserDisplayName: James Urian
ThreadText: # How to implement very simple move-ordering for alpha-beta pruning
  
  (Asked by: username_0 on 2021-01-22)
  
  I've done implementing alpha-beta, and transpositional table on my search tree algorithm so I decided to implement move-ordering next. But once I implemented it, it's way more longer to respond than before?
  Here's my code so far:
  function sortMoves(chess)
  {
      const listA = [], listB = chess.moves({ verbose: true });
      const scores = [];
  
      // calc best moves
      const moves = [...listB];
      for (const move of moves)
      {
          const state = chess.move(move, {
              promotion: 'q'
          });
          scores.push(evaluate(chess.board()));
          chess.undo();
      }
      
      // sort move
      for (var i = 0; i < Math.min(5, moves.length); i++)
      {
          let maxEval = -Infinity;
          let maxIndex = 0;
          
          for (var j = 0; j < scores.length; j++)
          {
              if (scores[j] > maxEval)
              {
                  maxEval = scores[j];
                  maxIndex = j;
              }
          }
          
          scores[maxIndex] = -Infinity;
          listA.push(moves[maxIndex]);
          listB.splice(maxIndex, 1);
      }
      
      const newList = listA.concat(listB);
      return newList;
  }
  
  I am expecting for this to respond quicker than before but it turns out it's not. So my question is am I actually sorting the moves correctly? or should I write some code for the alpha-beta pruning related to the sorted moves?
  Here's my negamax function:
  function negamax(chess, depth, depthOrig, alpha, beta, color)
  {
      // transposition table look up
      const alphaOrig = alpha;
      const hashKey = zobrist.hash(chess);
      const lookup = transposition.get(hashKey);
      if (lookup)
      {
          if (lookup.depth >= depth)
          {
              if (lookup.flag === EXACT)
                  return lookup.score;
              else if (lookup.flag === LOWERBOUND)
                  alpha = Math.max(alpha, lookup.score);
              else if (lookup.flag === UPPERBOUND)
                  beta = Math.min(beta, lookup.score);
              
              if (alpha >= beta)
                  return lookup.score;
          }
      }
  
  
      if (depth === 0 || chess.game_over())
      {
          // if current turn is checkmated,
          // remove the king on the board
          // so the AI knows if the move
          // will lead to checkmate or not, if
          // it's remove on the board, 
          // the checkmated team will
          // reduce the king's value leading
          // the AI to move in checkmate
          const kingPos = getPiecePos(chess, 'k', chess.turn());
          if (chess.in_checkmate())
              chess.remove(kingPos);
          
          const evaluation = evaluate(chess.board());
          chess.put({ type: chess.KING, color: chess.turn() }, kingPos);
  
          return color * evaluation;
      }
  
      
      /* let moves = chess.moves();
      if (lookup)
      {
          console.log(moves, depth)
          const bestMove = lookup.move;
          const moveIndex = moves.indexOf(bestMove);
          const arr = moves.splice(moveIndex, 1);
          moves = arr.concat(moves);
          console.log(moves, depth)
      } */
      const moves = sortMoves(chess);
      /* const moves = chess.moves({ verbose: true }); */
  
  
      let count = 0;
      let score = -Infinity;
      let bestMove = null;
      if (lookup)
          bestMove = lookup.move;
  
      
      for (const move of moves)
      {
          const state = chess.move(move, {
              promotion: 'q'
          });
          searchedMoves++;
          if (count === 0)
              score = -negamax(chess, depth-1, depthOrig, -beta, -alpha, -color);
          else
          {
              score = -negamax(chess, depth-1, depthOrig, -alpha-1, -alpha, -color);
              if (alpha < score < beta)
                  score = -negamax(chess, depth-1, depthOrig, -beta, -score, -color);
          }
          chess.undo();
  
          if (score > alpha)
          {
              alpha = score;
              bestMove = move;
          }
  
          // do I add something on this part?
          count++;
          if (alpha >= beta)
              break;
      }
  
      
      // transposition table store
      const key = zobrist.hash(chess);
      keyArr.push(key);
      const entry = new Transposition();
      entry.score = score;
      entry.depth = depth;
      entry.move = bestMove;
      if (score <= alphaOrig)
          entry.flag = UPPERBOUND;
      else if (score >= beta)
          entry.flag = LOWERBOUND;
      else
          entry.flag = EXACT;
      transposition.set(key, entry);
  
  
      return alpha;
  }
  ```
  
  **Tags:** chess, alpha-beta-pruning
  > **Comments:**
  > **username_1**: Are you saying that it's taking too long to sort the moves?  
  > **username_0**: Yes, when I sort moves, it takes longer than before (which has no sorted moves).  
  > **username_1**: No, my question was: what is taking too long: 1. sorting the moves, 2. minimax after sorting the moves? Also, I didn't look at your code and it's been a while I had to deal with minimax, but what would it mean to apply minimax after having sorted the moves? Can you explain a little bit what your idea is? Also, how long does it take?  
  
  ---
  
  ## 0 answers
  
  