Improving history tables

[Michael Sherwin]

Crediting fail highs only, makes no sense to me, because, they are just moves that take advantage of the opponents mistakes and may have no inherent worth other than that.

Crediting moves that raise alpha, also has a weakness in that, just because, a move raises alpha does not make it a good move.

So, what about crediting only best moves that do not fail high?

Then if this were used for LMR, does anyone have a guess at what would be a good LMR threshold?

[bob]

Crediting fail highs only, makes no sense to me, because, they are just moves that take advantage of the opponents mistakes and may have no inherent worth other than that.

Crediting moves that raise alpha, also has a weakness in that, just because, a move raises alpha does not make it a good move.

So, what about crediting only best moves that do not fail high?

Then if this were used for LMR, does anyone have a guess at what would be a good LMR threshold?

If you use PVS, this has to be a _tiny_ set of moves. I'm not sure it would end up being very functional since hardly any moves would have these history values...

[Michael Sherwin]

Yes, the set is small. A LMR threshold of 1 gives a speedup. A threshold of 2 gives a bigger speedup. Anything more than 4 does not give any bigger speedups. This is just for best moves that raise alpha. If best moves that do not raise alpha are included then I imagine that the set will not be nearly as small. Are these moves good to count? I will test.

[hgm]

Crediting fail highs only, makes no sense to me, because, they are just moves that take advantage of the opponents mistakes and may have no inherent worth other than that.

Not I never used history, so my opinions should be taken with a grain of salt.

But I think the usefulness of history comes about by the fact that cut moves that are the result of specific mistakes are different all the time (depending on what the mistake was) and thus never collect a high history value. Those moves that are good against almost any move of the opponent do collect far higher history values.

The power of the history heuristic is that you don't have to worry about the underlying reason for the cutoff. Dumb counting plus statistics do the job.

Note further that in an alpha-beta tree not all cut-move punish immediately preceeding mistakes. The only mistake by the opponent might have been his deviation from the PV, and after that he can no longer get to the PV score no matter what he tries. Most of what he tries is not a clear mistake, it is just not good enough, and by reasonable play in the cut moves the other side maintains his advantage.

Moves that are generally bad, so that they are not able to give a cutoff in most positions (e.g. because they give up control of a square of vital tactical importance) never collect a high history score, so the history heuristic also protects you from inadvertantly trying such a move early.

[yoshiharu]

But I think the usefulness of history comes about by the fact that cut moves that are the result of specific mistakes are different all the time (depending on what the mistake was) and thus never collect a high history value. Those moves that are good against almost any move of the opponent do collect far higher history values.

The power of the history heuristic is that you don't have to worry about the underlying reason for the cutoff. Dumb counting plus statistics do the job.

Yesterday's discussion triggered my thoughts as well as Michael's.
In a PVS framework, collecting history scores in every node couldn't be a source of randomness? After all, when searching with a null window the moves can only fail (either high or low), maybe not being particularly deserving (or bad). Wouldn't be reasonable to update history scores only in the part of the tree made by PV nodes?

Moves that are generally bad, so that they are not able to give a cutoff in most positions (e.g. because they give up control of a square of vital tactical importance) never collect a high history score, so the history heuristic also protects you from inadvertantly trying such a move early.

But how many of those moves gain a good history score just because the previous move was a horrible blunder, and/or maybe the position at that node is (like the majority of the positions in a search tree) totally pointless and semi-random?

This is a question to which I find hard to give a quantitative answer.

Cheers, Mauro

[bob]

I think that is the crux of the problem. Fail highs are very "local" in nature most of the time, as in refuting a blunder. So counting them leads to large numbers in the history table yet those numbers don't mean anything except in the local area of the tree where they were set.

On the other hand, counting only PV nodes (in a PVS framework) has exactly the opposite problem. There are so few PV nodes, particularly when things are going well with move ordering, that there would be no useful information in the history counters either.

Hence my decision to stop using them. I even kept up with when a supposedly good move didn't fail high, but that did not seem to help much either.

Avoiding reducing killer moves gets the same flavor into the search, but with data that is considerably more "local" and therefore probably more accurate.

[mjlef]

I think one problem I have with history information based only on failing high or low is it does not capture inofrmation about the score. At one point in the tree a move might fail high with a score of lets say -500. Is this useful in another part of the tree which needs a +300 to fail high? Perhaps a moving average of the fail high or fail low score can be kept to give an estimate of the average score a move yielded. If a move typically gives say a-300 score, it is less likely to be useful in causing a fail high that needs to be +300. Has anyone tried this approach? Just storing an average score returned from a search? Maybe it would be less random. I might try this tonight, and if it works great, I promise never to tell anyone!

Mark

[Michael Sherwin]

Given what everyone has said here, how about only storing those fail highs that are within a small margine of beta? I guess that failsoft alpha beta would need to be used?

[mjlef]

Actually, I am trying to figure out how to extract the most info I can from the search of a move. Of course, most will just be limts and not tell you the true score. But if a move fails above beta, you can probably assume there is a decent probability the same move might again have a score of at least beta in the future. And if it is below alpha, maybe it is safe to assume it would again return a score at least close to alpha. Also, moves leading to mate scores should probably be handles differently. They might again lead to mate, and so should probably not be reduced for a while. I am still experimenting with various ways to use this info. It seems to me that is you have afail soft score, it must be more useful than just saying it is >beta (one bit of info). Extracting the usefulness might be tricky, but I am trying some simple things, like a moving average score of the returned value of a search. Maybe that will be better than simple counting.

[YL84]

hi,
in my chess programme I store in "history tables":
- "scores" that improves best_score found so far (score is stored);
- "scores" that improves beta (score is stored);
- "scores" that improves beta but are not a capture (score+300 is stored)
(this one is a kind of killer move in the history table)
Note that my history tables depend on the depth, so they are not of a classical type.
It is the best combination I have found by trial and error experiments. It works for my programme, and could not work for others (for instance i have no transposition table).
I also have tried many things like taking into account "bad moves"
(storing score-something) but never succeded to find something good.
This methods are not perfect since most of the time we don't know the exact score, so there should be some place for improvements.

Yves