Lazy move generation and move ordering

[theob]

Hi,

Right now I have a legal move generator on which I perform a basic move ordering (captures first and non captures last but without SEE yet so this is quite bad). My move generator is not lazy and I am wondering if it is possible to mix lazy move generation and move ordering ?

I have no clue about it. My feeling is that it is maybe pointless because there is not such a big difference between generating all the captures in order to do SEE and then include all the quiet moves one by one (or piece by piece) between the "hopefully good" captures and "hopefully bad" captures (my alpha beta is still very basic and I already have some other features to do like a transposition and pawn table before improving my alpha beta in order to maximize the pruning while still finding the "good moves").

Have a nice day.

[AlvaroBegue]

You should concentrate on move ordering, because it's much more important than lazy generation.

In my engine RuyDos I roughly do the following:
* generate captures and sort them by MVV/LVA,
* filter the losing captures (SEE<0) and save them for later,
* generate non-captures and sort them by history heuristic,
* go through the list of losing captures.

The hash move and two killer moves are also there. Conceptually I implement this as a corroutine. In C++ that looks like a function with a large `switch' statement, so you can remember in a state variable where you were and continue from there.

Here's the actual code: https://bitbucket.org/alonamaloh/ruydos ... erator.cpp

[hgm]

What the heck is "lazy move generation"? Do you mean 'staged'?

What is more work and what not depends a lot on what board representation you use, (bitboard, various types of mailbox, attack map). Probably the biggest gain would be from abandoning legal generation and swicthing to pseudo-legal.

[theob]

Thanks,
Yes sorry, by lazy I mean staged.
I saw a few minimalist engines with staged move generation and I wasn't sure it was a good idea because you want to know all the moves first to do the best move ordering you can. So this one is settled.

I have a real question though on why pseudo legal move generation is a gain in performances ? I had first a pseudo legal move generation but with my implementation paying a legality check for each move was more expensive than computing absolutely pinned pieces once for every moves. When I had pseudo legal generation I was doing the legality check with a superpiece on the king because I couldn't use attack maps (we are making and unmaking moves so we cannot use a single attack map for all legality checks).

[hgm]

Well, identifying pinned pieces in advance can indeed be competitive. But it doesn't make the move generation fully legal. The point is that in general you want to postpone to later in the same node whatever you can postpone. Because you might get a beta cutoff, and everything you had postponed to after it then doesn't have to be done at all.

So if you want to test with the super-piece method, it would be better not to do it in the move generator, but just before or after MakeMove(). If you already took account of any pins, you would only have to do thattest for King moves (and perhaps e.p. capture, which can produce pins of a type your regular pin detector might overlook).

Staged move generation only makes sense if the various stages correspond so well to the ordering you want that you would never have to sort between stages. (Postponing the occasional move because it is obviously no good would not be so bad, though.) So if the primary ordering is MVV, and stage 1 would be all captures of a Queen (as opposed to 'by a Queen'), stage 2 every capture of a Rook, etc., it would be helpful. Especially since a capture of a Queen almost always would give such a fat gain that you will have a cutoff, and never get to any of the later stages. So a lot depends on how efficiiently you can selectively generate captures.

[tsoj]

I have staged move generation in my program and it doesn't change anything performance wise, maybe it is even a little worse than generating all moves at once (probably because it's quite a lazy implementation by me but anyway).

[Joost Buijs]

I have staged move generation in my program and it doesn't change anything performance wise, maybe it is even a little worse than generating all moves at once (probably because it's quite a lazy implementation by me but anyway).

I have exactly the same experience. Staged move generation helps a little bit at nodes with an early beta cutoff, but on other nodes it counteracts, the net result being nil.

At an SMP split-node it also has the drawback that the delayed move generation effectively blocks all the threads working on that node until the move generation is finished, this effect is small but noticeable. It probably depends upon the way my SMP search works, usually I get somewhat better results when I generate all the moves at-once before splitting. Maybe I should distinguish between PV, CUT and ALL nodes, but in my current engine I don't look at that at all.

[Michael Sherwin]

In RomiChess which is a bitboard engine I do a hybrid staged move generation. First a pseudo move generator creates all the move and attack bitboards. At anytime if the opposing king is captured it exits immediately. Then in the staged part it starts with the hashtable move checks to see if that move/capture bit is set for that piece which is a quick move verification, negates the bit and makes the move. Bits are turned into moves and negated as needed. Very simple. Very efficient.