en passant and hash key calculation

[Desperado]

It seems our misunderstanding was only caused by my assumption that you were looking at positions *after* a knight move like 4.Nb1, while you now seem to look at positions *prior* to such a move. If you reread your postings then you may get the same impression like I that it did really look like that ...

I think we can agree upon the fact that in a position *after* a knight move the ep target square is never set, so there is no point in thinking about repetitions of such a position.

Maybe you were thinking of the point in a game where a draw by repetition would actually be *claimed*, but that is clearly a separate issue since the first goal would be to correctly *detect* the repetition itself. (In fact you still would not claim the draw *after* making the next move, so there is still no point in seeing any draw *after* a knight move!)

Furthermore, I can agree on most everything else you have written now.

Sven

i think i am out of the jungle.

based on the assumption 4a+4b, it is clear now
why only putting the ept into the key by dblPwnPush, we will miss
some repetitions.

The only dblPwnPush strategy would detect the position 2 plies too late, but still keeps the rules and is a valid approach.
The other way around we may get a repetition 2 plies too early,but
that doesnt matter anyway, because most of us hack the repetition
detection with a repetitionCounter==1 condition already.

So, for functionality it doesnt play a role which approach someone uses.
From the view of effectiveness the 4a plus 4b approach should be considered.

@HGM : your refreshing ideas are always welcome.
@Sven: thx for your patience

Thx, Michael

[Sven]

So, to be absolutely correct for both probing and repetition detection the e.p. zorbrist should only be added in if there is a legal c.e.p. and it should be removed immediately after the next move. ?

Yes. You can view it that way, focussing directly on the hash key, or you can handle it indirectly by only setting the internal ep target square of the position if there is a legal ep capture, and then mapping that ep target to the appropriate strategy of updating the hash key.

For the latter, I know at least two possible and simple ways to map old + new ep target to a hash key update. One has been mentioned in a code example of Michael Hoffmann within this thread and looked like this in principle:

Code: Select all

hashKey ^= zobristEp[prevPos.epTarget];
hashKey ^= zobristEp[currPos.epTarget];

which involves having also a zobrist key for "no ep target square set". It is branchless and looks quite elegant.

The other, also straightforward way is slightly longer and was mentioned in one of my examples (pseudo code). A separate key for "not set" is not needed:

Code: Select all

if (prevPos.epTarget != currPos.epTarget) {
    if (prevPos.epTarget != "not set") {
        hashKey ^= zobristEp[prevPos.epTarget];
    }
    if (currPos.epTarget != "not set") {
        hashKey ^= zobristEp[currPos.epTarget];
    }
}

Both ways require the currPos.epTarget to be updated already. There will be even many more approaches to achieve the same.

Sven

[Michael Sherwin]

So, to be absolutely correct for both probing and repetition detection the e.p. zorbrist should only be added in if there is a legal c.e.p. and it should be removed immediately after the next move. ?

Yes. You can view it that way, focussing directly on the hash key, or you can handle it indirectly by only setting the internal ep target square of the position if there is a legal ep capture, and then mapping that ep target to the appropriate strategy of updating the hash key.

For the latter, I know at least two possible and simple ways to map old + new ep target to a hash key update. One has been mentioned in a code example of Michael Hoffmann within this thread and looked like this in principle:

Code: Select all

hashKey ^= zobristEp[prevPos.epTarget];
hashKey ^= zobristEp[currPos.epTarget];

which involves having also a zobrist key for "no ep target square set". It is branchless and looks quite elegant.

The other, also straightforward way is slightly longer and was mentioned in one of my examples (pseudo code). A separate key for "not set" is not needed:

Code: Select all

if (prevPos.epTarget != currPos.epTarget) {
    if (prevPos.epTarget != "not set") {
        hashKey ^= zobristEp[prevPos.epTarget];
    }
    if (currPos.epTarget != "not set") {
        hashKey ^= zobristEp[currPos.epTarget];
    }
}

Both ways require the currPos.epTarget to be updated already. There will be even many more approaches to achieve the same.

Sven

I realize now that the e.p. zorbrist needs to be part of the hash key for probing the hash tables only on the next ply and not be part of any future hash keys. I use a small hash table for repetitions.

Just one question then.

How does your method remove the e.p. zorbrist after the next probe.

a) 1. e4 e6 2. e5 d5 3. Nf3 Ne7

Should map to the same slot in the hash as

b) 1. e4 e6 2. Nf3 d5 3. e5 Ne7

But, if the key is still part of a) and not part of b) then it will not map to the same slot.

Can you show me how it will work in the above two lines?

[Desperado]

Code: Select all

 A:
===

 1. e4  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 2. e6  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 3. e5  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 4. d5  key^=zbrEpt[noEpt]^zbrEpt[ d6  ] -> key xored  in
 5. Nf3 key^=zbrEpt[ d6  ]^zbrEpt[noEpt] -> key xored out (removed)
 6. Ne7 key^=zbrEpt[noEpt]^zbrEpt[noEpt] 

 B:
====

 //condition to set ept: 
 //double pawn push + adjacent pawn

 1. e4  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 2. e6  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 3. Nf3 key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 4. d5  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 5. e5  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 6. Ne7 key^=zbrEpt[noEpt]^zbrEpt[noEpt]  

 //condition to set ept: 
 //only double pawn push approach
 
 1. e4  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 2. e6  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 3. Nf3 key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 4. d5  key^=zbrEpt[noEpt]^zbrEpt[ d6  ] -> key xored in
 5. e5  key^=zbrEpt[ d6  ]^zbrEpt[noEpt] -> key xored out (removed)
 6. Ne7 key^=zbrEpt[noEpt]^zbrEpt[noEpt]  

did you mean this ?

or "removing" when undoing a move ?
when undoing a move, i do not compute the key again.
i simply copy the backup value back into the board.

brd->key = undo->key;

hope it helps

Michael

[Sven]

Code: Select all

if (prevPos.epTarget != currPos.epTarget) {
    if (prevPos.epTarget != "not set") {
        hashKey ^= zobristEp[prevPos.epTarget];
    }
    if (currPos.epTarget != "not set") {
        hashKey ^= zobristEp[currPos.epTarget];
    }
}

Just one question then.

How does your method remove the e.p. zorbrist after the next probe.

a) 1. e4 e6 2. e5 d5 3. Nf3 Ne7

Should map to the same slot in the hash as

b) 1. e4 e6 2. Nf3 d5 3. e5 Ne7

But, if the key is still part of a) and not part of b) then it will not map to the same slot.

Can you show me how it will work in the above two lines?

Here you are. The key points are the effects of 2... d5 (add ept) and 3. Nf3 (remove ept) in line a). Line b) is completely neutral w.r.t. ep target square setting. With "ept" in the following I mean the internal ep target square of the position.


a)
Initial position: no ept set
=> no ept in hash key

after 1.e4: still no ept set
=> new ept == old opt
=> no change, so still no ept in hash key

after 1... e6: the same

after 2.e5: the same

after 2... d5: ept set to d6
=> new ept != old ept, so check influence of both
=> old ept "not set" has no influence
=> new ept == d6 so zobrist key for d6 XORed into hash key
=> ept "d6" now in hash key

after 3.Nf3: ept now "not set" again (no pawn move)
=> new opt != old ept, so check influence of both
=> old ept == d6 so zobrist key for d6 XORed into hash key (removed)
=> new ept "not set" has no influence
=> no ept in hash key (d6 was removed)

after 3... Ne7: ept still "not set"
=> still no ept in hash key


b)
Initial position: no ept set
=> no ept in hash key

after 1.e4: still no ept set
=> new ept == old opt
=> no change, so still no ept in hash key

after 1... e6: the same

after 2.Nf3: the same

after 2... d5: the same (no ep capture exists, not even an adjacent pawn)

after 3.e5: the same

after 3... Ne7: the same
=> no ept in hash key (never added and never removed)


Sven

[Sven]

Code: Select all

 A:
===

 1. e4  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 2. e6  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 3. e5  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 4. d5  key^=zbrEpt[noEpt]^zbrEpt[ d6  ] -> key xored  in
 5. Nf3 key^=zbrEpt[ d6  ]^zbrEpt[noEpt] -> key xored out (removed)
 6. Ne7 key^=zbrEpt[noEpt]^zbrEpt[noEpt] 

 B:
====

 //condition to set ept: 
 //double pawn push + adjacent pawn

 1. e4  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 2. e6  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 3. Nf3 key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 4. d5  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 5. e5  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 6. Ne7 key^=zbrEpt[noEpt]^zbrEpt[noEpt]  

 //condition to set ept: 
 //only double pawn push approach
 
 1. e4  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 2. e6  key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 3. Nf3 key^=zbrEpt[noEpt]^zbrEpt[noEpt]
 4. d5  key^=zbrEpt[noEpt]^zbrEpt[ d6  ] -> key xored in
 5. e5  key^=zbrEpt[ d6  ]^zbrEpt[noEpt] -> key xored out (removed)
 6. Ne7 key^=zbrEpt[noEpt]^zbrEpt[noEpt]  

did you mean this ?

or "removing" when undoing a move ?
when undoing a move, i do not compute the key again.
i simply copy the backup value back into the board.

brd->key = undo->key;

hope it helps

Michael

I think he did not mean "undo".

Your branchless approach obviously gives the same result as "my method" (in fact I did not invent it, it is common practice I think) but yours is easier to read and probably faster.

Thinking of zbrEpt[noEpt] as having the value 0 makes this even a little bit clearer. In this case you need one random key less but it is still necessary to be able to have an array of "ep" zobrist key values that do also cover the "undefined square" (noEpt), which is more or less difficult depending on what the value of "noEpt" is (it may be something like -1 or 0xffff and therefore a bad array index). But this turns out to be a minor implementation detail.

Sven

[Desperado]

I think he did not mean "undo".

Your branchless approach obviously gives the same result as "my method" (in fact I did not invent it, it is common practice I think) but yours is easier to read and probably faster.

Thinking of zbrEpt[noEpt] as having the value 0 makes this even a little bit clearer. In this case you need one random key less but it is still necessary to be able to have an array of "ep" zobrist key values that do also cover the "undefined square" (noEpt), which is more or less difficult depending on what the value of "noEpt" is (it may be something like -1 or 0xffff and therefore a bad array index). But this turns out to be a minor implementation detail.

Sven

using bitboards, 0 is often the a1-square, which may lead to the
following bug. for white not a problem, but black must take
care.

Code: Select all

//--------genCaptureWP------------------
//--------------------------------------

static void genCaptureWP(BOARD_T *brd,MLI_T *mli)
	{
	 MVE_T mve;
	 S64_T dst;
	 BTB_T cp9 = (brd->pli[wpEnum].compact&~bHF) << 9;
	 BTB_T cp7 = (brd->pli[wpEnum].compact&~bAF) << 7;
	 
     //if noEpt == 0

	 if(singleBit(brd->ept) & cp9){makeMove(/*params*/);}
	 if(singleBit(brd->ept) & cp7){makeMove(/*params*/);}
	
	 cp9 &= brd->occ[black];
	 while(cp9)
		{
		 dst = bsf64(cp9);
		 makeMove(/*params*/);
		 clrLsb(cp9);
		}

	 cp7 &= brd->occ[black];
	 while(cp7)
		{
		 dst = bsf64(cp7);
		 makeMove(/*params*/);
		 clrLsb(cp7);
		}

	 return;
	}

//--------genCaptureBP------------------
//--------------------------------------

static void genCaptureBP(BOARD_T *brd,MLI_T *mli)
	{
	 MVE_T mve;
	 S64_T dst;
	 BTB_T cp9 = (brd->pli[wpEnum].compact&~bHF) << 9;
	 BTB_T cp7 = (brd->pli[wpEnum].compact&~bAF) << 7;
	 
	 //enPassent (bitboard users must take care for noEpt==0)
	 //because a1==0 and may lead to captures from b2 to a1 :-))
    //of course here are different options available
   //so we need a further condition.(or just & with rank3 additionally...)


	 if(brd->ept!=noEpt)
		{
		 if(singleBit(brd->ept) & cp9){makeMove(/*params*/);}
		 if(singleBit(brd->ept) & cp7){makeMove(/*params*/);}
		}

	...

	 return;
	}

like you said, just an implementation detail, not more not less.

Michael

[Sven]

I think he did not mean "undo".

Your branchless approach obviously gives the same result as "my method" (in fact I did not invent it, it is common practice I think) but yours is easier to read and probably faster.

Thinking of zbrEpt[noEpt] as having the value 0 makes this even a little bit clearer. In this case you need one random key less but it is still necessary to be able to have an array of "ep" zobrist key values that do also cover the "undefined square" (noEpt), which is more or less difficult depending on what the value of "noEpt" is (it may be something like -1 or 0xffff and therefore a bad array index). But this turns out to be a minor implementation detail.

using bitboards, 0 is often the a1-square, which may lead to the
following bug. for white not a problem, but black must take
care.

I did not mean to use 0 for "ept not set" but for the zobrist key of "ept not set", which would mean that XORing it into the hash key has zero effect (no bits are inverted). It is clear that using 0 as "square not set" can often be a problem.

Sven

[Desperado]

I did not mean to use 0 for "ept not set" but for the zobrist key of "ept not set", which would mean that XORing it into the hash key has zero effect (no bits are inverted). It is clear that using 0 as "square not set" can often be a problem.

Sven

uhps, sorry.

of course

zbrEpt[noEpt] != 0

or the other way around

zbrEpt[noEpt] = rnd64()

[hgm]

I'm not sure about the overall influence of such a case, but is it necessary to even have to deal with such cases?

Confusing positions with and without e.p. rights in the hash table will cost you many, many games, in Pawn endings where the e.p. capturing Pawn walks straight to promotion.

I add the side to move and the e.p. rights only to a one-time key, which is used to probe the hash. The differentially updated key only depends on the board occupation, and the repetition detection is based on that.