Re: RMO - Randomized Move Order - yet another Lazy SMP derivate
Posted: Fri Jan 03, 2020 12:21 pm
ABDADA is good on paper, but Bread crumbs is better in the real worldDaniel Shawul wrote: ↑Thu Jan 02, 2020 11:41 pm I did some quick tests on a ryzen 3900x with 12-physical cores (24 threads but I used only 12) at tc 40/60
ABDADA beats plain SHT by a score of 10-3-15, and YBW beats ABDADA by a score of 9-6-9 so far.
Not so many games I know but It is clear to me YBW > ABDADA > SHT even at 12 threads.
Lazy SMP could definitely benefit from ABDADA ideas i.e. using transposition table to coordinate work-sharing
between threads rather than rely only on the threads searching at 2 depths. Michel mentioned about "Breadcrumbs" using ABDADA ideas -- I definitely agree threads working on the same depth could benefit from ABDADA ideas. Also, don't forget ABDADA is the original real lazy SMP implementation...so all this hype about lazy SMP is because stockfish uses it yikes! It happens to "widen" search somehow and helped it but it might not work in other engines which don't prune as heavily as stockifsh. Also, LazySMP is rather uninteresting for parallel search literature because it moves goal post to achieve something else ... The work should have been the same for all algorithms but LazySMP apparently changes selectivity even though I never tried it.
It adresses the problems of ABDADA which are:
1/ HT real estate: There is not a bit to waste on HT entries, no room for nproc. Need another table, preferable a much smaller one (see next point).
2/ Contention: HT is used (in a modern engine tuned for elo, not a toy engine) at every node, including qs nodes. So one needs to be careful with contention on hashEntry.nProc, especially as they have to be updated with atomic RMW operations (increment and decrement) with acquire/release ordering. So you want a smaller table of (key,nproc) and use it at high enough depths to minimise contention with large number of threads.
3/ Move ordering: Messiging around with move ordering is a very bad idea, in modern engines where move ordering is so massively fine tuned and path dependant. You just cannot mess up move ordering for the sake of SMP. I am ready to accept the superiority of ABDADA in toy engines where move ordering is deterministic (ie. no path dependance from history CMH etc.). And what about LMR and LMP ? ABDADA's re-ordering will completely screw that, which is worth hundreds of elo. But in real world modern engine, it's a terrible idea. Also, it messes up the codebase and introduces serious code smell (the logic of re-ordering moves). The Bread Crumbs solution of simply increasing the reduction is much superior. There is power in simplicity.