TalkChess.com

How does one sort without extracting moves into some kind of list-like (or array-like) data structure?

rob wrote: Initially a legality check might seem expensive but it amounts to a move generation on the (single) piece you have in your table (for example your killer move table). This will in general be up to 32 times faster than a full move generation (assuming 16 pieces per side on the board).

rob wrote:Heinz is being very particular in his construction. Essentially, it can be paraphrased as "Look at the (long) list of moves I try before I try anything which requires a (slow) move generation."

1. Hash move, retrieved from the hash table on a hash hit. We get the full move details from the table entry such as source square, destination square, etc., so no move generation is required. A move legality check should be performed.

2. (Skipping for now, this is the MVV/LVA sorted capture moves)

3. Killer moves, retrieved from a tiny killer move table, usually consisting of 2 entries of moves that caused a beta cutoff in some other previously searched branch of the tree. They may cause a beta cutoff again in a new branch of the tree. The killer move data is stored in a tiny two element table, so no move generation is required. A move legality check should be performed.

4. History moves, retrieved from a history table. Again, the table has the details of how to perform the move so no move generation is required. A move legality check should be performed.

5. Statically pre-sorted remaining moves. This will require a move generation and sorting of the generated move data, which is expensive.

Initially a legality check might seem expensive but it amounts to a move generation on the (single) piece you have in your table (for example your killer move table). This will in general be up to 32 times faster than a full move generation (assuming 16 pieces per side on the board).

Heinz is describing a well known method for trying captures in MVV/LVA order that does not require a full move generation, otherwise we should prefer history moves (which are relatively cheap) before the MVV/LVA routine requiring a full move generation.

Rob

rob wrote:How does one sort without extracting moves into some kind of list-like (or array-like) data structure? Heinz asserts this technique is used in virtually every performant chess engine in existence.

if( (aligned = capture_type[location[victim] - location[attacker]] & attack_flags[attacker])) {
  if(aligned & DISTANT) {
    if(!EmptyRay(attacker, victim)) aligned = 0;
  }
  if(aligned) SearchCapture(attacker, victim);
}

rob wrote: "… node-expansion step achieves good move ordering by arranging the sequence of recursive search calls as follows.

1. Hashed move form transposition table (L/U),
2. capture moves in MVV/LVA order (L/U),
3. killer moves (U),
4. history moves (U),
5. statically pre-sorted remaining moves (U).

This ordering scheme enjoys wide-spread use in computer chess because it represents one of the best currently known according to many independent researchers. A nice side effect of the scheme is that it saves precious memory bandwidth because it does not require the creation of a move list prior to history-move selection."

That's quite a trick, sorting all captures into MVV/LVA order without generating any move lists. In other words, there is no move generation performed for MVV/LVA sorting.

hgm wrote: But this is possible; I just implemented something like that in my engine Shokidoki, where I wanted to try a few best drop moves together with the board moves, before having generated all drops. I just remember the 4 drops with the best history score in a short, plus the history value of the 4th drop. Every time after incrementing a history score I test the new score against the latter, and in the rare case that it exceeds it, I have to replace one of the four drops (if it was not in yet) or adapt the score of the lowest (if it was the lowest). This way I can just pull the 4 drops with the best history score from that short list, append them to my list of non-captures, and sort the whole list by history. Preliminary test suggest this gained 70 Elo (in self play), while if I did the same with 8 drops, it broke about even.

One loops through the opponent piece list top-down to get the MVV, and for each victim then loops through the own piece list bottum-up…

As to history moves: he must have used a special data structure…

Of course in the incremental capture-generation scheme that we discussed here recently, the capture list would be represented by a 256-bit bitmap, each bit correstponding to an (attacker, victim) pair in MVV/LVA order. So you would just have to extract the set bits to loop through the captures in the desired order, and switch on or off bits in the incremental update.