lucasart wrote:Another thing about your simplified ABDADA: it only applies at root. Shouldn't the logic be applied at every node (perhaps with a min depth) ? This requires some data in TT entries, like how many threads are searching the hash move in this position. Or perhaps I'm reinventing ABDADA…
Yes.
The original implementation stores the number of threads that are working on a given node in the TT. As discussed in the other thread, you can get by with just storing if threads are searching the node (the exact number is not important). In this "simplified ABDADA" that information is stored in a separate table.
lucasart wrote:Another thing about your simplified ABDADA: it only applies at root.
Where do you see it only applies at root?
As I understand it Tom uses a separate small hash table (pos AND move hashed together) which he uses to postpone (defer) searching moves already searched by other threads (except for the first move).
This is only applied when depth >= limit (in this case 3).
It's a nice idea and should be trivial to implement and try.
I see. I misread the pseudo code.
So it's a separate hash table of (pos, move). So it's the same as ABDADA, except that you have a small, separate table for the (pos, move) -> nproc.
Now to make this scaable, you must ensure that low depth entries do not override high depth entries in long searches. So you need some form of overriding policy, accounting for depth, and perhaps node type (PV, All, Cut).
So I don't see the added value of this simplified ABDADA. May as well implement the real thing, and leverage on the already existing Hash override policy.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
I understood that you defer the search of moves already been searched by other thread.
Your code seems not able to prevent 2 thread to start searching the same move. Is this wanted? Or trying to avoid such Problem slow down too much the search??
elcabesa wrote:I understood that you defer the search of moves already been searched by other thread.
Your code seems not able to prevent 2 thread to start searching the same move. Is this wanted? Or trying to avoid such Problem slow down too much the search??
If that happens, the two threads will start helping eachother search the subtree, so it's not really a problem.
Basically you only want to search different moves in the same position once you are pretty sure it is an all-node. Otherwise one of the moves being searched could be a cut move, and make the search of all the others wasted time. (Especially when there is no way to abort searches.) So when you arrive in a node that is already being searched, and the search of the first few moves with a high cut potential has not been completed yet, you want to help in searching the move that is currently being searched. The cooperating threads will then diverge closer to the leaves, eventually combine their work through hash hits on each other's results, return the same score for the critical move, and perhaps can diverge then in the original node.
But it will need some adaptation to work. The main problem is that, with shared hashtable (aka lazy), you certainly don't want to have all threads searching the same depth, or running their own iterative deepening loop in a desynchronized manner. ...
I've never understood this about Lazy SMP, what's the point of having different threads search different depths?
What kind of speedups do you get on Hyatt's positions with your Lazy SMP implementation?
lucasart wrote:Another thing about your simplified ABDADA: it only applies at root.
Where do you see it only applies at root?
As I understand it Tom uses a separate small hash table (pos AND move hashed together) which he uses to postpone (defer) searching moves already searched by other threads (except for the first move).
This is only applied when depth >= limit (in this case 3).
It's a nice idea and should be trivial to implement and try.
I see. I misread the pseudo code.
So it's a separate hash table of (pos, move). So it's the same as ABDADA, except that you have a small, separate table for the (pos, move) -> nproc.
Now to make this scaable, you must ensure that low depth entries do not override high depth entries in long searches. So you need some form of overriding policy, accounting for depth, and perhaps node type (PV, All, Cut).
So I don't see the added value of this simplified ABDADA. May as well implement the real thing, and leverage on the already existing Hash override policy.
Not really. Let's say you have 16 threads and they're searching 50 moves each, which seems unlikely but let's consider this worst-case scenario for the sake of argument. So you have a total of 800 moves that you have to store in your "currently-searching" hash table. If your hash table is 2^20 entries, it'll only be 0.07% full. The odds of a hash collision when inserting a new move are 1 in 1310. So it doesn't seem like something you'd have to worry about too much. But if you are worried about collisions, it would be trivial to change the hash table code so that nothing ever gets overwritten. I think that would add 10-15 lines of code to the pseudocode that I've posted. But again, I don't think this is a problem that needs to be solved. The worst thing that happens if there's a collision is that multiple threads search the same move at the same time, which just means that the move gets searched faster.
lucasart wrote:Another thing about your simplified ABDADA: it only applies at root. Shouldn't the logic be applied at every node (perhaps with a min depth) ? This requires some data in TT entries, like how many threads are searching the hash move in this position. Or perhaps I'm reinventing ABDADA…
I dont see how any root only rule can be scalable at long tc.
Can you tell me what it was about my explanation and/or pseudocode that gave you the impression that the technique only applies at the root? Maybe there's something I can do to make that more clear. Although I don't know what. The word "root" isn't even mentioned on those pages.
lucasart wrote:Another thing about your simplified ABDADA: it only applies at root. Shouldn't the logic be applied at every node (perhaps with a min depth) ? This requires some data in TT entries, like how many threads are searching the hash move in this position. Or perhaps I'm reinventing ABDADA…
Yes.
The original implementation stores the number of threads that are working on a given node in the TT. As discussed in the other thread, you can get by with just storing if threads are searching the node (the exact number is not important). In this "simplified ABDADA" that information is stored in a separate table.
Indeed, note that the original ABDADA paper called for this field (that stores the number of threads searching a move) but never used the actual number for anything, just to check to see if ANY threads were searching a move.
I think the idea was that for systems with a huge number of threads, you would get into situations where ALL the moves are already being searched, so you would use nproc to intelligently pick which move to search next (i.e., the one with the fewest threads already searching it). But that's something for the future...
hgm wrote:Basically you only want to search different moves in the same position once you are pretty sure it is an all-node. Otherwise one of the moves being searched could be a cut move, and make the search of all the others wasted time. (Especially when there is no way to abort searches.) So when you arrive in a node that is already being searched, and the search of the first few moves with a high cut potential has not been completed yet, you want to help in searching the move that is currently being searched. The cooperating threads will then diverge closer to the leaves, eventually combine their work through hash hits on each other's results, return the same score for the critical move, and perhaps can diverge then in the original node.
Interesting idea, have the threads cooperate to search the first few moves and then divide up the rest of the moves between the threads. This is very easily accomplished with ABDADA: don't allow the first few moves to be deferred.
I just did a couple of tests, and not allowing the 2nd move to be deferred resulted in a small but measurable improvement. Not allowing the 3rd move to be deferred resulted in a fairly significant slowdown though.
I'm heading out to lunch now but will look at this idea more later. If I end up changing my code to add this improvement, is that okay with you? Would you like to be credited in the pseudocode file? And if so, how? Thanks!
