Alternatives to History Heuristics

[Tord Romstad]

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

Not only possible -- I think it is probably a very useful thing to do. Different move ordering at PV and non-PV nodes is also worth trying. Using root-like move ordering at internal PV nodes with a big remaining depth has been on my todo list since a couple of years now.

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!

Yes, this is a very important point.

[Zach Wegner]

Not only possible -- I think it is probably a very useful thing to do. Different move ordering at PV and non-PV nodes is also worth trying. Using root-like move ordering at internal PV nodes with a big remaining depth has been on my todo list since a couple of years now.

I thought you had already tried that, using a hash table?

[michiguel]

Not only possible -- I think it is probably a very useful thing to do. Different move ordering at PV and non-PV nodes is also worth trying. Using root-like move ordering at internal PV nodes with a big remaining depth has been on my todo list since a couple of years now.

I thought you had already tried that, using a hash table?

No, we had a discussion about it...

Miguel

[bob]

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.

Simple. I added a trivial bit of code so that Crafty would answer the following three questions cumulatively thru the first few moves of a normal game from a normal starting position from my cluster test set (starts 12 moves into the game, and accumulates the totals for 5 moves and then prints them and exits.)

1. What percent of all fail high conditions happen on the _first_ move (I am excluding the q-search here as that distorts the number upward significantly. So here I only include "full-width nodes" in any of these totals, which are the nodes where move ordering decisions like history and such might be useful). Answer: 92% average.

2. What percent of all fail high conditions happen while I am searching the well-ordered part of the moves (hash first, then non-bad SEE captures, then 2 killers). Whatever this is means that the remaining fail highs occur in the rest of the moves where I do ordering only based on moving advanced pieces first, and moving them to more advanced squares first, as that is how they are generated). Answer: 95%. So To re-order the remaining moves, there is the potential for picking up some fraction of that 5%, although obviously nowhere near all of it

3. What is the total cutoffs by first move searched, second move searched, ..., last move searched? This is a big table that looks like this:

Code: Select all

  0- 15:  32594507    1560828     422503     172914     106243      78280      65414      57394      50396      43542      36508      32766      30324      27882      25807      23766  
 16- 31:     21823      18893      17161      15276      13886      13125      12314      11403      10653       9509       8861       8258       7163       6366       5639       4949  
 32- 47:      4362       3738       3176       2563       2110       1585       1223        934        700        525        341        230        178        114         68         42  
 48- 63:        24         25         16          7          7          1          2          2          1          1          0          0 

Note that the above numbers come from a non-tactical test. Just a normal position, with normal moves to be made, no wild capture solution or anything.

One other interesting note. On the first search, I noticed that 92% of the fail highs were on the first move searched. But when I measured question #2, I discovered that only 74% of those fail highs were from hash, capture and killer moves. The remaining 18% of the fail high on first move cases were simply caused by the first move generated. This is a typical result of a null-move search, where you are material ahead in some strange path, and any move is good enough to fail high and get you out of there.

You say "my facility proves I have not been able to find a good way to sort the moves." I would claim that it has proven that most "sorting approaches" are simply no good, and if they incur any significant cost, even the simplistic idea of delta-piece-square-table values has a cost since you have to either do this once for every move, or use a selection sort which does it for every move tried by passing over the move list N times if it contains N moves, assuming you do not get a cutoff along the way.

As always, size doesn't necessarily count. Here it is all about time, not size.

Feel free to compare your results to mine. These searches were about 300M nodes each, for reference. If I count q-search fail highs, the percentage goes to 99%+, which is not very meaningful, although q-search is the biggest contributor of nodes obviously.

edit:

just realized I did not explain that table above. the first line, labelled 0-15, represents the first 16 moves searched. If the cutoff occurred on the first move (move zero in my way of counting) then the first value gets incremented. If the fail high occurs on the second move, the next value gets incremented. Add 'em all up and you get the total number of fail highs in the non-qsearch part of the tree. Each individual number tells how many times the Nth move was the move that caused this fail high.

[bob]

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!

Been there, done that, got the T-shirt. I tried this idea when I played with LMR for about 2-2.5 months earlier this year. I found no variation of ordering and then using a variable LMR counter so that you would reduce after N moves for PV nodes, M moves for non-PV nodes, or don't reduce M moves near the root and don't reduce N moves near the tips, etc.

The idea sounded good. And we had lots of ideas on how to make this test, from using a full evauation at each interior node, to a faster eval that did less work but still gave a reasonable approximation to the score without doing the more expensive mobility stuff and such. None of the ideas we tried, and we tried dozens, made any improvement in real game testing. Not a one. When 23.1 comes out, you can compare the LMR code to 23.0 and you will find no changes. I did find a few forward-pruning ideas that were more of an extension to futility/extended-futility/razoring than anything else. But nothing helped to improve LMR beyond the tests I was already doing.

As far as missing things goes, either you prune or you don't. Perfect pruning is inherently impossible. So errors will happen. The thing everyone overlooks is the net effect of a search with some known errors might be a better player, because we have to play full games. 2 plies deeper on every move, even if you make one gross error every 100 moves, still gives you an Elo gain. Because on 99 of the moves you play much stronger.

[Edsel Apostol]

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!

Been there, done that, got the T-shirt. I tried this idea when I played with LMR for about 2-2.5 months earlier this year. I found no variation of ordering and then using a variable LMR counter so that you would reduce after N moves for PV nodes, M moves for non-PV nodes, or don't reduce M moves near the root and don't reduce N moves near the tips, etc.

The idea sounded good. And we had lots of ideas on how to make this test, from using a full evauation at each interior node, to a faster eval that did less work but still gave a reasonable approximation to the score without doing the more expensive mobility stuff and such. None of the ideas we tried, and we tried dozens, made any improvement in real game testing. Not a one. When 23.1 comes out, you can compare the LMR code to 23.0 and you will find no changes. I did find a few forward-pruning ideas that were more of an extension to futility/extended-futility/razoring than anything else. But nothing helped to improve LMR beyond the tests I was already doing.

As far as missing things goes, either you prune or you don't. Perfect pruning is inherently impossible. So errors will happen. The thing everyone overlooks is the net effect of a search with some known errors might be a better player, because we have to play full games. 2 plies deeper on every move, even if you make one gross error every 100 moves, still gives you an Elo gain. Because on 99 of the moves you play much stronger.

Hi Bob,

Since I'm already convinced way before that history heuristic is not good, I will remove it as what I have planned and just rely on the order on which I generate them (using PST I think is just too costly as I will have to scale both sets of PST values according to game phase). Can you please elaborate further in what order you generate your non tactical moves? In my engine I do it by piece type, I generate pawns first, then knights, then bishops, etc..

Have you done tests like putting castling and interesting moves in the top of the movelist?

Your engine may not benefit from ordering the remaining 8% that may cause a cutoff but in my engine it is very important as the move ordering will decide which ones to reduce. That means when interesting moves is way down the move list my engine will tend to miss a lot of winning chances.

I also believe just like you that the less code, the more simple it is, the better. That's why my entire eval including pawn eval and the constant declaration of weights that's around 70 lines is only 600 lines.

[Michael Sherwin]

Hi Edsel,

If remaining depth > 6 Romi actually makes each remaining move, calls Eval() and uses that value to order the moves. Otherwise Romi uses PST to order the moves all the way to depth 1. Maybe I can speed Romi up some by doing it Bob's way if depth < n. I will try it.

Well it is just a little bit more complicated than the above, so I am posting the code.

Code: Select all

__inline
void AddMoves(trees *t, s32 depth) {
  s32 id;
  s32 cid;
  u64 indexs;
  u64 toSqs;
  
  indexs = wtm ? wIndexs & ~WLEGALbit : bIndexs & ~BLEGALbit;
  while(indexs) {
    id = FirstBit(indexs);
    indexs &= clrBit[id];
    toSqs = h->moves[id];
    while(toSqs) {
      t->fs = piece[id].sq;
      t->ts = FirstBit(toSqs);
      t->typ = piece[id].typ;
      toSqs &= clrBit[t->ts];
      if(depth > 6) {
        MakeMove((moves *)t);
        t->score = Eval();
        TakeBack();
        if(((h-1)->attacked & setBit[t->ts]) && ((h-1)->ts != t->ts))
          t->score -= (piece[id].val / 2);
      } else {
        t->score = piece[id].tbl[t->ts];
        t->score -= piece[id].tbl[t->fs];
        cid = board[t->ts];
        t->score += piece[cid].val;
        if(((h-1)->attacked & setBit[t->ts]) && ((h-1)->ts != t->ts))
          t->score -= (piece[id].val / 2);
      }
      t++;
    }
  }
  (h+1)->t = t;
}

[Edsel Apostol]

Hi Edsel,

If remaining depth > 6 Romi actually makes each remaining move, calls Eval() and uses that value to order the moves. Otherwise Romi uses PST to order the moves all the way to depth 1. Maybe I can speed Romi up some by doing it Bob's way if depth < n. I will try it.

Well it is just a little bit more complicated than the above, so I am posting the code.

Code: Select all

__inline
void AddMoves(trees *t, s32 depth) {
  s32 id;
  s32 cid;
  u64 indexs;
  u64 toSqs;
  
  indexs = wtm ? wIndexs & ~WLEGALbit : bIndexs & ~BLEGALbit;
  while(indexs) {
    id = FirstBit(indexs);
    indexs &= clrBit[id];
    toSqs = h->moves[id];
    while(toSqs) {
      t->fs = piece[id].sq;
      t->ts = FirstBit(toSqs);
      t->typ = piece[id].typ;
      toSqs &= clrBit[t->ts];
      if(depth > 6) {
        MakeMove((moves *)t);
        t->score = Eval();
        TakeBack();
        if(((h-1)->attacked & setBit[t->ts]) && ((h-1)->ts != t->ts))
          t->score -= (piece[id].val / 2);
      } else {
        t->score = piece[id].tbl[t->ts];
        t->score -= piece[id].tbl[t->fs];
        cid = board[t->ts];
        t->score += piece[cid].val;
        if(((h-1)->attacked & setBit[t->ts]) && ((h-1)->ts != t->ts))
          t->score -= (piece[id].val / 2);
      }
      t++;
    }
  }
  (h+1)->t = t;
}

Hi Michael,

I am familiar with your code as I have read it before (3 or 4 years ago). Doing eval after making the move may be too expensive for my engine. I know Romi has next to nothing eval calculation cost (very very fast) so it is not an issue with it.

Have you measured the performance gain of using that compared to just using history values for all depths?

I'm also interested in this:

Code: Select all

if(((h-1)->attacked & setBit[t->ts]) && ((h-1)->ts != t->ts)) 
          t->score -= (piece[id].val / 2); 

Is that a penalty for putting the moving piece to the squares attacked by the opponent except when it is a recapture?

Are you also using that AddMoves function to order captures?

By the way, I also have tried not using history ( afew hours ago) and just search them in the order on which they are generated just like what Bob has mentioned but it seems not to perform better than the one using history in my blitz test. I think that history is still useful when playing in blitz as it would still contain some relevant information. The problem with it is that it isn't reliable anymore when used in longer time controls.

[mcostalba]

The problem with it is that it isn't reliable anymore when used in longer time controls.

This is another problem. It is how to control the aging of history: scaling down values when they are too big, use two or more history tables, one for high depths and the other for low depths so to avoid the first get randomized by low depth entries, etc.

But we still have to find a satisfactory solution.

It is true that after a while history loses useful info, but the key here IMHO is to find a way to make that 'while' stay longer instead of trashing the whole history idea.

[bob]

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!

Been there, done that, got the T-shirt. I tried this idea when I played with LMR for about 2-2.5 months earlier this year. I found no variation of ordering and then using a variable LMR counter so that you would reduce after N moves for PV nodes, M moves for non-PV nodes, or don't reduce M moves near the root and don't reduce N moves near the tips, etc.

The idea sounded good. And we had lots of ideas on how to make this test, from using a full evauation at each interior node, to a faster eval that did less work but still gave a reasonable approximation to the score without doing the more expensive mobility stuff and such. None of the ideas we tried, and we tried dozens, made any improvement in real game testing. Not a one. When 23.1 comes out, you can compare the LMR code to 23.0 and you will find no changes. I did find a few forward-pruning ideas that were more of an extension to futility/extended-futility/razoring than anything else. But nothing helped to improve LMR beyond the tests I was already doing.

As far as missing things goes, either you prune or you don't. Perfect pruning is inherently impossible. So errors will happen. The thing everyone overlooks is the net effect of a search with some known errors might be a better player, because we have to play full games. 2 plies deeper on every move, even if you make one gross error every 100 moves, still gives you an Elo gain. Because on 99 of the moves you play much stronger.

Hi Bob,

Since I'm already convinced way before that history heuristic is not good, I will remove it as what I have planned and just rely on the order on which I generate them (using PST I think is just too costly as I will have to scale both sets of PST values according to game phase). Can you please elaborate further in what order you generate your non tactical moves? In my engine I do it by piece type, I generate pawns first, then knights, then bishops, etc..

Have you done tests like putting castling and interesting moves in the top of the movelist?

Your engine may not benefit from ordering the remaining 8% that may cause a cutoff but in my engine it is very important as the move ordering will decide which ones to reduce. That means when interesting moves is way down the move list my engine will tend to miss a lot of winning chances.

I also believe just like you that the less code, the more simple it is, the better. That's why my entire eval including pawn eval and the constant declaration of weights that's around 70 lines is only 600 lines.

I do castle moves first, then knight, bishop, rook, queen, king and finally pawn moves. For any piece type, I pick the most advanced piece first, and generate moves to the most advanced square first.