en passant and hash key calculation

[Fguy64]

p.s. to Sven I haven't bothered to do three fold repetition in my engine, it's just not a priority. Maybe if I run out of ideas, or decide I want to be competetive, I'll take what you say into account.

You define your priorities. I can only say that a chess engine that does not implement repetition detection cannot be considered a chess engine, it is just boring. It will be unable to win a won position in most cases.

Also my posts - including the second one I just sent - were not only related to repetition detection but mostly to your original question which was about how to deal with ep target and hash key. So please reconsider what you should take into account and what not

Sven

sigh. OK dude whatever you say, you're the expert. frankly I don't give a damn.

[Sven]

p.s. to Sven I haven't bothered to do three fold repetition in my engine, it's just not a priority. Maybe if I run out of ideas, or decide I want to be competetive, I'll take what you say into account.

You define your priorities. I can only say that a chess engine that does not implement repetition detection cannot be considered a chess engine, it is just boring. It will be unable to win a won position in most cases.

Also my posts - including the second one I just sent - were not only related to repetition detection but mostly to your original question which was about how to deal with ep target and hash key. So please reconsider what you should take into account and what not

Sven

sigh. OK dude whatever you say, you're the expert. frankly I don't give a damn.

Sorry Fred, that was not meant as a personal attack, I apologize if you felt it was. "... cannot be considered a chess engine" was badly expressed and is definitely not appropriate. What I meant is that an engine that does not know repetitions will play really boring chess in many cases, which is a given fact. That's all. I can understand of course that you have different priorities.

I'm always trying to help you in making progress, sorry again if I missed that goal this time ...

Sven

[Desperado]

Here's a dumb question. One of the factors that goes into the determination of a position is the existence of an e.p target square. Does the e.p. target square exist only when an e.p. capture can be made?

This question arises become it has been suggested that I made a mistake with my hash key calculation. I have been including a hash key component when a pawn moves forward two squares, regardless of whether or not there is a capture possible. As I think about it, this seems wrong, in that I eliminate a significant number of possible hash key matches and slow down my search.

doing the update like you have done so far is an absolutely correct
way to handle this.
What you described as mistake is at most a missing optimization.
(if it is ?!,because of the side effects to handle).

IMO it is like the question of generating all underpromotions,
and further to reduce the tree this way.
So, is it a mistake to generate all promotions ?

so here is what i do (keeping it simple and stupid i think is
often the best way to optimize things). just a little code
extraction... i hope it can help.

Code: Select all

//--------moveDo------------------------
//--------------------------------------

void moveDo(BOARD_T *brd,
			   UNDO_T  *udo,
			   MVE_T	 mve)
	{
	 //...

	 //BACKUP
	 //--------------------------------------
	 
	 //...
	 udo->ept = brd->ept;
	 udo->key = brd-key;
	 //...

	 //BOARD SPECIFIC UPDATE
	 //--------------------------------------

	 //...
	 brd->ept = noEpt;
	 //...

	 //MOVE SPECIFIC UPDATE
	 //--------------------------------------

	 //...
	 else if(moveIsDbl(mve))
		{
		 if(isWhitePiece(pMoved)) {brd->ept = dst-8;}
		 else					      {brd->ept = dst+8;}
		}

	 //additional key update
	 //...
	 brd->key ^= zbrEpt[udo->ept];
	 brd->key ^= zbrEpt[brd->ept];
	 //...

    //having a list including the fen position
    //and the positions from its move section part
    //you can simply update the list with
    //pushing the new position to the list.
    //this list you may need for repetition
    //detection

     addGameHist(brd->key); 

	 return
	}

//--------moveUndo----------------------
//--------------------------------------

void moveUndo(BOARD_T *brd,
			     UNDO_T  *udo,
			     MVE_T    mve)
	{
	 //RESET
	 //--------------------------------------

	 //...
	 brd->ept = udo->ept;
	 brd->key = udo->key;
	 //...

     //pop last key
     delGameHist();

	 return;
	}

this way you always have correct key according to
rules and repetitions.

...

just some additional lines of pseudocode

Code: Select all

bool drawByRule(/*params*/)
	{
	 if(halfMoveClock >= 100) return(true);

	 //repetition
	 lastIndex = gameHistIndexLastEntry;

	 for&#40;i=2;i<lastIndex;i+=2&#41;
		&#123;
		 if&#40;brd->key == gameHistoryEntry&#91;lastIndex-i&#93;)
			 repetition++;

		 //you can hack with rep == 1
		 if&#40;repetition==2&#41; return&#40;true&#41;;
		&#125;

	 return&#40;false&#41;;
	&#125;

Thats all to do for repetition detection.
Because this is a part of the rules, i would like
to suggest to implement as early as possible.
(and it is not much to implement).

cheers, Micha

[Michael Sherwin]

Hi Michael;

Now that you guys made me think about this I am not sure that the way that you (and I) are updating the zorbrist key is correct.

After.

1. e4 e6 2. e5 d5

I think that it is wrong to add in the e.p. zorbrist key after the double move because after

3. Nf3 Ne7 4. Ng1 Ng8

the hash key is the same as after the double move.

Instead.

1. e4 e6 2. e5 d5 3. Nf3

Now add in the e.p. zorbrist so that

3. ... Ne7 4. Ng1 Ng8

actually ends up with a different hash key than the position just after the double move.

[Michael Sherwin]

An easy solution is not to have e.p. zorbrist keys at all. They can be done away with if making a reversible move and 'fifty = 0;' triggers an extra zorbrist to be added.

[Michael Sherwin]

My second suggestion does not work if the move that resets the fifty move counter to zero is not a double pawn move that enables a legal c.e.p.

However, if there is a legal c.e.p. then adding in the zorbrist only on an immediately following reversible move does make sense.

[hgm]

You define your priorities. I can only say that a chess engine that does not implement repetition detection cannot be considered a chess engine, it is just boring. It will be unable to win a won position in most cases.

I can fully corroborate this. Early versions of micro-Max were blind to repetitions. This made it almost impossible to evaluate changes. When I added code tht should have been a big improvement, it did not result in any improvement of its score in gauntlets against other engines at all. When I analyzed the games, it turned ot that it was now consistently winning material against engines that formerly were its equal, but that it still would draw all these game. Once it was ahead enough for the opponent to realize it, the latter could almost always trick micro-Max into a repeat loop. So it was almost impossible to meaningfully test, and this hampered progress enormously.

The good news is that 95% of the problem was solved by recognizing repetitions of game positions (as opposed to tree positions). So what I do in micro-Max now is this: when a moe is made at gme level, it adapts the score of the corresponding hash entry to zero, and the depth to 99. Although it in principle uses always-replace, I forbid replacing d=99 entries ever. So the entire game history remains locked in the hash, and every hit on it will return a zero score, as the depth is always sufficient.

[hgm]

Hi Michael;

Now that you guys made me think about this I am not sure that the way that you (and I) are updating the zorbrist key is correct.

After.

1. e4 e6 2. e5 d5

I think that it is wrong to add in the e.p. zorbrist key after the double move because after

3. Nf3 Ne7 4. Ng1 Ng8

the hash key is the same as after the double move.

Instead.

1. e4 e6 2. e5 d5 3. Nf3

Now add in the e.p. zorbrist so that

3. ... Ne7 4. Ng1 Ng8

actually ends up with a different hash key than the position just after the double move.

If you do it like that, you definitely do it wrong!

The e.p. key should be added to the hash key when probing, but not to the differentially updated hash key. e.p. rights are a transient feature, and disappear after one ply. What you put in the differentially updated key stays there forever.

In micro-Max I have a differentially updated key where I incorporate from-square, two-square and captured victim in the usual way, but when probing, I do not use that key, but I add stm*epSquare first. The stm encoding in uMax is 8=white and 16=black, and the e.p. squares are square numbers on a 0x88 board, and range from 32-39 (white e.p. captures) and 80-87 (black e.p. captures), and 128 if there are no e.p. rights. So every combination of stm and e.p. will give me a different addition to the differential key.

[Desperado]

Hi Michael;

Now that you guys made me think about this I am not sure that the way that you (and I) are updating the zorbrist key is correct.

After.

1. e4 e6 2. e5 d5

I think that it is wrong to add in the e.p. zorbrist key after the double move because after

3. Nf3 Ne7 4. Ng1 Ng8

the hash key is the same as after the double move.

Instead.

1. e4 e6 2. e5 d5 3. Nf3

Now add in the e.p. zorbrist so that

3. ... Ne7 4. Ng1 Ng8

actually ends up with a different hash key than the position just after the double move.

Code: Select all

 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  ]; x0
 5. Nf3 -> key^=zbrEpt[ d6  ]^zbrEpt[noEpt]; y0
 6. Ne7 -> key^=zbrEpt[noEpt]^zbrEpt[noEpt]; 
 7. Ng1 -> key^=zbrEpt[noEpt]^zbrEpt[noEpt];
 8. Sg8 -> key^=zbrEpt[noEpt]^zbrEpt[noEpt]; x1
 9. Nf3 -> key^=zbrEpt[noEpt]^zbrEpt[noEpt]; y1
10. Ne7 -> key^=zbrEpt[noEpt]^zbrEpt[noEpt]; 

 x0 != x1
 y0 == y1

Well, with my understanding of this, it doesn t matter how you
reach the y-position(after execution of Ng8). All to consider is the piece placement and the board status.
so because y0 and y1 have the same pPlacement and the same bStatus, the key y0,y1 should match.

...
in that I eliminate a significant number of possible hash key matches and slow down my search.

So, i dont see (at least at the moment) why this can eliminate significantly
the number of possible hash key matches.
None of the subtree positions (after double pawn push) is influenced by the zbrEpt, with the only exception of the "x-position" which has the
same piece-placement but simply another board status.
(writing this, i wonder what the optimization can be in the context of
hashhits ?)

repetition issue:
===========

well, of course someone can consider x0==x1, so the
repetition code would report true for x2. But this would
only be an additionally hack. (like: avoid underpromotions,
reporting draw by repetition with a repetitionCount==1).

According to the rules of chess, the repetitiondetection code should recognize the repetition on x3.
(x0 is simply another position beside the pieceplacement).

@everyone: feel free to correct me

Michael

[micron]

I have been including a hash key component when a pawn moves forward two squares, regardless of whether or not there is a capture possible. As I think about it, this seems wrong, in that I eliminate a significant number of possible hash key matches and slow down my search.

doing the update like you have done so far is an absolutely correct way to handle this.
What you described as mistake is at most a missing optimization.

Making that optimization is worthwhile. After reading this useful thread, I now set an en passant square only if there is an opposing pawn that can capture it. My time for a nominal 10 ply search from the start went from 14.1 s to 11.6 s. A good result from 5 minutes' programming.

Robert P.