Move generation: staged vs all-at-once

[CThinker]

I have done both, and in the end, I went with the phased move generation scheme. Version 3.x of Thinker, and older versions of 4.x always generate all moves. Later versions of 4.x and all of 5.x generate moves in phases.

First, as has been mentioned, most of the time, the non-captures will never be used. The captures/promotions are usually good enough. After that, the killer moves are usually good enough.

Second, I sort the non-captures using history counts. The history counts get better after the captures and killer moves have been searched. So, the ordering of non-captures is better.

Third, in Thinker, sorting N moves and then sorting M moves is faster than sorting N + M moves, considering that the sorting algorithm in Thinker is order N^2 (the simplistic bubble sort).

[Bill Rogers]

I have a puzzeling question and that is how do you generate capture moves only without generating all moves to see if it is a capture?
And ( I know this is not the proper wat to start a sentence ) if you have to generate all moves then why isn't a center control squares included in the initial sort as this then gives you a good starting point for all future generated moves?
Bill

[bob]

I have a puzzeling question and that is how do you generate capture moves only without generating all moves to see if it is a capture?
And ( I know this is not the proper wat to start a sentence ) if you have to generate all moves then why isn't a center control squares included in the initial sort as this then gives you a good starting point for all future generated moves?
Bill

For bitboards it is trivial. Normally, to generate all moves, you create a "target square mask" that contains a 1 everywhere except for squares that contain your own pieces. You then complement this mask and hang on to it. When you generate any moves, the first thing you do is AND the move bitmap with the mask you saved, which excludes any move that would capture your own piece.

To generate captures, you change the mask to contain only 1 bits for the opponent's occupied squares, 0's everywhere else. Now you generate moves, AND with this bitmap, and it only leaves moves that capture opponent pieces, all others are "gone".

[bob]

I have done both, and in the end, I went with the phased move generation scheme. Version 3.x of Thinker, and older versions of 4.x always generate all moves. Later versions of 4.x and all of 5.x generate moves in phases.

First, as has been mentioned, most of the time, the non-captures will never be used. The captures/promotions are usually good enough. After that, the killer moves are usually good enough.

Second, I sort the non-captures using history counts. The history counts get better after the captures and killer moves have been searched. So, the ordering of non-captures is better.

Third, in Thinker, sorting N moves and then sorting M moves is faster than sorting N + M moves, considering that the sorting algorithm in Thinker is order N^2 (the simplistic bubble sort).

I've not seen anyone physically sort the move list for history moves. I always used a "selection" sort approach, which means making one pass over the list to pick out the move with the highest history counter. Then repeating when you want another move. After a few of these, you stop doing the history test and just take 'em in order since apparently order doesn't mean anything since this is an ALL node.

Doing this, you get (say) O(4*N) rather than O(N*N) if you just use history to select the first four moves and then give up and take the remainder in order generated. This is certainly more efficient.

[mcostalba]

I've not seen anyone physically sort the move list for history moves.

Toga does this, while Glaurung does as you explained in your post, in Glaurung the first 12 moves are picked up in order the others are taken as they come.

I have tried to change that value, but it seem 12 is a lucky number here

[wgarvin]

I have a puzzeling question and that is how do you generate capture moves only without generating all moves to see if it is a capture?
And ( I know this is not the proper wat to start a sentence ) if you have to generate all moves then why isn't a center control squares included in the initial sort as this then gives you a good starting point for all future generated moves?
Bill

For bitboards it is trivial. Normally, to generate all moves, you create a "target square mask" that contains a 1 everywhere except for squares that contain your own pieces. You then complement this mask and hang on to it. When you generate any moves, the first thing you do is AND the move bitmap with the mask you saved, which excludes any move that would capture your own piece.

To generate captures, you change the mask to contain only 1 bits for the opponent's occupied squares, 0's everywhere else. Now you generate moves, AND with this bitmap, and it only leaves moves that capture opponent pieces, all others are "gone".

I think the other part of the answer, is that with bitboards, if you know which squares are "occupied", there are various techniques (such as magic move generation) that with O(1) effort, can produce a bitboard of all the squares your slider can attack. You then AND that with the "squares containing enemy pieces" bitboard and you have all of the pieces that can be captured by this slider, *without* having to iterate over all the intermediate squares like you might in a mailbox engine.

[sje]

A chess primer will tell the beginner to always examine an opponent's last move and use that to help select a move. This works for humans who can determine the "tactical delta" created by a move: some squares get new attacks, some squares lose old defenses, etc.

Yet how many chess programs do this? Some might have some code to try and capture the last piece moved, but that's about it.

With all-at-once generation, it's much easier to fashion move ordering to take advantage of the beginner's advice. Bitboards that describe changes due to the last move are quickly and easily constructed, and these can be use in ordering moves when all moves are guaranteed to be present.

Ideas:

1) Capturing the last moved piece, preferably by a piece newly attacked.

2) Adding defenses to newly attacked pieces, or moving those insufficiently defended.

3) Capturing or attacking newly undefended pieces, or moving pieces to newly undefended squares.

[Greg Strong]

What I've been meaning to try is to generate moves in stages at expected CUT nodes and generate all moves at expected ALL and PV nodes. That seems the most logical to me.

[sje]

1) O(n^2) should be avoided where feasible. I have been experimenting with the gcc version of the standard function qsort() for ordering move-score pairs (eight bytes per record, four byte key) and it works well running O(n * log n). I suspect this is true in part because of 64 bit hardware and in part because it avoids the worst cases when the entire move vector needs to be scanned and searched that would otherwise cost the full O(n^2) effort.

2) Consider the case of when there are a typical 32 moves present. Repeated linear scanning will cost 1,024 operations in the worst case while qsort() will cost about 160 operations an any case. If more than five passes are needed by a linear scan, then qsort() wins. If the linear scan is at an ALL flavor node, qsort() wins big.

3) A homebrew version of qsort() with hard coded sizes and an inline comparator function should be even faster than the regular qsort(). I haven't tried this yet.

4) A lot of move ordering ideas that appear in public implementations work on a per-move basis and so fail to look at more global issues with the other moves and with the board. It is unreasonable to expect much of MVV/LVA or the like when the mover's queen is hanging.

5) How about a conditional compilation of the move ordering mechanism that would track the success of the various ordering heuristics? This could be more efficient than the alternative of many, many test runs. It could be possible to correlate the relative success of the ordering functions with certain characteristics of the position, the last move or two, etc. and use this data to adjust move ordering weighting dynamically.

[CThinker]

I've not seen anyone physically sort the move list for history moves.

This makes for a very compact code. Each phase is nothing more than a call to some move generator. It is assumed that the move generator will order the moves (or it can choose not to).

Its something like:

Code: Select all

TMoveGenerators MoveGenerators = {HashMoveGen,KillerMoveGen,GainingCapturesMoveGen,NonCapturesMoveGen,LosingCapturesMoveGen};

GetNextMove()
{
    while(true)
    {
        if (there is a move from the current move list)
        {
            get (pop) the move from the list;
            return the move;
        }

        go to the next move generator;
        if there are no more move generators
            return "no more moves";

        use the current move generator to populate the move list';
    }
}

The GainingCapturesMoveGen and the LosingCapturesMoveGen are related, in that, the later simply returns the moves that the former does not.

The use of such 'patters' is the reason for the simplicity and compactness of Thinker.