Perft and hash with legal move generator

Code, algorithms, languages, construction...
Peterpan
Posts: 44
Joined: Sat Nov 27, 2010 7:22 pm
Real Name: Izak

Re: Perft and hash with legal move generator

Post by Peterpan » Fri Feb 19, 2016 3:33 pm

I have tested several ep and castling positions for example kiwipete and position 4 on chessprogramming wiki.Position 4 even with hash on works fine even up to depth 8,and kiwipete correct also up to depth 8 without hash,cannot remember if it was correct with hash on,didn't test it recently.

Also tested several other positions,to check for promotion bugs and ep etc... all clear.

For a chess engine yes i suppose it is correct enough.I just would like to have it as correct as i can with the hash enabled.Hopefully with the latest change it will help.

What i mean with verification test is,that i do a AllBitboardOcc comparison,i do save that one as 8 bytes in the hash as well,and if the hashkey is the same,it checks if the position,is the same,well if there is the same amount of pieces on the same squares,i know it's not a full perfect position comparison,but it helps.

At the moment my hash looks like this :

if UseHash eq 1
hashdivide = 4 ;32 byte hash = 5 16 byte hash = 4
hashtabledepth = 0
hashtablekey = 1
hashtablenodes = 5
hashtableposition = 6
hashtablescore = 14
end if

Which is 16 bytes in size,hashtableposition is where i store the AllBitboardOcc

Yes i am sure 32 bit's might also influence the results,as you mention,it would just be nice to have a correct depth 10 initial position with hash on,i think once i can accomplish this i will be happy with my hash function,if possible with 32 bit key.

My goal is to write a chess engine,not a perft champ,this does not seem to be possible with my implementation,although i am quite happy with the speed of my pure legal move generator,and i like the fact that it is in assembler.There is no processor new instruction optimizations used,besides 2 popcn't insturctions,the rest is all basic instructions that works on quite old processors.

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: Perft and hash with legal move generator

Post by H.G.Muller » Fri Feb 19, 2016 4:00 pm

OK, that extra verification probably explains why you only find the first collisions at depth 10. The Occupied board is pretty low-density information, for identifying a position, though. (Especially since it tends to correlate a lot between positions from the same tree: with perft(10) only 10 of the 32 pieces can be displaced.) You would probably be off better by storing the static evaluation, and that would only take 2 bytes. I also suppose your hash key is actually longer than 32 bits, but that you use the other bits to derive the index from. If there stil are some bits left not used for the index, you could consider storing those too. Or adding the remainder of the key to Occupied board, or multiplying them. Or is the index derived from the same 32 bits as that you store?

Peterpan
Posts: 44
Joined: Sat Nov 27, 2010 7:22 pm
Real Name: Izak

Re: Perft and hash with legal move generator

Post by Peterpan » Fri Feb 19, 2016 6:21 pm

Originally it's 64 bits,and then i shift it 32 bits to the right.
At the moment i have not yet added static evaluation or any evaluation to my chess engine,this would be done in the near future though hopefully.

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: Perft and hash with legal move generator

Post by H.G.Muller » Fri Feb 19, 2016 6:55 pm

Well, as it is unlikely that you use all 32 bits to derive the index from, you could just XOR the entire key with the Occupied board, to store that as verification test. That should help distinguishing positions that happen to have the same Occupied pattern.

Peterpan
Posts: 44
Joined: Sat Nov 27, 2010 7:22 pm
Real Name: Izak

Re: Perft and hash with legal move generator

Post by Peterpan » Fri Feb 19, 2016 7:07 pm

Thanks,i will try that tomorrow once my test is completed.Thanks for all the advice!

Peterpan
Posts: 44
Joined: Sat Nov 27, 2010 7:22 pm
Real Name: Izak

Re: Perft and hash with legal move generator

Post by Peterpan » Sat Feb 20, 2016 5:36 am

I now tried what you said,i xor'ed the whole 64 bit hashkey with the AllbItboardOcc here on my pc at home,and still i have problems with this position at depth 12.

8/p7/8/1P6/K1k3p1/6P1/7P/8 w - -

up to depth 11 all is okay.
With hash off of course even depth 12 is okay.

With hash off i get this :

Number of nodes depth (1) = 5
Number of nodes depth (2) = 39
Number of nodes depth (3) = 237
Number of nodes depth (4) = 2002
Number of nodes depth (5) = 14062
Number of nodes depth (6) = 120995
Number of nodes depth (7) = 966152
Number of nodes depth (8) = 8103790
Number of nodes depth (9) = 72427818
Number of nodes depth (10) = 586519056
Number of nodes depth (11) = 5954842412
Number of nodes depth (12) = 46490836188

Which is the correct nodes.

With 8 gigs hash on and with the xor i get this,even without the xor it obviously also doesn't work.

The Starting HashKey = 13658426903227814746
Number of nodes depth (1) = 5
Number of nodes depth (2) = 39
Number of nodes depth (3) = 237
Number of nodes depth (4) = 2002
Number of nodes depth (5) = 14062
Number of nodes depth (6) = 120995
Number of nodes depth (7) = 966152
Number of nodes depth (8) = 8103790
Number of nodes depth (9) = 72427818
Number of nodes depth (10) = 586519056
Number of nodes depth (11) = 5954842412
Number of nodes depth (12) = 46492360913
Number of the hashnodes = 45861387726
The Ending HashKey = 13658426903227814746

Peterpan
Posts: 44
Joined: Sat Nov 27, 2010 7:22 pm
Real Name: Izak

Re: Perft and hash with legal move generator

Post by Peterpan » Sat Feb 20, 2016 9:57 am

Test completed! works correct now,this was before the xor fix! the 2 day test!

izak@izak-All-Series:~/DrawBoard$ time ./DrawBoard9088h
The Starting HashKey = 13658426903227814746
Number of nodes depth (1) = 20
Number of nodes depth (2) = 400
Number of nodes depth (3) = 8902
Number of nodes depth (4) = 197281
Number of nodes depth (5) = 4865609
Number of nodes depth (6) = 119060324
Number of nodes depth (7) = 3195901860
Number of nodes depth (8) = 84998978956
Number of nodes depth (9) = 2439530234167
Number of nodes depth (10) = 69352859712417
Number of the hashnodes = 66551617019467
The Ending HashKey = 13658426903227814746

real 3000m15.474s
user 2999m8.824s
sys 0m4.392s
izak@izak-All-Series:~/DrawBoard$

Now i must figure why Numpty 2 still gives wrong nodes at depth 12....

8/p7/8/1P6/K1k3p1/6P1/7P/8 w - -

Peterpan
Posts: 44
Joined: Sat Nov 27, 2010 7:22 pm
Real Name: Izak

Re: Perft and hash with legal move generator

Post by Peterpan » Sat Feb 20, 2016 5:22 pm

okay i see the perft 10 was starting with black,oops,and thus the correct nodes up to depth 10.
I tried the numpty 2 position again depth 12 with black starting,and then also correct nodes.
So the problem it seems has something to do with "side to move" or some silly bug,close now to closing in on it.

Post Reply