Stockfish 1.5 64-bit and 32-bit do not behave the same.

[mcostalba]

Interesting.

As I expected there are _no_ difference in the std::sort implementation from 32 to 64 bit as long as you stay with Micorsoft STL library.

BTW 20880860 is the number I have also on my PC

Now if you try using the gcc implementation of std::sort(), as example trying under Linux or under Windows with MinGW you will get a different number with std::sort(), but the _same_ number 22205054 with std::stable_sort()

BTW the Nodes/second figures does not seem to show a big regression with std::stable_sort(), although are not reliable because node count is different, anyhow I will defenitly do a test match with real games with std::stable_sort instead of std::sort and if result is acceptable new version of SF will show the same numbers on any platform, for the joy of everybody

[Eelco de Groot]

Thanks for the explanations and experiments guys!

I was thinking that this probably has a lot to do with the Late Move Reductions and the tactical search in Stockfish. If the search depth is not very high, a lot of moves are cut off that especially if they are otherwise allmost equally sorted, are still potentially interesting, i.e. they are candidates for producing a beta cut-off. Maybe it would be an idea, if moves are equally sorted, to somehow be able to sort them in rotation, meaning if you have n moves with the same sorting order and the LMR cut-off falls precisely across this range, each move would still have a chance of being sorted to the top of this range and therefore searched, at the expense of other moves in this range. Next time you visit this node it would be ideal to search another move from the same range because obviously if the same move is in that place as the last time you visited the node, this move you searched then did not reach a beta cut-off, because then it would have become the TT move.

The unstable sort does a similar thing but maybe it could be improved. I don't know the actual algorithm, maybe the effect is already good for reaching a different sorting order each time.

I already have a slight modification to the Late Move Reductions in Ancalagon, this is more critical I think in Ancalagon because its average search depth is just much lower, I search one extra move each time but with a lower search depth. This as a form of IID. It probably does not make very much performance difference but it still seemed a good idea.

But I had not thought of a good way to introduce some of the "rotation-sort" in the same spot, with that you could search for instance one additional move, but a different move each time you visit the node. I would probably use a reduced depth there as well. The results with the unstable sort by Marco and Dann's experiment to me would seem to indicate that it could help reducing node-counts.

This is the point I think where the move order and std::sort have the greatest impact because of the pruning taking place. Code from Ancalagon in the null window search routine, search()

Code: Select all

// Futility pruning
if (    useFutilityPruning
    && !dangerous
    && !threatreplyExtension
    && !mateThreat
    && !moveIsCapture
    && !move_promotion(move))
    {
        // History pruning. See ok_to_prune() definition
        if (   moveCount >= 2 + int(depth)
            && pruningAllowed
            && ext == DEPTH_ZERO) 
        // At the moment moves perpetualExtended are not labeled as 
        // dangerous, so this last condition makes some difference.
    {
            if (moveCount >= 3 + int(depth)) 
                continue; // Here you would like to introduce some "rotation".
            else newDepth = newDepth - 2*OnePly; // One extra move searched with reduced depth. Form of IID.

    }

Eelco


pruningAllowed does not exist in this form in Stockfish, it
is the same as ok_to_prune()

Code: Select all

bool pruningAllowed = ok_to_prune(pos, move, ss[ply].threatMove, depth);

but I'm using it earlier to dermine some extensions so it had to be put into a boolean so as not to call the same ok_to_prune() routine twice. I still have to test for the move not being a tactical move here etc. because that is not put into ok_to_prune and not yet determined when I call the routine beforehand, this is a bit messy.