# How to implement very simple move-ordering for alpha-beta pruning

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;
}
$$$$
`
• Are you saying that it's taking too long to sort the moves? – nbro Jan 27 at 11:55
• Yes, when I sort moves, it takes longer than before (which has no sorted moves). – James Urian Jan 27 at 14:53
• 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? – nbro Jan 27 at 15:59