Search algorithm in it's simplest forum

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
MahmoudUthman
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

Search algorithm in it's simplest forum

Post by MahmoudUthman » Wed Feb 25, 2015 11:31 pm

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
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Search algorithm in it's simplest forum

Post by kbhearn » Wed Feb 25, 2015 11:46 pm

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
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: Search algorithm in it's simplest forum

Post by tpetzke » Thu Feb 26, 2015 9:25 am

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.
Thomas...

=======
http://macechess.blogspot.com - iCE Chess Engine

User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

Re: Search algorithm in it's simplest forum

Post by SMIRF » Thu Feb 26, 2015 10:18 am

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
Posts: 3820
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Search algorithm in it's simplest forum

Post by Sven » Thu Feb 26, 2015 4:20 pm

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&#40;int alpha, int beta&#41;
&#123;
    int bestScore = evaluate&#40;);
    if &#40;bestScore >= beta&#41; return bestScore;
    generateLegalQSMoves&#40;);
    for &#40;all moves&#41; &#123;
        makeMove&#40;move&#41;;
        int score = -qSearch&#40;-beta, -Max&#40;alpha, bestScore&#41;);
        unmakeMove&#40;move&#41;;
        if &#40;score > bestScore&#41; &#123;
            bestScore = score;
            if &#40;bestScore >= beta&#41; break;
        &#125;
    &#125;
    return bestScore;
&#125;

int search&#40;int alpha, int beta, int depthLeft, int height&#41;
&#123;
    if &#40;depthLeft == 0&#41; return qSearch&#40;alpha, beta&#41;;
    generateLegalMoves&#40;);
    if &#40;numberOfLegalMoves == 0&#41; return &#40;isInCheck&#40;) ? -&#40;INF - height&#41; &#58; 0&#41;;
    int bestScore = -INF;
    for &#40;all moves&#41; &#123;
        makeMove&#40;move&#41;;
        int score = -search&#40;-beta, -Max&#40;alpha, bestScore&#41;, depthLeft - 1, height + 1&#41;;
        unmakeMove&#40;move&#41;;
        if &#40;score > bestScore&#41; &#123;
            bestScore = score;
            if &#40;bestScore >= beta&#41; break;
            if &#40;height == 0 && bestScore > alpha&#41; &#123;
                bestRootMove = move;
            &#125;
        &#125;
    &#125;
    return bestScore;
&#125;

Henk
Posts: 5746
Joined: Mon May 27, 2013 8:31 am

Re: Search algorithm in it's simplest forum

Post by Henk » Thu Feb 26, 2015 7:37 pm

Sven Schüle wrote: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&#40;int alpha, int beta&#41;
&#123;
    int bestScore = evaluate&#40;);
    if &#40;bestScore >= beta&#41; return bestScore;
    generateLegalQSMoves&#40;);
    for &#40;all moves&#41; &#123;
        makeMove&#40;move&#41;;
        int score = -qSearch&#40;-beta, -Max&#40;alpha, bestScore&#41;);
        unmakeMove&#40;move&#41;;
        if &#40;score > bestScore&#41; &#123;
            bestScore = score;
            if &#40;bestScore >= beta&#41; break;
        &#125;
    &#125;
    return bestScore;
&#125;

int search&#40;int alpha, int beta, int depthLeft, int height&#41;
&#123;
    if &#40;depthLeft == 0&#41; return qSearch&#40;alpha, beta&#41;;
    generateLegalMoves&#40;);
    if &#40;numberOfLegalMoves == 0&#41; return &#40;isInCheck&#40;) ? -&#40;INF - height&#41; &#58; 0&#41;;
    int bestScore = -INF;
    for &#40;all moves&#41; &#123;
        makeMove&#40;move&#41;;
        int score = -search&#40;-beta, -Max&#40;alpha, bestScore&#41;, depthLeft - 1, height + 1&#41;;
        unmakeMove&#40;move&#41;;
        if &#40;score > bestScore&#41; &#123;
            bestScore = score;
            if &#40;bestScore >= beta&#41; break;
            if &#40;height == 0 && bestScore > alpha&#41; &#123;
                bestRootMove = move;
            &#125;
        &#125;
    &#125;
    return bestScore;
&#125;
When can we expect a tutorial "How to create a top chess engine in 24 days" ?

mar
Posts: 1987
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Search algorithm in it's simplest forum

Post by mar » Thu Feb 26, 2015 7:49 pm

Henk wrote: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
Posts: 5746
Joined: Mon May 27, 2013 8:31 am

Re: Search algorithm in it's simplest forum

Post by Henk » Thu Feb 26, 2015 7:51 pm

mar wrote:
Henk wrote: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
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: Search algorithm in it's simplest forum

Post by tpetzke » Thu Feb 26, 2015 8:47 pm

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.
Thomas...

=======
http://macechess.blogspot.com - iCE Chess Engine

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Search algorithm in it's simplest forum

Post by cdani » Thu Feb 26, 2015 9:32 pm

Henk wrote: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.

Post Reply