Move ordering improvements

[Howard E]

Just some queries about the history of move ordering techniques.

1. Are there improvements yet to be discovered?
2. What have been the major breakthroughs in this part of chess programming?
3. What persons do you believe have contributed the most in this area?

[hyatt]

Just some queries about the history of move ordering techniques.

1. Are there improvements yet to be discovered?
2. What have been the major breakthroughs in this part of chess programming?
3. What persons do you believe have contributed the most in this area?

Obviously the first was Greenblatt with the transposition/refutation table idea.

First I heard of Killer moves was from Slate/Atkin in their Chess Skill in Man and Machine chapter on chess 4.x

History heuristic comes from Schaeffer so far as I know. He published a paper describing this in the JICCA.

The first two seem to be the mainstays of today's programs, not sure who uses the history heuristic today. I used to but as the depths went up it began to help less and less.

[armand]

I was wondering about the History Heuristics as well, so rather than opening a new topic, I'd like to ask a few questions here:

- HH seems a more general case of Killer Moves, wouldn't they be preferred over KM?
- at what ply depth do they start to become irrelevant? 6? 8?
- should they be considered for non-captures only?

[hyatt]

The problem with HH is that the table of counters is very small, and the numbers in the table simply get way out of control at today's speeds and depth. Killer moves are a local idea, since they are applied locally in the tree near positions where they were first discovered. History moves are more general. In fact, almost too general.

[BB+]

Just some queries about the history of move ordering techniques.
1. Are there improvements yet to be discovered?

Wow, there's an unanswerable question. At the risk of being a pessimist, I would say no, at least for large improvements. There was work by Schaeffer (also in his thesis) more than 2 decades ago about how to increment history counters (by depth, or depth*depth, or 2^depth), and the results showed it was likely irrelevant (though 2^depth was thought marginally best at the depths of those days). So fiddling with the specifics of history counters are unlikely to yield much. [I agree with Bob about why, though I never really thought of it as a local/global issue before]. I've never convinced myself that the "positional gain" aspects of Rybka/IvanHoe do all that much for move ordering (I forget even if they are used for this, outside qsearch). OTOH, move ordering is quite important in alpha-beta, so even a minor tweaking, if sufficiently better in general than what is there now, could be significant.

Schaeffer says the killer heuristic is a "special case" of the history heuristic (near end of Section III)-- he notes that Gillogly says it doesn't help, while Hyatt gets that it reduces tree size by as much as 80% (end of Section II).

Here is the full quotation of the former.

Note that the killer heuristic is just a special case of the history heuristic. Whereas the killer heuristic keeps track of one or two successful moves per depth of search, the history heuristic maintains the success for all moves at all depths. With the history heuristic, "killer" moves would earn high history scores. The generality of the history mechanism provides valuable ordering information at all nodes; not just those with "killer" moves.

[hyatt]

This got lost so I am doing it again...

In short, that quote by me is pretty well taken out of context. The reason I say that is that the context of the time was programs searching 5-6-7 plies deep, whereas today programs are searching 4x that deep. That changes a lot.

2^depth is unusable when depth can easily reach 50-60 in endgames. And even with numbers like 36-40, counters overflow terribly at today's NPS. Even depth*depth becomes problematic and needs a 64 bit counter. And going as deeply as we go today, the counters get pretty well whacked up.

Before I removed them completely, I took some "understandable" positions where there were a few good moves scattered around, and then dumped the counters and moves they represented. The numbers looked pretty random given a longish (2min+ search at 20M+ nodes per second). When I removed them I found absolutely no gain or loss, and anytime I can remove code without hurting speed or Elo, I do so for simplicity.

[BB+]

The reason I say that is that the context of the time was programs searching 5-6-7 plies deep, whereas today programs are searching 4x that deep. That changes a lot.

Yes, I fully agree. The historical nature of the discussion is of differing value that its modern implementation.

And even with numbers like 36-40, counters overflow terribly at today's NPS. Even depth*depth becomes problematic and needs a 64 bit counter.

The "fix" to this in Rybka 3 and environs is to make adjustments be scalable (not exactly a sigmoid, but of the same flavour).

Code: Select all

#define SHIFT 8
#define HISTORY_GOOD(move, depth) \
 { int sv = HISTORY_VALUE (POSITION , move); \
   HISTORY_VALUE (POSITION, move) = sv + (( (0xff00 - sv) * depth) >> SHIFT); \ [...]
[...]
#define HISTORY_BAD(move, depth)
  { int sv = HISTORY_VALUE (POSITION, move); \
    if (POS0->Value > VALUE - 50) \ # POS0->value is the positional evaluation
      HISTORY_VALUE (POSITION, move) = sv - ((sv * depth) >> SHIFT); }

So IvanHoe subtracts (depth/256) of the current history value when a move is bad. When a move is good, the "upper limit" is 0xff00 or 65280 [the "lower limit" being 0], and the difference of the current score to this is then scaled again by (depth/256) before adding it. Since all modifications are "multiplicative" as a percentage of the current value [or 65280 minus it], no overflow can occur. Admittedly, this only keeps the original "counter" sense as a concept, though good moves will definitely get better scores. The start values in IvanHoe are 0x800, or 2048, which leaves plenty of room for increase, and a fair bit for decrease.

R3 is essentially the same, though the numerology differs (and there are two history tables for bad history moves depending on the comparison of the scout value to the positional evaluation -- GCP was wondering about this, and recently I found that just "strings <rybka3-executable>" might already tell you such: history [0]: %d / (12*64) = %d and history [1]: %d / (12*64) = %d).

[hyatt]

That add/subtract idea is not new. You can find references to this in older versions of Crafty when I was playing around with the early "history pruning" idea (now called LMR). I am not sure that is a "fix" however. If you subtract too much, you get too many negative numbers, if you subtract too little, the numbers get large. I even tried a "zero" sum idea to keep all the counters limited to a overall sum. But after a ton of playing around I could find nothing worthwhile. That obviously doesn't mean there is no "good implementation". But I did do more than a "cursory attempt"... I had thought that some good history counter approach might make the "history pruning" effective. But no cigar. And then after noticing that any attempt made no improvement at all, I even removed HH ordering, and found that was a zero change as well. It doesn't do much to speed overall, since the selection sort is only tried for a few moves, but it did simplify the NextMove() code a bit.

I still think that even if the history counters become a zero-sum device, or a saturating counter approach, the significant depths we reach make moves that work at ply=2 worthless at ply=30. And vice-versa since the ply=30 moves most likely get updated much more frequently, yet the ply-2 moves are the ones most critical for move ordering.

[BB+]

I had thought that some good history counter approach might make the "history pruning" effective.

This was certainly all the craze when Fabien claimed success with it in Fruit. As for move ordering, after hash move, captures, and killer moves, I'm not sure there much to be gained from later ordering (as you say, the selection sort is rarely called).

I still think that even if the history counters become a zero-sum device, or a saturating counter approach, the significant depths we reach make moves that work at ply=2 worthless at ply=30. And vice-versa since the ply=30 moves most likely get updated much more frequently, yet the ply-2 moves are the ones most critical for move ordering.

Do you think it could be worthwhile to just use history counters at ply up to (say) 10 or 20?

[hyatt]

Really difficult to say. I actually tried a couple of variations.

1. Update history counters in early plies (tried several different "limits" here) but use them in all plies. This did not work well at all.

2. update and use only in the "early plies". But unfortunately I did not play much with this although it sounds like it might have some promise. But I was, at the time, trying to find a history counter approach that was worthwhile for LMR decisions. As I later posted, removing the history counter limit for LMR in fruit made no difference in Elo. I discovered this when Uri suggested that he had a better "history threshold" (I think he suggested 70) than the default. When I tried it, I found it was no better or worse. After I had been testing different ideas in Crafty for a month. And after discovering that no matter what I did with the counters (with respect to LMR) I could not make it play better, and could also not make it play worse unless I intentionally went to insane settings, which led me to see if varying the fruit setting made no difference. And the answer was no, so long as you didn't set the limit to a point that would effectively disable the reduction completely.

3. I even tried several sets of counters, one for early plies, one for late plies, as one example... But could not produce any improvement with that either...

4. I tried counters for black, counters for white, combined counters, and tried the <piece><to> index method as well as the <piece><to><from> (larger table). Nothing worked.

I seem to remember Vas saying something similar, that the idea was simply ineffective. But until all options are exhaustively tested and rejected, there is always hope, however slight...