Alternatives to History Heuristics

[bob]

And another point is that when probability for move to cause cutoff goes below certain threshold it becomes advantageous to prune it.

Sure, if there was any reasonable way to recognize that. The current approach used (LMR) is based on the idea that at an ALL node, all moves much be searched and they are not going to cause a cutoff and change the ALL to a CUT. The more moves you search from an ALL node, the more sure you become it is really an ALL node and pruning is acceptable. But LMR is not based on specific move characteristics in general, but rather in the observation "the more moves you search from a node, the more likely it becomes that you will search them ALL".

[bob]

That is the point. If you would know, then why expand it at all? If not, so why not have a move ordering?

I do not understand what you are talking about. You mentioned "narrowing the window". I pointed out that is impossible in most programs today since almost everyone uses PVS. You do want to try ordering early, but the more moves you search without a cutoff, the more convinced you should become that there will be no cutoff.

[bob]

Another point is, that if (as in my SMIRF) there is done a prefiltering of moves by a slightly wider alpha beta window, there might be a narrowing effect by move ordering.

That doesn't "parse" for me so I can't comment. We were originally talking explicitly about an ALL node.

[hgm]

Still, I don't think you could beat Reinhard's algorithm: Just take an immediate fail low in every ALL node, without searching or generating any moves. How can you be faster than that?

Not only ordering the moves is a waste of time in all nodes. Searching them is a much bigger waste of time!

[bob]

Still, I don't think you could beat Reinhard's algorithm: Just take an immediate fail low in every ALL node, without searching or generating any moves. How can you be faster than that?

Not only ordering the moves is a waste of time in all nodes. Searching them is a much bigger waste of time!

If you'd make useful suggestions rather than bullshit, I might be interested. I do not _know_ which nodes are "ALL" nodes. So I search. But for each move I search at an ALL node and get a fail low result, I become more convinced that this really is an ALL node. And that's where LMR (The L means Late, for those that do not post nonsense, where the L is important for the very reason I gave above).

I'd think that it is quite intuitive to grasp the notion that a tree has a given size, in terms of nodes, and each node takes a given amount of time to search, depending on the effort expended inside that node to order the branches. Your silly implication is that tree _size_ is the only valid measure of performance, my observation was that you have to consider _both_ components. If you shrink the size of the tree by some percentage, but the cost per node goes up at a larger percentage, you lose ground and take longer to search. If you increase the size of the tree by some percentage, but the cost of handling a single node goes down by _more_ than that percentage, again you win.

There is a balancing point here. I explicitly tried the history heuristic, only for move ordering, a month or two back. I reported my results here. Adding Schaeffer's history ordering idea did shrink the size of the tree on average. But it also increased the cost of doing business at a node as well, and the net result was a loss of 4-5 Elo overall. Based on that, _I_ concluded it does not work. I removed it from a couple of other programs. Same conclusion. I also tested it as a trigger for LMR. Same conclusion. It just does not appear to work given the depths we reach today. The counters contain nonsensical values that are mostly random noise.

That is a _serious_ discussion of the issue, not some stupid remarks that have no technical merit at all. And it is backed up by a _huge_ number of test games, not a few hundred which only produces random noise for changes that are this small.

your serve...

[hgm]

I do not _know_ which nodes are "ALL" nodes. So I search.

Ah. Well, Reinhard did not _know_ which nodes are "ALL" nodes either. So he sorts...

The chance on a cutoff might go down as you get deeper into the move list, but apparently no down enouh to make you skip searching the moves. But searching, even at reduced depth (LMR), is still far more expensive than sorting. So it is not obvious at all that one should drop the sorting before giving up searching...

[bob]

I do not _know_ which nodes are "ALL" nodes. So I search.

Ah. Well, Reinhard did not _know_ which nodes are "ALL" nodes either. So he sorts...

The chance on a cutoff might go down as you get deeper into the move list, but apparently no down enouh to make you skip searching the moves.

Why would I skip 'em? I am doing a tree search. But I am willing to give up on expending effort to order them when all it does is actually slow the overall search down, not speed it up.

But searching, even at reduced depth (LMR), is still far more expensive than sorting. So it is not obvious at all that one should drop the sorting before giving up searching...

It is obvious to me. Dropping the sorting will not cause the search to miss a key (and hard to find) move. It just makes it take a little longer. So in those _rare_ cases where a good move occurs very late in the list, I won't overlook it and make a fatal mistake. Ordering affects every last node, particularly the ALL nodes, and it affects _every_ game. I'm trying to optimize for the general case of all games, not the specific case of one game where one key move occurs late in a move list somewhere. Yes, moving it up will help _that_ case. But the general case? probably hurts.

It is certainly easy enough to actually test the ideas over a large number of games, unless early results show a significant improvement or degradation. Then there is no guesswork as to whether an idea is good or bad overall.

Fortunately, for me at least, I have access to facilities that let me answer these questions with decimal point accuracy rather than a "this ought to work" approach. And quite often my "this ought to work" falls flat and has to be tossed out, even though it seemed intuitively good.

[hgm]

Well, all your facility proves is that you have not been able to find a good way to sort the moves. Not that such a way does not exist...

What is the ratio of cutoffs by a late move compared and the number of ALL nodes? How many moves do you have to search before you typically hit such a cut move now, and how many moves do you on average search in an ALL node? That should tell you how much there is to gain by sorting.

[Tord Romstad]

For Stockfish, maybe you guys could try putting higher in the movelist those pieces attacked by the null threat move. I'm curious if that idea is good.

I've tried it, a long time back. It didn't seem to work, but maybe I just didn't test sufficiently thoroughly.

[zamar]

My point, therefore, was that you have to be _very_ careful in the effort you expend to reduce that remaining 8-10% of the CUT/PV nodes, so that the cost of improving the ordering is not outweighed by the cost of the ordering itself.

I understand your point. However it's possible to use different ordering techniques near root and near leaves.

Another point is that because of history pruning (a bit misleading name: IMO late move pruning would be much better name) move ordering near leaves is important: it's not only question whether we find a cutoff move quickly or not - We might entirely miss the winning move if it is pruned away because was too late in the list!