Need some help on speed optimization

[Felpo]

I'm completely refactoring my move generator, and I'm trouble with speed.
My representation is the 0x88, and I'm using c#.
Today, my generator perform three times slower than crafty
I've already tried bitboard with magic move generator, but surprisingly the 0x88 works faster in my implementation ( I suppose because with C# I have no control about method inlining, I have no way to define macro so creating some maintainable code drop the performance ).
The longest time consuming portion is the "InAttack" function, to check if the move leave the king in attack. My function is naive at the moment, have you please some suggestions to make it better ?
Would be creating and incrementally mantain some sort of attack map be the solution ? Do I have to stop optimizing and having the current performance in move generation ( 3xCrafty) could be acceptable with a very good move order function ?
Thanks to all in advance,
Felix

[Steve Maughan]

The fastest way of checking to see if the move puts the king in check is to use the move's "from" and "to" squares and the piece type to see if it's possible for the move to put the king in check. For example, if the white king is on H4 and make the move pawn c2 to c3; there is no way that, if the white king was not in check before, it can be in check after the move.

I hope this helps.

Steve

[hgm]

Do you use a piece list n combination with the 0x88 board? This would give a large bost of performance, as you can at anytime qickly consult where pieces of a given type are, in stead of having to scan the board to find them.

Another strategy would be to simply ignore if a move puts you in check, and leave it for the opponent to iscover that he can capture your King. This sounds efficient, but in fact only a very small fractions of all moves does put you in check, if you were not already in check.

[Felpo]

The fastest way of checking to see if the move puts the king in check is to use the move's "from" and "to" squares and the piece type to see if it's possible for the move to put the king in check. For example, if the white king is on H4 and make the move pawn c2 to c3; there is no way that, if the white king was not in check before, it can be in check after the move.

I hope this helps.

Steve

Thanks you Steve,
I think I got your Idea, but it can't find a way to render this in an algorithm.
It would be nice to know if there is some sample somewhere...

[Felpo]

Do you use a piece list n combination with the 0x88 board? This would give a large bost of performance, as you can at anytime qickly consult where pieces of a given type are, in stead of having to scan the board to find them.

Another strategy would be to simply ignore if a move puts you in check, and leave it for the opponent to iscover that he can capture your King. This sounds efficient, but in fact only a very small fractions of all moves does put you in check, if you were not already in check.

I did not yet implemented the piece list, because I'm a little bit confusing. I read about an array of 32 elements, one for each piece, indexing the 0x88 square, but... in any case, to discover, for example, where is an opponent slider, I have to loop on that array, just because due to promotion the only standing point about chess man is that there is at most 8 pawns for each color, the other can vary. I would like to try a Dictionary for this...
The second solution you propose is interesting, and I would like to apply in regular search, I have to study more to understand if it can improve perft too.

[bob]

I'm completely refactoring my move generator, and I'm trouble with speed.
My representation is the 0x88, and I'm using c#.
Today, my generator perform three times slower than crafty
I've already tried bitboard with magic move generator, but surprisingly the 0x88 works faster in my implementation ( I suppose because with C# I have no control about method inlining, I have no way to define macro so creating some maintainable code drop the performance ).
The longest time consuming portion is the "InAttack" function, to check if the move leave the king in attack. My function is naive at the moment, have you please some suggestions to make it better ?
Would be creating and incrementally mantain some sort of attack map be the solution ? Do I have to stop optimizing and having the current performance in move generation ( 3xCrafty) could be acceptable with a very good move order function ?
Thanks to all in advance,
Felix

Why would you do this when _generating_ moves? Most of the moves you generate will never be searched, so that effort is wasted. Wait to check for legality until you actually choose to search the move...

[Felpo]

Why would you do this when _generating_ moves? Most of the moves you generate will never be searched, so that effort is wasted. Wait to check for legality until you actually choose to search the move...

I know you are right... But it's a matter of challenge: I can't understand how can, for instance, the ( H.G. Muller ? ) perft.exe be more than 10 time faster than mine, even if it has a legal move generator! Crafty is still 3 time faster, and AFAIK it do a lot of supplementary work in move generation. What is a little frustrating is that, when I do some refinement that should produce a great speed-up, what I obtain is a little performance decrease
Perhaps c# can't reach the speed of C... but such a difference is too much in order to me. I just implemented the pieceList strategy: results: 25% performance decreased, seems that the effort in updating the piece list is more than looping the entire chessboard. This is probably due to the fact that I wrote a function to update the piece list, and perhaps the function is not ilnlined by the optimizer

[bob]

Do you use a piece list n combination with the 0x88 board? This would give a large bost of performance, as you can at anytime qickly consult where pieces of a given type are, in stead of having to scan the board to find them.

Another strategy would be to simply ignore if a move puts you in check, and leave it for the opponent to iscover that he can capture your King. This sounds efficient, but in fact only a very small fractions of all moves does put you in check, if you were not already in check.

I did not yet implemented the piece list, because I'm a little bit confusing. I read about an array of 32 elements, one for each piece, indexing the 0x88 square, but... in any case, to discover, for example, where is an opponent slider, I have to loop on that array, just because due to promotion the only standing point about chess man is that there is at most 8 pawns for each color, the other can vary. I would like to try a Dictionary for this...
The second solution you propose is interesting, and I would like to apply in regular search, I have to study more to understand if it can improve perft too.

I'm not sure why you are worrying about perft speed? perft was designed to validate a move generator. Not to serve as a speed measurement for comparison. Your move generator will end up being an insignificant part of the total computing you do. Some have optimized perft using hashing, etc, none of which helps their program play any better at all.

Work on the _right_ stuff first to make progress in playing skill...

[Felpo]

I'm not sure why you are worrying about perft speed? perft was designed to validate a move generator. Not to serve as a speed measurement for comparison. Your move generator will end up being an insignificant part of the total computing you do. Some have optimized perft using hashing, etc, none of which helps their program play any better at all.

Work on the _right_ stuff first to make progress in playing skill...

Thank You Robert,
I will try to come back to my original speed ( 1/3 crafty ) ant go with alpha beta.

[Edsel Apostol]

Bob is right. Never mind if your move generator is too slow for now, just focus on improving your engine and implementing all the basic features. Optimization can be done later, maybe with a complete rewrite from scratch.

This is based on my experience with my engine. And you will have a hard time beating Crafty's NPS anyway as it is well optimized and is written in C, whereas your engine is in C#.