Incremental Move Generation - Is it worth it?

[Steve Maughan]

I had thought that the perceived wisdom was that the move generation routine in a typical program only takes up only about 10% of a program's execution time and is therefore not worth spending too much time optimizing . However Fruit 2 introduced incremental move generation and I think Fabian said this was added as the nodes / sec were getting too low. This implies that you can get a (significant) speed impovement by adding IMG, which flies in the face of the conventional wisdom about move generator only taking up 10% of the a programs time.

So what are people's thought? Do IMGs really speed things up? Are they worth the effort and IMO the significantly increased potential for bugs?

Regards,

Steve

[Dann Corbit]

A large percentage of nodes are quiescent.

The places where you will see a savings are the places where you never end up generating the nodes at all.

Since there are a lot of nodes down at the leaves, your savings might be substantial.

I think it is a very good idea.

If you have already separated your move generator to do:

captures
promotions
checks
check-evasions
other (non-captures, etc.)

seprately and non-overlapping, then your savings may not be as great, since you won't have to generate most of them all in quiescence anyway.

An incremental makemove is also helpful to do an incremental evaluation.

[Pallav Nawani]

However Fruit 2 introduced incremental move generation and I think Fabian said this was added as the nodes / sec were getting too low.

Incremental move generation is an old idea. Crafty has been doing it for years, for example. What I don't know is whether Fruit also does incremental move generation in Qsearch (Crafty doesn't).

I have a suspicion that incremental move generation improves move ordering, but I have no data to back this claim.

[Alessandro Scotti]

Hi Steve,
in Kiwi, I used to separate move generation in three steps: move from the hash table, captures and promotions, and the rest.
For simplicity, captures and promotions were all generated and examined before going on the next step, which means losing captures were considered before any non-capture move.
However, this is not the best ordering. Later, I started to generate and sort all moves at the same time (after the hash move) and I could not notice any slowdown. In fact, I think the program got stronger because of better move ordering and the code got simpler as well, which I like.
I also tried to skip the "move from hash" phase, and even then I could hardly notice a slowdown, but that may just be Kiwi.
On the other hand having a specific generator for quiesce has been very useful. Because my quiesce skips over some captures I put discarded moves in a separate list and if I ever come to the "generate checks" phase I don't have to generate all the moves again, just the "others" (non-tactical).
In Kiwi I did not worry too much about NPS, but it could be interesting to get back to (an improved) incremental generation and see what happens...

[Fabien Letouzey]

I had thought that the perceived wisdom was that the move generation routine in a typical program only takes up only about 10% of a program's execution time and is therefore not worth spending too much time optimizing . However Fruit 2 introduced incremental move generation and I think Fabian said this was added as the nodes / sec were getting too low. This implies that you can get a (significant) speed impovement by adding IMG, which flies in the face of the conventional wisdom about move generator only taking up 10% of the a programs time.

Hi Steve,

I think "time" profiling functions separately is misleading in chess engines. Please for the "move generation" module include all move-ordering heuristics as well (because with incremental generation, fewer moves will be scored+sorted as well as generated). I am sure it is more than 10% in some engines. It is usually difficult to measure though, but advanced development tools might provide this.

As I recall 10% is what I GAINED by going incremental, but my previous code was really naive: generate all moves, then score all moves then sort all moves (sorting incrementally did not buy anything significant). This might be less for engines that generate+score at the same time.

Of course incremental generation is a lot more complex, no doubt. But I found it interesting to write (e.g. I see it as a virtual machine that has instructions). After making the change I could easily try different move orderings.

Let's sum up. I suggest you measure time spent in this module in a SERIOUS way, really find ALL functions that are related to this part of the engine. I think you will find the number is higher than what you might expect by say only looking at move_gen() or whatever.

I warn you (all) especially against measuring time in a naive way as they like to describe in so many software books. There will be no function eating 90% of the time in a decent chess engine (even if your eval does, it should be split further). Our programs are simply a lot more complex than beginner examples.

Fabien.

[Steve Maughan]

Thanks for the suggestions and help. I think I'm going to implement the IMG in the Q search to start with. I think this is where it'll have the most impact and it's also the easiest to implement.

Thanks again,

Steve

[Anonymous]

If you are in a node that is going to fail low, extra time spent messing around is wasted time.

If you are going to fail high on the first successor you search, it makes sense to get the first successor quickly.

These types of nodes occur with similar frequency.

The implication as far as I'm concerned is that if you have a move in hand that's going to cut off, you should search it now. If you don't know what is going on in this node, it may make sense to generate everything in order that you can make the best choice, in the hopes of a first-successor cutoff.

I have no idea how important quiescent search is. Some people get super-paranoid about quiescent search. My own attitude has always been that I would prune at the root if I could get away with it. I allow almost nothing in there. It's always been pretty easy for me to just generate the stuff that I may actually search.

But this whole deal about move generation probably is a 5-10% thing, and that's not going to make a good program bad or a bad program good.

bruce

[mridul]

Hi Bruce ,
Great to see you back !
The problem is more to do with whether we can find if a move will fail high or fail low.
I do use the info from hashtable to 'aid' in this , but one can never be sure - especially towards the leaves.
I dont usually care about movegen as such , but more with move eval.
My problem is more to do with whether I have to pseudo eval the moves a bit more carefully to get the cutoff fast , or whether it is all throwaway work at a fail low low.

Thanks,
Mridul

[diepeveen]

If you are in a node that is going to fail low, extra time spent messing around is wasted time.

If you are going to fail high on the first successor you search, it makes sense to get the first successor quickly.

These types of nodes occur with similar frequency.

The implication as far as I'm concerned is that if you have a move in hand that's going to cut off, you should search it now. If you don't know what is going on in this node, it may make sense to generate everything in order that you can make the best choice, in the hopes of a first-successor cutoff.

I have no idea how important quiescent search is. Some people get super-paranoid about quiescent search. My own attitude has always been that I would prune at the root if I could get away with it. I allow almost nothing in there. It's always been pretty easy for me to just generate the stuff that I may actually search.

But this whole deal about move generation probably is a 5-10% thing, and that's not going to make a good program bad or a bad program good.

bruce

I'm not sure i 100% agree here Bruce, i'm using a lot of loops in my evaluation function, so those loops i like to speedup whenever possible.

[Anonymous]

The choice is between:

1) Generate the moves you may eventually search, then deal with them.

2) Generate fewer than the moves you may eventually search, deal with those you've generated, then generate more if necessary.

If other aspects of the program intrude, then you may not be able to do it the second way.

If you can do it the second way, you:

1) Win on beta nodes, because you cut off without generating all the moves.

2) Potentially lose on alpha nodes, because presumably it takes more energy to generate in fits and starts than it does to just do it all in one blast.

bruce

[diepeveen]

The choice is between:

1) Generate the moves you may eventually search, then deal with them.

This eats like 0.3-0.5% system time in total here, so i don't know where you get the 5-10% from.

Question is how to efficiently get a move from the move list which is the best, without needing for example 1 ply to go to do an investigation and a full move ordering of all moves (which in case of diep just means assigning scores to the moves, so not order them physical). This move ordering is pretty slow, whereas odds are not too bad that we can get a quick cutoff with the first move.

2) Generate fewer than the moves you may eventually search, deal with those you've generated, then generate more if necessary.

Even this is pretty interesting if you're in qsearch and there is some trivial recapture with a huge score, because if you can save out 0.1% system time that's a huge saving.

[Gerd Isenberg]

The choice is between:

1) Generate the moves you may eventually search, then deal with them.

This eats like 0.3-0.5% system time in total here, so i don't know where you get the 5-10% from.

See Fabien's post above.

Question is how to efficiently get a move from the move list which is the best, without needing for example 1 ply to go to do an investigation and a full move ordering of all moves (which in case of diep just means assigning scores to the moves, so not order them physical). This move ordering is pretty slow, whereas odds are not too bad that we can get a quick cutoff with the first move.

2) Generate fewer than the moves you may eventually search, deal with those you've generated, then generate more if necessary.

Even this is pretty interesting if you're in qsearch and there is some trivial recapture with a huge score, because if you can save out 0.1% system time that's a huge saving.

Well, pxq, pxr etc. is cheap to determine. A finite state movegen, where states generate disjoint sets (even empty or complete) of moves, may be initialized with different state, depending on depth and node type (pv/cut/all) and/or some relations of (lazy) eval score and alpha/beta.

Gerd

[diepeveen]

The choice is between:

1) Generate the moves you may eventually search, then deal with them.

This eats like 0.3-0.5% system time in total here, so i don't know where you get the 5-10% from.

See Fabien's post above.

Question is how to efficiently get a move from the move list which is the best, without needing for example 1 ply to go to do an investigation and a full move ordering of all moves (which in case of diep just means assigning scores to the moves, so not order them physical). This move ordering is pretty slow, whereas odds are not too bad that we can get a quick cutoff with the first move.

2) Generate fewer than the moves you may eventually search, deal with those you've generated, then generate more if necessary.

Even this is pretty interesting if you're in qsearch and there is some trivial recapture with a huge score, because if you can save out 0.1% system time that's a huge saving.

Well, pxq, pxr etc. is cheap to determine. A finite state movegen, where states generate disjoint sets (even empty or complete) of moves, may be initialized with different state, depending on depth and node type (pv/cut/all) and/or some relations of (lazy) eval score and alpha/beta.

Gerd

Hi Gerd,

Fruit has a slow move generator. He has a fast SEE though and fast way to detect checks thanks to his 16x16 board. Memory efficient especially.

In A64 processors every mispredicted branch counts. To me i am under impression, correct me if i'm wrong, that if a branch is just a few instructions, that sometimes at A64 such mispredicted branch still goes not too slow. Yet the normal mispredicted branches of quite some code are real slow. Fruit has many of those.

This is however not a problem of course, but it gives a different profile to specific sections in the code.

Just that you feel what you're losing from, something just busy generating moves

[thumb up to Fabien]

Vincent