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

Perft and hash with legal move generator

Post by Peterpan » Thu Nov 12, 2015 3:40 pm

Hi There

I have my move generator going in fasm 64 bit,everything works correct,done the perft tests on various positions,all correct.
It does about start position in 50 seconds with no hash,and with 128 megs hash on around 15 seconds.
There are still place for some speed improvements,like doing pin check beforehand,but that later...

Also working when skipping the last node,depth 1 in this case,so that only the last nodes are added so that moves are not generated twice,the usual way.

What is not working is when i use the hash,and i know it has to do with en-passant,and perhaps other unique hash moves like castling etc..
With depth 0 and hash on everything is working perfect,so the hash is working.

The problem is that my move generator does not add moves to the hash in the move generation,only when make/unmaking.
So when skipping depth 0,with no hash no problem.But when skipping depth 0 with hash on,i get wrong results at depth 7 of starting position,and i know it has to do with the hash.

I wanted to add hash to the move generator of the engine,but then i cannot save the total amount of nodes,whilst when doing it with make/unmake i have that info from my move generation and can save the depth etc with the appropriate hashkey ...

So how to solve this,i do not want to move from a legal move generator to a pseudo legal,do i add hash to my move generator,or keep hash to make/unmake,and is it possible to have correct nodes with hash on and skipping depth 1 ? is there a mistake in my make/unmake hash implementation,or is it because i do not add hash in initial move generation,which would be depth 0

If i do not fix this,will the affect my chess engine later on,will i need to skip depth 1 in my normal search as well ?
Do i really need to fix this for depth 1 skip hash?

Thanks for any help

Best Regards
Izak

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 » Mon Nov 16, 2015 7:21 pm

hi Again

Okay i see no answer.I have decided to not worry about this anymore,since i cannot see a way to solve this problem with the current architecture of my engine (and i do not wish to change it),with depth 0 and perft and hash on all is perfect,around 1:05 seconds from initial position and depth 7 and 8 gigs hash single core,1:10 or 1:15 (can't remember) with 128 megs hash,without hash and not skipping depth 0 it's much slower,more than 2 minutes... anyway... although slower now with hash on than when skipping depth 0 and no hash,which is around 50 seconds.Most important thing is,hash is working perfectly.And i get all the stats i need,like how many checks,how many castles,how many ep's,how many captures... etc.. to keep things simple for me.Not going to add the pins code now,will perhaps do that later if i see my engine needs more speed...

So now instead of wasting more time,moving on to next phases,evaluation,piece square tables,material values and then finally search.

Maybe in a years time this engine will be able to play chess :)

Best Regards
Izak

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Perft and hash with legal move generator

Post by hyatt » Mon Nov 16, 2015 9:12 pm

Peterpan wrote:hi Again

Okay i see no answer.I have decided to not worry about this anymore,since i cannot see a way to solve this problem with the current architecture of my engine (and i do not wish to change it),with depth 0 and perft and hash on all is perfect,around 1:05 seconds from initial position and depth 7 and 8 gigs hash single core,1:10 or 1:15 (can't remember) with 128 megs hash,without hash and not skipping depth 0 it's much slower,more than 2 minutes... anyway... although slower now with hash on than when skipping depth 0 and no hash,which is around 50 seconds.Most important thing is,hash is working perfectly.And i get all the stats i need,like how many checks,how many castles,how many ep's,how many captures... etc.. to keep things simple for me.Not going to add the pins code now,will perhaps do that later if i see my engine needs more speed...

So now instead of wasting more time,moving on to next phases,evaluation,piece square tables,material values and then finally search.

Maybe in a years time this engine will be able to play chess :)

Best Regards
Izak

I did not understand your question, which is why I didn't answer. Didn't know when you mean when you say "my move generator does not add it to the hash"...

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 » Mon Nov 16, 2015 9:42 pm

hyatt wrote: I did not understand your question, which is why I didn't answer. Didn't know when you mean when you say "my move generator does not add it to the hash"...
hi hyatt

Thanks for your reply!

Yeah i meant my move generator is not adding any moves to the hash,it is only generating the legal moves,only the make/unmake part of my code adds the moves to the hash.

For example the enable en passant code is in the make part of my code.
It checks there if the pawn moved 2 places up.And enables a possible en passant for the next move.
If i add this in my move generation then it doesn't work anymore,cause that pawn move is for example one of 20 moves in the movelist,which doesn't then get made/unmade,and does not get added to the hash,and after move generation program would not know which move enabled the en passant for that ply,or other pawn moves will disable it again.

But when i make/unmake all the legal moves that my move generator created,i have no problems like that anymore,and then each ply's en passant move/or enable en passant move gets saved.

So when i skip depth 1 with hash on,all those moves of depth 0 don't get added to the hash,and this is where i run into problems with en passant etc..

This is the best i can explain it,sorry if i was unclear or still am.
But i think i solved the problem for myself now,it's unsolvable with the way my code is.

Best Regards
Izak

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 » Tue Nov 17, 2015 5:58 am

i might have found a solution!

I will add in my move generation phase a hash key for each move and store it in my movelist,at the moment my movelist is a word long,but i can make it a qword,and store the upper 32 bit hash key there for that move only,and then at the end of say my moves in my move generation,i add all the keys in my current movelist to the hash,and then i will also have the amount of legal moves,and depth,so that is all the info i need to store them to the hash.And then in my make/unmake move i can just update my global hashkey,since i already have the hashkey for the move i am about to make,so the time wasted in movegen is now saved here,or something like that.Now i can add the 2 pawn move check in my move generation,so now en passant should not be a problem anymore when i skip depth 0 and use hash and maybe perhaps i can now have a faster perft with hash on and skipping depth 0.We'll see!

Best Regards
Izak

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 » Sun Feb 14, 2016 3:20 pm

What could most likely be the problem here?
A hash collision ? or something else. I am quite sure my en passant and castling hashing is now done correctly,but... i am 235866 nodes off at depth 10,depth 9 no problem.
Selection_019.png
Correct nodes should be 69,352,859,712,417

Any ideas ?

User923005
Posts: 616
Joined: Thu May 19, 2011 1:35 am

Re: Perft and hash with legal move generator

Post by User923005 » Thu Feb 18, 2016 8:08 pm

If you get a correct answer with hashing turned off then the problem is your hashing.
If you get a wrong answer with hashing on and off, then it is your move generator.

If it is hashing, then debug the hash.

If it is the move generator, then use the divide command (or implement the divide command) to hash by category.
https://chessprogramming.wikispaces.com/Perft

You can also collect problem sets with known issues at given depths to see if they apply.
For instance, you can find problem sets with promotions or problem sets with e.p. etc.

Here is a useful article that may prove helpful:
http://www.rocechess.ch/perft.html

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 9:26 am

Well, it is often not possible to get such a deep perft result without hashing in a reasonable time. A simple test would be to change the Zobrist keys (e.g. through the seed of the random generator from which you obtain them), and see if the result changes with it. If so, it is almost certain key collisions play a role.

Whether that is reasonable to expect depends on the details of your hashing scheme. Such as the size of the key and the number of stored key bits.

That does not clear your move generator, but would have to be fixed before you will be able to meaning fully debug that move generator by divided perfts.

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 10:35 am

hi Thanks for the replies.

I have found some hash keys that overlapped.I used possibly the same hash keys for castling rights as some possible other hash keys,and same goes for en passant,i think i fixed that now,am currently busy running a perft 10,takes about 2 days with hashing on,will know by tomorrow if it is correct now or not.
The move generation works perfect,i tested on several positions,even one when at depth 12 it gives correct nodes,but with hashing on it doesn't.
Although like H.G.Muller says it takes a looooooong time to do a perft without hash on inition position :)

I am using a 32 bit hashkey,and i do a verification test as well on the position.

Thanks for the advice,will keep you posted

Best Regards
Izak

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 1:57 pm

With 32-bit keys there is a 1-in-4-billion chance that the key is the same by accident. If you hash the perft(1) results at ply 9, you already have 500 times as many probes, so you would expect 500 false hash hits. Unlike search perft is very sensitive to collisions, and a single collision usually spoils the result. Not sure what you mean by 'verification test'. But to reliably do perft(10) you probably need a longer key, no matter how carefully you select your basic Zobrist randoms to be independent. I think Steven Edwards uses a 128-bit key. (But he wants to do perft(14)!)

It depends on what your goals are. If you want to have a calculator for deep perfts, you will have to address the hashing problem. If your goal is to build an engine, and test its move generator, you can just stay away from perfts where your existing hashing scheme, which is good enough for search, would run into trouble for perft. There are plenty of positions that would fully exercise your move generator (including castling, promotion and e.p. captures) at much lower depth than the initial FIDE position.

Post Reply