Possible improvement to ABDADA -- checking for cutoffs

[TomKerrigan]

It's been a while since I last participated in a chess message board. I'd like to say hello to everybody (again, in some cases) and that it's nice to be back!

I implemented YBWC in my chess engine years ago but recently I got interested in multithreading again and implemented ABDADA on a whim and have been playing with that over the past few days.

The speedup from ABDADA is interesting because of how simple it is to implement, but not as good as YBWC, which I think is the expected result.

On 16 cores, I get a 5.12x speedup with ABDADA vs. a 6.31x speedup with YBWC. This is based on overall time-to-depth on the Bratko-Kopec positions.

Here's the biggest weakness I see with the ABDADA algorithm: you have two threads searching the same node. One thread starts searching a move, so the other thread skips it and puts it in a "deferred list" to be searched later, after all the other moves. So what if that move causes a beta cutoff? The 2nd thread has to search every other move before it gets back to the one that caused the cutoff--ALL of that is completely wasted work.

So, here's my simple improvement (which I haven't seen proposed anywhere else):

In the search function, at the beginning of the move loop, if any moves have been deferred, check the hash table to see if there was a beta cutoff at the current node. Then you can just return the score you got from the hash table and you waste minimal work searching other moves.

Doing this gives my engine a varying amount of improvement, and usually closes the gap between ABDADA and YBWC by about 50%. In the 16-thread example, it increases performance from 5.12x to 5.5x, which is 30% of the way to closing the gap.

The only disadvantage of this idea is that it increases the number of probes to the hash table. This could be disastrous to performance depending on the design of your system--certainly it was something they wanted to minimize in the original ABDADA implementation/paper. But in a modern shared-memory PC the overhead isn't too bad. It can also be controlled by only doing these checks at certain depths. And it can be controlled by having a special function to check the hash table without locking it first, to eliminate possible lock contention.

According to my measurements, I didn't find any negative performance impact due to this optimization. In fact, my searches all ran somewhat faster in terms of nodes/second. I could speculate about why this might be but I don't think it really matters. The optimization is simple enough that if you're using ABDADA, you might as well try it and see how it works for you.

With the optimization, this brings ABDADA much closer to YBWC performance but with a fraction of the implementation difficulty and complexity overhead. If I were a programmer who hadn't implemented parallel search yet, I would seriously consider just doing ABDADA with this optimization rather than bothering with YBWC.

[kranium]

Hi Tom-

Welcome back!
I recognized the name instantly, as your TSCP is a legend...

Michael Sherwin has been posting recently, isn't he the one that added bitboards to it?
The whole thing was (and still is to many I'm sure) quite instructional, thanks for sharing it all those years ago.

Best Regards-
Norm

[Rebel]

Hey Thomas.

[TomKerrigan]

Hi Norman,

Thank you for the warm welcome.

Yes, Michael Sherwin did do a bitboard version of TSCP which you can download from my page here, along with a bunch of other stuff that many other people have contributed to the project!

http://www.tckerrigan.com/Chess/TSCP/Community/

Thanks,
Tom

[TomKerrigan]

Hey Ed, good to "see" you again.

[Daniel Shawul]

Note that the original implementation of ABDADA is on a distributed machine so reducing the number of costly hash probes was important then, and is also now. If you probe the parent node TT entry every time you grab a move the cost of probes will increase by 2x times.

[TomKerrigan]

True, but as I mentioned towards the bottom of my post, you can control the number of probes vs. the gain to search efficiency by only probing when depth is greater than some number that you specify/control.

The improvement only takes a few lines of code and a few minutes to implement so it's probably worth trying. As I said in my original post, I saw a definite improvement from it.