Writing the fastest move generator. Up to 4BNodes/s

[chessbit]

You check whether the position reached by a move has already been searched. But you don't do that only in the leaf nodes. (Where in perft it would indeed be pretty useless, as you just want to count those, not process them in any other way that you could save time on.) You do it in every node in the tree. And that is also very useful in perft. The position after, say, 1. e3 d5 2. d4 is the same as that after 1. d4 e5 2. e3, and when calculating perft(7) you don't want to do the perft(4) from that position twice.

Engines store moves in a list, because they typically want to search them in a different order than they were generated. Unlike perft, the size of an alpha-beta tree is highly dependent on the move ordering. A factor 2 in speed that you might gain by skipping the sorting can easily mean you have to sort a thousand times larger tree.

I just had a wrong implementation of the TT initially, now it's working. Interestingly, when used with threads in the faster version of my engine, it is only a little bit faster than in my future chess engine version (with a move array that can be sorted). The chess engine version doesn't abuse templates as much, so the binary and compile time are much smaller. I guess it has less TT hits, but I will verify the numbers.

Code: Select all

Depth:          9
Nodes:          2439530234167
Time:           33500 ms
Average:        72821.3 Mn/s

Code: Select all

Depth:          9
Nodes:          2439530234167
Time:           34910 ms
Average:        69879.3 Mn/s

Edit: by not using the TT at depth 1 (bulk counting), it is much faster, so I guess I posted too quickly Don't mind my rambling then

Code: Select all

Depth:          9
Nodes:          2439530234167
Time:           17239 ms
Average:        141512 Mn/s

[Aleks Peshkov]

Engines store moves in a list, because they typically want to search them in a different order than they were generated. Unlike perft, the size of an alpha-beta tree is highly dependent on the move ordering. A factor 2 in speed that you might gain by skipping the sorting can easily mean you have to sort a thousand times larger tree.

I store all legal moves in the bitboards (per each 16 pieces) and currently do not sort anything.

I generate moves one by one picking from the move bitboards in tactical order: good MVV/LVA captures, Killers, CounterMove, safe non-captures for Queens, Rooks, Bishops/Knights, then pawn moves, then bad captures and noncaptures in LVA order and at last king moves.

There are many more possibilities to improve move order without history heuristics. For example, I plan to test "hot pieces heuristic" -- queque of individual pieces that recently made fail highs and hot squares: the good square queque per each individual peice, where pieces landed for fail high. My main current problem that I cannot directly compare value of moves between different pieces without global history heuristic table.

[hgm]

Interesting. I presented something similar in Thhe Mailbox Trials series of postings (an engine concept that generated captures in MVV/LVA order). I did not spend much effort on optimizing the non-captures, though. Only some 15% of the moves made in the tree were non-captures.

What do you think of 'analogy probing' for improving (non-capture) order, where in cut-nodes you would probe the TT in an attempt to try the same sequence of cut-moves as in a sibling line? So basically a killer heuristic, but for an entire line.

[Aleks Peshkov]

Interesting. I presented something similar in Thhe Mailbox Trials series of postings (an engine concept that generated captures in MVV/LVA order). I did not spend much effort on optimizing the non-captures, though. Only some 15% of the moves made in the tree were non-captures.

What do you think of 'analogy probing' for improving (non-capture) order, where in cut-nodes you would probe the TT in an attempt to try the same sequence of cut-moves as in a sibling line? So basically a killer heuristic, but for an entire line.

I have read about your TT killer idea. Sounds interesting but I am trying the most cheap ideas so far.

I had many hopes about trying the last moved piece first at ply-2, it does not gain or loss anything (positive, but <5 Elo), the same was recapture first. I have tried killingSquare[Color][PieceType][From] = To idea, it is -Elo.

[OliverBr]

mine can actually make/unmake moves

I think the community has settled on copy/make being superior to make/unmake, especially in light of NNUE updates. Modern SIMD makes copying even large boards cheap.

Not only for NNUE.
OlIThink does actually perform better with copy(restore)/make/copy(backup) than with make/unmake. It can do both.

Code: Select all

for (i = 0; i < mp.n; i++) {
    Move m = pick(&mp, i, -1);
    ...
    if (!pos.hash) memcpy(&pos, &P, sizeof(Pos));
    doMove(m, c);

    int w = ...

    memcpy(&P, &pos, sizeof(Pos));
    ...
}

PS: In the Java version, however, it's not the case.