Detecting if move that gives check exists
Moderators: hgm, Rebel, chrisw
-
- Posts: 127
- Joined: Sat Aug 21, 2021 9:55 pm
- Full name: Jen
Re: Detecting if move that gives check exists
Pssssh, and here i thought you didn't want to go to the generator routine at all, since you didn't seem to like that suggestion from others!
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Detecting if move that gives check exists
You may want to re-read my posts I suggested using a special movegen more or less right from the start as an alternative. That's not the same as generating moves and then determine if they will give check, is it?
-
- Posts: 127
- Joined: Sat Aug 21, 2021 9:55 pm
- Full name: Jen
Re: Detecting if move that gives check exists
You are right, you did say that afterwards. I got too fixated on this part of the original post i guess.
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.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Detecting if move that gives check exists
It can be tricky with checks. When I was optimizing micro-Max there was no benefit from a check extension, unless I disabled it in the end-game. Apparently it did as much damage in the end-game as it helped in the middle game. The problem was that once the King came out, the tree was blown up enormously by all these long sequences of extended checks, strongly reducing the nominal depth at which non-checking lines were searched. And we all know that checking in the end-game is usually a waste of time. (If these were dangerous, we would not come out with the King...)
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Detecting if move that gives check exists
Well, I guess I could have expressed myself in a better way. You were not the only one miss-understanding what I have in mind and just suggesting fast methods to detect if a move gives check.Mergi wrote: ↑Sat Sep 18, 2021 12:30 pm You are right, you did say that afterwards. I got too fixated on this part of the original post i guess.
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.
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Detecting if move that gives check exists
Hm... doing things differently, depending on the game phase might give the best of both worlds. But afaik in micro-Max you don't do any form of tapered eval and therefore don't keep track of the game phase - or am I ill-informed about that?hgm wrote: ↑Sat Sep 18, 2021 12:32 pm It can be tricky with checks. When I was optimizing micro-Max there was no benefit from a check extension, unless I disabled it in the end-game. Apparently it did as much damage in the end-game as it helped in the middle game. The problem was that once the King came out, the tree was blown up enormously by all these long sequences of extended checks, strongly reducing the nominal depth at which non-checking lines were searched. And we all know that checking in the end-game is usually a waste of time. (If these were dangerous, we would not come out with the King...)
In any case, concerning Pygmalion, I guess I really have to make the effort of comparing the different methods. In the worst case I will have spent a few days of coding on something that gets thrown out in the end. But that seems to be part of chess-programming many times.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Detecting if move that gives check exists
Micro-Max 4.8 does in fact have some form of tapered eval. It keeps track (in a variable R) of the game phase in the root, by subtracting victimValue/128 from it. The piece values are such that this results in 0, 2, 2, 3, 6 for the game-phase weights of the various piece types. This variable R (which thus runs from 0 to 40) is used for three things:
- deciding whether null move should be switched off (R <= 4)
- deciding whether King moves should be penalized by 20cP (R >= 10)
- deciding whether to extend check evasions (R >= 10)
- tapering the Pawn-push bonus (adding 76-R>>2, an increase of 10cP from opening to end-game)
-
- Posts: 6995
- Joined: Thu Aug 18, 2011 12:04 pm
Re: Detecting if move that gives check exists
I don't really have a good idea to offer and the following is a bit off topic and yet related because it's about checks without generating other moves.R. Tomasi wrote: ↑Sat Sep 18, 2021 1:16 amEDIT: 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.
In the 80's no one heard of futility pruning, recursive null move and recursive reductions, let alone LMR, all that was not invented. And with hardware that was only doing 500-600 NPS and 5-6 ply on tournament time control (40m/2h) I basically pruned the tree comparing alpha with the evaluation score, the result gave good elo but at times the search was a swiss cheese full of holes. One of tricks to fix holes was to detect if a move generated a new check on the opponent king without generating the moves. A FEN example is in place.
[fen]5rk1/1R3ppp/4p3/3pP3/2pP4/2P5/5PPP/6K1 b - -[/fen]
Black to move and the move Ra8 isn't pruned because it creates the possibility of a new check by Ra1. The anti_swiss_cheese() routine also discovers the situation when we put a white bishop on d1, or situations like:
[fen]r3k3/p7/1n6/8/4N3/8/P7/R5K1 w - -[/fen]
The move Re1 isn't pruned because it generates new checks with the knight.
At the time it gave good elo and was very useful in tactical situations that required a silent move.
Maybe something can be done with futility pruning (or reductions) taking the previous move of the tree (ply-1) as starting point, when it generates a new check don't prune (or reduce).
90% of coding is debugging, the other 10% is writing bugs.
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Detecting if move that gives check exists
Well, pruning the move at the parent node seems to be the same as pruning the node that the move creates. So, unless I'm missing something that actually seems like an idea that helps. It depends a little bit on the specifics of that anti_swiss_cheese() function. From what I get out of your explanation it will detect if the node (or the move at the parent node) introduces new checks - as opposed to my idea of detecting any check. It seems to me that - while theoretically not exactly equivalent to not pruning checks - it might actually be better, ELO-wise. If the check already existed at the parent node it would have been explored there, thus will probabily not hurt the strength of the engine lots if not re-explored. So the tree gets more pruning, but not in a dangerous way.
Edit:
Like in your first example: Ra8 introduces a new checking possibility by Ra1, so we pass a flag to the child node. There we search the moves that white has in response while passing the flag further down, and the subnodes (i.e. the grandchilds of the node that generated Ra8) are not allowed to be pruned.
[edited again to fix the stupid things I said while my brain was melting thinking about this]
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Detecting if move that gives check exists
What Ed descibes is detecting opportunities to capture a King with a sequence of 3 moves (of the same player). What you asked for is detecting opportunities to capture the King with a sequence of 2 moves.