Parallel Search to Fixed Depth

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
brianr
Posts: 249
Joined: Thu Mar 09, 2006 2:01 pm

Parallel Search to Fixed Depth

Post by brianr » Sun Jan 17, 2016 3:15 pm

I understand that parallel search is not deterministic the way a single thread fixed depth search is.

However, I was just wondering if a fixed depth parallel search should be expected to produce the same score using different numbers of threads. Very limited testing with the newest and an older Crafty give different scores. Crafty's parallel search has been significantly improved recently, so at first I thought perhaps there was something there. I think both versions were JA compiles.

I would think fixed depth would eliminate timing differences resulting in some threads searching a bit deeper than others. I was also expecting fixed depth to rule out extensions to deeper depths in some threads with different scores getting backed up.

Thank you for your insights.

elcabesa
Posts: 679
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Parallel Search to Fixed Depth

Post by elcabesa » Sun Jan 17, 2016 3:21 pm

I think that the parallel search is not deterministic. so you have diferent node count even trying fixed depth searches.

this happen because at some point of the search you split the search and search different nodes in parallel, when the best node has benn found the other threads are stopped, and since they are in different thread they could have searche a little more or less each time.

bob
Posts: 20348
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Parallel Search to Fixed Depth

Post by bob » Sun Jan 17, 2016 4:11 pm

brianr wrote:I understand that parallel search is not deterministic the way a single thread fixed depth search is.

However, I was just wondering if a fixed depth parallel search should be expected to produce the same score using different numbers of threads. Very limited testing with the newest and an older Crafty give different scores. Crafty's parallel search has been significantly improved recently, so at first I thought perhaps there was something there. I think both versions were JA compiles.

I would think fixed depth would eliminate timing differences resulting in some threads searching a bit deeper than others. I was also expecting fixed depth to rule out extensions to deeper depths in some threads with different scores getting backed up.

Thank you for your insights.
No. things are searched in a different order, reductions can be applied differently if you are not careful about order, hash table graph history interaction affects the search significantly, etc. BTW new and old crafty versions also have eval changes as well. But if you take the same version and let it search to the same depth, quite a few positions will cough up different scores... And the more threads you use, the merrier:

same position (wac2) searched to depth 20, 20 cores:

log.001: 20-> 0.40 -5.49 1. ... Rxb2 2. Rxb2 c3 3. Rb6+ Ke7 4. Rb7+
log.002: 20-> 0.57 -5.63 1. ... Rxb2 2. Rxb2 c3 3. Rb6+ Ke7 4. Rc6
log.003: 20-> 0.65 -5.82 1. ... Rxb2 2. Rxb2 c3 3. Rb6+ Ke7 4. Kf2
log.004: 20-> 0.59 -5.68 1. ... Rxb2 2. Rxb2 c3 3. Rb6+ Ke7 4. Rb7+
log.005: 20-> 0.67 -5.70 1. ... Rxb2 2. Rxb2 c3 3. Rb6+ Ke7 4. Rc6

Post Reply