An interesting bug in Hamsters

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Post Reply
Alessandro Scotti

An interesting bug in Hamsters

Post by Alessandro Scotti » Thu Aug 02, 2007 10:00 pm

While comparing Hamsters and Glaurung evaluation code (which means comparing detection of features but not scores since those would be completely different) I stumbled upon this position:

[D]4k3/7r/3nb3/2R5/8/6n1/1R3K2/8 w - -

Here Hamsters failed to recognize that... all rooks are on open files! :shock: Now for the reason. I store this information in the pawn hash table, but here there are no pawns and the pawn hash key value is just the initial value: zero. This means I probe the very first index of the pawn hash table and get a match, because at the beginning of the program all tables are reset to zero. So for me entry #0 is ok for that position, and from there I get no bits set for open files, so no open files.

Ok, I fixed this by initializing the pawn and material keys to something other than zero. I tested on just a couple of positions and I was a little surprised by the difference.

[D]8/1p4kP/5pP1/3p4/8/4P3/7K/8 w - - bm e4;

Old (key = 0):

Code: Select all

22/40 0:17.47 299 12834080 e4 dxe4 Kg3 b5 Kf4 e3 Kxe3 b4 Kd4 b3 Kc3 f5 Kxb3 f4 Kc2 f3 Kd3 f2 Ke2 f1=N Kxf1 Kh8 Ke2
23/42 0:21.80 308 15917026 e4 dxe4 Kg3 b5 Kf4 e3 Kxe3 b4 Kd4 b3 Kc3 f5 Kxb3 f4 Kc2 f3 Kd3 f2 Ke2 f1=N Kxf1 Kh8 Ke2 Kg7
24/44 0:28.32 308 20579650 e4 dxe4 Kg3 b5 Kf4 e3 Kxe3 b4 Kd4 b3 Kc3 f5 Kxb3 f4 Kc2 f3 Kd3 f2 Ke2 f1=N Kxf1 Kh8 Ke2 Kg7 Ke3
New (key = random constant):

Code: Select all

22/39 0:15.79 299 11578796 e4 dxe4 Kg3 b5 Kf4 e3 Kxe3 b4 Kd4 b3 Kc3 f5 Kxb3 f4 Kc2 f3 Kd3 f2 Ke2 f1=N Kxf1 Kh8 Ke2
23/40 0:19.92 308 14546912 e4 dxe4 Kg3 b5 Kf4 e3 Kxe3 b4 Kd4 b3 Kc3 f5 Kxb3 f4 Kc2 f3 Kd3 f2 Ke2 f1=N Kxf1 Kh8 Ke2 Kg7
24/42 0:25.79 308 18764888 e4 dxe4 Kg3 b5 Kf4 e3 Kxe3 b4 Kd4 b3 Kc3 f5 Kxb3 f4 Kc2 f3 Kd3 f2 Ke2 f1=N Kxf1 Kh8 Ke2 Kg7 Kd3
That's 9% less nodes in the last ply. The difference is not so big in other positions but the fix seems safe anyway so who knows, maybe this is even worth some elo... 8-)

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: An interesting bug in Hamsters

Post by wgarvin » Fri Aug 03, 2007 4:34 pm

Just to be clear, because there are no pawns your zobrist key for the pawn hash was zero? And the pawn hash entry for zero had also been cleared to zero and so you got a match on the pawn hash key stored there, though there was no valid data in it yet.

That is an excellent bug :)

Alessandro Scotti

Re: An interesting bug in Hamsters

Post by Alessandro Scotti » Fri Aug 03, 2007 4:45 pm

wgarvin wrote:Just to be clear, because there are no pawns your zobrist key for the pawn hash was zero? And the pawn hash entry for zero had also been cleared to zero and so you got a match on the pawn hash key stored there, though there was no valid data in it yet.

That is an excellent bug :)
Thanks, I got plenty but I must admit this is one of the nicest! :-)

MartinBryant

Re: An interesting bug in Hamsters

Post by MartinBryant » Fri Aug 03, 2007 6:12 pm

I recently spotted a similar problem in Colossus.
Mine was that in release build I wasn't ever initialising the pawn hash table, so the data in it was whatever was lying in that area of memory.
I only noticed it when comparing a test position in debug and release modes next to each other... the analyses were different!
So in release mode it must have at least in one position found what it thought was a valid entry and retrieved nonsense as the value! It was enough to affect the result at the root!!!

Instead of using a random key (which could surely possibly find a spurious hit?), surely the correct way to fix your bug is to init your #0 entry to have all files marked as open (whatever that value is in your coding).

Uri Blass
Posts: 8009
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: An interesting bug in Hamsters

Post by Uri Blass » Fri Aug 03, 2007 6:19 pm

MartinBryant wrote:I recently spotted a similar problem in Colossus.
Mine was that in release build I wasn't ever initialising the pawn hash table, so the data in it was whatever was lying in that area of memory.
I only noticed it when comparing a test position in debug and release modes next to each other... the analyses were different!
So in release mode it must have at least in one position found what it thought was a valid entry and retrieved nonsense as the value! It was enough to affect the result at the root!!!

Instead of using a random key (which could surely possibly find a spurious hit?), surely the correct way to fix your bug is to init your #0 entry to have all files marked as open (whatever that value is in your coding).
Another possibility is not to use pawn hash when there are no pawns and add if (numpawns>0) before probing the pawn hash.

Uri

Jan Brouwer
Posts: 201
Joined: Thu Mar 22, 2007 6:12 pm
Location: Netherlands

Re: An interesting bug in Hamsters

Post by Jan Brouwer » Fri Aug 03, 2007 7:10 pm

That is certainly an interresting bug, it may also be quite common.
Some time ago I found exactly that bug in my chess program, only I used a 'special' random constant to fix it :-).

Code: Select all

  memset(gMatHash, 0, sizeof gMatHash);
  // K-K is mapped to signature 0, avoid matching key:
  gMatHash[0].Key = 1;
  memset(gPawnHash, 0, sizeof gPawnHash);
  // no pawns is mapped to signature 0, avoid matching key:
  gPawnHash[0].Key = 1;

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

Re: An interesting bug in Hamsters

Post by Pradu » Fri Aug 03, 2007 7:15 pm

Jan Brouwer wrote:That is certainly an interresting bug, it may also be quite common.
Some time ago I found exactly that bug in my chess program, only I used a 'special' random constant to fix it :-).

Code: Select all

  memset(gMatHash, 0, sizeof gMatHash);
  // K-K is mapped to signature 0, avoid matching key:
  gMatHash[0].Key = 1;
  memset(gPawnHash, 0, sizeof gPawnHash);
  // no pawns is mapped to signature 0, avoid matching key:
  gPawnHash[0].Key = 1;
I designated one particular hashkey as an indicator that the hashkey is invalid:

Code: Select all

#define INVALID_HASH_KEY C64(0x1234567890ABCDEF)

Post Reply