On history counters again.

[Mincho Georgiev]

This is more like a request instead of helpful information, but here it goes.
I've never had any good results with usage of history counters in the usual way that most programs do - in conjunction with killer moves and storing on fail-high. I even remember that recently, Bob (and I think others too) removed them completely, considered them as a another "noisy" idea.
My case is somehow different and I will try to describe it. I'm using history counters for move ordering only (not for reduction avoidance as I believe was the idea behind the history pruning).
What I actually do is like "tree-way-heuristics" for move ordering which includes the pvmove, the killers and the history counters. Tree-way because the history is separated from the killers. I'm saving counters only if move raises alpha, but is within the window. Like instead of:

Code: Select all

if(value > alpha)
{
    /////do what you do - store pv, etc.
   if(value >= beta)
   {
        update_killers();
        update_history();
        return value;
  }
}

What I do is:

Code: Select all

if(value > alpha)
{
    /////do what you do - store pv, etc.
   if(value >= beta)
   {
        update_killers();
        return value;
  }
  update_history();
}

The reason to do that is that I get better results and I really have no explanation, but I've tested this 10 times already and it just shows +15 elo with good confidence. If I remove the history entirely, the result just drops with the same estimate as well as leaving the history like in the 1st example.
My request is to anyone with good resources for testing and willing to try this with his code. Thanks!

[rvida]

I am updating history every time the score is above alpha, even if outside of the window. Besides that I am storing this score as a new lower bound to hash table. This is what works best for Critter.

Code: Select all

      if (score > alpha) {
        best_move = move;
        if (is_quiet(move) && !(flags & FLAG_REPETITION))
          history.record_good_move(move, depth);
        tt.store_lower(board.hash_key(), depth, score, board.ply, move);
        alpha = score;
        if (score >= beta) {
          if (is_quiet(move) && !(flags & FLAG_REPETITION))
            update_killers(ss, move);
          break;
        }
      }

[Mincho Georgiev]

Tried that also. For some reason it didn't work for me. Thanks for the input, Richard!

[bob]

This is more like a request instead of helpful information, but here it goes.
I've never had any good results with usage of history counters in the usual way that most programs do - in conjunction with killer moves and storing on fail-high. I even remember that recently, Bob (and I think others too) removed them completely, considered them as a another "noisy" idea.
My case is somehow different and I will try to describe it. I'm using history counters for move ordering only (not for reduction avoidance as I believe was the idea behind the history pruning).
What I actually do is like "tree-way-heuristics" for move ordering which includes the pvmove, the killers and the history counters. Tree-way because the history is separated from the killers. I'm saving counters only if move raises alpha, but is within the window. Like instead of:

Code: Select all

if(value > alpha)
{
    /////do what you do - store pv, etc.
   if(value >= beta)
   {
        update_killers();
        update_history();
        return value;
  }
}

What I do is:

Code: Select all

if(value > alpha)
{
    /////do what you do - store pv, etc.
   if(value >= beta)
   {
        update_killers();
        return value;
  }
  update_history();
}

The reason to do that is that I get better results and I really have no explanation, but I've tested this 10 times already and it just shows +15 elo with good confidence. If I remove the history entirely, the result just drops with the same estimate as well as leaving the history like in the 1st example.
My request is to anyone with good resources for testing and willing to try this with his code. Thanks!

I've never just updated history counters on a fail high. I updated them every time I don't "fail low" in fact, which includes fail highs and PV nodes where a real score is backed up. I'm not sure why one would do it otherwise.

however, that being said, not even a tiny fraction of a percent of the positions meet that "pv" restriction, assuming you use PVS with null-window searches. Almost all positions either fail low or fail high. I can't imagine why it would make any measurable difference at all unless there is some unexplained bug or side-effect that is outside of the normal "history ordering idea"

[Mincho Georgiev]

unexplained bug or side-effect

Quite possible.

[Volker Annuss]

however, that being said, not even a tiny fraction of a percent of the positions meet that "pv" restriction, assuming you use PVS with null-window searches. Almost all positions either fail low or fail high. I can't imagine why it would make any measurable difference at all unless there is some unexplained bug or side-effect that is outside of the normal "history ordering idea"

But the PV moves are searched early. They are among the first moves that go into the history table. Later these moves get sorted first from their history scores and produce more cutoffs. That increases their history value. This may be the side-effect.
And it is reasonable that PV moves are good in other positions and also make transpositions more likely, so putting them into the history table might really increase strength.
I will try that.

[Mincho Georgiev]

Thanks in advance, Volker for any results you would share!
In the meantime, I allowed myself to try this with an old version of Glaurung (namely 0.2.3) because of
the similar way the history is used for ordering. I really hope that Tord wouldn't mind if i post some code.
Originally, the history update was done like that:

Code: Select all

void inc_history(move_t m, int side, int depth, int value) {
  if(!CAPTURE(m) && !PROMOTION(m)) {
    HISTORY(side, m) += (depth>>5);
    FailHighStats[HINDEX2(m)].success++;
    SearchStack[Ply].killer2 = SearchStack[Ply].killer;
    SearchStack[Ply].killer = m;
  }
  if(value==MATE_VALUE-Ply-1) SearchStack[Ply].mate_killer = m;
}

I separated the killers and history:

Code: Select all

void inc_history(move_t m, int side, int depth, int value) {
    if(!CAPTURE(m) && !PROMOTION(m))
      HISTORY(side, m) += (depth>>5);
}

void inc_killers(move_t m, int side, int depth, int value) {
  if(!CAPTURE(m) && !PROMOTION(m)) {
    FailHighStats[HINDEX2(m)].success++;
    SearchStack[Ply].killer2 = SearchStack[Ply].killer;
    SearchStack[Ply].killer = m;
  }
  if(value==MATE_VALUE-Ply-1) SearchStack[Ply].mate_killer = m;
}

and then in search and root search instead of:

Code: Select all

	//main search:
	if(value>bestvalue) {
	bestvalue = value;
	if(value>alpha) {
	  alpha = value; 
	  update_pv(move);
	  if(value>=beta) {
	    inc_history(move, Side, depth, value);
	    break;
	  }
	}
      }
	
	//root search:
      	if(value>bestvalue) {
	  bestvalue = value;
	  if(value>alpha) {
	    alpha = value; 
	    update_pv(move);
	    update_root_pv();
	    if(iteration>1) print_pv(iteration, value);
	    if(value>=beta) {
	      inc_history(move, Side, depth, value);
	      break;
	    }
	  }

I did it the way I've already described:

Code: Select all

      //main search:
      if(value>bestvalue) {
	bestvalue = value;
	if(value>alpha) {
	  alpha = value; 
	  update_pv(move);
	  if(value>=beta) {
	    inc_killers(move, Side, depth, value);
	    break;
	  }
	  inc_history(move, Side, depth, value);
	}
      }
	
	//root search:
	if(value>bestvalue) {
	  bestvalue = value;
	  if(value>alpha) {
	    alpha = value; 
	    update_pv(move);
	    update_root_pv();
	    if(iteration>1) print_pv(iteration, value);
	    if(value>=beta) {
	      inc_killers(move, Side, depth, value);
	      break;
	    }
	    inc_history(move, Side, depth, value);
	  }
	}

These are the only changes and compiles are both equivalent. And here are some quick head-to-head results:

Code: Select all

Rank Name             Elo   +    -   games score oppo. draws
1 Glaurung 0.2.3-h    17   14   14   400   55%   -17   42%
2 Glaurung 0.2.3     -17   14   14   400   45%    17   42%

Glaurung-h is the modified.
I've noticed that in Fire Xtreme this is named good and bad history, but I guess it's not so bad
at all and it's the ONLY history usage that is giving me some good results.
The reason to write all of this is just a request to anybody who is willing to test it.
I'm sorry in advance if your time gets wasted by this, but either I've had the very unfortunate luck
to get the wrong results over and over again, or it's just works better.
History is used in move ordering like:
every move that is not the bestmove, capture, promotion or killer gets scored from the history array.

[bob]

however, that being said, not even a tiny fraction of a percent of the positions meet that "pv" restriction, assuming you use PVS with null-window searches. Almost all positions either fail low or fail high. I can't imagine why it would make any measurable difference at all unless there is some unexplained bug or side-effect that is outside of the normal "history ordering idea"

But the PV moves are searched early. They are among the first moves that go into the history table. Later these moves get sorted first from their history scores and produce more cutoffs. That increases their history value. This may be the side-effect.
And it is reasonable that PV moves are good in other positions and also make transpositions more likely, so putting them into the history table might really increase strength.
I will try that.

Don't you ALWAYS search the PV moves first in any case? I do, because I make certain they are in the hash table before I start the next search iteration. That should stick them in the killer moves also as the moves get backed up...

Something tells me there is something else going on, because PV moves are such a tiny fraction of all nodes searched...

[Mincho Georgiev]

however, that being said, not even a tiny fraction of a percent of the positions meet that "pv" restriction, assuming you use PVS with null-window searches. Almost all positions either fail low or fail high. I can't imagine why it would make any measurable difference at all unless there is some unexplained bug or side-effect that is outside of the normal "history ordering idea"

But the PV moves are searched early. They are among the first moves that go into the history table. Later these moves get sorted first from their history scores and produce more cutoffs. That increases their history value. This may be the side-effect.
And it is reasonable that PV moves are good in other positions and also make transpositions more likely, so putting them into the history table might really increase strength.
I will try that.

Don't you ALWAYS search the PV moves first in any case? I do, because I make certain they are in the hash table before I start the next search iteration. That should stick them in the killer moves also as the moves get backed up...

Something tells me there is something else going on, because PV moves are such a tiny fraction of all nodes searched...

My point was exactly that. 1st - PV moves. Then the killers. And then the history moves which in the variant I suggested are moves that raising alpha, but don't cause cut-off. That's that difference. Unlike the usual - update history and killers all together. The point is that the current pv move will get stored in the history table if it doesn't cut-off. Then later, if any of the moves is better, it takes place as pv move, but the old one remains scored in the history table and takes advantage in ordering which of course might be wrong suggestion in different position. Yes, as you pointed out, during null move searches this looks quite useless, and it's still mystery for me why it makes difference.

[bob]

however, that being said, not even a tiny fraction of a percent of the positions meet that "pv" restriction, assuming you use PVS with null-window searches. Almost all positions either fail low or fail high. I can't imagine why it would make any measurable difference at all unless there is some unexplained bug or side-effect that is outside of the normal "history ordering idea"

But the PV moves are searched early. They are among the first moves that go into the history table. Later these moves get sorted first from their history scores and produce more cutoffs. That increases their history value. This may be the side-effect.
And it is reasonable that PV moves are good in other positions and also make transpositions more likely, so putting them into the history table might really increase strength.
I will try that.

Don't you ALWAYS search the PV moves first in any case? I do, because I make certain they are in the hash table before I start the next search iteration. That should stick them in the killer moves also as the moves get backed up...

Something tells me there is something else going on, because PV moves are such a tiny fraction of all nodes searched...

My point was exactly that. 1st - PV moves. Then the killers. And then the history moves which in the variant I suggested are moves that raising alpha, but don't cause cut-off. That's that difference. Unlike the usual - update history and killers all together. The point is that the current pv move will get stored in the history table if it doesn't cut-off. Then later, if any of the moves is better, it takes place as pv move, but the old one remains scored in the history table and takes advantage in ordering which of course might be wrong suggestion in different position. Yes, as you pointed out, during null move searches this looks quite useless, and it's still mystery for me why it makes difference.

How often can that happen in a modern PVS search? I can actually answer that thanks to my PV hash idea that I put in a few months back. I saw that most searches have to "store a PV" a couple of hundred times to a couple of thousand, except for REALLY rare positions. That is on a machine searching 20M nodes per second. If you do a real PVS, and even null-window null-move on PV nodes, almost everything is searched where it is impossible to "improve alpha" because to do that results in an instant cutoff...

I will say this... you will not be wasting time if you work to explain this. It is almost certainly something odd going on, and if it is good, you found it by accident, but it might just look good where you test, but be bad otherwise. I have learned to DESPISE "unexplainable improvements" (one would naturally dislike unexplainable bad results as well.) I have often discovered something interesting when explaining that which is not obviously explainable. At the very least, you will learn something you ought to know but don't. I've certainly had enough of "those moments."