Recursion in Chess AI

Question

I am currently in the process of completely rewriting an older Chess project and have written the main recurring function in the AI:

//Finds and applies the best move for the ai.
function aiTurn() {
//Recursive function. recurBoard is the board array passed to the function.
//Colour is either -1 or 1, -1 means it's calculating for black and 1, white.
//depth is simply how deep the recursion has gone.                                                      
var recur = function(recurBoard, colour, depth) {
    //Stops recurring when max depth is reached. Max is defined in index.html.           
    if (depth === max) return getEvaluation(recurBoard);
    //Setting a baseline for the biggest value of all deeper moves. 
    var mVal = -10000*colour;
    //Cycling through the entire board array.                                       
    for (var i = 0; i < 64; i++) {
        //Defines unit as the numeric representation of the current board position
        //(EG. -5 is a black queen, 1 is a white pawn and 6 is a white king).                               
        var unit = recurBoard[i];
        //Checks to see if the unit is a pawn
        //(currently only have programmed pawn movement for the ai).                                
        if (unit*colour != 1) continue;
        //Makes an array of all the moves the specific unit can make 
        //(formated like this: [[9,17],[9,25]]
        //This would be the moves of a pawn on square 9).                           
        var moves = getMoves(unit, i, recurBoard);
        //Loops through all the moves.              
        for (var j = 0; j < moves.length; j++) {
            //Defines movToUnt as the unit the current move will move on top of.            
            var movToUnt = recurBoard[moves[j][1]];
            //If moving on to a king simply return a massive advantage.         
            if (movToUnt === -6*colour) return 9000*colour;
            //Recurs. move(from,to,board) returns a board after a given move.
            var val = recur(move(moves[j][0], moves[j][1], recurBoard), -colour, depth+1);
            //Checks to see if the value of the move is bigger than that of the current best move
            if (val*colour > mVal*colour) mVal = val;                       
        }
    }
    //Returns the value of the best move.
    return mVal;
}

//This next part does pretty much the same thing as the for loop above, but stores the values.
var aiMoves = []
for (var i = 0; i < 64; i++) {
    var u = board[i];
    if (-u*playerSide != 1) continue;
    var uMoves = getMoves(u, i, board);
    for(var j = 0; j < uMoves.length; j++) {
        if (board[uMoves[j][1]] === 6*playerSide) {         //Shouldn't be necessary.
            uMoves[j][2] = -9000*playerSide;                //
            aiMoves[aiMoves.length] = uMoves[j];            //
            continue;                                       //
        }                                                   //
        uMoves[j][2] = recur(move(uMoves[j][0], uMoves[j][1], board), playerSide, 0);
        aiMoves[aiMoves.length] = uMoves[j];
    }
}
return aiMoves;
}

This properly recurs up to a given depth, but this gives the Chess AI the infamous "horizon effect" where it will make stupid decisions because it doesn't calculate far enough. This can be fixed simply by telling it to not stop recurring if it just killed a piece in its simulation.

Answer 1

While this is a reasonable initial attempt, this is not exactly what a modern chess engine would do. In fact, even if you would code the remaining pieces (you only have pawn now), the engine wouldn't be strong.

Before that, we should clear up some chess terminology:

• We don't say simulation, we say search
• The term AI is okay but even a better term would be engine

There're some very serious issues with your implementation:

• You will need to account for transposition. This can be done by hashing.
• You should take account of horizon effect by Quiescene Search.
• You should really consider alpha-beta search or the related nega-max search.
• In your code, you're just trying to brute force all moves in the deep-first fashion, this is absolutely unacceptable for chess programming. The search space will blow your code off. I repeat, you can't search every single position in chess, it's pointless.
• What kind of move representation are you using? This looks like a simple array to me, maybe you'd consider a faster implementation?
• Why is moving a pawn to the king is an advantage?

Depends on what you want to achieve, if you just want to code something that moves, it's fine. Unfortunately, the current code is nowhere close to anything what a modern chess engine is expected. As an experienced engine developer, I'd rate the code zero. It has lots improvement opportunities.

Please read about alpha-beta for your next attempt.