CMH question

[xr_a_y]

Hi,

I'm having a look to CMH (sorting, pruning and extenting) and I take as a basis of reading the, always very clear, Xiphos code.
Something I don't get in this heuristic is that it uses data from opponent turn (unless I missed something ...) :

In Xiphos code : MAX_CMH_PLY=2, so that when i==1 then pos = sd->pos - i; is opponent data ?

Code: Select all

static inline void set_counter_move_history_pointer
                           (int16_t **cmh_ptr, search_data_t *sd, int ply)
{
  int i, m_to;
  position_t *pos;

  for (i = 0; i < MAX_CMH_PLY; i ++)
  {
    pos = sd->pos - i;
    if (ply > i && pos->move)
    {
      m_to = _m_to(pos->move);
      cmh_ptr[i] = sd->counter_move_history[pos->board[m_to]][m_to];
    }
    else
      cmh_ptr[i] = NULL;
  }
}

[lucasart]

Hi,

I'm having a look to CMH (sorting, pruning and extenting) and I take as a basis of reading the, always very clear, Xiphos code.
Something I don't get in this heuristic is that it uses data from opponent turn (unless I missed something ...) :

In Xiphos code : MAX_CMH_PLY=2, so that when i==1 then pos = sd->pos - i; is opponent data ?

Code: Select all

static inline void set_counter_move_history_pointer
                           (int16_t **cmh_ptr, search_data_t *sd, int ply)
{
  int i, m_to;
  position_t *pos;

  for (i = 0; i < MAX_CMH_PLY; i ++)
  {
    pos = sd->pos - i;
    if (ply > i && pos->move)
    {
      m_to = _m_to(pos->move);
      cmh_ptr[i] = sd->counter_move_history[pos->board[m_to]][m_to];
    }
    else
      cmh_ptr[i] = NULL;
  }
}

It's best to move away from code, and try to understand the idea instead. Then you can implement it your own way.

First there is history: History[move], taking a move as [color][from][to], and giving a score, used for sorting moves, based on how successful it is at raising alpha.

Then all the ways of updating such a table. You want shallow depths to update less, as they are more frequent, and you need some absolute bounds to avoid overflows. Testing is key, there is no absolute truth beyond the experimental evidence. But what seems to work best is the history gravity pionnered by Stockfish, and later copied by everyone else (including Xiphos, Ethereal, Demolito, and probably most strong engines).

Now, history still has the problem of being too global, so every node updates it, and it's hard for it to gain specific / precise knowledge. In a sense, hostory is similar to neural networks, and we need deeper networks with more inputs.

So, again invented by SF, comes CounterMoveHistory[prevMove][move]. Such a table will be too big: 2*64^4 elements. So we shrink the prevMove part into [piece][to] instead of [from][to].

Then, pushing the idea further, SF invented FollowUpHistory, which takes [2movesAgo][move], with the same encoding, ie. piece x square x color x square x square.

Then, as CMH and FMH use quasi identical code, it makes sense to factorize this code, which is what you're looking at here.

[xr_a_y]

Thanks. That's what I understood. But I still don't get why Xiphos is using index -1 in its stack (and not -2 for FMH).

[lucasart]

Thanks. That's what I understood. But I still don't get why Xiphos is using index -1 in its stack (and not -2 for FMH).

Because indexing starts at zero. CMH is i=0, and FMH is i=1.

[xr_a_y]

Thanks. That's what I understood. But I still don't get why Xiphos is using index -1 in its stack (and not -2 for FMH).

Because indexing starts at zero. CMH is i=0, and FMH is i=1.

I think I get it now !
CMH is about a reply to an opponent move while FMH is about a continuation to our previous move ?

[PK]

One good way of telling about CMH is what Lucas said: it is basically local history table. The other way goes as follows: first you notice that certain moves tend to be refuted by the exact same move, so you create a table indexed by coordinates of a refuted move, save the refutation there and upon encountering the same move you sort the refutation high, just after the killers. Then you think: "wait, why did I restrict myself to just one refutation move". Then you implement CMH and use it for sorting. Finally you think "with such valuable data I can do much more than sorting, for example influence shape of search tree".

[lucasart]

Thanks. That's what I understood. But I still don't get why Xiphos is using index -1 in its stack (and not -2 for FMH).

Because indexing starts at zero. CMH is i=0, and FMH is i=1.

I think I get it now !
CMH is about a reply to an opponent move while FMH is about a continuation to our previous move ?

Yes.

Coming back to implementation, you can use piece x square x color x square x square as implemented in SF (and most engines). And it sure works fine, elo wise.

But, in Demolito, I value code simplicity, so instead I index by moveHash % N, where N is arbitrary (smaller reduces memory usage, but increases collisions). That way I don't need a search stack at all and the search stays in textbook recursive style, not a mix of recursive and iterative.

By moveHash, I mean the xor difference after ^ before, from Zobrist keys before and after a move. This encodes a move much more precisely, in fact.

PS: Of, course N should be a power of 2, so that the compiler can turn the expensive % into a cheap &.

[hgm]

Has it been investigated whether these counter-move and follow-up specifities are also beneficial for the killer heuristic instead of history? One could also keep a short list of moves to be tried as potential killers, in response to the move at some previous ply, rather than keeping complete statistics on all possible moves. When you swap a move that raises alpha with the one above it in the list (or replace the last move in the list by it when it was not yet in the list) the ordering in the list will become a poor-man's approximation to a sort-by-history-score when the list gets longer, as the moves that work most often will have the largest 'buyancy', and float to the top.

This would require much less memory than maintaining full statistics, and the moves can be tried directly from the list without the need to first generate all moves, look up their history and sort them by it.

[D Sceviour]

Then all the ways of updating such a table. You want shallow depths to update less, as they are more frequent, and you need some absolute bounds to avoid overflows. Testing is key, there is no absolute truth beyond the experimental evidence.

The Xiphos formula limits history scoring to a depth of 16. After that, all counter moves are valued equally. What happens to the value of history moves at very deep depths and why are they not significant?

[xr_a_y]

In Minic, I was using a [Piece_with_color][to] history table
I'm now trying a [color][from][to] history table
and a [Piece_with_color][to][Piece_with_color][to] counter history table

I wonder if I can use a combination of the 3 scores to build history score ...