Improving history tables

[Michael Sherwin]

You are using the history tables as a kind of super killer table. It sounds that you have an always replace scheme. By using the score entry as a score accumulator and adding a count variable (if you already do not have one) then you would be doing, what Mark has suggested, and keeping a running average for each move. I wonder if you have tried that. I wonder how differentiated the averages would remain.

[YL84]

Super Killer tables seems to be a good description of what is inside my code, since my tables are depth dependent. There is a counter for each move which is also depth dependent. So that the mean "score" for each move is known at any time (even if it's not an accurate score most of the time).
This mean score is used for move ordering in all cases (good captures, normal moves,...). I have found some time ago that doing that was the
best in my particular case (forgive me guys ).
The question is "is it better than normal history tables?". For my case the answer is yes, but I suspect it is not a general rule. The reason could be I have no "transposition tables", and no more "killer moves".
Yves

[YL84]

Also I tried to add constant scores depending on distance with beta and/or alpha, but found no improvements (should visit again this possibility); the most funny thing is I have no idea of how the "mean scores" evoluate during the search, and how they are different from other ones (should look at it). Also I'm obliged to test if the "total score" is not close to the maximum limit of 32 bit integers (using 64 bits integer to prevent this test did not help); if the score is too high or too low, it is kept constant.
Yves

[ed]

Here are my 2 cents to the topic....

I am using a [piece_type][TO square] history table since I added history reductions to my engine.

I have been experimenting with the (classic?) [piece_type][FROM square][TO square] and it is obvious inferior to the above formula.

The strange thing about formula-2 is that it makes my engine a lot faster (28%) and in testsets it behaves as good as formula-1 but in real life (games) it scores considerable worse, -3%.

So maybe some of you would like to try the [piece_type][TO square] approach.

Ed

[Michael Sherwin]

Here are my 2 cents to the topic....

I am using a [piece_type][TO square] history table since I added history reductions to my engine.

I have been experimenting with the (classic?) [piece_type][FROM square][TO square] and it is obvious inferior to the above formula.

The strange thing about formula-2 is that it makes my engine a lot faster (28%) and in testsets it behaves as good as formula-1 but in real life (games) it scores considerable worse, -3%.

So maybe some of you would like to try the [piece_type][TO square] approach.

Ed

Hi Ed,

I have both kind of tables. The [fig][ts] is used for tunning the piece square tables between iteratins and [fig][fs][ts] for LMR. I kept [fig][fs][ts] for LMR, because, for me it works better. I use neither if there are not at least 100 entries.

Mike

[ed]

I have both kind of tables. The [fig][ts] is used for tunning the piece square tables between iteratins...

Hi Mike,

What a tricky thing to do, I would not dare.... Can you give an example what you update?

Ed

[Michael Sherwin]

I have both kind of tables. The [fig][ts] is used for tunning the piece square tables between iteratins...

Hi Mike,

What a tricky thing to do, I would not dare.... Can you give an example what you update?

Ed

Hi Ed,

It is in a primitive state and needs attention by someone other than my self as I can think of such things, but, am weak when it comes to perfecting them. The code that I am posting works best, sofar.

Code: Select all

// in the routine that sets up the piece square tables
  points = evalHistTblg[BN][sq] / evalHistTbln[BN][sq];
  bKnightTbl[sq] += points/4;

Code: Select all

// in the eval routine itself, this is a seperate idea
  score += &#40;wEvalBonus - bEvalBonus&#41;;<====
  if&#40;wBishopNum > 1&#41; score += 32;
  if&#40;bBishopNum > 1&#41; score -= 32;
  score = score + wMat - bMat + wPos - bPos;
  return wtm ?  score &#58; -score;

Code: Select all

// part of the search routine
  best = NULL;
  legalMoves = 0;
  count = 0;
  h->tries = 0;
  h->phase = HASHMOVE1;
  for(h->node = h->t; h->phase ;h->node++) {
    if(!NextMove(alpha, beta, depth, extendBy)) break;
    fs = h->node->fs;
    ts = h->node->ts;
    fig = piece[board[fs]].fig;
    if(Ply == 1) { //also done in the root for the computer side
      s32 g = evalHistTblg[fig][ts]; // and is part of the eval for the whole
      s32 n = evalHistTbln[fig][ts]; // tree above
      if(computer == WHITE) {
        bEvalBonus = g/n/8;
      } else {
        wEvalBonus = g/n/8;
      }
    }
    reduce = 1;
    if(depth > 3 && h->phase == NEXTMOVE) { My LMR routine
      count++;
      if&#40;!inCheck && !inNull && !inShort && h->node->score < alpha&#41; &#123;
        if&#40;didNull&#41; reduce += 2;
        if&#40;count > 3 && board&#91;ts&#93; == EMPTY&#41; &#123;
          s32 g = histTblg&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;;
          s32 n = histTbln&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;;
          if&#40;n > 99 && g / n < 16&#41; &#123;
            reduce += &#40;1 + &#40;depth - 2&#41; / 4&#41;;
          &#125; 
        &#125;
      &#125; 
    &#125;
    h->tries++;
    MakeMove&#40;&#40;moves *)&h->node->m&#41;;
    g = h - 1;
    if&#40;GetReps&#40;) || h->fifty >= 100&#41; &#123;
      if&#40;InCheck&#40;1 - wtm&#41;) 
        g->node->score = -mate + 1;
      else
        g->node->score = -100 + &#40;ply >> 1&#41;;
    &#125; else &#123;
        g->node->score = -Search&#40;-beta, -alpha, depth - reduce, extendBy&#41;;
    &#125;
    ClrReps&#40;);
    TakeBack&#40;);
    if&#40;histTbln&#91;fig&#93;&#91;fs&#93;&#91;ts&#93; > 200&#41; &#123;// reduce only one entry
      histTbln&#91;fig&#93;&#91;fs&#93;&#91;ts&#93; /= 2;
      histTblg&#91;fig&#93;&#91;fs&#93;&#91;ts&#93; /= 2;
    &#125;
    if&#40;evalHistTbln&#91;fig&#93;&#91;ts&#93; > 20000&#41; &#123;
      evalHistTbln&#91;fig&#93;&#91;ts&#93; /= 2;
      evalHistTblg&#91;fig&#93;&#91;ts&#93; /= 2;
    &#125;
    histTbln&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;++; // increment the table count
    evalHistTbln&#91;fig&#93;&#91;ts&#93;++;
    if&#40;h->node->score > h->eval && board&#91;ts&#93; == EMPTY&#41;
      evalHistTblg&#91;fig&#93;&#91;ts&#93; += 8; // multiple stages of reward
    if&#40;h->node->score > alpha&#41; &#123;
      histTblg&#91;fig&#93;&#91;fs&#93;&#91;ts&#93; += 100;
      if&#40;h->node->score > h->eval && board&#91;ts&#93; == EMPTY&#41;
        evalHistTblg&#91;fig&#93;&#91;ts&#93; += 12;
      if&#40;h->node->score >= beta&#41; &#123;
      if&#40;h->node->score > h->eval && board&#91;ts&#93; == EMPTY&#41;
        evalHistTblg&#91;fig&#93;&#91;ts&#93; += 8;

I am interested in your opinion!

Mike

[ed]

Hi Mike,

I am totally new to the (genius) idea, so don't expect too much from my feedback.

The first thing that came into my mind are the dangers of the approach, the history counters aren't exactly a shining example of accuracy and that is softly speaking. I wouldn't go as far as Bob who said that history counters are a useless set of random numbers but it's simply true history counters contain a lot of randomness. And to add randomness to eval is the world up-side-down since eval is supposed to be about accuracy.

Nevertheless, considerations don't gain elo-points, tries do and if your program plays better in real games with than without you have a winner no matter how weird and/or controversial the idea behind.

Needless to say I will do some experiments, I suppose that if you keep the modifications within a margin of (say) -0.10 and +0.10 not much harm can be done.

This is fun.....

Ed

[Michael Sherwin]

Hi Mike,

I am totally new to the (genius) idea, so don't expect too much from my feedback.

The first thing that came into my mind are the dangers of the approach, the history counters aren't exactly a shining example of accuracy and that is softly speaking. I wouldn't go as far as Bob who said that history counters are a useless set of random numbers but it's simply true history counters contain a lot of randomness. And to add randomness to eval is the world up-side-down since eval is supposed to be about accuracy.

Nevertheless, considerations don't gain elo-points, tries do and if your program plays better in real games with than without you have a winner no matter how weird and/or controversial the idea behind.

Needless to say I will do some experiments, I suppose that if you keep the modifications within a margin of (say) -0.10 and +0.10 not much harm can be done.

This is fun.....

Ed

Hey Ed,

Looking forward to your experiments!

Mike

[ed]

Looking forward to your experiments!

I have something running now, it will go into the autoplayer tonight. If you hear nothing no improvement, else I will report. The routine basically updates the PST between 2 iterations with (binary) values between -16 and + 24 based on the height of the corresponding history value. Here is some debug output from a random position:

Code: Select all

White Knight
+----+----+----+----+----+----+----+----+     +----+----+----+----+----+----+----+----+
| 00 | 10 | 20 | 20 | 20 | 20 | 10 | 00 | 8   | 00 | 11 | 21 | 21 | 23 | 21 | 10 | 00 |
+----+----+----+----+----+----+----+----+     +----+----+----+----+----+----+----+----+
| 10 | 24 | 26 | 26 | 26 | 26 | 24 | 10 | 7   | 10 | 25 | 27 | 32 | 21 | 27 | 25 | 10 |
+----+----+----+----+----+----+----+----+     +----+----+----+----+----+----+----+----+
| 10 | 28 | 40 | 50 | 50 | 40 | 28 | 10 | 6   | 01 | 23 | 41 | 51 | 51 | 52 | 29 | 11 |
+----+----+----+----+----+----+----+----+     +----+----+----+----+----+----+----+----+
| 10 | 23 | 36 | 40 | 40 | 36 | 23 | 10 | 5   | 08 | 09 | 39 | 41 | 41 | 39 | 07 | 11 |
+----+----+----+----+----+----+----+----+     +----+----+----+----+----+----+----+----+
| 10 | 22 | 28 | 30 | 30 | 28 | 22 | 10 | 4   | 10 | 17 | 29 | 31 | 31 | 29 | 09 | 11 |
+----+----+----+----+----+----+----+----+     +----+----+----+----+----+----+----+----+
| 00 | 26 | 26 | 30 | 30 | 26 | 26 | 00 | 3   | 00 | 13 | 27 | 31 | 31 | 27 | 12 | 00 |
+----+----+----+----+----+----+----+----+     +----+----+----+----+----+----+----+----+
| 05 | 20 | 20 | 23 | 20 | 20 | 20 | 05 | 2   | 06 | 15 | 20 | 26 | 21 | 21 | 20 | 00 |
+----+----+----+----+----+----+----+----+     +----+----+----+----+----+----+----+----+
| 00 | 05 | 15 | 15 | 15 | 15 | 00 | 00 | 1   | 00 | 05 | 08 | 01 | 09 | 01 | 00 | 00 |
+----+----+----+----+----+----+----+----+     +----+----+----+----+----+----+----+----+
  a    b    c    d    e    f    g    h          a    b    c    d    e    f    g    h 


+------+------+------+------+------+------+------+------+
|   100|   133|   127|   126|  2484|   549|    47|    98| 8
+------+------+------+------+------+------+------+------+
|   100|   690|   207|  6346|    87|   446|   221|    44| 7
+------+------+------+------+------+------+------+------+
|    75|    94|   110|  1235|   554| 27474|   108|   106| 6
+------+------+------+------+------+------+------+------+
|    98|    49|  2848|  1012|   583|  3055|   145|   110| 5
+------+------+------+------+------+------+------+------+
|    49|    92|   226|   225|  1009|   107|    54|   170| 4
+------+------+------+------+------+------+------+------+
|   100|    49|   130|   159|   138|   252|    52|    52| 3
+------+------+------+------+------+------+------+------+
|   257|    91|   100|  2424|   449|   408|   100|    95| 2
+------+------+------+------+------+------+------+------+
|    98|    49|    71|    49|    90|    49|    99|    49| 1
+------+------+------+------+------+------+------+------+
    a      b      c      d      e      f      g      h

Table-1 being the original white_knight_piece_square_table and table-2 the updated one, table-3 the history values. As it seems square F6 is the way to go and got an extra 12 points, the squares on the 1st rank are penalized. Geez, it looks like real chess

No expectations however, first tries seldom do, I will be more than glad if it doesn't score worse, that would mean the idea has a future.

Ed