Scorched Earth Algorithm and Unmove-engine would be powerful tools for study composers.
If I understand correctly, SEA requires EGT re-generation...?
An Unmove-engine seems to be easier for Effective-UMS searching.
If UMS line strikes WTM duals A, B, C... with their DTM values a, b, c..., (let 'a' be the lowest), and if b=a or b=a+1, then B is a 'dead dual'.
If b=a+k, then make move B, and only Black's replies with DTM values > 'a' must be taken into consideration.
And so on: to spot a repetition, Black's replies always must have DTM value >= a...
May be very fast?
UMS-, EUMS-facilities, 'Scorched Earth' and Unmove-engine
UMS-, EUMS-facilities, 'Scorched Earth' and Unmove-engine
- Attachments
-
- KQRKQRfortress.pgn
- Two versions of Sukharev MT study
- (9.08 KiB) Downloaded 283 times
-
guyhaw
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
The Scorched Earth Algorithm SEA
Let SP be a non-empty set of wtm, 1-0 (i.e. win for White) positions - let's start with SP == {P} with just one position as we don't need SP to have multiple positions here.
White's moves are constrained by its ambition to win, and by Black's choices.
Let us imagine that chess has another rule (lifted from Go), namely that if a position is repeated, it is a draw. Therefore, White must not allow repetition if it is to win.
Z(SP) is the set of positions from which Black can force a visit to a position in SP. Then White must not move from P to Z(SP) and 'eliminating duals' is about proving that after moves P --> P', P' is in Z(SP) apart from one progressing move.
The generation of any endgame's EGT E0 retro's the initial, given conditions back into the whole endgame. Even the KQK EGT requires the input of "Kk is a draw". One way to detect Z(SP) is to _define_ all SP's positions as draws (even though they are actual wins) as part of the 'given' conditions. Then create EGT E1 which will be a perturbation (or 'corruption') of E0. Check all the destination positions to make sure that all except one have had their values changed from 1-0 to draw. This is the simplest, and slowest, version of the Scorched Earth Algorithm.
However, it's clear that no position of shallower depth than P's (and think of depth in plies rather than moves) will be affected. So we should unmove from P [pretending to be a 'draw', remember] and (say) unset all theoretical values to 'unknown', meanwhile noting these positions somewhere. Then we can run a Nalimov-type algorithm to see which of these 'unknown' positions can be restored to a 1-0 win for White. These will have 'routes down' not involving P.
[ Since we are making no use of the relative depths of positions, the above can be done with a WDL 'SHREDDERBASE' EGT, and in fact, this is all that needs to be done. We can just ask if the destination positions P' are (all but one) in the new set of draws. It might be v efficient because one has 2-bit entries rather than 8-16-bit entries per position. But even so, we are missing setting some positions (e.g. 'btm has a draw to move to' and wtm "White has only draws to move to" positions) to draws. ]
Returning to EGTs with depth information, it may be that some positions can be immediately set to draws (because Black can reach a draw or because White's one route to win has vanished), or can be left as wins (because they have an advancing move to a position that is still a win). However, the positions that only have retreating winning moves (and drawing moves) must be set to 'unknown' - to be revisited later in 'Phase 2'.
If one wants to avoid looking at the whole EGT, one has to keep track of the 'now unknown' positions and the 'frontier of perturbation from P' (the ripple on the lake after the stone is dropped in). Doing this efficiently is the key.
It is not possible to retro back _just_ to the prior depth of the positions P'. They may or may not have an escape to a position P" with a higher depth (previously), implying that P' is still a win but with greater depth. So I think the whole Z(SP) has to be identified.
When testing the successive moves of a study, if the previous White moves have been forced, one just perturbs E0 to E1, E2 etc - and you find that the 'non-mainline dual moves' have often been eliminated before you get to P. This is when Black can force a return to a mainline position before P. Happens all but one time (+ the two moves you noted) in your study.
Certainly, in playing a game, one might have a rule not to repeat positions too (when chasing a win). Again here, the original EGT E0 can be perturbed to E1 after move m1, to E2 after move m2 etc.
If you work through these ideas, as I'm doing, in the context of study EG #15958, you'll hopefully see how the above works.
This is about as far as the write-up of the algorithm has got at the moment: I'm working on saying it more formally, and giving examples.
g
[/i]
White's moves are constrained by its ambition to win, and by Black's choices.
Let us imagine that chess has another rule (lifted from Go), namely that if a position is repeated, it is a draw. Therefore, White must not allow repetition if it is to win.
Z(SP) is the set of positions from which Black can force a visit to a position in SP. Then White must not move from P to Z(SP) and 'eliminating duals' is about proving that after moves P --> P', P' is in Z(SP) apart from one progressing move.
The generation of any endgame's EGT E0 retro's the initial, given conditions back into the whole endgame. Even the KQK EGT requires the input of "Kk is a draw". One way to detect Z(SP) is to _define_ all SP's positions as draws (even though they are actual wins) as part of the 'given' conditions. Then create EGT E1 which will be a perturbation (or 'corruption') of E0. Check all the destination positions to make sure that all except one have had their values changed from 1-0 to draw. This is the simplest, and slowest, version of the Scorched Earth Algorithm.
However, it's clear that no position of shallower depth than P's (and think of depth in plies rather than moves) will be affected. So we should unmove from P [pretending to be a 'draw', remember] and (say) unset all theoretical values to 'unknown', meanwhile noting these positions somewhere. Then we can run a Nalimov-type algorithm to see which of these 'unknown' positions can be restored to a 1-0 win for White. These will have 'routes down' not involving P.
[ Since we are making no use of the relative depths of positions, the above can be done with a WDL 'SHREDDERBASE' EGT, and in fact, this is all that needs to be done. We can just ask if the destination positions P' are (all but one) in the new set of draws. It might be v efficient because one has 2-bit entries rather than 8-16-bit entries per position. But even so, we are missing setting some positions (e.g. 'btm has a draw to move to' and wtm "White has only draws to move to" positions) to draws. ]
Returning to EGTs with depth information, it may be that some positions can be immediately set to draws (because Black can reach a draw or because White's one route to win has vanished), or can be left as wins (because they have an advancing move to a position that is still a win). However, the positions that only have retreating winning moves (and drawing moves) must be set to 'unknown' - to be revisited later in 'Phase 2'.
If one wants to avoid looking at the whole EGT, one has to keep track of the 'now unknown' positions and the 'frontier of perturbation from P' (the ripple on the lake after the stone is dropped in). Doing this efficiently is the key.
It is not possible to retro back _just_ to the prior depth of the positions P'. They may or may not have an escape to a position P" with a higher depth (previously), implying that P' is still a win but with greater depth. So I think the whole Z(SP) has to be identified.
When testing the successive moves of a study, if the previous White moves have been forced, one just perturbs E0 to E1, E2 etc - and you find that the 'non-mainline dual moves' have often been eliminated before you get to P. This is when Black can force a return to a mainline position before P. Happens all but one time (+ the two moves you noted) in your study.
Certainly, in playing a game, one might have a rule not to repeat positions too (when chasing a win). Again here, the original EGT E0 can be perturbed to E1 after move m1, to E2 after move m2 etc.
If you work through these ideas, as I'm doing, in the context of study EG #15958, you'll hopefully see how the above works.
This is about as far as the write-up of the algorithm has got at the moment: I'm working on saying it more formally, and giving examples.
g
[/i]
Similar problems may be solved this way:
1) Start with {P}, value of position altered =’unknown’=’u’
2) Generate corrupted E’ database (with the only difference to normal database: now P value is ‘u’), so only a set Z(P) will get values=‘u’
3) Check if White’s alternatives are now ‘u’, they are ‘repetition-duals’.
1) Start with two ‘final’ study-like positions P’ and P’’, their values altered=’u1’ and ‘u2’
2) Generate corrupted E’ database with Z(P’) of ‘u1’ values, and Z(P’’) of ‘u2’ values
3) Check if there are positions with both ‘u1’ and ‘u2’ values – they are candidates for a study with two finals…
1) Start with {P}, value of position altered =’unknown’=’u’
2) Generate corrupted E’ database (with the only difference to normal database: now P value is ‘u’), so only a set Z(P) will get values=‘u’
3) Check if White’s alternatives are now ‘u’, they are ‘repetition-duals’.
1) Start with two ‘final’ study-like positions P’ and P’’, their values altered=’u1’ and ‘u2’
2) Generate corrupted E’ database with Z(P’) of ‘u1’ values, and Z(P’’) of ‘u2’ values
3) Check if there are positions with both ‘u1’ and ‘u2’ values – they are candidates for a study with two finals…
-
guyhaw
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
Reply to Tulean (2)
As this is currently a one-to-one dialogue, we could go back to email 
But, assuming someone else is interested, here are some further thoughts prompted by your reply.
I think you are now seeing (very quickly) that the thrust of SEA is to identify Z(P) rather than to follow-the dual-moves to a shallower depth than P's. The problem with the latter is White can keep conceding depth, and diving deeper. This all gets very messy, and eventually I gave up on this approach entirely.
I wondered whether it was aesthetically right to set the current position P's value to 'draw', or whether 'broken' or 'unknown' would be more appropriate.
We certainly create 'unknown' values temporarily, and the rules of retro'ing back have to include retro'ing back an unknown-value. So, yes, we could set P to unknown initially - but should we? If we do, then all the btm positions that move to P (which could have been set to 'draw') would be set to unknown too. So there would be more 'unknown' positions at the end of the 'killing-off 1-0s phase' than need be, and therefore I think more tidying up to do in phase 2.
'Unknown' has to mean "draw or 1-0" in the algorithm and therefore doesn't reflect the fact that we are pretending that P is _not_ a 1-0 win for White.
So we should set P to 'draw' or 'broken': by the way, setting P to 0-1 just creates more perturbation than we need. Choosing 'broken' as the new value is more honest, but choosing 'draw' is more pragmatic in that it probably gives a more efficient algorithm - and it does provide the perturbation to EGT E that we need.
I'm happy with the economy of Z(P) rather than Z({P}) etc.
Certainly, Z(P) and Z(P') might overlap. I used to think of Z(P) as a 'Basin of Attraction' B(P), borrowing the mathematical concept, but there are some problems in doing that. The Z(P) are not disjoint basins, and P is not a point of stability. The concept of 'attraction' works as well here as in the mathematical basins, which is to say - not that well.
However, I think your claim that overlapping Z(P) and Z(P') means two finales for a study is based on an assumption that White's moves in Z(P) are unique. This is not so, and the Saavedra study is our ilustration as before. White must get its K from Kb4 to Kc2 and has the choice Kb3-Kc2 or Kc3-Kc2, so - strictly speaking - no 'unique winning moves' there.
However, if you say that the theme of the study is to get from somewhere in Z(P) to P, then these 'reconverging lines' may artistically be seen as ignorable - both being entirely in Z(P) - and maybe there's a computer algorithm here too.
I think we need to work in terms of specific examples, to check the conceptual arguments here. As I suggested, try implementing SEA by hand in the context of yr KQRKQR study.
email preferred for me; we can always come back to the board with an attached file tidying all this up.
g
But, assuming someone else is interested, here are some further thoughts prompted by your reply.
I think you are now seeing (very quickly) that the thrust of SEA is to identify Z(P) rather than to follow-the dual-moves to a shallower depth than P's. The problem with the latter is White can keep conceding depth, and diving deeper. This all gets very messy, and eventually I gave up on this approach entirely.
I wondered whether it was aesthetically right to set the current position P's value to 'draw', or whether 'broken' or 'unknown' would be more appropriate.
We certainly create 'unknown' values temporarily, and the rules of retro'ing back have to include retro'ing back an unknown-value. So, yes, we could set P to unknown initially - but should we? If we do, then all the btm positions that move to P (which could have been set to 'draw') would be set to unknown too. So there would be more 'unknown' positions at the end of the 'killing-off 1-0s phase' than need be, and therefore I think more tidying up to do in phase 2.
'Unknown' has to mean "draw or 1-0" in the algorithm and therefore doesn't reflect the fact that we are pretending that P is _not_ a 1-0 win for White.
So we should set P to 'draw' or 'broken': by the way, setting P to 0-1 just creates more perturbation than we need. Choosing 'broken' as the new value is more honest, but choosing 'draw' is more pragmatic in that it probably gives a more efficient algorithm - and it does provide the perturbation to EGT E that we need.
I'm happy with the economy of Z(P) rather than Z({P}) etc.
Certainly, Z(P) and Z(P') might overlap. I used to think of Z(P) as a 'Basin of Attraction' B(P), borrowing the mathematical concept, but there are some problems in doing that. The Z(P) are not disjoint basins, and P is not a point of stability. The concept of 'attraction' works as well here as in the mathematical basins, which is to say - not that well.
However, I think your claim that overlapping Z(P) and Z(P') means two finales for a study is based on an assumption that White's moves in Z(P) are unique. This is not so, and the Saavedra study is our ilustration as before. White must get its K from Kb4 to Kc2 and has the choice Kb3-Kc2 or Kc3-Kc2, so - strictly speaking - no 'unique winning moves' there.
However, if you say that the theme of the study is to get from somewhere in Z(P) to P, then these 'reconverging lines' may artistically be seen as ignorable - both being entirely in Z(P) - and maybe there's a computer algorithm here too.
I think we need to work in terms of specific examples, to check the conceptual arguments here. As I suggested, try implementing SEA by hand in the context of yr KQRKQR study.
email preferred for me; we can always come back to the board with an attached file tidying all this up.
g
-
guyhaw
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
Corrected pgn file - and update
AZ, the study author, has pointed out some mistakes in my .pgn file - so I have (hopefully) applied all those corrections and at the same time clarified the position-labelling.
It would obviously have been a good idea to give different positions different labels: this has been done.
It all goes to show how useful a tool to spot 'the zone' of a position P, and all the looping-circuits, would have been.
g
It would obviously have been a good idea to give different positions different labels: this has been done.
It all goes to show how useful a tool to spot 'the zone' of a position P, and all the looping-circuits, would have been.
g
- Attachments
-
- EG165 KQRKQR.pgn
- Analysis of study main line.
- (4.86 KiB) Downloaded 254 times