Quick history move

[hgm]

I am looking for an alternative to the history heuristic for which I don't have to generate all those non-captures first. Like killer, where you can search them after just testing their pseudo-legality. I was thinking of the following:

I keep a small hash table of cut-moves, with 256 entries, say. Of these, 32 moves are 'ranked' 1-32. If a beta cutoff occurs, the entry in the hash table corresponding to the move will be treated as follows:

* If it already contained that move, and was ranked, it swaps ranking with the move that was ranked just above it.
* If it already contained that move, and was not ranked, it gets rank 32, and the old number 32 of the ranking becomes unranked.
* If it contained another move, and was not ranked, the new cut-move replaces the old.
* If it contained another move, and was ranked, the new cut-move is out of luck, and discarded.

This should make moves that frequently cause cutoffs 'bubble' towards the top of the ranking list, at the expense of moves that cause cutoffs less frequently. After searching the killers, the engine could go through the top of the ranking list, and treat the moves there the same as it treats the killer moves: search them when they are pseudo-legal in the current position.

To find moves of a given rank, a table of 32 numbers would hold the index in the move (hash) table for each given rank. This makes it easy to find the move the current cut-move should be swapped with, and to find the moves at the top of the list when we want to play them.

[Michael Sherwin]

Sounds inefficient because of all the moves in the hash that do not exist at any given time. I think that two history tables, one of long period and one of short period, might be a good idea.

[hgm]

Why would that be inefficient? Most moves will be 'intrinsically useless', and never cause any cutoffs. For those moves there is nothing to keep track of in the first place, so who cares if they are not in the move hash? And the size of the move hash table can always be increased.

Conventional history tables do not give me a move. I either would have to come up with the moves myself (through non-capture generation), look up the history score for each of them, and extract the one with the highest score. Or I would have to run through the history table for extracting the highest history scores, and test those moves for pseudo-legality. (Which seems even slower, as the history table could be a hundred times larger than the average number of moves.) The move-hash ranking supplies moves directly. My only worry is that too many of the successful cut-moves would not be pseudo-legal in a given position. (But how could they cause frequent cutoffs if they are not possible in most positions?) Then you would have to test a lot of moves near the top of the ranking for being pseudo-legal.

The test for pseudo-legality can be quite cheap, however. The move hash should not only store from-square and to-square, but also the moved piece (and perhaps the victim, if not only used for non-captures). If the from-square contains the right piece that already guarantees the to-square is a potential target, and you would only have to test whether the move is blocked (and only if it is a distant move). Perhaps instead of the to-square the table should record direction and distance, so that you can test the distance for being > 1, and check the free path in that direction if this is the case.

What could be a problem is when two frequent cut-moves map to the same entry in the move hash. One of those would get ranked, and then exclude the other from getting in. I assumed that 256 entries was enough to make this chance pretty small. In principle it could be improved by making a 2-way hash table, where each move can map to 2 entries. It would be a bit more work to determine when there has been a hit, but since you only do that when you get a cutoff due to the score from a search, the amount of work done there must be negligible compared to that of that search. If a cut-move would map to an entry that already contains another ranked move, you could then try the other entry where it then still could replace an unranked move.

[Ras]

Quiet move generation doesn't take a relevant amount of time because most of it is spent in QS anyway. It's more relevant whether it can improve the move sorting and cut off whole trees.

[hgm]

True, but it is by no means certain that the proposed metod does that any worse than conventional history. One example I can see is that it prefers recently successful moves over older ones.

[Cardoso]

Interesting idea, it could work well near the tips where we need a fast retrieving method for ordered moves.
I have a few doubts:
1 - Could you please describe in details the hash entry?
Does it have the full 64bit hash key along with the move data?
2 - Could you please give details on probing? I'm not sure if you use the hash key for probing.
Maybe you are only using hashing for storing.

thanks,
Alvaro

[hgm]

This has nothing to do with the position hash key. I usually store moves in an int32, where the high byte is the sort key, and the lower 3 bytes the fromSqr, toSqr and possibly other (e.p. or promotion) info. For the purpose of the move table the sort key would be overwritten by the moved piece (type or number), or packed with it in a different way. The hashing works by multiplying this move format with some magic constant, and shifting it right 24 bits, to get an 8-bit index to which all components contributed. The table contains the moves themselves, so that there never is any chance on false hits. Each entry also has a byte to hold the ranking number of the move it contains.

Code: Select all

#define NONE 64
int moveHash[256];
char ranking[256];
char histMove[32];

  // on cutoff
  unsigned int packed = cutMove << 8 | piece; // shifts out sort key
  int index = packed*MAGIC >> 24;
  if(packed == moveHash[index]) { // hit
    int r = ranking[index];
    if(r == NONE) { // was unranked
      ranking[histMove[31]] = 0; // unrank old 31st
      ranking[index] = 31; // and rank new one at bottom
      histMove[31] = index;
    } else if(r) { // was ranked and not yet at top
      int above = histMove[r-1];
      ranking[index] = r-1; // promote one rank
      histMove[r-1] = index;
      ranking[above] = r; // demote one rank
      histMove[r] = above;
    }
  } else { // miss
    if(ranking[index] == NONE) moveHash[index] = packed;
  }

If we want a smaller chance for a good move being kept out of the table by a not-so-good ranked move, (which, with the sizes in the example, is 12.5%), we could replace the test for a hit by

Code: Select all

 if(packed == moveHash[index] || packed == moveHash[index ^= 1]) { // hit

and in the miss case

Code: Select all

  if(ranking[index] == NONE || ranking[index ^= 1] == NONE) moveHash[index] = packed;

That would reduce the fraction of non-eligible moves to 1.5%.