Detecting if move that gives check exists

[R. Tomasi]

I'm currently implementing futility pruning in Pygmalion. This is a part of the engine that I do not want to just transfer from my old engine, since I suspect that many of the instabilities and tactical weaknesses that I had in the old engine are due to a bad implementation of futility pruning. At the time I wrote the respective code, I did simply not grasp the concept fully.

Currently I have a working Implementation in Pygmalion that seems to be tactically stable. I do not prune moves that give check. Now, a straight-forward improvement would be to implement "general futility pruning" in a way that is similar to what HGM describes on his Micro-Max homepage (https://home.hccnet.nl/h.g.muller/deepfut.html). However, I want to keep the philosophy of not pruning moves that give check. Therefore I would like to not prune the entire node, if the side to move might have a move that gives check.

Obviously, the whole idea of HGMs "general futility pruning" is to prune the node before any moves are generated, therefore I do need a way to determine if such a move might exist in a fast way, without generating the moves. I am sure I will be able to come up with code that does that, but I guess other people (who are smarter than me) have already thought about this, so any ideas or hints are very welcome.

[algerbrex]

I haven't studied the code incredibly closely, but Stockfish would be one place to look: https://github.com/official-stockfish/S ... n.cpp#L629

[R. Tomasi]

I haven't studied the code incredibly closely, but Stockfish would be one place to look: https://github.com/official-stockfish/S ... n.cpp#L629

Thanks for the link. I have to shamefully admit that I never looked at the stockfish source code But I guess, it might be worth doing - I kind of feel stupid now, for not having done so...

EDIT: However, the function you linked to does check if a move gives check. That is precisely not what I want to do: I want to know if there is any move in a position that gives check without generating every move. Nevertheless I will try and see if something like that might be in stockfish.

[R. Tomasi]

Maybe I should elaborate a little bit on what I have in mind:

Get the knight attacks from the square of the opponent king and see if any of my knights can move to one of these squares. If so, then it's possible to give check => return true.

Do the same for pawns.

Do something similar for sliders. Thats the part that seems tricky to me, since sliders might give check from a lot of squares. I am thinking of something à la kogge-stone here.

Then I will also have to check if I have a way of giving a discovered check. Maybe do that before doing the sliders (since that seems to be the most expensive part to me).

[algerbrex]

I haven't studied the code incredibly closely, but Stockfish would be one place to look: https://github.com/official-stockfish/S ... n.cpp#L629

Thanks for the link. I have to shamefully admit that I never looked at the stockfish source code But I guess, it might be worth doing - I kind of feel stupid now, for not having done so...

EDIT: However, the function you linked to does check if a move gives check. That is precisely not what I want to do: I want to know if there is any move in a position that gives check without generating every move. Nevertheless I will try and see if something like that might be in stockfish.

Ah, apologies. I misread your original post. I misread "generate moves" as "make a move".

And I don't think there's any shame in not referencing Stockfish code oftentimes it's more rewarding to figure things out for yourself and there are plenty of other good resources!

[R. Tomasi]

oftentimes it's more rewarding to figure things out for yourself and there are plenty of other good resources!

Yeah, I guess that's why I never had a look. The goal shouldn't be to just clone stockfish... But just having a look might not be that much of a cheat.

[algerbrex]

oftentimes it's more rewarding to figure things out for yourself and there are plenty of other good resources!

But just having a look might not be that much of a cheat.

One thing I've often realized while writing my engine is that chess programming has a great atmosphere of open exchange and sharing ideas, and as long as you don't copy and paste huge chunks of other people's work and/or give credit when appropriate then I don't think it's a huge deal looking at other engines code.

Often times when I'm trying to understand and/or implement a new search feature or whatnot, I'll do it myself first or get a rough idea from somewhere like the CPW or the CPW engine, and then peek at the source code for some other respected engines as a sanity check to make sure I'm not missing something stupid. Once I've done that, I'll experiment with new ideas and tweak parameters myself until I'm happy with the results.

To me, this strikes a good balance between writing original code, and also benefiting from a very rich community.

[R. Tomasi]

Often times when I'm trying to understand and/or implement a new search feature or whatnot, I'll do it myself first or get a rough idea from somewhere like the CPW or the CPW engine, and then peek at the source code for some other respected engines as a sanity check to make sure I'm not missing something stupid.

Indeed, the CPW is my main source of knowledge. Basically everything I know about chess programming was learned from there. And I totally agree, the atmosphere of open exchange is a big part of what makes chess programming so fun. But, as you said, figuring stuff out for yourself (and thus really understanding it) is as big of a part of the fun...

[Mergi]

It seems to me that finding out whether there's a move that would give a check without generating any moves would be very expensive.

Do something similar for sliders. Thats the part that seems tricky to me, since sliders might give check from a lot of squares. I am thinking of something à la kogge-stone here.

Then I will also have to check if I have a way of giving a discovered check. Maybe do that before doing the sliders (since that seems to be the most expensive part to me).

You could validate without too much overhead whether a move gives a check during the make unmake loop and prune there. Would that not work for you? There's been some discussion on this in another thread recently. There's couple of ways to do this, for example generating a small lookup table is quite fast:

You can first during generator/position initialization in a new node generate attacks from the king's square. Then when you are generating moves for a piece, you use this information to determine whether it gives a check. For example when you are generating rook moves: if(attacks_from_king[rook] & to_square) -> checking move. Easy to implement and it doesn't slow down the engine too much.

[algerbrex]

Often times when I'm trying to understand and/or implement a new search feature or whatnot, I'll do it myself first or get a rough idea from somewhere like the CPW or the CPW engine, and then peek at the source code for some other respected engines as a sanity check to make sure I'm not missing something stupid.

But, as you said, figuring stuff out for yourself (and thus really understanding it) is as big of a part of the fun...

Absolutely. I remember the first time I was able to generate magic numbers and use them to generate slider moves, by myself. It felt incredibly rewarding, especially since a month ago I thought I'd never been able to do it.