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).