0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.