"Simplified ABDADA" updated

[nionita]

Hi Tom,

Many thanks for the write up!

I followed your ideas and implemented simplified ABDADA in Barbarossa (up to step 6, but without cutoff checks yet). I skipped some of the preparation steps which were meant basically to make sure the implementation is correct so far.

In my own tests I got ~80 Elo for 2 cores, which is in accordance with the theory. Not sure how it scales further, I will need more tests.

The multi threading Barbarossa will be used in next HGM tournament.

There were some technical complications with:
- LMR: when I defer a move, it will be played at the end with the "later" reduction (not sure if this is correct)
- re-search (because I use PVS): I think you already stated that in this case the "currently searching" of that move should be deleted, so that other threads eventually help with the re-search: I implemented this idea, but I'm not sure if it is quite correct or if it has any effect without synchronization between threads

[TomKerrigan]

Hi Tom,

Many thanks for the write up!

I followed your ideas and implemented simplified ABDADA in Barbarossa (up to step 6, but without cutoff checks yet). I skipped some of the preparation steps which were meant basically to make sure the implementation is correct so far.

In my own tests I got ~80 Elo for 2 cores, which is in accordance with the theory. Not sure how it scales further, I will need more tests.

The multi threading Barbarossa will be used in next HGM tournament.

That's great! I'm glad it's working well and that you (presumably) found it useful!

There were some technical complications with:
- LMR: when I defer a move, it will be played at the end with the "later" reduction (not sure if this is correct)

I haven't tried LMR (I know, I know) but I suspect this isn't correct. What you could do is, as you're deferring the move, record the depth that you WOULD have searched the move at.

- re-search (because I use PVS): I think you already stated that in this case the "currently searching" of that move should be deleted, so that other threads eventually help with the re-search: I implemented this idea, but I'm not sure if it is quite correct or if it has any effect without synchronization between threads

Here's the rationale: when you mark a move as currently being searched, the theoretical idea is that you're dividing up work between threads, but the PRACTICAL effect of doing that is to make other threads search that move later.

When you're re-searching a move because of a null-window failure, that means the move is very likely to fail high or at least change alpha, so that's important search information that every thread should ideally know before searching any subsequent move. So the last thing you want your threads to do is skip over the move that's failing. So that's why it shouldn't be marked as currently being searched.

So that's the theoretical explanation. In practice, the benefit is small but measurable with my chess engine. Hope this helps!

[nionita]

I haven't tried LMR (I know, I know) but I suspect this isn't correct. What you could do is, as you're deferring the move, record the depth that you WOULD have searched the move at.

Ok, I will have to try this. I was thinking that, when you defer a move, chances are high that when you come to search it, there is a TT entry for it, and that should have the correct depth anyway, as it was searched in the same position, but not deferred.

But of course if the search in the first thread was not finished at that time then this is not the case. It is hard to understand all implications of this concurrent search... I guess best approach is to try both variants and take the best.

[jcw66]

Thanks for enhancing this old parallel search! I hope you find it usefull.

[TomKerrigan]

Thanks for enhancing this old parallel search! I hope you find it usefull.

Great to hear from you and thank you so much for developing the original algorithm!

I think almost anything that's self-synchronizing is terrific. Self-synchronizing Young Brothers Wait is a stroke of genius.