Re: Most efficient way to generate legal king moves?
Posted: Thu Feb 09, 2017 5:51 pm
Ah, you are right, but I was thinking of the King moves. I often do take account of pins, if circumstances allow it. E.g. in Joker (of which I never published the source code, but which is based on qperft, which I did publish) I do determine pinned pieces in advance, to generate their moves along the pin line, and mark them as captured during the normal move generation. This does save time in the full-width search.
But in QS I often use 'reverse' move generation, where I loop through all possible opponent pieces from high to low, to test what can capture them, rather than through my own pieces to see what they can capture. This is slightly more difficult (because you have either to look in all 8 directions, or consider all 8 pieces in the piece list as attackers, rather than just in the directions the piece moves). But you usually have to do it for only a subset of the possible victims. Because you can stop when you reach victims not valuable enough to bring the score above beta even if you can capture them and they are not protected. And because you can immediately start searching as soon as you have generated the move of the most-valuable victim, a beta cutoff would save you the trouble of generating the captures on the remaining victims. Knowing what is pinned in that case is not very helpful. The pinned piece might just have one capture, or no captures at all, on any victim of interest.
I guess the lesson is that perft speed can be a very misleading measure for the speed of an engine. Because it puts far too much weight on generation of a complete move set, and ensuring their legality. While in an engine 85% of the nodes are QS nodes, where you only want to generate captures, and perhaps even a subset of those (with valuable-enough victims). Generating all moves, extracting the captures and sorting those is a very inefficient way to do that, no matter how efficiently you generated all moves.
My currently favorite design (that I am stillworking on) is to replace the move list in QS by a 'capture map', which has a a bit assigned to every (victim, attacker) pair (so 256 bits in total per side). These bits are assigned in the order QS would want to search them. Then to add ore remove captures one would just have to set or clear the corresponding bits, by OR and AND operations. And there would never have to be any sorting, as they would be extracted automatically in the desired order. Each piece would have a victimMask and an attackerMask that can be used to clear or isolate all moves that capture it, or all moves with it, (e.g. to remove these in case the piece gets captured, or moves elsewhere). This makes it easy to update the set of possible captures incrementally.
By also keeping such capture maps for captures of own pieces (i.e.protectors) a piece that captures another can simply inherit all the attacks on it. The moves of sliders that could capture a piece that moved away would have to be exteded to the target downstream, which is also easy if the capture map already tells which pieces attacked it, and you kept a view_distace table to immediately tell you where 'downstream' is.
But in QS I often use 'reverse' move generation, where I loop through all possible opponent pieces from high to low, to test what can capture them, rather than through my own pieces to see what they can capture. This is slightly more difficult (because you have either to look in all 8 directions, or consider all 8 pieces in the piece list as attackers, rather than just in the directions the piece moves). But you usually have to do it for only a subset of the possible victims. Because you can stop when you reach victims not valuable enough to bring the score above beta even if you can capture them and they are not protected. And because you can immediately start searching as soon as you have generated the move of the most-valuable victim, a beta cutoff would save you the trouble of generating the captures on the remaining victims. Knowing what is pinned in that case is not very helpful. The pinned piece might just have one capture, or no captures at all, on any victim of interest.
I guess the lesson is that perft speed can be a very misleading measure for the speed of an engine. Because it puts far too much weight on generation of a complete move set, and ensuring their legality. While in an engine 85% of the nodes are QS nodes, where you only want to generate captures, and perhaps even a subset of those (with valuable-enough victims). Generating all moves, extracting the captures and sorting those is a very inefficient way to do that, no matter how efficiently you generated all moves.
My currently favorite design (that I am stillworking on) is to replace the move list in QS by a 'capture map', which has a a bit assigned to every (victim, attacker) pair (so 256 bits in total per side). These bits are assigned in the order QS would want to search them. Then to add ore remove captures one would just have to set or clear the corresponding bits, by OR and AND operations. And there would never have to be any sorting, as they would be extracted automatically in the desired order. Each piece would have a victimMask and an attackerMask that can be used to clear or isolate all moves that capture it, or all moves with it, (e.g. to remove these in case the piece gets captured, or moves elsewhere). This makes it easy to update the set of possible captures incrementally.
By also keeping such capture maps for captures of own pieces (i.e.protectors) a piece that captures another can simply inherit all the attacks on it. The moves of sliders that could capture a piece that moved away would have to be exteded to the target downstream, which is also easy if the capture map already tells which pieces attacked it, and you kept a view_distace table to immediately tell you where 'downstream' is.