Winboard Forum

Hi,

I'm having some trouble inside my alpha-beta algorithm when i try to save the PV move list. Right now i'm only saving the best move at ply 1 It would be great if anyone could tell me a simple method to save the whole list. Thanks.

http://www.seanet.com/~brucemo/topics/pv.htm
/Peter

Peter Fendrich wrote:http://www.seanet.com/~brucemo/topics/pv.htm
/Peter

I tried hash method of extracting the PV and it works well .

Thanks all! I've used the non-hash method and it works...
i haven't implemented the TT yet so i'll try the other method later
and thanks for taking me to that wonderful website

Wing Lee wrote:Hi,

I'm having some trouble inside my alpha-beta algorithm when i try to save the PV move list. Right now i'm only saving the best move at ply 1 It would be great if anyone could tell me a simple method to save the whole list. Thanks.

Hi Wing Lee,

Code: Select all

int QuickPVS_AB(int side,int alfa,int beta,int depthleft,int realply,int *mainline) {
   int *curmainend;
   ...

  curmainend    = mainline+2;
  *mainline     = -1;
  *(mainline+1) = -1;


  for all moves ...
    int t;
     t = -QuickPVS ...
      if( t > alfa ) {
        int *pml,*cml;
        *mainline = nzet->zet;
        if( nextdepth > 0 ) {
          pml = mainline+1;
          if( pml != curmainend ) {         
            cml = curmainend;
            while( *cml != -1 ) {
              *pml = *cml;
              pml++;
              cml++;
            } 
            *pml = -1;       
            curmainend = pml+2;
          }             
        }
        else
          *(mainline+1) = -1;
        alfa = t;
      }


}

....

  void QuickPrintMainline(int *mainline) {
  char prom2piece[8]={" PNBRQK"};
  int prom,zet,f,t,i=0; // prints maximum a line of 32 ply
  printf("==>");
  while( i < 32 ) {
    zet = mainline[i];
    if( zet == -1 )
      break;
   
    zet &= 0x00007fff;
    t    = zet&63;
    f    = (zet>>6)&63;
    prom = (zet>>12);

    printf(" %s%s",M2A[f],M2A[t]);
    if( prom )
      printf("%c",prom2piece[prom]);
    i++;
  } 
  printf("\n");
  fflush(stdout);
}

Please note it ignores quiescencesearch here. If nextdepth==0 then
it calls qsearch.

However it is no problem to add this to your quiescencesearch too.

The cost is nearly nothing.

Yet this is a beancounter running at like what is it 2.2 million nps or so (including checks in qsearch and hashtables etc) at a k7 2.1ghz,
so i did some concessions to keep the qsearch cheapo cheapo.

Best regards,
Vincent

Pradu wrote:

Peter Fendrich wrote:http://www.seanet.com/~brucemo/topics/pv.htm
/Peter

I tried hash method of extracting the PV and it works well .

Hash is what i use in Diep too.

However there is 2 approaches basically.

First approach is what i do in Diep which is pretty tricky that's
a combination of hashtable and storing 3 type of bounds.

In a quick search approach i keep it simpler by just using 1 bit for
a bound and something is either >= beta or a score is <= alfa.

No other choices

In such case you can always generate a mainline using a simple array
and what i posted.

Hi,

for the method using the hashtable to collect the PV, isn't it possible that one or more of the PV nodes gets replaced by another one further in the search? in this case, we can't retrieve it...

would a possible solution be to include some kind of indicator in the hash entry that would mean "do not delete" ?

Thanks

Wing Lee wrote:Hi,

for the method using the hashtable to collect the PV, isn't it possible that one or more of the PV nodes gets replaced by another one further in the search? in this case, we can't retrieve it...

would a possible solution be to include some kind of indicator in the hash entry that would mean "do not delete" ?

Thanks

If you use the overwrite system as i described, odds are, as shown,
less than 1 in a million that you will lose more than a few ply from the
mainline.

Diep's overwrite strategy in hashtable:

- 16 bytes per entry
- 4 probes
- storing_mask = depth+searches_performed_in_game
- always overwrite the entry with lowest storing_mask
- diep is also storing in qsearch (it can do because of low nps speed)

Calculating hashtable index (each processor has its own shared hashtable):

procnr = ((((unsigned int)(hashpos.lo&0x000000000000ffff))*nprocesses)>>16);
hindex = (unsigned int)((((hashpos.lo>>16)&0x00000000ffffffff)*abmod)>>32);
hentry = &(globaltrans[procnr][hindex]);

here is code. note you might be able to get rid of some branches if
speed is a big concern in your engine:
// quadword1 = 51:key 5:flags 8:age
// quadword2 = 20:score 20:eval 2:bound 7:diepte 15:zet
//
// flags : 'vrij', matethreat, pvsingmove, egtbscore, STM

sflag = (unsigned int) side;
age = (ulzetnr+diepte2hash[ply]);
if( AllFlag&pvs_egtbentry ) {
sflag |= 2;
age += 14;
}
if( AllFlag&pvs_singularmove )
sflag |= 4;
if( AllFlag&pvs_matethreat )
sflag |= 8;
age &= 255;
s1 = ((hashpos.hi&0xffffffffffffe000)|((BITBOARD)(sflag<<8))|((BITBOARD)age));
bound = 0; // <= alfa bound
if( AllFlag&pvs_hashbound ) // score >= beta
bound |= 1; // >= beta bound
else if( AllFlag&pvs_truebound )
bound |= 2; // == true bound

if( bestscore >= -MATEVALUE+1000
&& bestscore <= MATEVALUE-1000 ) {
w2a = ((unsigned int)(bestscore+0x00080000));
}
else {
w2a = ((unsigned int)(bestscore+0x00080000+realply));
if( bestscore < 0 )
w2a -= ((unsigned int)(realply+realply));
}

s2 = (
(((BITBOARD)w2a)<<44) // !!!!! not all compilers do this correct
// as it is outside ansi-c
| (((BITBOARD)(eval+0x00080000))<<24)
| (((BITBOARD)bound)<<22)
| (((BITBOARD)ply)<<15)
| ((BITBOARD)(pvmove&0x00007fff))
);

s1 ^= s2;

hentry->key = s1;
hentry->half = s2;
#if Statistics
if( ply > 31 )
ss.stat_transstore++;
else
ss.stat_qtransstore++;
#endif

diepeveen wrote: - storing_mask = depth+searches_performed_in_game
- always overwrite the entry with lowest storing_mask

Excellent idea, Diep! It should also work well when the user uses the engine for analyzing a game (with takebacks and such).

diepeveen wrote: - 16 bytes per entry

Yes, I finally agree that storing the whole 64 bit key is correct.

diepeveen wrote: - 4 probes

Why 4 probes? Isn't this effectively the same as spiltting your hash table into 4 (thereby reducing its effective size by 4).

I see
Thanks alot diepeveen

odds are, as shown,
less than 1 in a million that you will lose more than a few ply from the
mainline.

I like the odds

diepeveen wrote:Diep's overwrite strategy in hashtable:

- 16 bytes per entry
- 4 probes
- storing_mask = depth+searches_performed_in_game
- always overwrite the entry with lowest storing_mask
- diep is also storing in qsearch (it can do because of low nps speed)

What is searches_performed_in_game?
Is it moves searched from root?
Doesn't that take more space than a simple generation counter?
/Peter[/quote]

Peter Fendrich wrote:What is searches_performed_in_game?

It is the number of times search is called. In a straight forward game (no takebacks and such) it is the number of times your engine was on move. If pondering is on, it is the number of half moves in the game.

Peter Fendrich wrote:Doesn't that take more space than a simple generation counter?

Not quite following...

Pradu wrote:

Peter Fendrich wrote:What is searches_performed_in_game?

It is the number of times search is called. In a straight forward game (no takebacks and such) it is the number of times your engine was on move. If pondering is on, it is the number of half moves in the game.

Ok, I separate my Search from the Root. Root calls Search many times for each game-move!

Pradu wrote:

Peter Fendrich wrote:Doesn't that take more space than a simple generation counter?

Not quite following...

Explained by the above?
Still I think that storing remaining_depth and a Generation_Counter needs less compared to a mask composed by remaining_depth and Search_Counter. Search_Counter can be quite high. My Generation_Counter is between 0-7.
/Peter

Peter Fendrich wrote:Ok, I separate my Search from the Root. Root calls Search many times for each game-move!

Then searches_performed_in_game is the number of times you are at the Root doing a search.

Peter Fendrich wrote:Still I think that storing remaining_depth and a Generation_Counter needs less compared to a mask composed by remaining_depth and Search_Counter. Search_Counter can be quite high. My Generation_Counter is between 0-7.
/Peter

By the way Peter, what is a Generation_Counter? The number of move generations? Sorry if I'm not an experienced enough programmer to understand programmign jargon (I also don't know what a Bean Counter is).

And on the topic of space:

Diep managed to do it in 16 bytes ... so it shouldn't be too bad (he stores the full 64-bit hash key by the way).

I don't know how Diep does it but here's an idea:

How about some kind of hash structure like this:

Code: Select all

8 bytes for hash key:

22 bits for the best move:
Here's how I do it in my program:
/*********************Format of a Move*************************
A move is stored in 23 bits:
Bits   (6)   0-5      are for the "to square".
Bits   (3)   6-8      are for the "capture piece".
Bits   (3)   9-11      are for the "moving piece".
Bits   (6)   12-17      are for the "from square".
Bits   (3)   18-20      are for the "promoting piece".
Bit   (1)   21      is for identifying "enpassant" or "castling"
Bit   (1)   22      is for identifying "kingside" or "queenside"
*************************************************************/


4 bytes for the hashed score.  (Note it can be done with 2 bytes if you are using 2 bytes for the score)

2 bits for the hash value flags (alpha=1, beta=2, exact=0)

This leaves you a byte for the repalement qualifier.


That means 256 qualifers .

Note: 2 extra bytes could be used for the qualifier if your score takes 2 bytes.

Now it becomes a concern about what to do when more than 256 searches occur.

Here's a (at the top of my mind) solution:

Code: Select all

//Do this somewhere in your code before starting a search:
      .
      .
      .
   board.qualifier++;
   if(board.qualifier&0xFF)
   {
      adjustHashTableQualifiers();
      board.qualifier=2;
   }
      .
      .
      .

void adjustHashTableQualifier()
{
   /*code that sets your Hash table qualifiers in the following manner
    *1)set all qualifiers which are board.qualfier-1 to 1
    *2)set the rest of the Hash table qualifiers to 0
    */
}

Of course this is a linear replacement algorithm but I seem to be able to initalize a hash table (with over a million entries) very quickly in the lousy Alpha 17 version of Witz. But this qualifer replacement scheme has some problems.

Now lets say your in an important endgame with a huge number of Hash Table hits but your engine has the misfortune to approach this 256 qualifier limit during this time. Will all those hard earned hash table be replace over in the following search?

Fortunately, I have another solution (off the top of my head again) for this problem.

Everytime you have a Hash Table hit set that Hash Table's replacement qualifer to board.qualifer.

All this is off the top of my head at the moment ... what I have written may not be best but at the moment it seems reasonable. Also note that the 256 hash table limit (0-255=256 qualifiers so I call it the 256 limit instead of the 255 limit) can become the 16,777,216 limit if your score takes 2 bytes.

EDIT:
Ok I had a rethink ... the above isn't correct.

Correction: seperate depth and searches_in_game so that the qualifier replacement scheme will work.

Pradu wrote:By the way Peter, what is a Generation_Counter? The number of move generations? Sorry if I'm not an experienced enough programmer to understand programmign jargon (I also don't know what a Bean Counter is).

Well, the generation counter I think is widely used. I have 8 generations (0-7) incremented each time it's 'my' turn. I only trust probes finding the same generation otherwise I only use the move.
Bean counter: I think it's one who is more concerned about coding techniques, bitboard tweaks etc compared to chess related knowledge.

[code]8 bytes for hash key:

22 bits for the best move:
Here's how I do it in my program:
/*********************Format of a Move*************************
A move is stored in 23 bits:
Bits (6) 0-5 are for the "to square".
Bits (3) 6-8 are for the "capture piece".
Bits (3) 9-11 are for the "moving piece".
Bits (6) 12-17 are for the "from square".
Bits (3) 18-20 are for the "promoting piece".
Bit (1) 21 is for identifying "enpassant" or "castling"
Bit (1) 22 is for identifying "kingside" or "queenside"
*************************************************************/

I only store from, to and promotion for the move.
Didn't you forget the depth | move_counter we talked about?
/Peter

Peter Fendrich wrote: I only store from, to and promotion for the move.

That means even more space for the qualifiers!

I have to store more information because I use bitboards.

Peter Fendrich wrote:Didn't you forget the depth | move_counter we talked about?
/Peter

Yes I did forget the depth, I made an edit to the post stating that. Hopefully I'm not misunderstand your post again... .

Hi,

just as an aside with the TT stuff (didn't feel the need to start a new topic)

its possible that the pieces are in the same place but castling and en-passant rights might be different in a position, so do we need to XOR hash keys for en-passant and castling rights when we update the position's hash key? (i'm using zobrist keys)

but if i wanted to detect repetitions with hash keys as well, i would need to keep a separate key for the position without the enpassant, castling and side to move, right?

Thanks

Wing Lee wrote:but if i wanted to detect repetitions with hash keys as well, i would need to keep a separate key for the position without the enpassant, castling and side to move, right?

Thanks

No. Here's a link for any other rule related questions:
http://www.fide.com/official/handbook.asp?level=EE101

Section 9.2 wrote:Positions as in (a) and (b) are considered the same, if the same player has the move, pieces of the same kind and colour occupy the same squares, and the possible moves of all the pieces of both players are the same.
Positions are not the same if a pawn that could have been captured en passant can no longer in this manner be captured or if the right to castle has been changed temporarily or permanently.

Either you can check if the pawn is capturable and update the hash entry accordingly or you can treat it as you are doing now.

Another possibility would be to not update the EP square if the pawn is not capturable (this seems to be the best method that I could devise).