Make intelligent mode more intelligent

[JoshuaGreen]

While using Popeye to assess the soundness of various ser-h=s, I discovered that many of its target positions were simply infeasible, and I suspect that a lot of them can be knocked out automatically.  For example:

• If a bP is blocked in the diagram position and no captures are immediately available, then that pawn can never move without that blocking piece being captured (and hence removed from the board).
• If a bP needs to capture to reach a square, then White piece(s) must already be on appropriate square(s) to be so captured.
• White's move cannot require a Queen, Rook, or Bishop to jump over a piece.
• The bK cannot finish on a square next to the wK's initial square. More generally, Black can't be in check when it's White's turn to move.
• There are relatively few paths for bSs and bBs to reach the corner squares, and those paths can be easily "blocked" by, e.g., pieces, checks, and captures.  (This is especially true if the intent is to bottle them there with bPs.)
  • As a simple example, with a bP remaining on g7 Popeye has been trying to get a bB to h8, but that's clearly impossible.
• If White's move must be a capture, it cannot be a pawn moving straight forward.
• Whatever square White's piece moves from must be empty in the target position.  (Popeye may already know this one.)

It would interesting to implement some such heuristics in the target position generation logic.

[JoshuaGreen]

The second bullet could perhaps be well handled by ignoring the Black pieces and characterizing all reachable positions by:

• where Black pawns are
• what White units may still be on the board
• how many Black pawns promoted on light squares and how many promoted on dark squares

By just considering pawn moves while allowing captures when necessary, it shouldn't be hard to determine every possible final structure before trying to place the rest of the units (or after, as a quick check before launching into full solving).

[JoshuaGreen]

I've placed proof-of-concept code in optimisations/intelligent/intelligent.c in my forked JoshuaGreen/popeye feature/optimize_intelligent_mode branch.  That code assumes that we're solving a seriesmover without any (other) fairy conditions or pieces in which Black will make some nonzero number of moves followed by White making a single move to reach the target position, possibly with some extra White pieces still around.  (The simplification to the case where White makes all the moves would be straightforward.)

This code is not meant to be taken as-is; it's complicated and it's still undergoing testing, and I could probably better make use of some of Popeye's own functionality.  Also, the best use of these ideas is within the target position generation machinery, not at the end. Rather, some of the ideas might be useful elsewhere, and I primarily want to show the benefits of this approach.  Against one of my own compositions

BeginProblem
    Author Joshua Green
    Origin "StrateGems" -- October-December 2001
    Pieces
        White Kd6 Ba5 Sb5 Pd2e3
        Black Ke1 Pd3e2e4e5f3g4
    Stipulations ser-h=21
    Option intelligent movenumbers
EndProblem

these added heuristics seem to knock out ~ 90% of the generated target positions and provide an associated solving speedup.

[JoshuaGreen]

An extension of this idea would be to perform similar checks in the solving phase after every considered capture, pawn move, and castling (as well as after the first move, if an initial en passant capture was considered).  I'm not sure where/how best to experiment with that.

[JoshuaGreen]

I've continued working on this idea, extending my previous work to also estimate the number of moves needed to reach a target position. The result is my feature/ feature/optimize_intelligent_mode_count_moves branch, and the results seem pretty dramatic — even when compared to my previous version which just checked feasibility — on some problems, e.g.:

BeginProblem
    author Radovan M. Tomasevic and Joshua Green
    origin "StrateGems" January-March 2021
    stipulation ser-h=16
    option intelligent movenumbers
    Pieces
        White Ka4 Qf4 Ra2g1 Ba5b5 Sa1b1
        Black Kh3 Rc8 Bc1f3 Pb2c2c3g2
EndProblem

Assuming that these improvements are real (i.e., there are no bugs that invalidate these timings), I think it's worth trying to get these heuristics into the next release, possibly as an "experimental" option.