Endgame fortress handling

[Evert]

Here's another idea: a form of retrograde analysis.

First task: identify whether the current position can be broken down immediately (by forcing a piece to evacuate a crucial defensive position). If not, it's clearly not a fortress.
Second task: assuming defender to move, identify moves that keep the fortress in tact.
Third task: try to force the defender to make a move that breaks the fortress.

If you cannot do that, the current position is a fortress draw.

Example using a position from the first post:

[d]6k1/5p2/4r2p/8/3Q4/8/6P1/6K1 w - - 0 1
1. White's king cannot assault black's king (potential fortress).
2. All of black's pieces are defended (the position cannot be broken down immediately)
3. Black moving Kf8/g8/g7 keeps the fortress in tact.
4. Glue the pawns, rook and white king in place.
5. Is it possible, using just the queen, to force the black king to a square from which it cannot maintain the fortress (this requires building a bitbase over the black king/white queen queen positions)? The answer is no.
6. Make pawn-slices by advancing the white pawn; this changes nothing.
7. Possibly test some of the crucial positions that come out of the analysis by seeing if the white king can possibly contribute at all (even if it cannot penetrate the fortress), but this is probably not needed since the white king cannot penetrate the fortress (and it cannot drive the defending king from the corner in general).

There are still details that need to be worked out, but this may be a useful way to look at it. It may be too slow for the search during play, but could well be useful during analysis. The interesting thing is that this will not only identify fortresses, but also the way to dismantle something that isn't really a fortress at all, but that superficially looks like one.

What's needed to turn this type of speculation into source code though is a set of test positions, both fortresses and non-fortresses that can be broken down with the correct plan.

[Lyudmil Tsvetkov]

Other possible reasons why testing this method might fail.

Well, you try to detect shuffling moves, when the score does not increase, but testing at very short TC might really create a serious problem, as when low on time, engines might shuffle both in normal positions for a while at least, and in fortress positions. This will make impossible to register any available elo benefit, and quite probably you will see only elo drops.

So that, in order to test this in a proper way, maybe a longer or considerably longer TC is necessary, otherwise you might not be able to distinguish between shuffling in normal and fortress positions. I do not really quite see how one can test this at TC smaller than 2 min per game.

[Lyudmil Tsvetkov]

All 3 things you stated are completely wrong.

- in all fortress positions scores do not increase at all, or just marginally, to reflect changing piece psqt and mobility, as practically nothing else changes

Already refuted by Uri's example: the score clearly rose from +4 to +6 in the presence of the fortress, and would have risen further with more depth.

- large scores tend to increase very rapidly always, unless the position is a fortress (maybe though they decrease in the case of FairyMax, I am not certain ):shock:

You really don't know anything about engines, do you? All lines always tend in score towards the PV, because the engine would not make any effort whatsoever to increase it, or even keep the advantage, if it is already better than the PV.

- for the first time I hear adding many lines of code with heavy specific rules only speeds up the engine; I hope Marco does not see this

We already concluded that your knowledge of programming, and Chess engines in particular, is dismal. Could you even manage to install and run one? And why do you hope Marco would overlook things? Are you unfriendly to the Stockfish development?

You are dreaming of something that really never happened.

[Uri Blass]

I am fully certain search can do the job much better instead, but you need a lot of testing to tune the respective parameters, but, first of all, an engine whose eval does not bounce back and forth like mad, but is more or less stable. Unfortunately, even among the top, such engines are rare.

So you are wrong. As Uri's example, and the engine analysis of it convincingly showed. Scores will continue to increase steadily with search depth even in dead drawn fortress positions, in Uri's case from +4 to +7 in some 35 ply, while the initial position is already a dead draw, and could have been trivially recognized as such. (Only Rook Pawns and a Bishop, the King on the promotion square where your Bishop cannot get at it.)

And it still seemed not to have sunk in with you that in alpha-beta searches large scores typically do not increase at all, in non-PV branches of the tree (i.e. 99.99999% of the branches...), but on the contrary decrease, from +3, to +0.01 (compared to the PV score).

Finally that the number of lines added to a code would determine the slowdown is also a misconception. It doesn't matter how many lines you add. Just how many of them are typically executed, and how often. Adding 50000 lines of code does not have to cause any measurable slowdown, if only a small fraction of them would be executed, and then even in rare situations where there really is a fortress. And whether executing additional code is a slowdown or a speedup is determined by what the alternative behavior is. If that would be a 20-ply search on the position that could otherwise have been pruned without further search becasue a fortress was detected, even executing all 50000 lines would be a speedup of a factor 100.

I agree that it is possible that a big evaluation may be one way to solve the problem but I think that more interesting way to solve the problem may be by search but not what lyudmil suggested.

The way that I think to solve the problem is the following.

You start with engine X that does not know nothing about fortress.

Now you build engine Y that has the following expensive evaluation function.

Tell engine X to play against itself at 0.1 seconds for all the game(hopefully with future fast hardware the level of the game can still be super GM level).

If the result of the game is a win for white evaluate the position as closer to win for white relative to X's evaluation
If the result of the game is a win for black evaluate the position as closer to win for black relative to X's evaluation.

If the result is a draw evaluate the position as closer to zero relative to X's evaluation and not more than 2 pawns for one side.

Engine Y need 0.1 seconds in order to evaluate a position so it cannot search very deep but engine Y can detect many fortress position with evaluation closer to draw (and in my example it is clear that the result of the game is going to be a draw inspite of the big advantage).

Engine Y will probably be weaker than X but at least Y is going to detect fortress correctly in many cases.

Now it is possible that using Y at small depth and using X later may be better than X because you can decide that sons of position that you suspect to be a fortress position based on draw inspite of big evaluation are also positions that you suspect to be a draw so you also reduce the score for them to be closer to draw.

[hgm]

I think what you propose is already more than is needed. The algorithm should discard the b-Pawn, as it is marked for trading against the a-Pawn, and cannot attack any other black piece before it gets traded. So the only question is whether any of the other pieces is vulnerable to K+Q. Well, the Rook and a-Pawn are protected, and the worst that could happen to them is that Q is traded for R+P. f7 is only protected by the King, but the other King is cut off from it, and against attack of only Q a King is sufficient protection. The squares from which the King can protect it cannot be covered by Q all at the same time.

So the only possible exits to the fortress are:

[d] 8/5k2/4r2p/5K2/6P1/8/8/8 w

[d] 5k2/8/4K2p/8/6P1/8/8/8 b

[d] 6k1/5p2/7K/8/6P1/8/8/8 b

The first doesn't really have to be taken as a serious threat (because the Q-for-P sac keeps the Rook protected). The other two possible exits could be evaluated by the normal search. The score of the fortress should just receive the score of the exit that is worst for black. (Because presumably white will determine the best way to break it.) If this score is not good eough for black to give him a fail high, he should start searching moves from the candidate-fortress position to see if he can improve the fortress. (E.g. the Rook could not have been in the optimal place yet, like Re8, Kf8.)

[hgm]

You are dreaming of something that really never happened.

Except that everyone just saw it happening. And thus also saw that you are the only one dreaming here. The engine scores I posted were clear enough. What did you post in this thread that ever exceded the level of nonsensical babble that only reflects your unfounded misconceptions,completely disconnected from any reality?

[hgm]

I guess the following simple procedure would work pretty well. It supposes there is some cheap pattern recognition that can qualify the black position as a 'candidate fortress'. Like: white has only Queen and non-passers; all black pieces protected, enemy King cut off from pieces only protected by King.

This recognition would be good enough to reduce the eval of the position to 0, but allow the the following search privilege to white:
In stead of doing a move, white is allowed to re-arrange his pieces in any way he wants, in order to launch an attack on the fortress. With the restriction that his confined pieces cannot leave the confinement, i.e. his King will not be able to pass through check, and Pawns are not allowed to move through occupied squares, or squares covered by opponent Pawns. And the rearrangement can include a single capture or move to threaten PxP, when not checking with another piece. After that rearrangement, normal search will continue, with black to move.

In particular, useful rearrangements might be advancing its Pawn to a square covered by an opponent Pawn, with its King or Queen put in a place to protect it, and its Queen put to pin the Pawn it tries to pass, if possible. Or capture one of the black pieces, and put his King to protect the capturer, and advance the Pawn as far as allowed. Or give a check, and put its King to limit the number of possible evasions as much as possible. Other rearrangement would not seem to add anything, and might as well be pruned pre-emptively.

This would search all possible ways to break the fortress, without going through the very large tree of pointless move that leave it intact, and having to wait for the 50-move rule (or an ad-hoc 20-ply rule) to discover they lead nowhere, a few million nodes later. Challenge him to break down the fortress immediately by taking any shortcut he wants, so that it will be immediately clear he will not be able to do it, no matter what.

Of course if one of the re-arrangements would break the fortress condition (i.e. make the pattern recognition would no longer qualify it as a fortress candidate) in a way that does not end well for black, the 'fortress challenge' would have failed low, and black would have to start searching real moves from the candidate-fortress position in the hope he can enhance the fortress to one that will be able to survive the challenge.

If white elects to 'play' a check rearrangement, black would be forced to move, and in the discussed example would attempt to evade in a way to maintain the fortress pattern (i.e. protect f7 now from another location). This would immediately be recognized as a fortress candidate again, and thus pose a new challenge to white to break the fortress with the King in the new place. White would quickly find out that checking doesn't achieve anything on this fortress, not even when done consecutively with a teleporting Queen and simultaneously semi-teleporting King. The fortress would in fact consist of the three positions with the black King on f8, g8 and g7, and checks would merely interconvert these into each other. And none of these would have any satisfactory 'capture exits' to the fortress challenge. (Although the one after QxR, PxR, KxP with the black King comes close, just lacking a tempo.) The score of the 'fortress challenge' would be that of the best white exit, in this case KPKP or worse. So they would be scored as equal from the very first moment the search would encounter them.

[petero2]

I guess the following simple procedure would work pretty well. It supposes there is some cheap pattern recognition that can qualify the black position as a 'candidate fortress'. Like: white has only Queen and non-passers; all black pieces protected, enemy King cut off from pieces only protected by King.

This recognition would be good enough to reduce the eval of the position to 0, but allow the the following search privilege to white:
Instead of doing a move, white is allowed to re-arrange his pieces in any way he wants, in order to launch an attack on the fortress. With the restriction that his confined pieces cannot leave the confinement, i.e. his King will not be able to pass through check, and Pawns are not allowed to move through occupied squares, or squares covered by opponent Pawns. And the rearrangement can include a single capture or move to threaten PxP, when not checking with another piece. After that rearrangement, normal search will continue, with black to move.
...

Interesting procedure. However I think it will have problems in some positions where a candidate fortress can be broken by a long sequence of maneuvering relying on checks and zugzwang. Consider this position:
[d]8/5k2/4p3/3r4/5K2/2Q5/8/8 w - - 0 1
White can force mate in 47 moves (starting with Kg4), but if the candidate fortress condition is that all black pieces are protected and row(rook) > row(white king), it takes some 20 plies of maneuvering to break the candidate fortress condition.

If white is allowed to maneuver for 20 plies it will realize that this is not a real fortress, but then it might also be allowed to maneuver for 20 plies in real fortress positions (such as the one below), thus significantly delaying the fortress detection.
[d]8/7k/6p1/5r2/7K/4Q3/8/8 w - - 0 1

[Evert]

Interesting procedure. However I think it will have problems in some positions where a candidate fortress can be broken by a long sequence of maneuvering relying on checks and zugzwang. Consider this position:
[d]8/5k2/4p3/3r4/5K2/2Q5/8/8 w - - 0 1
White can force mate in 47 moves (starting with Kg4), but if the candidate fortress condition is that all black pieces are protected and row(rook) > row(white king), it takes some 20 plies of maneuvering to break the candidate fortress condition.

I'm not sure that's a problem. The question is: is there a sequence of moves that will force black to break the fortress? You don't necessarily need to know what it is.

In this particular case you begin by teleporting the white queen to h8 and now the black king can be forced out of the defensive position, or the rook needs to move - either of those breaks open the fortress.

Perhaps that isn't enough in general to proof that the fortress cannot hold, but the weaker version (you cannot proof that the fortress does hold) may be sufficient to decide.

If white is allowed to maneuver for 20 plies it will realize that this is not a real fortress, but then it might also be allowed to maneuver for 20 plies in real fortress positions (such as the one below), thus significantly delaying the fortress detection.
[d]8/7k/6p1/5r2/7K/4Q3/8/8 w - - 0 1

That's why I think you don't want to do a forward search for a position where the fortress is broken, but a type of retrograde search starting from a position where the fortress is broken up - and in fact if it's just about evaluation, you don't even need to build up the path to get there, you just need to know if it's possible.

Consider: it's faster to solve KBNK by building a tablebase on the fly than by doing a forward search.

[hgm]

I'm not sure that's a problem. The question is: is there a sequence of moves that will force black to break the fortress? You don't necessarily need to know what it is.

Indeed, this is why the proposed procedure skips the manoeuvring, and replaces it by teleporting. White will always have to prove he can break the fortress in single pseudo-move. And I think the number of pseudo-moves that has to be considered can be limited to an acceptable number. (Although I forgot one: another possible fortress exit is QxR, while K attacks a6, which was protected by the Rook.)

For the recognition the condition that all black pieces have to be protected is also too much: black can have expendable pieces in addition to a fortress, and you don't want those to impede fortress recognition. So the procedure of recognition should be something like:

Oops, only Q + non-passer. Can my King reach his? No, cut off by Rook! Is Rook protected? Yes, by Pf7! Is Pf7 Protected? Yes, but only by King! Is Pf7 safe from white King? Yes! That would have identified the fortress candidate in absence of the white Pawn, but now the latter is there we have to worry about it becoming a passer. We so far have identified only the 'fortress core', as it were. The core transitively qualifies the pieces it protects as 'safe', however. So Ph6 is safe, because it is protected by the Rook, which was part of the fortress core.

Then the test continues: Is white Pawn passer? No, h6 stops it! Is h6 safe? Yes! This disquaifies the passer as an obvious show stopper, and finishes confirming the fortress candidate. If black in addition would have a Pawn on b5, it would not be safe, but it would also be no show stopper: it would be 'expendabe'. If white would have another Pawn on c2, black Pb5 would not be expendable, as it is needed to prevent Pc2 from being a passer, and black would have no fortress. If the black Pawn would be on b6, however, it would be kept safe by the Rook, and we would again have a fortress candidate.

Now Peter does have a good point: the fortress should also be 'zugzwang proof'. So a single black constellation can never be a fortress. Black most be forced to move after white has been allowed to teleport his pieces, to see if he can reach another candidate fortress. He cannot be allowed to just sit there, null moving. Also in non-checked positions. In this case there always seems to be a King move that does preserve the fortress condition (which hinges on keeping f7 protected by King here.) It would need searching of some more white pseudo-moves, though. Namely also the Queen positions that restrict black King mobility without checking.

I am still thinking about the retrograde analysis. Of course the whole fortress is so simple that it could have been solved on the fly by retrograde analysis: it is just KQKR (i.e. 4-men) plus a few Pawns. That is fine if it is close to the root, but you cannot do it at many leaves. And I don't think there is much need to solve the fortress exits by retrograde analysis. What matters is that the engine should realize it can only break the fortress by a Queen sac, and that it will realize that without first doing 20 ply of manoeuvring. That would immediately disqualify the branch if there are alternatives that do not involve a Queen sac.

Note that other forms of cutting off the King than with a Rook can also be recognized in the same way. E.g.

[d]6k1/6b1/8/4n2K/Q1p5/8/3P4/8 w