Moderator: Ras
Hi Uri,Uri Blass wrote:
The idea is clearly more than 3 years old and the article is nothing new.
Many engines use history tables for ordering moves and I believe that many people use depth*depth because I remember it from old code that is more than 3 years old.
Uri
The coincidence is, Vincent predicted in 2002 what Bob is doing now with history heuristic - he threw it out.Uri Blass wrote: I do not know what do the majority and it is not clear to me if Bob is the majority.
It is only clear that Vincent claims nonsense when he claims
"In not a single top program history tables work"
because he does not know what works or does not work for other people.
Note that Strelka that is clearly stronger than everything of 2002 is using depth*depth in history tables for order of moves and it is not clear for me that history does not work for strelka.
If the counters are too big today because of overflow(when depth*depth may be above 2^32 then it is possible to use 64 bit numbers).
Uri
You are right and I did not read the article before replying and replied too fast.Gerd Isenberg wrote:Hi Uri,Uri Blass wrote:
The idea is clearly more than 3 years old and the article is nothing new.
Many engines use history tables for ordering moves and I believe that many people use depth*depth because I remember it from old code that is more than 3 years old.
Uri
the issue is relative history heuristic, not how to increment history by square(depth).
Gerd
Yes this is how history is implemented in Glaurung. You count success and failures and value depends on both.Gerd Isenberg wrote:
The idea of relative history was tried by Bob and others as well. Don't care whether you increment by depth*depth or 1<<depth, he considered a relation of two counters[from][to], incremented at Cut-nodes - one counting the fail-highs of a move, the other counting how often the move didn't fail high, while another did.
Gerd
I am not certain, but I think I was the first to use depth*depth. The original paper by Schaeffer suggested 1<<depth but that was not usable at the search depths I was reaching. One branch to 31 plies would blow the counter up. The squared depth approach was an obvious try to still strongly reflect that shallower ply moves were move important that moves deep in the tree, without seriously overflowing a 32 bit counter...Gerd Isenberg wrote:Hi Uri,Uri Blass wrote:
The idea is clearly more than 3 years old and the article is nothing new.
Many engines use history tables for ordering moves and I believe that many people use depth*depth because I remember it from old code that is more than 3 years old.
Uri
the issue is relative history heuristic, not how to increment history by square(depth).
Gerd
If the problem is overflowing a 32 bit counter then you can use 64 bit counters.bob wrote:I am not certain, but I think I was the first to use depth*depth. The original paper by Schaeffer suggested 1<<depth but that was not usable at the search depths I was reaching. One branch to 31 plies would blow the counter up. The squared depth approach was an obvious try to still strongly reflect that shallower ply moves were move important that moves deep in the tree, without seriously overflowing a 32 bit counter...Gerd Isenberg wrote:Hi Uri,Uri Blass wrote:
The idea is clearly more than 3 years old and the article is nothing new.
Many engines use history tables for ordering moves and I believe that many people use depth*depth because I remember it from old code that is more than 3 years old.
Uri
the issue is relative history heuristic, not how to increment history by square(depth).
Gerd
Thanks for the correction. I referrerd to your LMR post from March 2006, because you explained something similar, as inside the mentioned Relative History Heuristic pdf-paper by Winands et al. from 2006. I was aware that your focus was on LMR, but I guess your way of RHH was also used in move ordering as well.bob wrote:let me slightly correct "history". This is talking about two different history issues.
1. LMR
2. Move ordering.
I first got rid of history for LMR, because tests with Crafty and Fruit on our cluster showed that changing the history threshold made absolutely no difference in the playing strength of either program. Based on that, the original LMR (called history-pruning in Fruit, if you recall) was modified in Crafty to no longer use any history information.
But once I had the cluster testing ability, I discovered that the history heuristic for move ordering was offering no improvement at all, and chose to take it out as well. If it doesn't help, I don't keep a change unless the change simplifies the code in some way...
I did experiment with the LMR-type history for ordering moves, but it did not work either. Whether that is a function of today's search depths, or an artifact of the LMR + extensions being used I am not sure... but nothing worked for me to produce a stronger performance, and it was all removed for simplicity...
Hi Marco,mcostalba wrote:Yes this is how history is implemented in Glaurung. You count success and failures and value depends on both.Gerd Isenberg wrote:
The idea of relative history was tried by Bob and others as well. Don't care whether you increment by depth*depth or 1<<depth, he considered a relation of two counters[from][to], incremented at Cut-nodes - one counting the fail-highs of a move, the other counting how often the move didn't fail high, while another did.
Gerd
See Glaurung or Stockfish (the same algorithm with a different code style) sources for reference.
Actually in Glaurung history ordering is VERY important for non capture moves, namely it is the ONLY used ordering scheme apart from killer moves...and it works!
In Stockfish I think I have improved over it using piece/square tables values but only as a second order choice when history is not enough (as example is zero) or two moves have the same history values.
Marco
Uri Blass wrote:If the problem is overflowing a 32 bit counter then you can use 64 bit counters.bob wrote:I am not certain, but I think I was the first to use depth*depth. The original paper by Schaeffer suggested 1<<depth but that was not usable at the search depths I was reaching. One branch to 31 plies would blow the counter up. The squared depth approach was an obvious try to still strongly reflect that shallower ply moves were move important that moves deep in the tree, without seriously overflowing a 32 bit counter...Gerd Isenberg wrote:Hi Uri,Uri Blass wrote:
The idea is clearly more than 3 years old and the article is nothing new.
Many engines use history tables for ordering moves and I believe that many people use depth*depth because I remember it from old code that is more than 3 years old.
Uri
the issue is relative history heuristic, not how to increment history by square(depth).
Gerd
Uri