Alternatives to History Heuristics

[bob]

By the way, what I don't like with History is that as the time spent on search increases, the randomness of the values contained in the history table also increases, and I don't want to trust that value.

It's really ugly isn't it? I hate that too. I use what works best at the levels I test at! And I assume this is better than nothing at all.

I have seen 3 flavors of history tables. <piece><to>, a 512 entry table. <from><to>, a 4096 entry table, <piece><from><to> a 32,768 entry table.

As an example, since those sources are handy, stockfish/glaurung uses the first example. I think that is probably the worst possible case. If Nf3xe5 fails high and gets entered, later in the tree do I really want to try moves like Nc4-e5? Or Re1-e7 fails high, do I really want to try moves like Re8-e7, or Ra7-e7 first, just because the original Re1-e7 failed high? For shallow searches, maybe. But not for 20+ ply searches.

The history numbers begin to become almost purely random after a couple of minutes of very deep searching at speeds of 20M nodes per second. I think the latter example with 32768 entries has the best hope, at least you keep trying the same piece from the same square to the same square, but is such a move played at ply 2 and failing high going to mean that playing the same move at ply 30 will have the same result?

The idea looks hopeless to me, and I have yet to find an approach that actually improves cluster test results. Most hurt, the rest didn't help. Not that it can't be made to work, but I have tried every idea ever mentioned here, and some that have not been mentioned, all with the same bad overall result. Some seemed to be quite reasonable, until you shine the "cluster light" on them.

[Don]

By the way, what I don't like with History is that as the time spent on search increases, the randomness of the values contained in the history table also increases, and I don't want to trust that value.

It's really ugly isn't it? I hate that too. I use what works best at the levels I test at! And I assume this is better than nothing at all.

I have seen 3 flavors of history tables. <piece><to>, a 512 entry table. <from><to>, a 4096 entry table, <piece><from><to> a 32,768 entry table.

As an example, since those sources are handy, stockfish/glaurung uses the first example. I think that is probably the worst possible case. If Nf3xe5 fails high and gets entered, later in the tree do I really want to try moves like Nc4-e5? Or Re1-e7 fails high, do I really want to try moves like Re8-e7, or Ra7-e7 first, just because the original Re1-e7 failed high? For shallow searches, maybe. But not for 20+ ply searches.

With every draw-back comes some advantages. I'm not defending it, but I want to point out that you do get better generalization. With <from><to>, you are not covered if Bb5 is a great move, regardless of whether it comes from f1, e2, d3, c4 etc. Of course I fully understand the drawbacks too.

But for move ordering this seems pretty reasonable to me. I have never tried this variant (and I do assume it's not good, but if Glaurung uses it I take that as having some weight that it may be worth a shot.)

The history numbers begin to become almost purely random after a couple of minutes of very deep searching at speeds of 20M nodes per second. I think the latter example with 32768 entries has the best hope, at least you keep trying the same piece from the same square to the same square, but is such a move played at ply 2 and failing high going to mean that playing the same move at ply 30 will have the same result?

I hear you talking, but I cannot get around the fact that my program plays stronger with history tables. I don't use this for LMR however, just for move ordering.

The idea looks hopeless to me, and I have yet to find an approach that actually improves cluster test results. Most hurt, the rest didn't help. Not that it can't be made to work, but I have tried every idea ever mentioned here, and some that have not been mentioned, all with the same bad overall result. Some seemed to be quite reasonable, until you shine the "cluster light" on them.

Perhaps I have not tried this with long time controls. Out of necessity I am restricted to pretty fast testing. So that could explain why this "appears" to be useful.

Do you have a specific ordering for generating moves? Like do you generate pawn moves first, or piece moves first, etc? It's possible that I could at least generate my moves in a different sequence and perhaps I would find that history doesn't help. It's not a lot for me, but it's a clear win.

[Gerd Isenberg]

Do you have a specific ordering for generating moves? Like do you generate pawn moves first, or piece moves first, etc? It's possible that I could at least generate my moves in a different sequence and perhaps I would find that history doesn't help. It's not a lot for me, but it's a clear win.

To make this graph cyclic
Bob's reply from the same thread:
http://www.talkchess.com/forum/viewtopi ... 44&t=29611
Edit: Oups, not a parent node, therefor only a transposition.

[Don]

Do you have a specific ordering for generating moves? Like do you generate pawn moves first, or piece moves first, etc? It's possible that I could at least generate my moves in a different sequence and perhaps I would find that history doesn't help. It's not a lot for me, but it's a clear win.

To make this graph cyclic
Bob's reply from the same thread:
http://www.talkchess.com/forum/viewtopi ... 44&t=29611

I completely missed that. Thanks for the pointer. Maybe I can respond to that post and make a link back to the one I'm responding to now

I'll take a look at how difficult it is to do Bobs move ordering and see if that helps.

[Jan Brouwer]

The history numbers begin to become almost purely random after a couple of minutes of very deep searching at speeds of 20M nodes per second.

I think this can be avoided by half-ing all entries in the table after any entry exceeds some lowish number (I use 10000 as threshold, and depth^3 for updates).
This gives a decaying effect of older updates and should reduce the noise. Using a history[from][to] table this way saves about 10% of nodes in my program.

[Aleks Peshkov]

It may be worse a try to reduce history counters at a moment when search recursion does return back from deep subtree to a depth equal to, say, iteration_number/2 and to reduce in quantity relative to the total number of counted history increments inside that subtree.

This way different search depths and different tree sizes will gradually influence the history heuristic dumping factor.

[BubbaTough]

I have seen 3 flavors of history tables. <piece><to>, a 512 entry table. <from><to>, a 4096 entry table, <piece><from><to> a 32,768 entry table.

I think I use <from><to><ply>. Its been a while since I looked at that code.

-Sam

[Edsel Apostol]

I have seen 3 flavors of history tables. <piece><to>, a 512 entry table. <from><to>, a 4096 entry table, <piece><from><to> a 32,768 entry table.

I think I use <from><to><ply>. Its been a while since I looked at that code.

-Sam

Hi Sam,

Have you verified if it is better than [piece][to]?

[Edsel Apostol]

By the way, what I don't like with History is that as the time spent on search increases, the randomness of the values contained in the history table also increases, and I don't want to trust that value.

It's really ugly isn't it? I hate that too. I use what works best at the levels I test at! And I assume this is better than nothing at all.

Yes, it's ugly because of the inconsistency depending on the time control.

By the way, I've just realized that History Tables can still help even in longer time controls, but I'm not sure how much. The reason why I think so is that we are using Iterative Deepening Framework and in the first few iterations, lets say 6 or 7 iterations, the History Heuristic is still effective. Therefore at bigger iterations the one using History Heuristic might even have an advantage over the one not using it as it already has a boost on those early iterations.

In summary, if the game has an average iteration of 8 (depth 8, very fast time control) and below the History Heuristic seems to help. At iterations 9 to 14 (blitz time control) it might still be effective based on what I mentioned above. At iteration 15 and above there might still be a boost from History heuristic but it will most probably be minuscule and I'm expecting that the advantage may not be measurable at all.

Based on this observations, History Heuristic may be better than nothing at all. Therefore it would be better to find ways to make its effectiveness extend to deeper search than not doing it at all.

P.S. I've changed my mind already a couple of times since this thread started whether to retain the History Heuristic or not.

[BubbaTough]

I have seen 3 flavors of history tables. <piece><to>, a 512 entry table. <from><to>, a 4096 entry table, <piece><from><to> a 32,768 entry table.

I think I use <from><to><ply>. Its been a while since I looked at that code.

-Sam

Hi Sam,

Have you verified if it is better than [piece][to]?

Its been a number of years since I played with that stuff...but I don't think I have tried that, even though it makes a lot of sense. Just [from][to][color], and [to][ply] and a few things like that. I think I also played with how to increment, and do depth*depth or something. I put a lot more energy into coming up with chess knowledge related move sorting since history seems a little silly intuitively when depths get great, but it never worked out for me as well as my simple version of history.

-Sam