Endgame fortress handling

Discussion of anything and everything relating to chess playing software and machines.

Moderator: Ras

lech
Posts: 1175
Joined: Sun Feb 14, 2010 10:02 pm

Re: Endgame fortress handling

Post by lech »

hgm wrote:
Lyudmil Tsvetkov wrote:As said, there are simply so many different types of eg fortress positions, not to mention mg ones, that, in order to be consistent, and deal with all of them, or at least half, you will have to add 50 000 lines of eval code into your engine!
...
Lyudmil, you are absolutely right.
Engines should not do some interpretations. It is a question for GUI or users if they can play chess. :)
Maybe, I can't be friendly, but let me be useful.
vincenegri
Posts: 73
Joined: Wed Feb 11, 2015 9:19 am

Re: Endgame fortress handling

Post by vincenegri »

I believe that as a starting point it would be quite straightforward to check the efficacy of this rule.

One would patch a tool like cutechess to monitor the reported evals of the engines during the game (as it does already for adjudication) but look for the "eval over X but has not increased by more than Y over N moves" condition. If triggered, cutechess would register that this had occurred but carry on playing the game out. If the game was indeed drawn, this would be recorded as a 'rule hit' otherwise a 'rule miss'.

At the end of a match of 1000s of games, you then look at the hit/miss figures, and use these to tune the values X/Y/N above to get the best result.

You would always want to be conservative so that you don't miscategorise a position as a fortress that is in fact lost (that would be very bad for Elo!)


To actually apply the rule into the search of an engine such that it was able to /steer away/ from fortresses would require (I think) nodes in the TT to keep track of their eval history as they get updated by propogation during the search.
User avatar
hgm
Posts: 28543
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Endgame fortress handling

Post by hgm »

The problem is that the rule is pretty pointless. You want to know whether the position is a draw well in advance, so that you can still avoid it. If you can see that only when you search 20 ply beyond it, it will be too late.

Note that current top engines very heavily prune non-PV branches. If the opponent can convert to a fortress by a small sacrifice, initially the engine will not think the sacrifice is worth it, because it won't recognize the value of the fortress. So the fortress will not end up on the PV first time it is seen.

To then search 20 ply beyond it, so the rule triggers and the fortress posiiton gets upgraded enough to become PV, would require a PV depth of perhaps 80 plies....

An additionalproblem is that an alpha-beta search will not really be able to see if there is progress or not. When you did sac, say, R for B to reach the KQPKRPP fortress, white will not make the slightest attempt to make any progress. It will think "wow, I am already an exchange ahead compared to other branches, no need to do anything at all!", and it will then just sit there, playing null move after null move. Needless to say, the null moves won't make much progress... You would really have to wait for the defence in the main line to make enough progress that it forcibly gains at least an exchange to trigger any activity at all in the side branch.

Alpha-beta search is 'lazy': it won't try to make progress if it thinks the position is already good enough without further progress. In fact if the position was better than needed, it will allow the opponent to slowly eat most of that advantage away, as long as just enough of it remains to stay better than the PV. So even in dramatically won positions on a side branch you would see no progress. If the rule would start penalizong that (supposing you ever could force the engine to search that branch deep enough to triggerthe rule) you would force the engine to be less lazy on all side branches where it has totally won, to prove it can make progress. That would be extremely expensive, and would easily reduce the depth reached by, say, Stockfish, in an average position by a factor 2. Not much of its strength would remain...
Last edited by hgm on Thu Mar 26, 2015 3:14 pm, edited 1 time in total.
User avatar
Evert
Posts: 2929
Joined: Sat Jan 22, 2011 12:42 am
Location: NL

Re: Endgame fortress handling

Post by Evert »

Lyudmil Tsvetkov wrote:
hgm wrote:I don't think having to search 10 moves (20 ply!) to recognize these positions as a draw is the right approach. Because they are all very easily recognizable as fortresses, they could already be recognized as draws at 0 ply. It is just a matter of having some knowledge in the eval, and wrapping it such that it won't take measurable time to apply it.

The positions you show have cheap and easy triggers:
*) unlike Bishops
*) connected passers vs Bishop
*) almost all value in a single piece
*) King trapped
*) interlocked Pawn chains of >6 Pawns

These are things that almost any evaluation looks at anyway (e.g. when evaluating King safety, Pawn structure or material balance). They could be used to trigger a slightle more elaborate analysis of the positions. Like if Queen and non-passer are your only possession, can you ever hope to gobble up an unprotected piece? (As even a 2-for-1 trade means the end of your ambitions.) Well, if every opponent piece is already protected (also something that can be easily checked), the chances for that seem slim. And your King is cutoff from his. (Slightly more difficult to figure out, but the chances that you would pass the lone-Queen + all-protected test are already so slim that you would virtually never have to do it.)

If engines do not see this, it just means they are stupid. As mentioned before, a high Elo is no cure against stupidity. There just aren't any cheap search tricks that can substitute for true knowledge. (Not even expensive ones!)
As said, there are simply so many different types of eg fortress positions, not to mention mg ones, that, in order to be consistent, and deal with all of them, or at least half, you will have to add 50 000 lines of eval code into your engine!

IMHO, impossible.
Therefore I think search should really try to see it somehow.

If the eval approach had been so easy, many engines would have implemented that by now, but we see that almost none recognizes similar patterns, for example in TCEC SF does not have a clue about Q vs R eg fortress.
I think the idea of scaling the score because the search fails to make any progress is really fundamentally broken.

Consider the following scenario: the position is a fortress position, but the engine does not realise this and gives some large (material) evaluation. However, the engine completely fails to make any progress, so the score stays essentially constant from the very first iteration onward: the best move and score at depth N are not different from those at depth 1. Now, this is something that one could fairly easily detect, and you can then apply a correction to the score that scales it back closer to 0. Easy enough and if you set the engine to analyse a fortress position, it will (eventually) display a draw score, so it looks smart. Awesome!
Except we haven't really changed the search at all, we're just fudging the score for the benefit of the user. For game play this is irrelevant (it only triggers if we're already in the fortress position) and I claim that it is pretty useless for analysis too, exactly because you only recognise it if it's already too late. Really what you want is to see the score drop when it becomes inevitable that the fortress position is reached, not just after the fact.

So fortress detection in the root is going to be cosmetic only, and feeding the knowledge back into the search isn't going to help because it doesn't change the fact that the root is already a fortress position. What's needed is a way to detect the fortress position before we move into it. I can probably come up with an algorithm that will detect this for nodes with an exact score (record the score and depth history of the search in addition to the current values: if the score does not change with increased depth, you can set a flag to indicate that the position is probably a fortress position) but it becomes trickier with bounds - not to mention the fact that once you record a drawish score for a position (because it's a fortress) any regular research of the position that doesn't know that the draw score comes from fortress detection is going to see a large change in score and destroy the fortress detection code (leading to search instability or worse). Solvable, but requires some careful attention to detail. I don't know how to handle bounds here.

Some sort of special quiescence search can do it, where you see if a d=0, d=1, d=2... search yield different scores, but this is almost certainly prohibitively expensive unless it is very heavily restricted.

Another way to look at this is the following: a (static) fortress is a fortress where the defender (say black) can just null-move since white can make no serious threats to his current position. Importantly, black has to be able to just shuffle his pieces around without breaking the fortress (white cannot place black in zugzwang).

So I would really suggest that the only way to properly handle fortress positions in a way that is useful for analysis is through some very specialised evaluation routine. It will not detect all of them, but detecting some of them reliably will already be quite a feat.

I would try something like this just to get started:

Code: Select all

 * If more than one piece on both sides -> assume no fortress
 * If the attacker has passers, or there are pawns on both wings -> assume no fortress
 * If the attacking king can approach the defending king -> assume no fortress
 * If there are undefended pieces -> assume no fortress
Otherwise: if all pieces are defended, and there is no way to force the defending king to abandon the defence, then we assume that this position is a fortress

Or:
 * If all pawns are blocked and
 * there is no way for rooks to penetrate the enemy position
 * there is no way for bishops to penetrate the enemy position
 * there is no way for knights to penetrate the enemy position
 * there is no way for kings to penetrate the enemy position
Then the position is a fortress draw
The second one is relatively easy to code up, but probably relatively less important in actual games.

Probably the way to detect fortresses should be some combination of the evaluation pre-conditions I just listed and a special null-move based search along the lines I just listed:

Code: Select all

All pre-conditions satisfied, can we drive away the king?
 - Check, evade
   Does the position still qualify as a fortress candidate?
 - No: -> not a fortress
 - Yes: -> check, evade
   Is the king back to where it started two moves ago?
 - Yes: -> fortress 
 - No: continue based on a depth argument?
You can prolong the cycle over which you detect the fortress based on remaining depth. I do something similar for the Tsume (mate) search in SjaakII: near the leaves, I only ever check for 3-ply mates (check-evade-mate) but further from the leaves the cycle can be longer (check-evade-check-evade-mate, etc).

EDIT: oh, forgot to bring up cases where it takes more than 10 (20, 30) moves to make progress. They're there, but any fortress detection will screw them up. Also forgot to bring up a point about testing with node-counts to test whether the idea works independently of whether it works on time-based testing (better eval works better for fixed-node games where the cost of evaluation is irrelevant).
Uri Blass
Posts: 11270
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: Endgame fortress handling

Post by Uri Blass »

I think that rules like this are not going to work.

There are cases when you can make progress with a fortress position.

For example bilnd bishop
Suppose that you do not know about it and get this position

[d]7k/8/8/p7/8/7P/6BP/7K w - - 0 1

White can go with the king and capture the pawn a5 and later get progress with the pawn a2 a3 to improve the position so the program is not going to detect it as a fortress.

It may also detect as a fortress positions that are not fotress and the search is simply not deep enough to see the win and you need a lot of moves.

For example I am afraid that it may detect mate in 50 with KNN vs KP as
a draw.
Lyudmil Tsvetkov
Posts: 6052
Joined: Tue Jun 12, 2012 12:41 pm

Re: Endgame fortress handling

Post by Lyudmil Tsvetkov »

Evert wrote:
Lyudmil Tsvetkov wrote:
hgm wrote:I don't think having to search 10 moves (20 ply!) to recognize these positions as a draw is the right approach. Because they are all very easily recognizable as fortresses, they could already be recognized as draws at 0 ply. It is just a matter of having some knowledge in the eval, and wrapping it such that it won't take measurable time to apply it.

The positions you show have cheap and easy triggers:
*) unlike Bishops
*) connected passers vs Bishop
*) almost all value in a single piece
*) King trapped
*) interlocked Pawn chains of >6 Pawns

These are things that almost any evaluation looks at anyway (e.g. when evaluating King safety, Pawn structure or material balance). They could be used to trigger a slightle more elaborate analysis of the positions. Like if Queen and non-passer are your only possession, can you ever hope to gobble up an unprotected piece? (As even a 2-for-1 trade means the end of your ambitions.) Well, if every opponent piece is already protected (also something that can be easily checked), the chances for that seem slim. And your King is cutoff from his. (Slightly more difficult to figure out, but the chances that you would pass the lone-Queen + all-protected test are already so slim that you would virtually never have to do it.)

If engines do not see this, it just means they are stupid. As mentioned before, a high Elo is no cure against stupidity. There just aren't any cheap search tricks that can substitute for true knowledge. (Not even expensive ones!)
As said, there are simply so many different types of eg fortress positions, not to mention mg ones, that, in order to be consistent, and deal with all of them, or at least half, you will have to add 50 000 lines of eval code into your engine!

IMHO, impossible.
Therefore I think search should really try to see it somehow.

If the eval approach had been so easy, many engines would have implemented that by now, but we see that almost none recognizes similar patterns, for example in TCEC SF does not have a clue about Q vs R eg fortress.
I think the idea of scaling the score because the search fails to make any progress is really fundamentally broken.

Consider the following scenario: the position is a fortress position, but the engine does not realise this and gives some large (material) evaluation. However, the engine completely fails to make any progress, so the score stays essentially constant from the very first iteration onward: the best move and score at depth N are not different from those at depth 1. Now, this is something that one could fairly easily detect, and you can then apply a correction to the score that scales it back closer to 0. Easy enough and if you set the engine to analyse a fortress position, it will (eventually) display a draw score, so it looks smart. Awesome!
Except we haven't really changed the search at all, we're just fudging the score for the benefit of the user. For game play this is irrelevant (it only triggers if we're already in the fortress position) and I claim that it is pretty useless for analysis too, exactly because you only recognise it if it's already too late. Really what you want is to see the score drop when it becomes inevitable that the fortress position is reached, not just after the fact.

So fortress detection in the root is going to be cosmetic only, and feeding the knowledge back into the search isn't going to help because it doesn't change the fact that the root is already a fortress position. What's needed is a way to detect the fortress position before we move into it. I can probably come up with an algorithm that will detect this for nodes with an exact score (record the score and depth history of the search in addition to the current values: if the score does not change with increased depth, you can set a flag to indicate that the position is probably a fortress position) but it becomes trickier with bounds - not to mention the fact that once you record a drawish score for a position (because it's a fortress) any regular research of the position that doesn't know that the draw score comes from fortress detection is going to see a large change in score and destroy the fortress detection code (leading to search instability or worse). Solvable, but requires some careful attention to detail. I don't know how to handle bounds here.

Some sort of special quiescence search can do it, where you see if a d=0, d=1, d=2... search yield different scores, but this is almost certainly prohibitively expensive unless it is very heavily restricted.

Another way to look at this is the following: a (static) fortress is a fortress where the defender (say black) can just null-move since white can make no serious threats to his current position. Importantly, black has to be able to just shuffle his pieces around without breaking the fortress (white cannot place black in zugzwang).

So I would really suggest that the only way to properly handle fortress positions in a way that is useful for analysis is through some very specialised evaluation routine. It will not detect all of them, but detecting some of them reliably will already be quite a feat.

I would try something like this just to get started:

Code: Select all

 * If more than one piece on both sides -> assume no fortress
 * If the attacker has passers, or there are pawns on both wings -> assume no fortress
 * If the attacking king can approach the defending king -> assume no fortress
 * If there are undefended pieces -> assume no fortress
Otherwise: if all pieces are defended, and there is no way to force the defending king to abandon the defence, then we assume that this position is a fortress

Or:
 * If all pawns are blocked and
 * there is no way for rooks to penetrate the enemy position
 * there is no way for bishops to penetrate the enemy position
 * there is no way for knights to penetrate the enemy position
 * there is no way for kings to penetrate the enemy position
Then the position is a fortress draw
The second one is relatively easy to code up, but probably relatively less important in actual games.

Probably the way to detect fortresses should be some combination of the evaluation pre-conditions I just listed and a special null-move based search along the lines I just listed:

Code: Select all

All pre-conditions satisfied, can we drive away the king?
 - Check, evade
   Does the position still qualify as a fortress candidate?
 - No: -> not a fortress
 - Yes: -> check, evade
   Is the king back to where it started two moves ago?
 - Yes: -> fortress 
 - No: continue based on a depth argument?
You can prolong the cycle over which you detect the fortress based on remaining depth. I do something similar for the Tsume (mate) search in SjaakII: near the leaves, I only ever check for 3-ply mates (check-evade-mate) but further from the leaves the cycle can be longer (check-evade-check-evade-mate, etc).

EDIT: oh, forgot to bring up cases where it takes more than 10 (20, 30) moves to make progress. They're there, but any fortress detection will screw them up. Also forgot to bring up a point about testing with node-counts to test whether the idea works independently of whether it works on time-based testing (better eval works better for fixed-node games where the cost of evaluation is irrelevant).
Interesting why, if the eval approach should really work with fortresses, why more than half a century of very active computer chess development, the only fortress position even the top engines manage to assess correctly is the very simple wrong bishop fortress? Is not this just a bit too negligeable a progress, if the eval approach really could have worked?

Also, the eval suggestions you and Harm are making will possibly solve only 1 to 3% of all eg fortress positions, and for that you will have to add a big chunk of code, and then test if it really works.

If you can not solve eg fortresses based on eval, and if the seacrh approach also does not work, that simply means we will never have top engines understanding fortresses.

But thanks for the rest of the suggestions.
I think you have a point especially about using null-moves technique to try improve on a potential algorithm. Not quite certain how this will work, but there should be a way to do this.

I think that, even if you add no elo at all, just showing the right scores in such positions would be very nice to see from engines. Imagine Komodo and SF in TCEC, even with tbs, playing a queen vs rook fortress, which actually already has happened, and both engines giving huge white advantage for the queen side, while the game actually ends in a draw in 50 moves time after a lot of shuffling. Who benefits from that? Neither the engines, nor the spectators. It would be much better that the engines instead agree to a draw after a couple of moves with 0.0 scores.

But I am fully certain that a way could also be found so that the engine uses the available history data concerning lack of score improvement over a specific depth so that it feeds that info back into its search to take pruning decisions. I do not know how exactly that would be done, but it is possible. In this case, engines will benefit from a similar rule both in terms of appealing play, and elo contribution.

If there are so many eg fortress positions, the actual elo gain should not be that small after all.
Vinvin
Posts: 5378
Joined: Thu Mar 09, 2006 9:40 am
Full name: Vincent Lejeune

Re: Endgame fortress handling

Post by Vinvin »

Uri Blass wrote:I think that rules like this are not going to work.

There are cases when you can make progress with a fortress position.

For example bilnd bishop
Suppose that you do not know about it and get this position

[d]7k/8/8/p7/8/7P/6BP/7K w - - 0 1
In this kind of position, the rule is : if the king can go in the corner (no piece can prevent that), it's draw !
User avatar
hgm
Posts: 28543
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Endgame fortress handling

Post by hgm »

Lyudmil Tsvetkov wrote:Interesting why, if the eval approach should really work with fortresses, why more than half a century of very active computer chess development, the only fortress position even the top engines manage to assess correctly is the very simple wrong bishop fortress? Is not this just a bit too negligeable a progress, if the eval approach really could have worked?
Because it does not provide measurable Elo? Most engine authors are not interested at all in having their engine play good Chess. They are only interested in whether their engine can beat other engines that also do not know how to play good Chess.
Also, the eval suggestions you and Harm are making will possibly solve only 1 to 3% of all eg fortress positions, and for that you will have to add a big chunk of code, and then test if it really works.
That estimate seems to have no basis at all. It is just something you make up. Well, I can play that game too: my eval suggestion will solve 97-99% of the fortress positions. :lol:
But I am fully certain that a way could also be found so that the engine uses the available history data concerning lack of score improvement over a specific depth so that it feeds that info back into its search to take pruning decisions. I do not know how exactly that would be done, but it is possible. In this case, engines will benefit from a similar rule both in terms of appealing play, and elo contribution.
There seems no need for the engines to do that. You could simply have the GUI adjudicate the game as draw when they make no progress.
If there are so many eg fortress positions, the actual elo gain should not be that small after all.
That doesn't necessarily follow. It only matters which percentage of games does end in a fortress. But that fraction could be significantly larger when you play games between one engine that knows about them, and one that doesn't. I have seen that in Xiangqi with perpetual chasing. If both engines think it is an acceptable way to force a draw, it hardly ever happens, perhaps only in 1-2% of the games. If one engine knows that it is forbidden, and the other doesn't, 18% of the games end in a forfeit for the latter!
Lyudmil Tsvetkov
Posts: 6052
Joined: Tue Jun 12, 2012 12:41 pm

Re: Endgame fortress handling

Post by Lyudmil Tsvetkov »

Uri Blass wrote:I think that rules like this are not going to work.

There are cases when you can make progress with a fortress position.

For example bilnd bishop
Suppose that you do not know about it and get this position

[d]7k/8/8/p7/8/7P/6BP/7K w - - 0 1

White can go with the king and capture the pawn a5 and later get progress with the pawn a2 a3 to improve the position so the program is not going to detect it as a fortress.

It may also detect as a fortress positions that are not fotress and the search is simply not deep enough to see the win and you need a lot of moves.

For example I am afraid that it may detect mate in 50 with KNN vs KP as
a draw.
The position you post is wrong, because white simply can not take the black pawn without black taking both of white's pawns.

Black simply plays a5-a4-a3-a2, and the bishop should take the pawn in 3 moves time. Otherwise, if the bishop blocks the pawn on a2, then, when the white king goes to a3 to capture the pawn, the black king will capture both of white's pawns.

So the rule is valid also above.

Concerning NN vs pawn, well, there are tbs for such simple positions, but in most cases this will simply be a draw.

For reference, please check wikipedia article here: http://en.wikipedia.org/wiki/Two_knights_endgame
specifically the section about the Troitzky line

The article states, that NN vs pawn is rare and practically unimportant, though theoretically interesting. The side with the two knights, if a win is present, may win within 115! moves sometimes, in most cases shorter, but well beyond 50 moves.

Practically though, either an easy win will be seen with enemy king in a corner, or the win will be altogether unavailable.

So I appreaciate your very original contribution as usual, Uri, but I do not see how the rule will suffer after this. :)
User avatar
hgm
Posts: 28543
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Endgame fortress handling

Post by hgm »

Lyudmil Tsvetkov wrote:Black simply plays a5-a4-a3-a2, and the bishop should take the pawn in 3 moves time. Otherwise, if the bishop blocks the pawn on a2, then, when the white king goes to a3 to capture the pawn, the black king will capture both of white's pawns.
But it is white's turn, and I would play 1. Bc6. Then not much of your a5-a4-a3-a2 plan would remain, if you would not want me to make progress by gaining the black Pawn immediately. And then I would advance the first white Pawn under cover of my King to h6, whith my King on g6, so that black has to keep his King on g8-h8 to prevent me promoting. After that I would move the Bishop via a5 to c2 (so it covers h7 as soon as I move my King). Up to that point moving up the black Pawn loses the Pawn without compensation, as my own Pawns are still protected by the King.

Then I move Kf6, and at that point luring the Bishop away with a5 still doesn't get you the white Pawn back in compensation, as after you attack it with Kh7 I can still protect it with Kg5. And one move later I step into the Pawns 'quadrate' with Ke5, so the King will now eat the Pawn, and my own Pawn will move to h7 under protection of the Bishop, so you will never get it. And you cannot go to the rear Pawn because you cannot step behind the front one without allowing it to promote...

But I guess you missed Uri's point. which is that you can always supplement an iron-clad fortress with some indefensible superfluous material, to allow the opponent some progress by putting up a fight for gaining that (and eventually succeeding), and that would delay the recognition of the fortress by your heuristic even more.