Alternatives to History Heuristics

[bob]

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.

Here's a little-known tidbit. When I was playing with LMR, and using a counter to say "don't reduce the first N moves", I tried all sorts of ordering. Computing the static eval for each move. Computing the static eval + SEE for each move. And it hardly affected my NPS, because the search is dominated by the q-search. You might well get away with doing an eval for each move to order them, but I found no benefit to doing so and chose to remove code that does not help.

[Edsel Apostol]

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.

I have tried not to scale my history values before and I also have tried scaling all the values in two if one entry is greater than 2^15 but the best result comes from scaling it when its greater than 2^14 just like in Fruit/Toga. I have not tried scaling it on 2^13.

By the way, I have an idea on how to make the history values more effective. This may be unsound but we'll never know unless we try it. Here goes:

Instead of using this:

Code: Select all

HistoryTable[color][piece][to]

we can use:

Code: Select all

HistoryTable[numpawnsw][numpawnsb][color][piece][to]

where numpawnsw and numpawnsb is the number of pawns for both sides. It will be 81 times bigger in size than the old history table. Or maybe we can use the game phase or a combination of game phase and pawn count for both sides.

[mcostalba]

By the way, I have an idea on how to make the history values more effective. This may be unsound but we'll never know unless we try it. Here goes:

This is an interesting idea, although is not clear to me the link between pawns number and similitude of the sub-tree and from there validity of history.

I have tried a simpler approach that is to link the history table to a sub-tree only instead of all the tree. The idea is that history is good when search is not very deep and this means that history is good when applied to a sub-tree that is not very deep either.

To buildup a fast implementation I associated the history table with threads: one history table per thread

This should approximate the history table to sub-tree idea and is much easier to implement.

With my surprise the result was not so bad. Actually a bit weaker then the standard version but not so much weaker, so perhaps there is still to dig in the "one history table per sub-tree" idea.

[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;
}

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.

1.When Romi first came out it had no history tables, because they proved useless for move ordering (I posted about it). Then Bob sometime later validated my belief in this when he dropped them from Crafty. However, when I added LMR to Romi the history tables were brought back (similar to how it is done in Kiwi) and I have not been able to get rid of them since. I also posted in one of the other forums that I thought that Fruit's (2.1) history pruning made no difference in Fruits strength. I took a lot of heat for that one, but later Bob also validated that claim as well. However, history tables for LMR by themselves was of not much use. They were used in Romi as a 'second witness' to my shallow searches with an open window. So, if the value for a move, from the shallow search was less than alpha--only then was the history table used. I have now added a second history table that I use in the PST and Eval() that I have also not been able to get rid of with out losing strength. To reduce randomness two things that I have tried that look promising are limiting the depth range that statistics are taken and using two tables, one with a short period and one with a long period that both must agree.

2. Yes!

3. Romi is bitboard, but the move bits are not spun (enumerated) into a move structure when they are generated. It is very easy to pick out the hash move, winning or even captures, promotions and killers--clearing their bits. Addmoves() then just spins (with various move orderings) the remaining move bits which includes loosing captures.

4. Romi is performing at longer time controls just as well with two history tables. Maybe even better--see CCRL.

And not ordering the remaining moves at depth = 1 is an improvement of about 80,000 nodes per second and a shorter search time.

I was getting ready for OW6 when my hard drive crashed. I lost a months work and out of frustration I did not even enter. Took some time off from anything computer and did some reading as well as wasting a lot of time watching movies from the library. Well the only engines that are on my computer now are the ones that come with Arena 2.01. So, I've been testing against Dragon 4.6. an engine that always in the past got the best of Romi in a long match. But, now with half of my improvements back in plus not doing PST ordering at depth = 1 ... waiting for the match to end ... Romi is kicking Dragon behind worse than what she ever did to those five pesky little hamsters!

RomiChess96 - Dragon 4.6 : 71.5/100 62-19-19 (1=10111111=1=011=0111111=1111==11=101001=11001111110==1111111100111===1111=01=11111110==1=1010010010) 72% +164

[Edsel Apostol]

By the way, I have an idea on how to make the history values more effective. This may be unsound but we'll never know unless we try it. Here goes:

This is an interesting idea, although is not clear to me the link between pawns number and similitude of the sub-tree and from there validity of history.

I have tried a simpler approach that is to link the history table to a sub-tree only instead of all the tree. The idea is that history is good when search is not very deep and this means that history is good when applied to a sub-tree that is not very deep either.

To buildup a fast implementation I associated the history table with threads: one history table per thread

This should approximate the history table to sub-tree idea and is much easier to implement.

With my surprise the result was not so bad. Actually a bit weaker then the standard version but not so much weaker, so perhaps there is still to dig in the "one history table per sub-tree" idea.

I'm thinking of associating the history table being used with the pawn structure and there is no easier method to do that but count the pawns for both sides. My theory is that when there is a pawn that's being captured that the game dynamics changes and therefore it's time to use another table.

For example we are going to search at depth 8 and we have 7 pawns for both sides, then we are going to use the history table indexed by the number of pawns. When the search progressed and for example at ply 3 (remaining depth = 4) there is a pawn capture then we use another table that was indexed by the new number of pawns.

I want to try and test it though I still have a lot of ideas to test at the moment. I will try it sometime if I don't have anything to test anymore.

Your idea of using separate history table for each thread is also interesting. Why don't you try having separate history table also for each split point. I'm not sure if this idea is good. I'm not well versed yet with SMP programming.

By the way, in your idea above is it possible that a certain thread with history values from a certain sub tree will help search another thread with another subtree after finishing it's own task? If yes then that thread may be using history values not calculated for that subtree.

[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.

1.When Romi first came out it had no history tables, because they proved useless for move ordering (I posted about it). Then Bob sometime later validated my belief in this when he dropped them from Crafty. However, when I added LMR to Romi the history tables were brought back (similar to how it is done in Kiwi) and I have not been able to get rid of them since. I also posted in one of the other forums that I thought that Fruit's (2.1) history pruning made no difference in Fruits strength. I took a lot of heat for that one, but later Bob also validated that claim as well. However, history tables for LMR by themselves was of not much use. They were used in Romi as a 'second witness' to my shallow searches with an open window. So, if the value for a move, from the shallow search was less than alpha--only then was the history table used. I have now added a second history table that I use in the PST and Eval() that I have also not been able to get rid of with out losing strength. To reduce randomness two things that I have tried that look promising are limiting the depth range that statistics are taken and using two tables, one with a short period and one with a long period that both must agree.

2. Yes!

3. Romi is bitboard, but the move bits are not spun (enumerated) into a move structure when they are generated. It is very easy to pick out the hash move, winning or even captures, promotions and killers--clearing their bits. Addmoves() then just spins (with various move orderings) the remaining move bits which includes loosing captures.

4. Romi is performing at longer time controls just as well with two history tables. Maybe even better--see CCRL.

And not ordering the remaining moves at depth = 1 is an improvement of about 80,000 nodes per second and a shorter search time.

I was getting ready for OW6 when my hard drive crashed. I lost a months work and out of frustration I did not even enter. Took some time off from anything computer and did some reading as well as wasting a lot of time watching movies from the library. Well the only engines that are on my computer now are the ones that come with Arena 2.01. So, I've been testing against Dragon 4.6. an engine that always in the past got the best of Romi in a long match. But, now with half of my improvements back in plus not doing PST ordering at depth = 1 ... waiting for the match to end ... Romi is kicking Dragon behind worse than what she ever did to those five pesky little hamsters!

RomiChess96 - Dragon 4.6 : 71.5/100 62-19-19 (1=10111111=1=011=0111111=1111==11=101001=11001111110==1111111100111===1111=01=11111110==1=1010010010) 72% +164

Romi seems to be promoted from Hamster Slayer to Dragon Slayer now.

By the way, I think that I also have tried the idea of using shallow searches to order my remaining moves but that was years ago (around 3 to 4 years) when I was just starting. I think I got that idea from Romi source code also. I was still in College back then and I don't even have a PC that time to test my ideas. I don't remember anymore how it performs. Maybe I will give it a try again.

I'm thinking of using history tables only for remaining depth of 4 and for those with higher depth a shallow search with depth / 4 or something.

[Don]

I haven't read all the answers yet - but I will at least tell you what I am doing and what I found works and what doesn't.

I use the history heuristic for move ordering. It's a small but clear improvement. The "classic" version of the history heuristic does NOT help the program. For every move sampled, I note how often it was sampled and how often it succeeded. If a beta cutoff occurs, the move doesn't get sampled so I suppose you get a little bit of a feedback effect. If a move produces a cutoff an even better move won't even get sampled for instance. But this is a clear move ordering enhancement in my program. I sort of course by the percentage of success. I track how often this move was best, regardless of whether it produced a cutoff or not.

I also put losing moves to the end of the move list (not counting the captures, killers, hash table move etc.) and that is a definite help.

I have tried ordering the moves according to a fast evaluation function, which is based mostly on piece square tables. This does NOT help with move order, to my surprise.

I cannot speak to the issue of LMR, as I don't really believe in using history this way - although I do believe in trying things even if you don't like them But so far I have never experiemented with this and find it rather distasteful and too much of a black art for my tastes.

One thing I have found is that what works in one program may not work in another, although it's generally true that works for me has always worked for all my programs, even though some of them are significantly different than others.

I strongly suspect that MANY times if something appears to work for one person and not another, it is because of poor testing methodology. One person either thought it worked and didn't test it well enough, or perhaps the implementations were different (the devil in the details) or there was a bug in one of the implementations.

Of course I know there are legitimate reasons why it might really be true due to real differences in the programs but I generally like to try to understand why (why it worked for him and not me) if it's possible to figure that out.

I don't have History Pruning and History Based Reductions in my engine and I'm planning to remove the History Heuristic altogether.

The question is what are the possible alternatives to it? I'm thinking of using values from piece square tables to order my non tactical moves instead of the data in the history table. Has anyone tried it? Is it better than using history?

Has anyone also tried ordering those non tactical moves by type of piece? For example prioritize pawn moves first, knight and bishop next and so on.

Another idea would be to put those moves at the end of the movelist when the "to" square is being attacked by a lower value piece. For example a queen move to a square attacked by the opponent pawn. Is it a sound idea?

[Don]

Finding proper alternative for (stupid) history move ordering is really hot question. This could give enormous elo boost.

The question is what are the possible alternatives to it? I'm thinking of using values from piece square tables to order my non tactical moves instead of the data in the history table. Has anyone tried it? Is it better than using history?

Stockfish uses psqt delta to order moves with zero history value.

Another idea would be to put those moves at the end of the movelist when the "to" square is being attacked by a lower value piece. For example a queen move to a square attacked by the opponent pawn. Is it a sound idea?

Sounds wise at first sight, but it's not so clear. Very stupid looking moves are also very fast to refute (and sometimes they still work!). So when thinking about cost/benefit ratio, it's not clear whether they should be played first or last. I think we would need some way to identify "boring moves" (which are neither good nor bad, but meaningless) and put them last in the list. Unfortunately this is very position dependant.

I think my last forum post was slightly inaccurate. I don't actually put losing moves at the end of the list, I just downgrade them. I implemented this long ago so I don't remember the details without looking, but I did something like lower their sort score a bit so that if they were hot moves they were not just warm - or something like that. I think the net affects is still that most of them moved to the end of the list.

[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.

[mcostalba]

By the way, in your idea above is it possible that a certain thread with history values from a certain sub tree will help search another thread with another subtree after finishing it's own task? If yes then that thread may be using history values not calculated for that subtree.

Yes it is like this. That's the reason I say an history table per thread is just an approximation of an history table per sub-tree

But to my surprise even this gross approximation performed not bad, actually very near to the standard version.