PVS

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.
Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

PVS

Post by Edmund » Thu Mar 12, 2009 10:06 am

Concerning the implementation of PVS in the chessprogramming wiki I read:

Code: Select all

   for ( all moves)  {
      make
      if ( bSearchPv ) {
         score = -pvSearch(-beta, -alpha, depth - 1);
      } else {
         score = -pvSearch(-alpha-1, -alpha, depth - 1);
         if ( score > alpha ) // in fail-soft ... && score < beta ) is common
            score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;; // re-search
      &#125;
      unmake
      if&#40; score >= beta )
         return beta;   // fail-hard beta cutoff
      if&#40; score > alpha ) &#123;
         alpha = score; // alpha acts like max in MiniMax
         bSearchPv = false;
      &#125;
   &#125;
So this in fact searches full-window (in pv nodes) as long as alpha is not raised. Now I just encountered a position with a fail low at root level and found out that this algorithm just presented was the reason that it took the engine extremely long to reach the desired result.

Another implementation I tried was to just do the full-window search at the first move. This solved the problem. So my question now .. is there any overall advantage in the implementation as shown in the CPW? Or is it wise to use different algorithms for root-level and internal pv nodes?

Pradu
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: PVS

Post by Pradu » Thu Mar 12, 2009 11:23 am

Another implementation I tried was to just do the full-window search at the first move.
Is this the same thing as not using aspiration at all?

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: PVS

Post by Edmund » Thu Mar 12, 2009 11:30 am

Pradu wrote:
Another implementation I tried was to just do the full-window search at the first move.
Is this the same thing as not using aspiration at all?
Sorry, I didn't mean full window, but the aspiration window from the previous search.

The main difference at the root would be that in case of a fail low the CPW algorithm would search all moves with this aspiration window and start a full width re-search afterwards, while my second option would just search the first move with the aspiration window and the rest with null windows and do a full window research at the re-search.

Gian-Carlo Pascutto
Posts: 1138
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: PVS

Post by Gian-Carlo Pascutto » Thu Mar 12, 2009 1:30 pm

Codeman wrote: So this in fact searches full-window (in pv nodes) as long as alpha is not raised.
The code you posted is simply wrong, for the reason you stated.
// in fail-soft ... && score < beta ) is common
This also looks wrong to me. Why would you search if score >= beta? Just cut, doesn't matter if we're fail hard or fail soft!

Gian-Carlo Pascutto
Posts: 1138
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: PVS

Post by Gian-Carlo Pascutto » Thu Mar 12, 2009 1:51 pm

Fixed:

Code: Select all

   for ( all moves&#41;  &#123;
      make
      if ( bSearchPv ) &#123;
         score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;;
      &#125; else &#123;
         score = -pvSearch&#40;-alpha-1, -alpha, depth - 1&#41;;
         if ( score > alpha && score < beta ) 
            score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;; // re-search
      &#125;
      unmake
      if&#40; score >= beta )
         return score;  
      if&#40; score > alpha )
         alpha = score; // alpha acts like max in MiniMax      
      bSearchPv = false;
   &#125; 

bob
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: PVS

Post by bob » Thu Mar 12, 2009 2:12 pm

Codeman wrote:Concerning the implementation of PVS in the chessprogramming wiki I read:

Code: Select all

   for ( all moves&#41;  &#123;
      make
      if ( bSearchPv ) &#123;
         score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;;
      &#125; else &#123;
         score = -pvSearch&#40;-alpha-1, -alpha, depth - 1&#41;;
         if ( score > alpha ) // in fail-soft ... && score < beta ) is common
            score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;; // re-search
      &#125;
      unmake
      if&#40; score >= beta )
         return beta;   // fail-hard beta cutoff
      if&#40; score > alpha ) &#123;
         alpha = score; // alpha acts like max in MiniMax
         bSearchPv = false;
      &#125;
   &#125;
So this in fact searches full-window (in pv nodes) as long as alpha is not raised. Now I just encountered a position with a fail low at root level and found out that this algorithm just presented was the reason that it took the engine extremely long to reach the desired result.

Another implementation I tried was to just do the full-window search at the first move. This solved the problem. So my question now .. is there any overall advantage in the implementation as shown in the CPW? Or is it wise to use different algorithms for root-level and internal pv nodes?
You aren't interpreting the code correctly. Let's suppose when we enter, alpha=0, beta=100. We search the first move with alpha=0 and beta=100. If we don't fail high on that single move search, we then search with a null-window for the next move (temp_alpha=-beta-1, temp_beta=-current alpha). If, on any of those searches, we get a result that is > original alpha, and < original beta, we need to do a re-search. The reason for this test is that it is possible that we enter Search() with a null-window to start with, which would make the research impossible since the original alpha = X and the original beta = X+1. If that happens, the re-search can.'t happen (it would be pointless. The variable bSearchPV is only true for the _first_ move searched at any node. 99.999% of the time, beta = alpha+1 anyway, and a re-search would be futile.

bob
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: PVS

Post by bob » Thu Mar 12, 2009 2:14 pm

Gian-Carlo Pascutto wrote:
Codeman wrote: So this in fact searches full-window (in pv nodes) as long as alpha is not raised.
The code you posted is simply wrong, for the reason you stated.
// in fail-soft ... && score < beta ) is common
This also looks wrong to me. Why would you search if score >= beta? Just cut, doesn't matter if we're fail hard or fail soft!
It is correct, it just reads funny. See my explanation in the other post in this thread. The if (val > alpha && val < beta) is simply a trick to avoid the research if this call to Search (from previous ply) started out with a null-window..
.
When I looked again, I realized that the bSearchPV is in the wrong place. You are right. It needs to be moved outside the if-test for value > alpha...

Gerd Isenberg
Posts: 2125
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: PVS

Post by Gerd Isenberg » Thu Mar 12, 2009 4:19 pm

Gian-Carlo Pascutto wrote:Fixed:

Code: Select all

   for ( all moves&#41;  &#123;
      make
      if ( bSearchPv ) &#123;
         score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;;
      &#125; else &#123;
         score = -pvSearch&#40;-alpha-1, -alpha, depth - 1&#41;;
         if ( score > alpha && score < beta ) 
            score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;; // re-search
      &#125;
      unmake
      if&#40; score >= beta )
         return score;  
      if&#40; score > alpha )
         alpha = score; // alpha acts like max in MiniMax      
      bSearchPv = false;
   &#125; 
I thought this was the difference between PVS and NegaScout ;-)
PVS waits until a move is found that improves alpha, and then searches every move after that with a zero window around alpha. NegaScout just searches the first move, and then searches every move after that with the same zero window.
The PseudoCode mentioned is almost identical with Bruce Moreland's PVS code.
If no PV move has been found, "AlphaBeta()" is recursed normally. If one has been found, everything changes. Rather than searching with a normal (alpha, beta) window, we search with (alpha, alpha + 1). The premise is that all of the searches are going to come back with a score less than or equal to alpha, and if this is going to happen, the elimination of the top end of the window results in more cutoffs. Of course, if the premise is wrong, the score comes back at alpha + 1 or higher, and the search must be re-done with the wider window.

Code: Select all

int AlphaBeta&#40;int depth, int alpha, int beta&#41;
&#123;
    BOOL fFoundPv = FALSE;

    if &#40;depth == 0&#41;
        return Evaluate&#40;);

    GenerateLegalMoves&#40;);
    while &#40;MovesLeft&#40;)) &#123;
        MakeNextMove&#40;);
        if &#40;fFoundPv&#41; &#123;
            val = -AlphaBeta&#40;depth - 1, -alpha - 1, -alpha&#41;;
            if (&#40;val > alpha&#41; && &#40;val < beta&#41;) // Check for failure.
                val = -AlphaBeta&#40;depth - 1, -beta, -alpha&#41;;
        &#125; else
            val = -AlphaBeta&#40;depth - 1, -beta, -alpha&#41;;
        UnmakeMove&#40;);
        if &#40;val >= beta&#41;
            return beta;
        if &#40;val > alpha&#41; &#123;
            alpha = val;
            fFoundPv = TRUE;
        &#125;
    &#125;
    return alpha;
&#125;
see also
http://www.talkchess.com/forum/viewtopic.php?t=24883

Gerd

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: PVS

Post by diep » Thu Mar 12, 2009 4:34 pm

Pradu wrote:
Another implementation I tried was to just do the full-window search at the first move.
Is this the same thing as not using aspiration at all?
Diep is using PVS without aspiration window.

You get straight from hashtable a great bound anyway.

My 10x10 international checkers (polish draughts) program did use aspiration window. It works for it.

Vincent

Gian-Carlo Pascutto
Posts: 1138
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: PVS

Post by Gian-Carlo Pascutto » Thu Mar 12, 2009 4:45 pm

Gerd Isenberg wrote: I thought this was the difference between PVS and NegaScout ;-)
PVS waits until a move is found that improves alpha, and then searches every move after that with a zero window around alpha. NegaScout just searches the first move, and then searches every move after that with the same zero window.
The PseudoCode mentioned is almost identical with Bruce Moreland's PVS code.
I believe Bruce's page is just wrong.

I found a paper from 1983 from T.A. Marsland, "Relative Efficiency of Alpha-Beta implementations", which should predate NegaScout.

It has the correct algorithm, i.e. zero window on all but the first move.

Post Reply