bob wrote:Sorting the other moves using the same approach doesn't seem as attractive.
Is there any reason to treat the root different from any other PV node?
(snip)
...it seems to me that what is good in the root, must be good in other PV nodes. The problem you are facing in those nodes is exactly the same.
There is indeed one difference: for ordering at the root you may well use e.g. a global array, that you keep overwriting during ID, while for ordering a PV node at ply>0 you have to find out a place to record the node count informations for _that_ node, to be used next time you visit it.
I think Tord wrote something on this issue, proposing a small (entrywise) hash table with extended informations, to be used only for PV nodes. I tried to figure out how to use this idea, but never really started implementing anything.
Have you got something like this in mind? Any tries?
bob wrote:Sorting the other moves using the same approach doesn't seem as attractive. The root move list has to be completely searched. at plies 2-3 most of those do not require this, and for many of them ordering is irrelevant anyway (ALL nodes). You could try it, but I think it will offer very little above hash, captures and killers that most already use inside the tree. Worth trying? Certainly. But high expectations? probably not.
Is there any reason to treat the root different from any other PV node? I can imagine that little can be gained in ALL or CUT nodes (either because the ordering doesn't matter at all, or because in most moves in ALL nodes are so poor that the refutation in the subsequent CUT node is trivial to find). But it seems to me that what is good in the root, must be good in other PV nodes. The problem you are facing in those nodes is exactly the same.
I think this is a reasonable idea to experiment with.
One way to implement this is to keep a very small hash table of "move lists" and whatever other context you need to go with it. It would be saved only at PV nodes and only the ones closest to the root (your rule would be to squeeze out shallow entries when you need more space.)
OK, I see the problem. There are two ways to solve this:
You could keep a special move stack where you keep the entire move list of all PV nodes, which you manipulate just like you would manipulate the PV through the tri-angular array method. The only difference would be that in stead of only storing the PV move in an element of that tri-angular array, you would store the entire (sorted) move list.
An alternative is to store the node count (or the log of the node count, to save some bits) of every sub-tree in the hash element for that sub-tree. When entering a PV node, you would start with hash probes for all daughter nodes, to retrieve the node counts, before sorting the list, and searching the moves at full depth.
bob wrote:Sorting the other moves using the same approach doesn't seem as attractive.
Is there any reason to treat the root different from any other PV node?
(snip)
...it seems to me that what is good in the root, must be good in other PV nodes. The problem you are facing in those nodes is exactly the same.
There is indeed one difference: for ordering at the root you may well use e.g. a global array, that you keep overwriting during ID, while for ordering a PV node at ply>0 you have to find out a place to record the node count informations for _that_ node, to be used next time you visit it.
I think Tord wrote something on this issue, proposing a small (entrywise) hash table with extended informations, to be used only for PV nodes. I tried to figure out how to use this idea, but never really started implementing anything.
Have you got something like this in mind? Any tries?
Cheers, Mauro
That is what I do in Gaviota. I have a [EDIT: dedicated extra] hash table that remembers moves and node counts. The idea gave me a slight ELO *decrease*, but I still have it in one developing branch because I think it deserves some tweaking and experimentation, which I did not do yet. I think it needs to be combined with something else to work. For instance, the ordering procedure should be dependent on depth. At the root we know it works because the node counts are somehow accurate. At the leaves, the node counts could be very noisy.
Miguel
Last edited by michiguel on Thu Jul 01, 2010 6:21 pm, edited 2 times in total.
bob wrote:Sorting the other moves using the same approach doesn't seem as attractive. The root move list has to be completely searched. at plies 2-3 most of those do not require this, and for many of them ordering is irrelevant anyway (ALL nodes). You could try it, but I think it will offer very little above hash, captures and killers that most already use inside the tree. Worth trying? Certainly. But high expectations? probably not.
Is there any reason to treat the root different from any other PV node? I can imagine that little can be gained in ALL or CUT nodes (either because the ordering doesn't matter at all, or because in most moves in ALL nodes are so poor that the refutation in the subsequent CUT node is trivial to find). But it seems to me that what is good in the root, must be good in other PV nodes. The problem you are facing in those nodes is exactly the same.
My only thought is that the root is the only node you can guarantee is a "PV" node, using aspiration search. When I tried the node-count at deeper plies, we are talking Cray Blitz days, where the depths were _much_ shallower than what we see today. That's the reason I suggested it was worth testing, as I have not tried it since 24+ plies became the norm. This may well be one of those ideas that works well early in the tree since the cost will be small.
bob wrote:Sorting the other moves using the same approach doesn't seem as attractive.
Is there any reason to treat the root different from any other PV node?
(snip)
...it seems to me that what is good in the root, must be good in other PV nodes. The problem you are facing in those nodes is exactly the same.
There is indeed one difference: for ordering at the root you may well use e.g. a global array, that you keep overwriting during ID, while for ordering a PV node at ply>0 you have to find out a place to record the node count informations for _that_ node, to be used next time you visit it.
I think Tord wrote something on this issue, proposing a small (entrywise) hash table with extended informations, to be used only for PV nodes. I tried to figure out how to use this idea, but never really started implementing anything.
Have you got something like this in mind? Any tries?
Cheers, Mauro
That is what I do in Gaviota. I have a hash table that remembers moves and node counts. The idea gave me a slight ELO *decrease*, but I still have it in one developing branch because I think it deserves some tweaking and experimentation, which I did not do yet. I think it needs to be combined with something else to work. For instance, the ordering procedure should be dependent on depth. At the root we know it works because the node counts are somehow accurate. At the leaves, the node counts could be very noisy.
Miguel
One possible draw-back. At the root, ordering by using "biggest tree first" has some merit, particularly if you have no intention of completing the search on the last iteration. There, you'd want to be sure to at least search candidate PV moves before bailing on time. But deeper in the search, one doesn't necessarily want to search the most complicated-looking move first, when probing for a cutoff. One wants to expend the least effort possible, instead. This was the idea behind ETC, for those that use or tried to use that idea. So I can, after thinking, see a potential issue with using node counts, since we want to search the move that will produce a cuttoff, -with the smallest tree- first.
bob wrote:Sorting the other moves using the same approach doesn't seem as attractive. The root move list has to be completely searched. at plies 2-3 most of those do not require this, and for many of them ordering is irrelevant anyway (ALL nodes). You could try it, but I think it will offer very little above hash, captures and killers that most already use inside the tree. Worth trying? Certainly. But high expectations? probably not.
Is there any reason to treat the root different from any other PV node? I can imagine that little can be gained in ALL or CUT nodes (either because the ordering doesn't matter at all, or because in most moves in ALL nodes are so poor that the refutation in the subsequent CUT node is trivial to find). But it seems to me that what is good in the root, must be good in other PV nodes. The problem you are facing in those nodes is exactly the same.
I think this is a reasonable idea to experiment with.
One way to implement this is to keep a very small hash table of "move lists" and whatever other context you need to go with it. It would be saved only at PV nodes and only the ones closest to the root (your rule would be to squeeze out shallow entries when you need more space.)
We simply made a very _large_ entry when we tried this in Cray Blitz. The entry was identified by the hash signature, and contained a move list and node count for each move. We were doing 10 ply searching, typically, and I think we tried this first just at ply 2, and then at 2 and 3 (we always did it at ply 1, as I do today).
But it seemed to hurt in general, but perhaps because we tried it at all ply-3 positions, rather than just those where alpha != beta-1...
The idea is that in a new iteration you will walk the old PV first, to get a new score for it at the tip, and then will try to find alternatives working from the tip down, to see if they are better. The earlier you find an improvement, the more favorable the window will be for which you have to make all other moves fail low. If you find a better PV move late in the move list, you will have wasted a lot of time searching the other moves with an artificially low alpha (and beta).
hgm wrote:The idea is that in a new iteration you will walk the old PV first, to get a new score for it at the tip, and then will try to find alternatives working from the tip down, to see if they are better. The earlier you find an improvement, the more favorable the window will be for which you have to make all other moves fail low. If you find a better PV move late in the move list, you will have wasted a lot of time searching the other moves with an artificially low alpha (and beta).
Sure. And we know that a "change of mind" is a roughly 15% probability event, at the root. And I can't imagine using node counts to override the first move searched at ply=2 for that best root move, where I would use a node count rather than the hash move to follow the PV.
So whether this will help or not is a subject for testing.
Say, on a related note, I remember a discussion about a year ago about trying to order the root moves based on number of beta cut-offs instead of number of nodes. Has this ever been tested?
