Search algorithm in it's simplest forum

[MahmoudUthman]

I'm a beginner in chess engine programming so far I have implement Strictly Legal move generator and verified it's correctness using perft routine ,I'm trying to implement the search and evalution functions but to no avail ,reading the source code of several other programmers even simple one's like TSCP the search routine is full of heuristic and transposition code...etc which makes it pretty much hard for me to understand , could someone provide an example search routine out of this PVS algorithm with heuristic whatsoever :

Code: Select all

int PVS(alfa,beta,depthleft) {
   if&#40; depthleft <= 0 ) return qsearch&#40;alpha, beta&#41;;
 
   // using fail soft with negamax&#58;
   make first move
   bestscore = -PVS&#40;-beta, -alpha, depthleft-1&#41;;
   unmake first move
   if&#40; bestscore > alpha ) &#123;
      if&#40; bestscore >= beta )
         return bestscore;
      alpha = bestscore;
   &#125;
 
   for&#40; all remaining moves ) &#123;
      make move
      score = -zwSearch&#40;-alpha-1, -alpha, depthleft-1&#41;; // alphaBeta or zwSearch
      if&#40; score > alpha && score < beta ) &#123;
         // research with window &#91;alpha;beta&#93;
         score = -PVS&#40;-beta, -alpha, depthleft-1&#41;;
         if&#40; score > alpha )
           alpha = score;
      &#125;
      unmake move
      if&#40; score > bestscore ) &#123;
         if&#40; score >= beta )
            return score;
         bestscore = score;
      &#125;
   &#125;
   return bestscore;
&#125;
// fail-hard zero window search, returns either beta-1 or beta
int zwSearch&#40;int beta, int depth ) &#123;
   // alpha == beta - 1
   // this is either a cut- or all-node
   if&#40; depth == 0 ) return quiesce&#40;beta-1, beta&#41;;
   for ( all moves&#41;  &#123;
     make
     score = -zwSearch&#40;1-beta, depth - 1&#41;;
     unmake
     if&#40; score >= beta )
        return beta;   // fail-hard beta-cutoff
   &#125;
   return beta-1; // fail-hard, return alpha
&#125;
int Quiesce&#40; int alpha, int beta ) &#123;
    int stand_pat = Evaluate&#40;);
    if&#40; stand_pat >= beta )
        return beta;
    if&#40; alpha < stand_pat )
        alpha = stand_pat;
 
    until&#40; every_capture_has_been_examined )  &#123;
        MakeCapture&#40;);
        score = -Quiesce&#40; -beta, -alpha );
        TakeBackMove&#40;);
 
        if&#40; score >= beta )
            return beta;
        if&#40; score > alpha )
           alpha = score;
    &#125;
    return alpha

those is the pseudo code posted on chess programming wiki, but I don't know how to incorporate it in my program, where(in which method ,and is it in search or evaluation) , when and if I should check for check/stale mate , how to do that properly and if there is any other thing, (what score should I return for both and does it depend on the side to move),also what is Quiescence Search is it important ,and do I need to implement a special move generator for it (right now the move generator generates captures then quiets and in case of evasion king moves then captures and blocks),finally what are the most important "easy to mid difficult" heuristics/techniques to implement after this ?

[kbhearn]

That is PVS in its simplest form as far as i can see, try the page on alpha-beta, and specificly the negamax framework section for a more compact representation of the core of alpha-beta search.

http://chessprogramming.wikispaces.com/Alpha-Beta

PVS is an addition to that to search a well-ordered alpha-beta tree faster and is simple enough to implement at a later time once you've understood plain ol alpha-beta.

[tpetzke]

Welcome to chess programming

but I don't know how to incorporate it in my program, where (in which method ,and is it in search or evaluation)

This is the search algorithm, but as Kevin stated start with NegaMax (this removes all this zero window stuff and is still powerful)

also what is Quiescence Search is it important

Yes it is important for a good playing strength, not necessarily that your search algorithm works. For a start you can just replace the call to qSearch with a call to eval (make sure to adjust the sign of eval to the side to move for negamax). Without qSearch your engine might want to play a Queen captures Pawn move in the last ply of search and consider this a good move although the pawn is protected and you will lose your queen next move. qSearch will extend the search in that case a bit so you see that the pawn capture is not good.

You don't have to use a special move generator for this (this would be another optimization). Just use the one you have and skip all non captures/ non queen promotion moves.

finally what are the most important "easy to mid difficult" heuristics/techniques to implement after this ?

The most important/easiest pruning method to implement would then be the null move heuristic.

EDIT: Actually even before that improve your move ordering, this will give you the biggest improvement and is necessary for alpha / beta to show its advantage over mini/max.

[SMIRF]

While I am also just about to optimize my quiescence search, it would be helpful to know, whether there are common testing examples.

Those examples should provide their node expansions' count at a given alpha/beta range. This would help to review the quality of the used move sort and the correctness of the quiescence procedure.

[Sven]

Hi Mahmoud,

since I find mixing fail-soft and fail-hard confusing (you can read more about it in the CPW if you want to know the difference) I prefer to write the search based on fail-soft only. A very basic alpha-beta negamax search with quiescence search could look like this:

Code: Select all

int qSearch(int alpha, int beta)
{
    int bestScore = evaluate();
    if (bestScore >= beta) return bestScore;
    generateLegalQSMoves();
    for (all moves) {
        makeMove(move);
        int score = -qSearch(-beta, -Max(alpha, bestScore));
        unmakeMove(move);
        if (score > bestScore) {
            bestScore = score;
            if (bestScore >= beta) break;
        }
    }
    return bestScore;
}

int search(int alpha, int beta, int depthLeft, int height)
{
    if (depthLeft == 0) return qSearch(alpha, beta);
    generateLegalMoves();
    if (numberOfLegalMoves == 0) return (isInCheck() ? -(INF - height) : 0);
    int bestScore = -INF;
    for (all moves) {
        makeMove(move);
        int score = -search(-beta, -Max(alpha, bestScore), depthLeft - 1, height + 1);
        unmakeMove(move);
        if (score > bestScore) {
            bestScore = score;
            if (bestScore >= beta) break;
            if (height == 0 && bestScore > alpha) {
                bestRootMove = move;
            }
        }
    }
    return bestScore;
}

[Henk]

Hi Mahmoud,

since I find mixing fail-soft and fail-hard confusing (you can read more about it in the CPW if you want to know the difference) I prefer to write the search based on fail-soft only. A very basic alpha-beta negamax search with quiescence search could look like this:

Code: Select all

int qSearch(int alpha, int beta)
{
    int bestScore = evaluate();
    if (bestScore >= beta) return bestScore;
    generateLegalQSMoves();
    for (all moves) {
        makeMove(move);
        int score = -qSearch(-beta, -Max(alpha, bestScore));
        unmakeMove(move);
        if (score > bestScore) {
            bestScore = score;
            if (bestScore >= beta) break;
        }
    }
    return bestScore;
}

int search(int alpha, int beta, int depthLeft, int height)
{
    if (depthLeft == 0) return qSearch(alpha, beta);
    generateLegalMoves();
    if (numberOfLegalMoves == 0) return (isInCheck() ? -(INF - height) : 0);
    int bestScore = -INF;
    for (all moves) {
        makeMove(move);
        int score = -search(-beta, -Max(alpha, bestScore), depthLeft - 1, height + 1);
        unmakeMove(move);
        if (score > bestScore) {
            bestScore = score;
            if (bestScore >= beta) break;
            if (height == 0 && bestScore > alpha) {
                bestRootMove = move;
            }
        }
    }
    return bestScore;
}

When can we expect a tutorial "How to create a top chess engine in 24 days" ?

[mar]

When can we expect a tutorial "How to create a top chess engine in 24 days" ?

I think for some "How to fix bugs" would be even more useful

[Henk]

When can we expect a tutorial "How to create a top chess engine in 24 days" ?

I think for some "How to fix bugs" would be even more useful

Only amateurs like me don't use a version control system.

[tpetzke]

Only amateurs like me don't use a version control system.

You don't need one. A random mover like is best developed with random changes.

[cdani]

Only amateurs like me don't use a version control system.

I use a text file to take note of the changes, and I copy all the versions in a folder.