1

I was following a tutorial for making a chess engine and in that, while writing the alpha beta pruning function the tutorial before checking for all possible moves generated , checks weather the current side is in check or not. If in check the depth was increased and i couldn't understand the reason. I am fairly new to chess engine programming and have searched about this but couldn't find anything relevant. Any help will be much appreciated.Thanks.

Here is the code for alpha beta pruning.

function AlphaBeta(depth, alpha, beta)
{
    SearchController.nodes++;
    if (depth <= 0)
    {
        return Evaluate();
    }

    //fiftyMove rule or if a position is Repeated
    if ((IsRepeated() || GameBoard.fiftyMove >= 100) && GameBoard.hisPly != 0)
        return 0;

    if (GameBoard.ply > MAXDEPTH - 1 )
        return Evaluate();

    //this is the line i am talking about
    var InCheck = SqAttacked(GameBoard.pieceList[Kings[GameBoard.side] * 10] , GameBoard.side ^ 1 );
    if (InCheck)  {
        depth++; //<---------HERE
    }

    var score = -INFINITE;

    GenerateMoves();

    var Move = NOMOVE, MoveNum = 0, BestMove = NOMOVE;
    var legal = 0; // To see weather any legal moves are possible
    var start = GameBoard.moveListStart[GameBoard.ply], end = GameBoard.moveListStart[GameBoard.ply + 1];

    for(MoveNum = start; MoveNum < end; MoveNum++)
    {
        Move = GameBoard.moveList[MoveNum];

        if (!MakeMove(Move))
            continue;

        legal++;

        score = -AlphaBeta(depth - 1, -beta, -alpha);

        TakeMoveBack();


        if (score > alpha)
        {
            if(score >= beta)
                return beta;

            alpha = score;
            BestMove = Move;
        }

        console.log('For move : ' + PrMove(Move) + ' Score : ' + score );
    }

    if (BestMove != NOMOVE)
    {
        StorePvMove(BestMove);
    }

    if (legal == 0)
    {
        if (SqAttacked(GameBoard.pieceList[Kings[GameBoard.side] * 10] , GameBoard.side ^ 1))
        {
            return MATE - GameBoard.ply;
        }
        else return 0;
    }

    console.log("");
    console.log("Best Move at Height : " + depth + ' Move : ' + PrMove(BestMove) + ' Score : ' + alpha);
    return alpha;

}

2 Answers 2

5

I can see more than one reason for that.

One reason is that after a check there are very few moves available: usually there are 30 moves available, but after a check there are usually at most 4 or 5. So that move doesn't count as a full ply if you want to measure the size of the resulting tree, and in the same search time you can go deeper.

Another reason, and I think it is the most important, is that a check is a forcing move, and consequences of a forcing move must be considered more deeply. So it is good to go deeper after a check.

Note that in this way, the program will tend to analyze all forced sequences of consecutive checks very deep, in this way it can easily find all perpetual checks and many forced mates. So this is can be very useful.

3
  • But how does this eliminates horizon effect. I mean what you said can be applied to other valuable pieces as well. Like if at the end of depth we take a pawn but the next move can be a queen capture by other side. So in that way increasing the depth should be done for every major piece. But we can see that no matter how much depth we go there will always be a horizon. Mar 9, 2018 at 6:02
  • 2
    A Quiescence search is used to evaluate the position when there are no captures, checks, and serious threats. This reduces most of the horizon effect, and makes it a lot easier to evaluate the position. Mar 9, 2018 at 6:37
  • Okay..i think I got it...thanks for help... Mar 9, 2018 at 9:18
5

This is known as Quiescence Search.

The purpose of this search is to only evaluate "quiet" positions, or positions where there are no winning tactical moves to be made. This search is needed to avoid the horizon effect. Simply stopping your search when you reach the desired depth and then evaluate, is very dangerous. Consider the situation where the last move you consider is QxP. If you stop there and evaluate, you might think that you have won a pawn. But what if you were to search one move deeper and find that the next move is PxQ? You didn't win a pawn, you actually lost a queen. Hence the need to make sure that you are evaluating only quiescent (quiet) positions.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.