50 moves rule

[Kirill Kryukov]

Perhaps this is worth its own topic.

Do you have 50 moves rule or something like that in checkers?

The venue for tournament checkers is not nearly what it is in chess. In checkers, they have a vaguely worded "40 move rule" where you simply must "show progress" towards a win, to be adjudicated by a referee if the need arises. The problem would be, in many instances a referee is not on par with the playing strength of those who tend to play out such endings.

OK, it's 40 moves then. I agree that ambiguously worded rules are potential sources of troubles. Can "progress" be defined similarly to chess as irreversible move (move of a checker, a capture, or a promotion)?

In December of 2004, checkers World Champion Alex Moiseyev visited my house, and played against the 7-piece database. It should be noted, this was a win that required 253 plies of perfection. All along the way, one slip would turn it into a draw. Alex was not able to complete the win on the strong side, and when defending the loss, the database found a much shorter route to the win. It is safe to say, such incredibly complex positions are beyond the capabilities of the strongest human.

It causes a lot of issues and debates in chess endgame solving, and limits the usefulness of Win-Draw-Loss tables. Also Nalimov tables (the most popular format in chess, distance to win, up to 6 pieces currently) are suffering from not accomodating this rule.

In my opinion, that rule was designed for human play, and it should remain in the domain of human vs. human competitions. What player would want to play out a 100-move ending in R + B vs. R, for example?

In computer vs. computer tournaments, I say wave the rule and let the programs play it out. Maybe a special set of rules would make sense.

1) If a program announces mate at any point before the 50 move rule would stop the game, the counter resets.
2) If the announcement was "Mate in X" and X + 1 moves elapse, the defending side is awarded the draw.
3) If "X" is ridiculously large and deemed a deliberate exaggeration to circumvent the 50-move rule, the declaring program is given a forfeited loss.

That should make the computer-computer endgames more interesting, and the tablebase generator effort would become more worthwhile.

I'm not sure if it's easy to strictly define "deliverate exaggeration", or to formalize such rule for computer play. To be practical a rule has to be clearcut. Draw after 40 consecutive reversible moves seems simple enough to be practical. Clearly some such rule is necessary for computer-computer games too, because sometimes it's the only way to interrupt an otherwise infinite game.

My bigger problem with ignoring the 50 moves (or 40 moves) rule in endgame tablebases is that it increases the fragmentation of the game ecosystem. Many human players use tablebases to analyze actual tournament games. Now suddenly they find themselves in a situation where supposedly "perfect" endgame knowledge is not applicable to the very same game, because it's not for exactly same game they play in tournaments. A position may be a tablebase win, but the winning line contains a longer-than-50-moves series of reversible moves. Then often it is (currently) impossible to know if the position can really be won or not under tournament rules.

Same for computer tournaments. All computer chess tournaments (that I am aware of) are employing the 50 moves rule. The Elo advantage of considering 50 moves rule in the tablebase is probably unmeasurable (much smaller than the really tiny Elo gain from using tablebases at all). Although things may change slightly when 7-pieces tablebases will become practical in chess.

In checkers the fragmentation is already high (with half a dozen realy popular checkers variants). Adding with / without 40 moves rule will again double the number of variants.

Although I agree that an unbounded database has some more methematical beauty.

[Ed Trice]

OK, it's 40 moves then. I agree that ambiguously worded rules are potential sources of troubles. Can "progress" be defined similarly to chess as irreversible move (move of a checker, a capture, or a promotion)?

Yes to both of those, and moving a checker forward or executing a capture resets the counter. In checkers, though, I believe "gaining space" and "coordinating your kings better" also counts as "progress", and it is rather nebulous. They have a very small playing population, and I don't think they have to worry about claims that much.

I'm not sure if it's easy to strictly define "deliberate[edit] exaggeration", or to formalize such rule for computer play.

I agree. I added that just to cover an obvious example. Suppose a computer were to announce "Mate in 300" on move 1 of the game? Then it would not have to worry about the 50-move rule restriction from the previous rules I mentioned. Rule #3 can discourage such undermining attempts

To be practical a rule has to be clearcut.

Again, I agree

Draw after 40 consecutive reversible moves seems simple enough to be practical.

I recently asked if castling, being an irreversible move, resets the 50 move rule. I was told it does not, even though it is irreversible! While it is very rare that a king would be uncastled for so long, you can see even existing rules in the tournament arena have not been completely thought out.

My bigger problem with ignoring the 50 moves (or 40 moves) rule in endgame tablebases is that it increases the fragmentation of the game ecosystem. Many human players use tablebases to analyze actual tournament games. Now suddenly they find themselves in a situation where supposedly "perfect" endgame knowledge is not applicable to the very same game, because it's not for exactly same game they play in tournaments. A position may be a tablebase win, but the winning line contains a longer-than-50-moves series of reversible moves. Then often it is (currently) impossible to know if the position can really be won or not under tournament rules.

I guess the shortcut would be to try an irreversible move at each junction, and see if it throws away the win (draw returned by tablebase). If it does not, then you get a fresh counter, and can try again. Also, there are some DTZ metrics possible, aren't there (Distance to Movecount Zeroing)? You can build tablebases that consider the N-Move Rule, where you can specify what N is (currently 50) and it will solve the tablebases keeping this metric in mind.

[Kirill Kryukov]

Draw after 40 consecutive reversible moves seems simple enough to be practical.

I recently asked if castling, being an irreversible move, resets the 50 move rule. I was told it does not, even though it is irreversible! While it is very rare that a king would be uncastled for so long, you can see even existing rules in the tournament arena have not been completely thought out.

Yeah, it's a known issue. There are other irreversible moves that don't reset the 50 move counter, for example losing the right to en-passant capture or the right to castle.

Also, there are some DTZ metrics possible, aren't there (Distance to Movecount Zeroing)? You can build tablebases that consider the N-Move Rule, where you can specify what N is (currently 50) and it will solve the tablebases keeping this metric in mind.

Yes, DTZ50 is my favorite metric for chess. I am all for its wider adoption.

[guyhaw]

Consideration of a k-ply rule, and the 50-move rule in particular, does touch on a number of themes, some mentioned above.

First, Checkers and even more so, Chinese Chess do seem to be afflicted by rules which call on the judgement of an arbiter who - at the top level of the game when these rules are more likely to be referred to - will be less able in the game than the two players. This does not help translate the rules of the game into a formal system, q.v. http://centaur.reading.ac.uk/4515/ where Joe Hurd refers to his mapping of the FIDE rules into HOL.

Second, as mentioned by KK, the zeroing of the ply count is associated with 'change of force' and/or 'Pawn advance' on the board after which the game cannot return to a previous position. But this is also true when castling rights change (e.g. after castling!) or an e.p.-opportunity is rejected. In neither of these cases is the ply-count rejected, and maybe this should be put to FIDE as a rule change. Including 'e.p.' in this would only reduce the ply-count by one ply so this would be 'for completeness' only.

FIDE's decision-making is not that predictable and seems at times to be quixotic. I think the life-expectancy of the 50-move rule is not as great as it was, and although a change to a 'round number' divisible by ten is more likely than to another number, the likelihood of FIDE replacing the 50-move rule by a 51-move rule or a 61-move rule is non-zero. Never say 'never'. The original move-figure was set at '50' but has been on tour recently before returning to its starting-point.

For 'C-C' computer-computer tournaments, the organisers are free to decide whether a k-move rule is in place, and it would be interesting to hear if different approaches have been involved here. Certainly, algorithmic rules can be defined to ensure that play continues as long as is necessary - but not unnecessarily. The win-claiming computer could not only say 'win in k' but publish a sample line and guarantee to follow it as long as the opponent does. The depth of the position in (DTM, DTC, DTZ)-space should move in a way consistent with the knowledge claimed by the potential winner.

For H-C, human-computer, carbon-silicon tournaments, the last matches involving Kasparov and I think Kramnik outlawed 6-man EGTs. However, the march of parallelism is such that, given enough HDD I/O bandwidth, the generation of 6-man EGTs can become part of what a program does in real-time during the game and their use is a legitimate part of 'forward search' even though it involves backward-search from identifiable, intermediate goals.

Now we come to the limitations of EGTs to the DTM (Depth to Mate) metric, the DTC (to Conversion) metric, the DTZ (to ply-count zeroing-move) or other, e.g. DTR and DTZR. http://centaur.reading.ac.uk/view/creat ... 00763.html and specifically http://centaur.reading.ac.uk/4566/ review the use of metrics and provides a notation to define strategies ro methods of filtering down to the set of preferred moves.

It is worth noting that in all cases, depth is measure in winner's moves which is less than symmetrical and actually leads to an edge-effect. If a phase starts with a loser's move and forcibly ends with a loser's move 100 plies later, then the initial position in the phase would look like a win with DTZ=50 but in fact the loser could cite the 100-ply rule before playing their only available move and takinig the game into the next phase. Should FIDE finesse the k-move rule by saying that no claim is possible if the next move is forced?! I suspect not as there is likely to be some position in which being able to make the draw-cliam seems ludicrous.

Each EGT, if they are - as now - simply linear lists of position depths, one per position, can deliver only that one fact about the position. If DTM > 50, there may be issues about the mimimaxed length of some constituent phase of the game and that is why I defined the DTR (Depth by The Rule) and supporting DTZR metrics. It is not possible to build (DTR, DTZR) EGTs in the usual way to guarantee in the conventional way that a win will be won, thus postponing further the day when any (DTR, DTZR) EGT will exist. In their absence, the DTC EGT can be used to some effect when DTM > 50, at least ensuring that DTC < 51 but maybe on occasion making the draw-claim more likely. SImilarly, the DTZ or DTZ50 EGT may be used to moderate a pure DTM-centric strategy.

Note that the familiar DTM and the less familiar DTC, DTZ and DTZ50 EGTs are all constructed on the basis that the loser is maximising the same metric that the winner is minimising. It may be that the winner is minimising DTM while the loser, to their advantage, is maximising DTZ. The next phase would hten not arrive as quickly as it did in the DTM EGT. This is underlined by a hypothetical (DTR, DTZR) EGT where the winner is minimising DTR and DTZR in that order, but where the loser might choose to sacrifice in DTR terms in order to route the winner to a smaller DTR target which is not achievable in the available moves: more thinking is needed to undersand whether this scenario can be defended against - but even so, I think that 'DTR, DTZR' EGTs bring further inforamtion to the party. The winner knows they have a win and have some measure of how far they are away from the requisite k-move win.

I have made sub-6-man 'Nalimov; DTC and DTZ EGTs available on the web - see a previous post - and will put the s6m-DTZ50 EGTs there too. JT used to have a complete set of 6m-pawnless DTZ50 EGTs but they may need regenerating. A problem with using them is that the Nalimov file-format does not identify the metric and even if it did, the Chess GUIs do not yet have the built-in inteliggence to use anything other than DTM. A curious effect happen when using DTC EGTs: the chess-engine walks up to a capture and then refuses to carry it out.

All the s6m positions in Chessbase's BIG CHESSBASE 2010 have been identified and the games they are in have been reviewe: 35m positions, 4.2 s7m positions etc. Again, the extreme situations are recognisable: the final position's theoretical value not agreeing with the advertised result (unnecessary resignation or agreement of draw, clock or arbiter intervention, the DGT effect when Kings are centralised) ... and there are cases of the endgame starting as a win for one side and finishing as a win for the other. KPPPKR is a favourite here. I suspect the analysis potentially identifies transcription errors re moves or the final result and have left this observation with Chessbase.

The DTM>50, DTC>50 and even DTZ>50 part of the chess firmament is visited by human players and an analysis of their efforts gives an indicator of relative competence. q.v. http://centaur.reading.ac.uk/4550/ , http://centaur.reading.ac.uk/4548/ and http://centaur.reading.ac.uk/4523/ where KQKR and KBBKN play were looked at.

g

[Kirill Kryukov]

I have made sub-6-man 'Nalimov; DTC and DTZ EGTs available on the web - see a previous post - and will put the s6m-DTZ50 EGTs there too.

Which post you are referring to? Can you post a direct link?

[guyhaw]

The offer of DTC and DTZ EGTs is at viewtopic.php?f=6&t=5262

The DTZ50 EGTs that I have are not there yet. g

[Kirill Kryukov]

Thanks, somehow I missed it. It would be interesting to compare DTZ vs DTZ50 in terms of how many positions have different outcome. Especially for 6-pieces endings. Please post if you'll make the DTZ50 available too.

[Kirill Kryukov]

Second, as mentioned by KK, the zeroing of the ply count is associated with 'change of force' and/or 'Pawn advance' on the board after which the game cannot return to a previous position. But this is also true when castling rights change (e.g. after castling!) or an e.p.-opportunity is rejected. In neither of these cases is the ply-count rejected, and maybe this should be put to FIDE as a rule change. Including 'e.p.' in this would only reduce the ply-count by one ply so this would be 'for completeness' only.

This got me thinking - can there be other irreversible moves? Perhaps even more difficult to detect? I took out the board and pieces and after some shuffling produced this position (rb6/rpp2b2/k7/8/K7/RP3B2/P7/8 w - - 0 1):

rb6/rpp2b2/k7/8/K7/RP3B2/P7/8 w - - 0 1

Both sides can move their white-colored bishops freely, but any move of a king (either white or black) will be irreversible, since after such move the position before the move can never be repeated. It's easy to see that the position is legal, that is, can result from starting one with a sequence of legal moves. (I hope there are no holes in the logic).

I am sure a more beautiful example can be made. I am also sure that some positions exist where irreversability can be much more difficult to detect or prove.

Irreversability assosiated with castling rights or en-passant is trivial to detect, but other irreversable moves exist and are more hard to detect. Therefore I think that it would be futile for FIDE to implement the 50-moves rule based on true irreversability. Keeping it simple, like now, is a good option. (As a bonus, current rules are easier to learn for newbies).

[guyhaw]

KK: see http://centaur.reading.ac.uk/4524/ ... Table 5a - g

[guyhaw]

Yes, there are certainly other moves that are irreversible (other than P-push, capture, e.p.-capture rejection and castling-rights-changing moves).

Your example is indeed one such - nice - however, I think it's not possible to identify all of these (or maybe any) with a simple, computer-implementable set of rules.

g

[Kirill Kryukov]

KK: see http://centaur.reading.ac.uk/4524/ ... Table 5a - g

Thanks, interesting!

Yes, there are certainly other moves that are irreversible (other than P-push, capture, e.p.-capture rejection and castling-rights-changing moves).

Your example is indeed one such - nice - however, I think it's not possible to identify all of these (or maybe any) with a simple, computer-implementable set of rules.

g

Yes, they are very hard to detect algorithmically. That's why 50-moves rule should not depend on true irreversability.

One simple example of irreversable move is moving a king out of check, given by a pawn. Certainly a king can't return into the check, so the move is irreversible, but such move can take place only immediately after the pawn's move, same like rejecting the en-passant. So it would change the counter by 1 only.

In the example position above, on the other hand, the irreversible move does not have to immediately follow, nor be followed by a pawn's move or capture. It can occur anywhere in the middle of a sequence of reversible moves.

Here is one more example, only slightly different. (8/8/8/8/RQrr4/p7/P2ppp2/K2kb3 w - - 0 1). Here Qb1 (also Rc1, if it's black to move) would be irreversible:

8/8/8/8/RQrr4/p7/P2ppp2/K2kb3 w - - 0 1


I'm curious if a less trivial example can be found.

I'm also curious if checkers can have irreversible move that does not involve a checker move or a capture.

[koistinen]

Yes, there are certainly other moves that are irreversible (other than P-push, capture, e.p.-capture rejection and castling-rights-changing moves).

Your example is indeed one such - nice - however, I think it's not possible to identify all of these (or maybe any) with a simple, computer-implementable set of rules.

g

Do you by simple mean near O(N) rather than near O(N^2)?

[guyhaw]

Oops - I see I filed this snippet in a new thread which was not my intention (and it can be deleted): the item was meant to be under this '50-move-rule' thread ...

http://centaur.reading.ac.uk/4524/, 'Chess Endgames: 6-man data and strategy', includes the max DTZ50 position 'BB-NN' and a DTZ50-minimaxing line of 28 moves.

Really quite elegant and one of my favourite bits of chessic choreography: Black keeps trying to sac a N (to go to KBBKN with DZ > 50) and White keeps turning it down.

g

[guyhaw]

We are discussing if there are any other scenarios when the ply-count can be set to zero because the last move is 'easily seen' to be irreversible.

Currently only capture and P-push zero the ply-count but a move which rejects an e.p.-pawn-catpure-offer or reduces castling rights is also irreversible.

As the 50-move rule was introduced in the interests of professional players in coffee-houses, it's worth noting that they would not have been interested in increasing the number of opportunities to zero the ply-count


KK rises well to my challenge and immediately comes up with another scenario which is easily describable: 'King moves away from P-check'. Excellent: 'add to shopping cart'!

I wasn't thinking of a formal measure of complexity but of a condition which can be tested by observation of only the comparison of the positions before and after the irreversible move. KK's 'King-retreat from P-check' example can be easily identified in this way.

A 'FIDE rule' would have to be one that a rank-and-file arbiter could be expected to implement correctly, easily and quickly - and so should avoid the potential requirement for extended chessic analysis.


We now have the challenge of the minimal chess position (i.e. least men on the board) from which an irreversible move can be mode (not involving capture, P-push, castling rights reduced, e.p.-offer-spurned ... or K-retreat from P-check). This would be one for the 'study community' who read the magazine EG - except that the 50-move rule does not apply to studies other than retrograde studies.

g

[Kirill Kryukov]

We now have the challenge of the minimal chess position (i.e. least men on the board) from which an irreversible move can be mode (not involving capture, P-push, castling rights reduced, e.p.-offer-spurned ... or K-retreat from P-check). This would be one for the 'study community' who read the magazine EG - except that the 50-move rule does not apply to studies other than retrograde studies.

Here is one with 3 pieces (and one more item for the shopping cart): a move that forces a capture, or a pawn push, is itself irreversible (Kf1 in this example):

8/8/8/8/8/8/7P/4K2k w - - 0 1
8/8/8/8/8/8/7P/4K2k w - - 0 1


Perhaps this should be included into a catalog of trivial irreversible moves. Then looking for a non-trivial irreversible move with fewest pieces possible should be an interesting challenge.

[Kirill Kryukov]

Extending the last one: "a move that forces a move that forces a capture or a pawn push" - is irreversible. Only 6 pieces here:

8/8/8/8/8/1r1p4/p2Q4/k2K4 b - - 0 1
8/8/8/8/8/1r1p4/p2Q4/k2K4 b - - 0 1


1...Rb1+ is irreversible, as it forces 2.Qc1, after which black has to choose between 2...Rxc1+ and 2...d2.

A study composer can probably find a position with much longer sequence of forced moves. Some may even include multiple choices for some moves, like the last move in this example.

[guyhaw]

The 3-man position would appear to sort minimality out - except that White would obviously play 1.h4 or 1/h3 to be really annoying.

... and you don't want to be forcing a zeroing of the move-count if you're losing, so I think the minimal position for a so-far-non-trivial-irreversible-move is still open.

Clearly, the extension of rules for zeroing the move-count could get complicated, so how about:

- one cannot claim a 'k-move draw' if one's opponent can prove that the game will irreversibly advance by some unavoidable sequence (to be declared).

The 6-man position is better ... Black would certainly be annoyed if White claimed the 50-move draw just before 2.Qc1 which is forced.

g