sort every moves or pickNext

[xr_a_y]

I was wondering if a pickNext thing will be faster than sorting all moves. Which looks for me not clear at all without testing.

So I try this pick next function based on std::min_element (yes my MoveSortOperator is reversed)

Code: Select all

const Move * MoveSorter::pickNext(MoveList & moves, size_t & begin){
    if ( moves.begin()+begin == moves.end()) return nullptr;
    START_TIMER
    auto it = std::min_element(moves.begin()+begin,moves.end(),MoveSortOperator());
    std::iter_swap(moves.begin()+begin,it);
    STOP_AND_SUM_TIMER(MoveSorting)
    return &*(moves.begin()+(begin++)); // increment begin !
}

instead of calling std::sort on the whole vector of move.

So, instead of

Code: Select all

generate(moves)
score(moves)
sort(moves)
for(auto it = moves.begin() ; it != moves.end() ++it){
   ...
}

I now have

Code: Select all

generate(moves)
score(moves)
int count = 0;
while ( (it = pickNext(moves,count)) ){
   ...
}

This way, the pickNext function is called around 8 or 9 times more than generate, which is clearly more than Minic EBF of course but less than the mean number of moves per position.

So it is better ???

Answer seems to be yes in terms of nps, maybe around a 3% or 5% increase. A test is in progress to verify that Elo-wise.

[Sesse]

Ideally, I guess just generate the good moves first, instead of generating and then sorting? E.g., if you sort good captures first, generate them before anything else.

The canonical structure for this would be the binary heap, but it suffers from extreme branch misprediction. (A winner tree is better in that aspect, since it can use min/max instructions.)

[xr_a_y]

From my test
generation / scoring / sorting are more of less equal in time, each 10% of Minic load.

[mhouppin]

Well, as you refine your pruning techniques and your branching factor decreases to come around 2, I think it would definitely be worth using a pickNext function (as 90% of the generated moves will get discarded anyway, so no need to sort them).

An even better approach could be to generate moves as they are needed y the search (so first only the TT move, then the captures sorted by SEE + killers, then maybe the checks, then the quiet moves), saving even more time on move generation, scoring and sorting.

[abulmo2]

In Amoeba I started with a legal move generator and sorted the full move list. Now I use a staged move generator but still sort partial list of moves (good capture, quiet moves, bad captures). Just picking the best move of an unsorted list of moves did not work well in Amoeba. I think my insertion sort algorithm implementation works well on short list of moves pre-sorted during the move generation. I also got some speed enhancement by avoiding sorting functions from the standard (D) library, and using my own simple code.

[bob]

There's a good word to follow in computer chess engine design: Procrastination: (n) the action of delaying or postponing something. In this case, postpone the sort because you will be doing it at two types of nodes that are bad. (1) nodes that are going to fail low, where order is not so important; (2) this is the important one, fail-high nodes. If you go to all the effort of sorting the entire move list (most likely O(N^2/2, or N log(N) if you go out on a limb) and fail high on the first move, you wasted a ton of effort. Best answer is some sort of NextMove (Crafty) or a flavor of PickMove(), where you use a simple selection sort. This is one pass over the moves to pick what you think is the best, then the next time you make one pass over the remaining N-1 moves, etc. If you get a cutoff, you eliminate the effort you would have expended to sort the moves.

You can take this much further. For example, search the transposition move before generating anything. Then generate captures only and order those with MVV/LVA or whatever. Then come the non-capture moves starting with killers. Search those before generating the remaining non-capture moves. Again avoiding any sorting or whatever.

Overall the idea is, never do now what you can do later (and you might not even have to do it at all.)

[Patrice Duhamel]

In Cheese I also use staged move generation but picking moves instead of sorting them is slower.
Last time I tested it was almost the same speed for picking captures but slower for picking quiet moves.

Does picking moves works only with very good move ordering ?

[bob]

If you think about "picking" over sorting, the first gain comes from not generating things. IE try hash move BEFORE generating a single move. Then generate captures, sort according to whatever criteria you want. Then try the killer moves (quiet since captures are not allowed in them) without generating anything further. Now you can generate the rest of the moves. If you fail high on hash move, you did no generation or sorting of any kind... Ditto for killers where all you have generated so far are captures...

[Patrice Duhamel]

If you think about "picking" over sorting, the first gain comes from not generating things. IE try hash move BEFORE generating a single move. Then generate captures, sort according to whatever criteria you want. Then try the killer moves (quiet since captures are not allowed in them) without generating anything further. Now you can generate the rest of the moves. If you fail high on hash move, you did no generation or sorting of any kind... Ditto for killers where all you have generated so far are captures...

Yes, this is what I am doing, trying hash first, generating captures only, then killers, generating quiets, and trying bad captures at the end.

I don't understand why picking moves for captures or quiets instead of sorting them after generating + scoring is slower in some engines.

[hgm]

Sorting by picking the best every time is an O(N^2) process, which can get pretty slow if there are many moves (like there typically would be for non-captures). Using quick sort for sorting the whole lot at one is only O(N*log(N)), which is significantly less work if N is large. The picking speculates that you will get a quick cutoff; to find the best move is only O(N). But not every node is a cut node; about half of them are all-nodese, where you eventually search all moves.

Of course you can try to be clever, and use quick sort in stages: first split the entire set into a lhigh and a low half, then split the upper half in to, then the upper quarter, etc. This is only O(N), and would give you the best move. Every time you run into a sub-section that was not yet completely sorted, you fist complete the quick sort of that sub-section. If you get to the end of the move list you would have done a full quick sort, otherwise only part of it.