Steve Maughan wrote:The problem seem to be I'm checking to see if the piece is pinned from scratch after every move. Of course it will be much faster to generate the pins and store this as a bitboard. Then use this bitboard as the first port-of-call in the legality checker. This should speed things up.
Yes, you can do that and you should do that. And no, I don't think this will help significantly. According to your numbers checking for pins does not take much time. But look at the huge number of calls of is_in_check_after_move(), it is called 2594 million times while make_move() is called 82 million times, so roughly 32 calls per make_move(). That tells me that you test all pseudo-legal moves for legality by internally making them (not with make_move() but with something smaller, I suppose), then checking whether the king was left in check, then unmaking them again. And that is what I meant in my other post: you don't need to do that for most of the moves.
For a perft with bulk counting it is OK to have about 32x as many checks for legality as there are make_move()s.
Of course when doing an alpha-beta search, it would not make sense to check all generated moves for legality.
Steve Maughan wrote:The problem seem to be I'm checking to see if the piece is pinned from scratch after every move. Of course it will be much faster to generate the pins and store this as a bitboard. Then use this bitboard as the first port-of-call in the legality checker. This should speed things up.
Yes, you can do that and you should do that. And no, I don't think this will help significantly. According to your numbers checking for pins does not take much time. But look at the huge number of calls of is_in_check_after_move(), it is called 2594 million times while make_move() is called 82 million times, so roughly 32 calls per make_move(). That tells me that you test all pseudo-legal moves for legality by internally making them (not with make_move() but with something smaller, I suppose), then checking whether the king was left in check, then unmaking them again. And that is what I meant in my other post: you don't need to do that for most of the moves.
For a perft with bulk counting it is OK to have about 32x as many checks for legality as there are make_move()s.
Of course when doing an alpha-beta search, it would not make sense to check all generated moves for legality.
Yes, but checking for legality does not necessarily involve making, testing for "king left in check" and unmaking of all moves, that was my point. Even in perft with bulk counting you can avoid that for the vast majority of moves, i.e. all but evasions, king moves, pinned piece moves, and ep captures, since the other pseudo-legal moves are always legal.
Sven Schüle wrote:Yes, but checking for legality does not necessarily involve making, testing for "king left in check" and unmaking of all moves, that was my point.
I don't think that is what Steve is doing, but I could be wrong.
It is what I am (currently) doing though, and I don't think there is much wrong with it unless your goal is to get a fast perft.
If Steve is testing for legality by making, testing for "king left in check" and unmaking before doing the "real" make_move(), then obviously he should instead just do the make_move(), test, and only unmake if the move was illegal. But I rather have the impression that he is already doing more or less what you describe, except that his test for the moving piece being pinned can be made more efficient.
Yes Ron is right. Before I was checking every move to see if it would result in the king in check - if it was OK I'd go ahead and make the move. I've improved upon this by finding all of the pinned pieces at the start of the generate_move procedure and only doing the in_check test if the piece is pinned (or it's an ep or king move). This gave a significant speed-up to the perft time.
Yes Ron is right. Before I was checking every move to see if it would result in the king in check - if it was OK I'd go ahead and make the move. I've improved upon this by finding all of the pinned pieces at the start of the generate_move procedure and only doing the in_check test if the piece is pinned (or it's an ep or king move). This gave a significant speed-up to the perft time.
Best regards,
Steve
Did you implement this perft speedup after opening this thread, or was it already there when you published your profiling results? In the latter case I would still be surprised about seeing 32x "is_king_in_check" compared to "make_move".
Sven Schüle wrote:Did you implement this perft speedup after opening this thread, or was it already there when you published your profiling results? In the latter case I would still be surprised about seeing 32x "is_king_in_check" compared to "make_move".
I implemented it after the I opened the thread. See also here:
Sven Schüle wrote:Did you implement this perft speedup after opening this thread, or was it already there when you published your profiling results? In the latter case I would still be surprised about seeing 32x "is_king_in_check" compared to "make_move".
I implemented it after the I opened the thread. See also here:
I guess for a fast perft it makes sense to have a legality check that performs a cheaper kind of internal makemove just to test whether the king will be in check, but that does not really make the move.
However, it seems to me that in a real chess program such an approach runs a high risk of being slower than simply doing a real makemove and then checking whether the move was legal (i.e. whether the king is in check). In a real chess program, you only want to test whether a move is legal if you actually want to make the move. This is a big difference with perft where you don't want to make most moves at all (i.e. those at the leafs) but only need to know how many are legal.
It is probably possible to make legality checking before making a move pay off in a real chess program, but the legality checking (including finding all pinned pieces) will have to be optimised very very well.
syzygy wrote:I guess for a fast perft it makes sense to have a legality check that performs a cheaper kind of internal makemove just to test whether the king will be in check, but that does not really make the move.
However, it seems to me that in a real chess program such an approach runs a high risk of being slower than simply doing a real makemove and then checking whether the move was legal (i.e. whether the king is in check). In a real chess program, you only want to test whether a move is legal if you actually want to make the move. This is a big difference with perft where you don't want to make most moves at all (i.e. those at the leafs) but only need to know how many are legal.
It is probably possible to make legality checking before making a move pay off in a real chess program, but the legality checking (including finding all pinned pieces) will have to be optimised very very well.
Implementing a function "isLegalMove()" that takes a perfect decision about legality of a pseudo-legal move without actually making it on the board (perhaps except for very rare cases like EP which are not significant for overall performance) can pay off in both cases, for writing a fast perft as well as for normal search. That function would take the current board, the move, and information about all pins as arguments. It will also require to maintain a separate evasion generator. Its implementation will basically have to care about pins and about king moves to attacked squares.
Whether this is really faster or slower than the trivial "make move - test king left in check" approach will of course depend on the board representation, here I fully agree with you. I tested it with bitboards, and it works for me.
Whether this is really faster or slower than the trivial "make move - test king left in check" approach will of course depend on the board representation, here I fully agree with you. I tested it with bitboards, and it works for me.
+1, works for me too. I even go further and I never even generate illegal moves. I wasn't able to detect this often stated huge performance impact.
Yes I test some moves that I will never execute. But how often does this happen. With a hash table that gives you a hash move, killers and captures that have a high fail high success rate and can be generated efficiently with bitboards chances are that when I get to generate the quiet moves I will have to execute them all anyway.
