DarkThought sorts MVV/LVA without looking at any moves?

[rob]

I came across a surprising statement in Heinz's thesis, "Scalable Search in Computer Chess".

Heinz writes (Appendix A.4.1 Node Expansion):

"… 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.

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.

Rob

[jdart]

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

You don't need to avoid generating a list. But you can avoid sorting. The list of capture moves is almost always small. So you can sort it or you can just iterate through the moves each time and pick the best unused one.

I generate using MVV/LVA, but then when it is time to pick a move out of the array I do a static exchange analysis on any moves with MVV-LVA <= 0, and moves that show a losing SEE value are put into a "losers" list and tried last in the sort order.

--Jon

[rob]

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]

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

Correction: It's the branching factor or number of moves that determines the speed up factor, not the number of pieces on the board.

Sorry for the mistake.

Rob

[kbhearn]

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

MVV/LVA could be generated one at a time in order thus avoiding ever actually making a list... Not saying it's a great idea, but depending on structure of the engine in general it might not be horrible.

The 'well known' option is to generate only captures and have a short list which then can be sorted quickly with primitive search routines like selection sort or bubble sort.

History moves should come after MVV/LVA captures because

1) they are quiet moves, captures are more likely to cause a cutoff and messing up your move ordering (an exponential factor) is not worth any amount of time saved in move generation (a constant factor).

2) they do require a full move generation - the history table is going to contain information on thousands of moves that are not legal in your current position, it's not like killers where it's just a couple of moves with a high probability of being legal and a high probability of being good if it's legal. Instead you generate the legal moves, look up their history value, and sort based on it.

[hgm]

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.

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 to get the (potential) LVA capturer. One then only has to test whether the relative positioning of attacker and victim is such that the attacker could indeed make that move, and in case of a distant slider attack, verify that the intervening squares are empty.

Code: Select all

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

As a micro-optimalization you start with the Pawn attacks on any given victim by testing for enemy Pawns on the two board squares from which they could come. That is usually faster than looping through 8 Pawns in the piece list to test if any of them attacks. You then only have to loop through 8 pieces in the piece list to test for alignment, and occasionally (in the rare case there is alignment of a slider) for blocking. Another refinement that is needed is the case of equal-valued victims. You really have to loop through victim groups in the outer loop, then through attackers, and then through victims in the group.

This is actually quite competitive, because you can stop generation as soon as you get a cutoff, or when you reach the futile victims. Even if you have to do it for all victims it is not extremely expensive, comparable in cost to generating all moves of a piece, and looking if any of them are captures (as the average number of moves a piece has is not that much lower than 8). Of course it might pay to stash 'suspect' captures (High x protected Low) in a short list, postponing their search to after the others.

Note that the question "can the piece at X move to Y" can be answered by a similar ("0x88-")test much faster than by generating all moves of X. So it can alsobe used for testing validity of killers.

As to history moves: he must have used a special data structure for the history table that would keep the items with the highest history scores rapidly accessible. Looping through a history table of 64x64 (or perhaps 16x64) elements to extract the highest score, and then testing if the move is possible (which is unlikely, as most positions have far fewer than 4096 legal moves), and doing it again if it was not, until you have a move, is not competitive at all.

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.

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.

[Evert]

"… 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.

Read carefully: he doesn't say that there's no move generation, he says there's no need to generate a move list - and indeed there isn't because you can generate single moves:

1. Only generate the hash move. You might call this verifying that it's legal.
2. You can generate moves that capture a queen before moves that capture a rook (etc.) and then pawn captures before knight captures (etc). You need a piece-list (or bitboards, which act similarly) to do this efficiently, but there are good reasons for having those anyway. If you do staged generation there is no need to store them in a list.
3. Again, you only need to verify that the killer moves are actually legal.

It isn't before you get to history moves that you run out of tricks that allow you to only look for specific moves that make it unnecessary to look at the entire board. Then you do need to generate all moves and place them in a list and sort them.

[Evert]

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.

Impressive. I keep separate killer and history list for drop moves, but I don't think they were worth nearly as much. I'll have to give it another look.

[hgm]

Well, this was based on 100 games only, so it could be a fluke. A 60.5-39.5 score is better than 2 sigma, though, so it seems likely it must be an improvement. Today I will run a longer test, and also try it against SPEAR. I guess an additional benefit of the patch, other than just improving move sorting, is that at d=1, where I otherwise would only generate check drops, it can now also try a few drops from the history table.

[rob]

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…

In other words, perform an O(n^2) operation at each node in the tree, and the tree itself is growing exponentially in the number of nodes. Assuming very few pieces are en prise, in other words, a relatively quiet position, wouldn't this be disastrous?

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

My mistake, Heinz states that he performs a move generation while doing history moves.

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.

This looks a lot more plausible than the above idea. But it seems to me one of only two possibilities exist:
a. Incremental generation of captures, one piece at a time. Allows for early termination via a beta cutoff without generating all captures. But then we know we are not performing a proper sorting into MVV/LVA.*
* (unless we need to prioritize only one of MVV or LVA, see below)
b. Generate all captures, allowing for sorting correctly into MVV/LVA. In other words, a full move generation, which Heinz claims is *not* needed to accurately sort all captures into MVV/LVA order.

I now realize that it's possible to perform accurate MVV or LVA sorting without performing a full move generation in advance of the sort, but this can only work if one or other sorting requirement is needed (we can do MVV or LVA, but not both). For example, if only MVV matters, then we move generate one piece at a time starting with the enemy queen(s), then proceed to the enemy rooks, etc.

But I have consistently seen the ordering described as MVV/LVA, implying priority is given to one (e.g., MVV) and then, within a given tier of MVV (e.g., all captures of the enemy queen), there is a secondary sort to produce a list with sorted LVA as well.

You can't have accurate sorting on both MVV/LVA with incremental ("one piece at a time") move generation. It requires generating all captures in advance and then sorting them.

At least, that's what I think. But Heinz states that he has an algorithm that does sorting on both MVV and LVA without generating a list of all moves. I would think what he's saying is he's somehow doing it incrementally, looking at just one piece (the enemy's or his own) and then moving on to the next piece.

My thinking is what he's describing is impossible.

Rob