Idea to virtually zero hash collisions

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

Re: Idea to virtually zero hash collisions

Post by Peterpan » Tue Mar 15, 2016 9:12 pm

Here is my perft function's code... look at how i use hashnodes,and that it clearly is not hashhits!

Code: Select all

Perftw:push rsp
                                                                                                                                                                                                     
       mov r14,[ply]
       shl r14,shiftvalue
       mov [make.pointer + r14],0

       mov rax,[count]
       mov [make.oldcount + r14],rax                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          
if UseHash eq 1                
       cmp [my.hashkey],0
        je notrestorehash
       mov r15,[my.hashkey]
       mov rcx,r15
       shr rcx,32
       and r15,[hashkeymask]
       
       shl r15,hashdivide
       add r15,[HashBuffer]
       
       cmp dword [r15 + hashtablekey],ecx
        jne notrestorehash
         
       mov cl,[my.depth]
       cmp byte [r15 + hashtabledepth],cl
        jne notrestorehash
        
       ;mov rcx,[my.position]
       ;cmp qword [r15 + hashtableposition],rcx
       ; je restorehash 
       ;add [hashcollision],1
       ; jmp notrestorehash

restorehash:
       xor rcx,rcx
       mov cl,byte [r15 + hashtablenodes] 
       add [count],rcx 
       add [hashnodes],rcx
       pop rsp 
        ret

notrestorehash: 
end if
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           
       call CreateMovesList
       
       mov rax,[make.numberofmoves + r14] 
       shr rax,3
       cmp rax,0
        jnz weeer01
       mov [mateflag],1 
       pop rsp
        ret

weeer01:     
 mov rcx,[depth]
 add [my.depthnodes + (rcx * 8)],rax 
         
       cmp [depth],1
        jne weeer
       add [count],rax
       pop rsp
        ret 

weeer:
 
       mov r14,[ply]
       shl r14,shiftvalue
              
       mov rbx,[make.pointer + r14] 
       cmp rbx,[make.numberofmoves + r14]
        je gomake
      
       add [make.pointer + r14],8
      
       call Make
  
if UseDraw eq 1
  call SaveTopScreen
  call DrawBoard
  call PrintHash
  mov [DelayThis],1000000000
  pause1hggh:dec [DelayThis]
  jnz pause1hggh                
end if       

       call Perftw
   
       cmp [mateflag],1
        jne storehash
       mov [mateflag],0
        jmp skipmate
        
storehash:
if UseHash eq 1
       mov r15,[my.hashkey]
       
       mov rcx,r15
       shr rcx,32
       and r15,[hashkeymask]
       
       shl r15,hashdivide
       add r15,[HashBuffer]
   
       mov dword [r15 + hashtablekey],ecx
     
       mov cl,[my.depth]
       mov byte [r15 + hashtabledepth],cl
       
       ;mov rcx,[my.position]
       ;mov qword [r15 + hashtableposition],rcx   
      
       mov rcx,[count]
       
       sub rcx,[make.oldcount + r14] 
       mov byte [r15 + hashtablenodes],cl
       
end if
skipmate:

       call UnMake

if UseDraw eq 1
   call SaveTopScreen
   call DrawBoard
   call PrintHash
   mov [DelayThis],1000000000
   pause1hggjh:dec [DelayThis]
   jnz pause1hggjh                 
end if
       
        jmp weeer
 
gomake:
                                                                            
       pop rsp
        ret       

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

Re: Idea to virtually zero hash collisions

Post by H.G.Muller » Tue Mar 15, 2016 10:25 pm

I don't see the logic behind this. Getting a hit in a position with 25 moves might save you a billion moves, rather than 25, because it allows you to prune an entire tree whch without hash would have taken a billion nodes to traverse.

SEven with the factor 25 it is still extremely suspect. That would bring the number of claimed hits close to perft(9). But the total number of probes in a tree with only hash misses should be of that order. With hash hits the tree should be enormously smaller than perft(9). E.g. with qperft:

Code: Select all

C:\cygwin\home\perft>qperft 8 H24
Hash-table size = ffffff, Starts at 83b040,section = 1fffff
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: Hash-table size = 256MB, bulk counting in horizon nodes

perft( 1)=           20 ( 0.000 sec)
perft( 2)=          400 ( 0.000 sec)
perft( 3)=         8902 ( 0.000 sec)
perft( 4)=       197281 ( 0.002 sec)
perft( 5)=      4865609 ( 0.029 sec)
perft( 6)=    119060324 ( 0.432 sec)
perft( 7)=   3195901860 ( 5.066 sec)
perft( 8)=  84998978956 (67.957 sec)

C:\cygwin\home\perft>qperft 8
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft( 1)=           20 ( 0.000 sec)
perft( 2)=          400 ( 0.000 sec)
perft( 3)=         8902 ( 0.000 sec)
perft( 4)=       197281 ( 0.002 sec)
perft( 5)=      4865609 ( 0.043 sec)
perft( 6)=    119060324 ( 1.080 sec)
perft( 7)=   3195901860 (28.144 sec)
perft( 8)=  84998978956 (761.648 sec)

C:\cygwin\home\perft>
You can see that with 256MB hash perft(8) is about 11x faster than without hash, and that the speedup increases with depth: for perft(7) it is only 5.5, for perft(6) it is 2.5. It approximately doubles for each extra ply. (Beware that the nodes-per-second in the hashed case will be much lower: hash probes are time consuming. So the savings on the number of nodes will be more!) From that it follows that at every ply level about half the hash probes are hits (and thus pruned). Tne number of hits in that perft(8) calculation should have been at least 2x11 = 22 times smaller than perft(7) (and taking the nps into account even 40 or 60 times lower). Not about equal.

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

Re: Idea to virtually zero hash collisions

Post by H.G.Muller » Tue Mar 15, 2016 10:47 pm

Actually I have to take back that the nps would be lower. qperft does not hash or probe in the d=1 nodes, because caluclating perft(1) was faster than the hash probe. But that makes the number of visited nodes (and thus hash probes) for the perft(8) calculation about 11 times smaller than perft(6). Putting in a counter showed it was only 12 million. The number of hits should have been about half of that.

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

Re: Idea to virtually zero hash collisions

Post by Peterpan » Wed Mar 16, 2016 5:13 am

I see...

Thank you for your help.It seems i am doing something wrong somewhere.
This is bad and good news for me.
The bad is,i have to rethink my approach and see where i have gone wrong,and correct my mistake.
The good is,there is potential for my program to become much faster at higher plies with hash enabled and bigger hash sizes.

perft should be simple,like on chessprogramming wiki,if you find a hit,pop out of the recursive loop,like i am doing.

I am not using a bucket system,just overwriting hash at the moment.

Any ideas where the fault can be,other than what you have already mentioned so far ?

Best Regards
Izak

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

Re: Idea to virtually zero hash collisions

Post by Peterpan » Wed Mar 16, 2016 6:01 am

Personally i think it might have to do with the way i save hashkey.For example at the moment it uses the global my.hashkey.
Instead perhaps i should use a make.hashkey + r14 kind of thing,like i do for many other variables,in that structure,so that the hashkey gets saved for each ply.
Since i do not use the stack to save my variables,i use the make.structure + the r14 instead,to save data for each ply,but it now seems logical to have the hashkey in there as well.
Maybe the problem lies somewhere there... I do not think it's something big,but this small mistake makes my program slow,as you have pointed out.
And makes my hash not as efficient as it could be.And perhaps unusable for my chess engine.

Will let you know if i fix it and post results.
The bright side is,without hash i do a perft 7 in 22 seconds with the one who updates hash inside the creatmovegen (the current example),and 21 seconds for the one who updates hash in make/unmake on my pc.Still slower than Stockfish,i think he does it in 15 or less on my pc.

Code: Select all

izak@izak-System-Product-Name:~/DrawBoard$ time ./DrawBoard9163zNumber 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

real	10m21.408s
user	10m19.870s
sys	0m1.127s
Best Regards
Izak

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

Re: Idea to virtually zero hash collisions

Post by H.G.Muller » Wed Mar 16, 2016 9:20 am

It would be a very useful diagnostic to print the total number of calls to the recursive perft() function, the number of probes to the hash table, and the number of hits (matching key). And compare the number of calls for the case where hashing is on and where it is off. Without such information the best you can do is make blind guesses.

The hash key can be a global variable (most of my engines have that too), but the place where you save the old hash key for restoring it on UnMake() of course will have to be local to the current ply level. Otherwise it would be overwritten by every UnMake() in any daughter node.

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

Re: Idea to virtually zero hash collisions

Post by Peterpan » Wed Mar 16, 2016 10:32 am

Okay i will try the diagnostics as you suggest and put a hashkey in my make.structure.Thank you kindly for your help sir.
Much appreciated.

Best Regards
Izak

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

Re: Idea to virtually zero hash collisions

Post by Peterpan » Sun Mar 20, 2016 8:16 pm

I would like to thank H.G.Muller for his help,now my perft works as it should!!

This is with 1 gig hash,and with the source that generates the hashkeys in the MoveGeneration.
Now i must add this code to the source which generates the hashkeys in the make/unmake.

Code: Select all

izak@izak-System-Product-Name:~/DrawBoard$ time ./DrawBoard9193z
The Starting HashKey = 12888282270356907191
Number of nodes depth (1) = 20
Number of nodes depth (2) = 400
Number of nodes depth (3) = 8902
Number of nodes depth (4) = 134318
Number of nodes depth (5) = 1800765
Number of nodes depth (6) = 20274733
Number of nodes depth (7) = 3195901860
Number of the hashnodes = 2639179443
The Ending HashKey = 12888282270356907191
Number of Hashhits = 1040030
Perft Count = 22219138
Hash Collision = 0

real	0m6.933s
user	0m6.812s
sys	0m0.118s
izak@izak-System-Product-Name:~/DrawBoard$ 
hmm... okay i see depth 7 is correct,this is all i am interested in now,see the previous depths's nodes are incorrect,but that's a small problem :)
I am very happy!
Now time to benchmark and get excited!

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

Re: Idea to virtually zero hash collisions

Post by Peterpan » Sun Mar 20, 2016 8:35 pm

and this version also works now,the other one mentioned in previous post!

Code: Select all

izak@izak-System-Product-Name:~/DrawBoard$ time ./DrawBoard9117h
The Starting HashKey = 12618288114827198257
Number of nodes depth (1) = 20
Number of nodes depth (2) = 400
Number of nodes depth (3) = 8902
Number of nodes depth (4) = 135450
Number of nodes depth (5) = 1815271
Number of nodes depth (6) = 20487774
Number of nodes depth (7) = 3195901860
Number of the hashnodes = 2633504779
The Ending HashKey = 12618288114827198257
Number of Hashhits = 1046453
Perft Count = 22447817
Hash Collision = 0

real	0m4.539s
user	0m4.495s
sys	0m0.041s
izak@izak-System-Product-Name:~/DrawBoard$ 

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

Re: Idea to virtually zero hash collisions

Post by Peterpan » Sun Mar 20, 2016 8:53 pm

Initial position depth 9 !! with 8 gigs hash!

Code: Select all

izak@izak-System-Product-Name:~/DrawBoard$ time ./DrawBoard9118h
The Starting HashKey = 12618288114827198257
Number of nodes depth (1) = 20
Number of nodes depth (2) = 400
Number of nodes depth (3) = 8902
Number of nodes depth (4) = 163233
Number of nodes depth (5) = 2514061
Number of nodes depth (6) = 39901584
Number of nodes depth (7) = 276728082
Number of nodes depth (8) = 2764546866
Number of nodes depth (9) = 2439530234167
Number of the hashnodes = 2358536726592
The Ending HashKey = 12618288114827198257
Number of Hashhits = 204329222
Perft Count = 3083863148
Hash Collision = 0

real	11m20.402s
user	11m15.236s
sys	0m4.751s
izak@izak-System-Product-Name:~/DrawBoard$ 


Post Reply