PVS + ZWS

[flok]

Hi,

I'm implementing the PVS+ZWS from http://chessprogramming.wikispaces.com/ ... ion+Search.

I though it helped dramatically for the time-to-depth (12 plies in seconds) but that was caused by a bug (position hash was not removed from history-list (for move repetition detection)).

Now the results are underwhelming.
My regular alpha/beta searcher reaches depth 6 in 2 seconds:

Code: Select all

info depth 6 seldepth 6 score cp 2 time 2025 nodes 283186 pv b1c3 d7d5 e2e3 d8d6

and the pvs+zws searcher in almost 8 (EIGHT) seconds:

Code: Select all

info depth 6 seldepth 6 score cp 2 time 7595 nodes 887015 pv b1c3 d7d5 e2e3 d8d6

So it somewhat works but I'm not entirely sure if I do the right thing.

For starters: I'm not sure when to select the move. Only when score > alpha? Or also for the beta-cut-off? or?

search

Code: Select all

function search()

loop_through_movelist() {
        make_move();

        int score = 0;
        // addToHistory checks for position repetition
        if (!addToHistory(sd -> history, newHash.newHash))
        {       
                if (bSearchPv)
                        score = -search(sd, newDepth, co, -beta, -alpha, newHash, stopFlag, false, mCurPrevBest, false, &tempPv);
                else    
                {       
                        score = -zwSearch(sd, co, -alpha, newDepth, newHash, stopFlag);

                        if (score > alpha)
                                score = -search(sd, newDepth, co, -beta, -alpha, newHash, stopFlag, false, mCurPrevBest, false, &tempPv);
                }       
        }       
        removeFromToHistory(sd -> history, newHash.newHash);

        unmake_move();

        if (score > bestVal)
        {       
                bestVal = score; // bestVal is the value which is returned at the end of the function
                mBestMove = cm;

                newPv.assign(tempPv, false); // keep track of pv
                mCurPrevBest = tempPv.back(); // use this move, so this is for the root

                if (score >= beta)
                {       
                        bestVal = beta; 
                        betaCutOff = true; 
                        break;  
                }       

                if (score > alpha)
                {       
                        alpha = score;
                        bSearchPv = false;
                }       
        }       

zwSearch

Code: Select all

        if (depthLeft == 0)
                return quiesceSearch(sd, c, beta - 1, beta, zh, stopFlag, invalidMove, &moveDummy, &pvDummy);

        for&#40;size_t idx=0; idx<nMoves && !*stopFlag; idx++)
        &#123;       
                make_move&#40;idx&#41;;
                
                int score = 0;
                if (!addToHistory&#40;sd -> history, newHash.newHash&#41;)
                        score = -zwSearch&#40;sd, co, 1 - beta, depthLeft - 1, newHash, stopFlag&#41;;
                removeFromToHistory&#40;sd -> history, newHash.newHash&#41;;

                unmake_move&#40;idx&#41;;
                
                if &#40;score >= beta&#41;
                        return beta;   // fail-hard beta-cutoff
        &#125;

        return beta - 1; // fail-hard, return alpha

Any ideas?


regards

[mar]

I only search the first move with full bounds (n first moves at root in mpv mode), so maybe rewriting it like

Code: Select all

int score = beta;    // anything above alpha
...
if ( !bSearchPv )
    score = -zwSearch(...)
bSearchPv = 1;
if ( score > alpha )
    score = -search(...)

alternatively you could process the first move outside the loop, but as search gets more complicated... not sure it'd be worth it

Maybe even

Code: Select all

int score = beta;    // anything >= beta
...
if ( score < beta )
    score = -zwSearch&#40;...)
if ( score > alpha )
    score = -search&#40;...)

if you want to get rid of auxiliary bSearchPv

[Joost Buijs]

Code: Select all

function search()
      
                if (bSearchPv)
                        score = -search(sd, newDepth, co, -beta, -alpha, newHash, stopFlag, false, mCurPrevBest, false, &tempPv);
                else    
                {       
                        score = -zwSearch(sd, co, -alpha, newDepth, newHash, stopFlag);

                        if (score > alpha)
                                score = -search(sd, newDepth, co, -beta, -alpha, newHash, stopFlag, false, mCurPrevBest, false, &tempPv);

It is unnecessary when the score returned from the zw-search >= beta to research with the pv-search.
e.g. like:

Code: Select all

function search()
      
                if (bSearchPv)
                        score = -search(sd, newDepth, co, -beta, -alpha, newHash, stopFlag, false, mCurPrevBest, false, &tempPv);
                else    
                {       
                        score = -zwSearch(sd, co, -alpha, newDepth, newHash, stopFlag);

                        if &#40;score > alpha && score < beta&#41;
                                score = -search&#40;sd, newDepth, co, -beta, -alpha, newHash, stopFlag, false, mCurPrevBest, false, &tempPv&#41;;

[Karlo Bala]

Hi,

I'm implementing the PVS+ZWS from http://chessprogramming.wikispaces.com/ ... ion+Search.

I though it helped dramatically for the time-to-depth (12 plies in seconds) but that was caused by a bug (position hash was not removed from history-list (for move repetition detection)).

Now the results are underwhelming.
My regular alpha/beta searcher reaches depth 6 in 2 seconds:

Code: Select all

info depth 6 seldepth 6 score cp 2 time 2025 nodes 283186 pv b1c3 d7d5 e2e3 d8d6

and the pvs+zws searcher in almost 8 (EIGHT) seconds:

Code: Select all

info depth 6 seldepth 6 score cp 2 time 7595 nodes 887015 pv b1c3 d7d5 e2e3 d8d6

So it somewhat works but I'm not entirely sure if I do the right thing.

For starters: I'm not sure when to select the move. Only when score > alpha? Or also for the beta-cut-off? or?

search

Code: Select all

function search()

loop_through_movelist() {
        make_move();

        int score = 0;
        // addToHistory checks for position repetition
        if (!addToHistory(sd -> history, newHash.newHash))
        {       
                if (bSearchPv)
                        score = -search(sd, newDepth, co, -beta, -alpha, newHash, stopFlag, false, mCurPrevBest, false, &tempPv);
                else    
                {       
                        score = -zwSearch(sd, co, -alpha, newDepth, newHash, stopFlag);

                        if (score > alpha)
                                score = -search(sd, newDepth, co, -beta, -alpha, newHash, stopFlag, false, mCurPrevBest, false, &tempPv);
                }       
        }       
        removeFromToHistory(sd -> history, newHash.newHash);

        unmake_move();

        if (score > bestVal)
        {       
                bestVal = score; // bestVal is the value which is returned at the end of the function
                mBestMove = cm;

                newPv.assign(tempPv, false); // keep track of pv
                mCurPrevBest = tempPv.back(); // use this move, so this is for the root

                if (score >= beta)
                {       
                        bestVal = beta; 
                        betaCutOff = true; 
                        break;  
                }       

                if (score > alpha)
                {       
                        alpha = score;
                        bSearchPv = false;
                }       
        }       

zwSearch

Code: Select all

        if (depthLeft == 0)
                return quiesceSearch(sd, c, beta - 1, beta, zh, stopFlag, invalidMove, &moveDummy, &pvDummy);

        for&#40;size_t idx=0; idx<nMoves && !*stopFlag; idx++)
        &#123;       
                make_move&#40;idx&#41;;
                
                int score = 0;
                if (!addToHistory&#40;sd -> history, newHash.newHash&#41;)
                        score = -zwSearch&#40;sd, co, 1 - beta, depthLeft - 1, newHash, stopFlag&#41;;
                removeFromToHistory&#40;sd -> history, newHash.newHash&#41;;

                unmake_move&#40;idx&#41;;
                
                if &#40;score >= beta&#41;
                        return beta;   // fail-hard beta-cutoff
        &#125;

        return beta - 1; // fail-hard, return alpha

Any ideas?


regards

It is better to replace "bSearchPv" with "movenumber == 1" just in case that you are using aspiration windows. Also, simple A-B works better then PVS if move ordering is poor. Are you sure that your hash table is working correctly?

[flok]

if you want to get rid of auxiliary bSearchPv

Yes, I replaced that by the iterator.

It is unnecessary when the score returned from the zw-search >= beta to research with the pv-search.

Ok, applied.

It is better to replace "bSearchPv" with "movenumber == 1" just in case that you are using aspiration windows. Also, simple A-B works better then PVS if move ordering is poor. Are you sure that your hash table is working correctly?

Well, what I do is: move the move from the pv-list for that depth to position 0 of the movelist and then move the best-move of the sibling to position 1. After that I sort the rest of the moves (offset 2 and further) according to the "(victim_value << 16) | (10000 - attacker_value)"-value.

Sofar these changes have not give a better result.

Regarding the hash-table: I don't have a tt for zwSearch. I probably can't use the regular one for it? Or a seperate of the same sort? Or should I create one that has only entry-type "exact"? Because my tt implementation for other searches also has a lower- and upper-bound flag.

Apart from those considerations, is this code correct?

Code: Select all

if (score > bestVal) 
        {        
                bestVal = score; // bestVal is the value which is returned at the end of the function 
                mBestMove = cm; 

                newPv.assign(tempPv, false); // keep track of pv 
                mCurPrevBest = tempPv.back(); // use this move, so this is for the root 

                if (score >= beta) 
                {        
                        bestVal = beta; 
                        betaCutOff = true; 
                        break;  
                }        

                if (score > alpha) 
                {        
                        alpha = score; 
                        bSearchPv = false; 
                }        
        }

[bob]

if you want to get rid of auxiliary bSearchPv

Yes, I replaced that by the iterator.

It is unnecessary when the score returned from the zw-search >= beta to research with the pv-search.

Ok, applied.

It is better to replace "bSearchPv" with "movenumber == 1" just in case that you are using aspiration windows. Also, simple A-B works better then PVS if move ordering is poor. Are you sure that your hash table is working correctly?

Well, what I do is: move the move from the pv-list for that depth to position 0 of the movelist and then move the best-move of the sibling to position 1. After that I sort the rest of the moves (offset 2 and further) according to the "(victim_value << 16) | (10000 - attacker_value)"-value.

Sofar these changes have not give a better result.

Regarding the hash-table: I don't have a tt for zwSearch. I probably can't use the regular one for it? Or a seperate of the same sort? Or should I create one that has only entry-type "exact"? Because my tt implementation for other searches also has a lower- and upper-bound flag.

Apart from those considerations, is this code correct?

Code: Select all

if (score > bestVal) 
        {        
                bestVal = score; // bestVal is the value which is returned at the end of the function 
                mBestMove = cm; 

                newPv.assign(tempPv, false); // keep track of pv 
                mCurPrevBest = tempPv.back(); // use this move, so this is for the root 

                if (score >= beta) 
                {        
                        bestVal = beta; 
                        betaCutOff = true; 
                        break;  
                }        

                if (score > alpha) 
                {        
                        alpha = score; 
                        bSearchPv = false; 
                }        
        }

Same hash table for ALL searches...

[Joost Buijs]

if you want to get rid of auxiliary bSearchPv

Yes, I replaced that by the iterator.

It is unnecessary when the score returned from the zw-search >= beta to research with the pv-search.

Ok, applied.

It is better to replace "bSearchPv" with "movenumber == 1" just in case that you are using aspiration windows. Also, simple A-B works better then PVS if move ordering is poor. Are you sure that your hash table is working correctly?

Well, what I do is: move the move from the pv-list for that depth to position 0 of the movelist and then move the best-move of the sibling to position 1. After that I sort the rest of the moves (offset 2 and further) according to the "(victim_value << 16) | (10000 - attacker_value)"-value.

Sofar these changes have not give a better result.

Regarding the hash-table: I don't have a tt for zwSearch. I probably can't use the regular one for it? Or a seperate of the same sort? Or should I create one that has only entry-type "exact"? Because my tt implementation for other searches also has a lower- and upper-bound flag.

Apart from those considerations, is this code correct?

Code: Select all

if (score > bestVal) 
        {        
                bestVal = score; // bestVal is the value which is returned at the end of the function 
                mBestMove = cm; 

                newPv.assign(tempPv, false); // keep track of pv 
                mCurPrevBest = tempPv.back(); // use this move, so this is for the root 

                if (score >= beta) 
                {        
                        bestVal = beta; 
                        betaCutOff = true; 
                        break;  
                }        

                if (score > alpha) 
                {        
                        alpha = score; 
                        bSearchPv = false; 
                }        
        }

Yes, the code looks fine, but you can omit bestVal because it is the same as alpha, but maybe you have another use for it.

Code: Select all

if (score > alpha) 
{
    alpha = score;
    bSearchPv = false;

    if (alpha >= beta)
    {
        betaCutOff = true;
        break;  
    }
}

I use the main TT everywhere, PV, ZW and in quiescence.

[Sven]

Apart from those considerations, is this code correct?

Code: Select all

if (score > bestVal) 
        {        
                bestVal = score; // bestVal is the value which is returned at the end of the function 
                mBestMove = cm; 

                newPv.assign(tempPv, false); // keep track of pv 
                mCurPrevBest = tempPv.back(); // use this move, so this is for the root 

                if (score >= beta) 
                {        
                        bestVal = beta; 
                        betaCutOff = true; 
                        break;  
                }        

                if (score > alpha) 
                {        
                        alpha = score; 
                        bSearchPv = false; 
                }        
        }

If you are using fail-hard alpha-beta then, as others already stated, you do not need two variables alpha and bestVal, just alpha. For fail-soft you need both, though.

Usually the best move (and PV) is only set if the score is also > alpha.

[Sven]

Code: Select all

                mBestMove = cm; 

                newPv.assign(tempPv, false); // keep track of pv 
                mCurPrevBest = tempPv.back(); // use this move, so this is for the root

With this piece of code, how does the current move make it into the new PV? Neither cm nor mBestMove are mentioned in the assign() or back() calls ...

[flok]

Code: Select all

                mBestMove = cm; 

                newPv.assign(tempPv, false); // keep track of pv 
                mCurPrevBest = tempPv.back(); // use this move, so this is for the root

With this piece of code, how does the current move make it into the new PV? Neither cm nor mBestMove are mentioned in the assign() or back() calls ...

At the bottom of that search(), just before the return-statement, there's a pv.push_back(mBestMove);
(they're in reverse order to prevent large memmoves)