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.
Detecting if move that gives check exists
Moderators: hgm, Rebel, chrisw
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
-
- Posts: 596
- Joined: Sun May 30, 2021 5:03 am
- Location: United States
- Full name: Christian Dean
Re: Detecting if move that gives check exists
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
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Detecting if move that gives check exists
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...algerbrex wrote: ↑Sat Sep 18, 2021 1:06 am 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
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.
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Detecting if move that gives check exists
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).
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).
-
- Posts: 596
- Joined: Sun May 30, 2021 5:03 am
- Location: United States
- Full name: Christian Dean
Re: Detecting if move that gives check exists
Ah, apologies. I misread your original post. I misread "generate moves" as "make a move".R. Tomasi wrote: ↑Sat Sep 18, 2021 1:16 amThanks 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...algerbrex wrote: ↑Sat Sep 18, 2021 1:06 am 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
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.
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!
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Detecting if move that gives check exists
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.
-
- Posts: 596
- Joined: Sun May 30, 2021 5:03 am
- Location: United States
- Full name: Christian Dean
Re: Detecting if move that gives check exists
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.
Last edited by algerbrex on Sat Sep 18, 2021 1:48 am, edited 1 time in total.
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Detecting if move that gives check exists
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...algerbrex wrote: ↑Sat Sep 18, 2021 1:40 am 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.
-
- Posts: 127
- Joined: Sat Aug 21, 2021 9:55 pm
- Full name: Jen
Re: Detecting if move that gives check exists
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.
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.
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: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 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.
-
- Posts: 596
- Joined: Sun May 30, 2021 5:03 am
- Location: United States
- Full name: Christian Dean
Re: Detecting if move that gives check exists
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.R. Tomasi wrote: ↑Sat Sep 18, 2021 1:44 amBut, as you said, figuring stuff out for yourself (and thus really understanding it) is as big of a part of the fun...algerbrex wrote: ↑Sat Sep 18, 2021 1:40 am 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.