Page 1 of 3

Enpass + Castling for Zorbist hashes

Posted: Fri Jan 06, 2017 4:20 am
by AndrewGrant
So I recently got around to factoring in the castling rights + enpass square into my zorbist hash calculations.

Self testing showed a rather large drop in elo.

I then went an decided to only factor in the enpass square if an enemy pawn could actually form the enpass. This made my node counts more simliar to my base line. However, self testing showed a reasonable elo drop once again. But a greater drop than what is expected for the overhead added.

My question here is, has anyone else found that ignoring castle rights and / or enpass is an improvement? It seems like a horrid idea to drop these two factors, but self-testing suggests otherwise.

Re: Enpass + Castling for Zorbist hashes

Posted: Fri Jan 06, 2017 9:59 am
by Sven
AndrewGrant wrote:So I recently got around to factoring in the castling rights + enpass square into my zorbist hash calculations.

Self testing showed a rather large drop in elo.

I then went an decided to only factor in the enpass square if an enemy pawn could actually form the enpass. This made my node counts more simliar to my base line. However, self testing showed a reasonable elo drop once again. But a greater drop than what is expected for the overhead added.

My question here is, has anyone else found that ignoring castle rights and / or enpass is an improvement? It seems like a horrid idea to drop these two factors, but self-testing suggests otherwise.
No, it suggests that you need to find the bug :-)

You definitely need to use castling rights and ep target square in your hash key. Not using them can't be an improvement of your engine. However, both involve a lot of pitfalls when implementing it. Here are some suggestions how to proceed:

1) Basic assumption is that "perft" returns correct numbers for some important test positions. Otherwise make/unmake and move generator would be typical sources for hash key problems as well.

2) Double check that "make move" updates the hash key correctly in all cases and "unmake move" restores it to its original value. The latter is usually guaranteed by saving the hash key on a stack, the former can be checked in a debug version by adding a function that calculates the whole hash key from scratch, and then comparing the incremental and the "from scratch" hash key, it must be the same after each make or unmake operation.

Typical update rules for castling rights and en passant are (I hope I did not miss anything):

- Moving the king (including castling) clears both castling rights of the moving side.
- Moving a rook (including castling) clears one of the castling rights of the moving side.
- Capturing a rook in a corner clears one of the castling rights of the opponent.
- No other legal move affects any castling right.
- Even the null move does not affect any castling right.

- The ep target square always changes when making a move (including the null move!) from a position where the ep target square is set to a valid square.
- The ep target square always changes when making a pawn double step to a square left or right to an enemy pawn (unless you have implemented the detection of exceptional cases where en passant is not allowed after such a move due to a pinned piece).
- No other situation affects the ep target square.

3) If "perft" and hash key updating do not show any errors then you can still have errors, either by always treating two different positions as identical or by always treating two identical positions as different. Both can cause trouble regarding repetition detection (if that is based on hash keys, as in most engines) and in search, where the more severe case for both would be to always treat two different positions as identical.

4) Another possible source of trouble is how castling rights and ep target square are mapped to zobrist keys. For both there are different solutions around. In any case, even if a solution is not the most efficient one, it must lead to correct code in the sense that different values of the position properties (CR, EP) are mapped to different zobrist keys and identical values aren't. You can write simple test code for this, independent from any concrete board position.

Re: Enpass + Castling for Zorbist hashes

Posted: Fri Jan 06, 2017 10:05 am
by AndrewGrant
Thanks for the response, Ill start working my way though checking off all your points. Clearly i'm inclined to say it works perfectly, but alas there likely is a bug.

Your mention of the nullmove might be on point. As of now, my null move consists of only the following. Swap the turn, add a NULL to the history, and invert the key. that code actually sits in my null search portion, not even in a function like applyNullMove...

Re: Enpass + Castling for Zorbist hashes

Posted: Fri Jan 06, 2017 11:06 am
by PK
As of now, my null move consists of only the following. Swap the turn, add a NULL to the history, and invert the key.
Null move should also clear en passant rights! And of course unmaking it should restore them to the previous state.

Re: Enpass + Castling for Zorbist hashes

Posted: Fri Jan 06, 2017 9:11 pm
by AndrewGrant
To further add to the mystery, correctly updating the zorbist hash with respect to the enpass square during null moves shows a further loss of elo.

Testing with no castling and no enpass factoring = 0elo
Testing with casting and enpass (but no null) = -1elo
Testing with castling and enpass = -3elo


1) Basic assumption is that "perft" returns correct numbers for some important test positions. Otherwise make/unmake and move generator would be typical sources for hash key problems as well.
Confirmed via PERFT testing
2) Double check that "make move" updates the hash key correctly in all cases and "unmake move" restores it to its original value. The latter is usually guaranteed by saving the hash key on a stack, the former can be checked in a debug version by adding a function that calculates the whole hash key from scratch, and then comparing the incremental and the "from scratch" hash key, it must be the same after each make or unmake operation.
Confirmed by computing the key at each step in and comparing to the incrementally updated values
4) Another possible source of trouble is how castling rights and ep target square are mapped to zobrist keys. For both there are different solutions around. In any case, even if a solution is not the most efficient one, it must lead to correct code in the sense that different values of the position properties (CR, EP) are mapped to different zobrist keys and identical values aren't. You can write simple test code for this, independent from any concrete board position.
Not doing any magic with the table.

As for the update rules the only one i'm missing is capturing a rook causing a clearing of rights, which would cause an issue. Promote a pawn to a rook to replace a captured rook, move the pawn to the rooks initial location, and then castle. I am very surprised the perft suite im using does not cover it. Just ran a test using this position 8/P6P/8/4k3/3bb3/8/8/R3K2R w KQ - and my number differs from stockfish6. I've fixed (just needed two lines) this but this little issue cannot possibly the source of the original problem.[/quote]

Re: Enpass + Castling for Zorbist hashes

Posted: Fri Jan 06, 2017 10:32 pm
by Sven
AndrewGrant wrote:To further add to the mystery, correctly updating the zorbist hash with respect to the enpass square during null moves shows a further loss of elo.

Testing with no castling and no enpass factoring = 0elo
Testing with casting and enpass (but no null) = -1elo
Testing with castling and enpass = -3elo
I guess you mean something like -100elo/-300elo? -1/-3 would be like random.
AndrewGrant wrote:As for the update rules the only one i'm missing is capturing a rook causing a clearing of rights, which would cause an issue.
Definitely a problem!
AndrewGrant wrote:Promote a pawn to a rook to replace a captured rook, move the pawn to the rooks initial location, and then castle.
Definitely a non-issue w.r.t. castling rights update and hash key, since only the capture of the rook can affect castling rights.

But please be aware that castling with a rook that has already moved is illegal, so you may have another problem there.
AndrewGrant wrote:I am very surprised the perft suite im using does not cover it. Just ran a test using this position 8/P6P/8/4k3/3bb3/8/8/R3K2R w KQ - and my number differs from stockfish6. I've fixed (just needed two lines) this but this little issue cannot possibly the source of the original problem.
As I wrote above: your numbers differ because you allow castling with a rook that has already moved. So you are missing one more of the update rules I listed. And you *must* find this particular problem (illegal castling move generated!) with perft!

Re: Enpass + Castling for Zorbist hashes

Posted: Fri Jan 06, 2017 10:34 pm
by noobpwnftw
The symptoms you observed may be a proof of my assumption (http://www.talkchess.com/forum/viewtopic.php?t=62639) that ignoring castling rights probably won't break the overall consistency of the search tree.

I didn't thought about sending a pawn to be captured via EP is a bad move on ply-1 unless the situation is already bad enough, which usually doesn't happen either.

Your elo loss is probably due to the extra search introduced by differentiating the hash keys, but I wonder what is the scale of your test to get the numbers for your elo change?

P.S. I'm still being open-minded on my assumptions since I've already ran into too many situations that seems anti-science. :lol:

Re: Enpass + Castling for Zorbist hashes

Posted: Fri Jan 06, 2017 11:09 pm
by AndrewGrant
~20,000 games for each of my elo observations.

Running a test now with the final fix to castling rights. Interestingly, test shows a reasonable gain after only a few thousand games when I cut my usual time control in half.

Running the usual time control now.

[quote]Your elo loss is probably due to the extra search introduced by differentiating the hash keys[/quote]

That's what I expect.



Any reason that ignoring castling rights / enpass would be good at some time controls, but not others?

Re: Enpass + Castling for Zorbist hashes

Posted: Sat Jan 07, 2017 12:30 am
by Sven
AndrewGrant wrote:~20,000 games for each of my elo observations.

Running a test now with the final fix to castling rights. Interestingly, test shows a reasonable gain after only a few thousand games when I cut my usual time control in half.

Running the usual time control now.
Your elo loss is probably due to the extra search introduced by differentiating the hash keys
That's what I expect.
With 20.000 games I guess you probably have error bars of +/5, so are you really talking about an Elo loss of 3 points?

Re: Enpass + Castling for Zorbist hashes

Posted: Sat Jan 07, 2017 1:26 am
by AndrewGrant
I had posted the upper bounds of the elo difference,

IE the elo was -7 +- 4

The overhead of handling this issue is so small it should not be able to account for the drop of at least 3. Not to mention, that in theory, fixing this bug should be an elo gain.