<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>

CC BY-SA 4.0
2021-01-27T11:55:38.723Z
Are you saying that it's taking too long to sort the moves?
nbro
CC BY-SA 4.0
2021-01-27T14:53:43.207Z
Yes, when I sort moves, it takes longer than before (which has no sorted moves).
James Urian
CC BY-SA 4.0
2021-01-27T15:59:32.243Z
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
<chess><alpha-beta-pruning>
How to implement very simple move-ordering for alpha-beta pruning
James Urian
# 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

