# Recursion in Chess AI

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.

• First step. Put your comments on line above where they are appropriate , not way out at the end of the line. Seriously, the code is so hard to review right now, that you may not even get a meaningful review. You should strive to keep your lines of code <80 characters per line. Even break up your comments across lines as necessary to keep within this limit. – Mike Brant Sep 3 '16 at 3:31
• Alright, thanks for the feedback. I've done that now. – Lasse Møldrup Sep 3 '16 at 11:41

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.

• Well I am very much a novice and really want to learn from what I write so i don't want to copy someone else's solution. It doesn't have to be particularly good as long as I learn from it. However I definitely see your point and will be doing some research on the things you listed. – Lasse Møldrup Sep 4 '16 at 16:55
• My move representation is indeed as simple as an array [from, to], what would be a faster solution? Moving a pawn to the king is an advantage as it wins you the game and it should also stop searching, which is why it returns. – Lasse Møldrup Sep 4 '16 at 16:56
• @LasseMøldrup why does moving a pawn to the King wins a game? We need to checkmate to win. – SmallChess Sep 4 '16 at 17:07
• Any reference to learn how to create such an engine ? – Steve Chamaillard Sep 4 '16 at 19:47
• @SteveChamaillard chessprogramming.wikispaces.com – SmallChess Sep 5 '16 at 2:24