[Retros] Math aspects of Retro from Yefim Treger 08/21/2004

[andrew buchanan]

Folks,

 

(1) I think Yefim *was* asking in his interesting mail about positions which you can't prove whether they are legal or not.

 

And as Seth pointed out, this won't be true since chess has a finite number of possible positions (where I'm taking the definition of position is defined in Article 9.2 of the Laws of Chess). Yefim doesn't respond to Seth's point, which seems pretty conclusive. Seth's argument does not depend upon agreeing a definition of position anyway.

 

One other possibility is to take an infinite board. In a forwards direction, there is a famous paper:

 

"A. S. Fraenkel and D. Lichtenstein. Computing a perfect strategy for n \Theta n Chess requires time exponential in n." Journal of Combinatorial Theory Series A, 31:199--214, 1981.

 

which analyzes chess in a forwards direction. It is a real question whether something similar might be doable in a reverse direction. And then of course there is the question of moving from n to infinity. And what should the starting position be on an infinite board?

 

I must look up the Fraenkel and Lichtenstein paper some time. It probably has some interesting chess constructions at the root of the result.

 

(2) Of course, Joost, you cannot be surprised that I object when you say:

"You can never prove the legality of castling, only the illegality." This has been known not to be true for several years. :-) But I agree that there are very few exceptions.

 

(3) Yefim is asking about the definition of position. There is some cloudiness in the wording of the Laws here. The definition comes from Art 9.2 of the Laws. http://www.fide.com/official/handbook.asp?level=EE101. 

"Positions ... are considered the same, if the same player has the move, pieces of the same kind and colour occupy the same squares, and the possible moves of all the pieces of both players are the same.
Positions are not the same if a pawn that could have been captured en passant can no longer be captured or if the right to castle has been changed temporarily or permanently."

E.p. seems relatively clear though, and I think implies that a possible e.p. must be legal to affect the position. Castling talks about *rights* to castle, which presumably refers to 3.8.ii(1)&(2).

 

I don't quite know why the words "...temporarily or..." appear in the castling part of 9.2. I can't think of how a temporary prevention of castling *could* change between one occurence of an arrangement of pieces and the next occurence of that arrangement.

 

One nit which I presume doesn't work, but is worth closing off, is that after some returning to the game array for the second time, say at move 8.0, after at least one rook has danced around, one might argue a draw can be claimed a draw because even in the starting position at move 0, castling rights were prevented "temporarily" by the blocking actions of Bs, Ns & Qs. 

 

(4) There are some thought-provoking nuggets in Yefim's paper.

 

Here's an example of an illegal position, from which every move goes to a legal position. wKc5, bKb6, bPa7. White to play. This is no more illegal than a position in which there are e.g. way too many pawn captures. There is no way this can happen in a legal game, due to Art. 3.9, but it violates no other Law. Why have bPa7? Because otherwise 1.Kxb6 is legal? (By the way, capturing a king is presumably generally a bad move because after that there is no way to checkmate the opponent :-)

 

Oh, and bare kings can't just cycle round retrogressively. One must uncapture immediately. :-) (See point 2 above.)

 

Regards,

Andrew.


TregerYefim at aol.com wrote:   From Yefim Treger  08/21/2004 Letter to all in retros.at mailing list.
Now, as a mathematician, I am writing a book about Math and Chess where, in particular, some retro aspects are being used. In connection with this I have some questions and thoughts... Understanding a legality as key point of retro topic (and chess itself!) I have come to this "at first look unusual" idea: there might exist a position which cannot be proved to be legal or illegal.
              Let me explain in details.
1. The main idea of my book is analyzing chess game (here: usual game, recorded, for example, by score sheet) from the math prospective, especially by the help of sequence theory. Any game is some sequence of positions (it is better to say so than  "it is a sequence of moves" because Position contains specific details, for example right to castling, ed passant, etc., but there is one to one correspondence between sequence of moves and positions).
On this way I found some interesting results, but do not object to have somebody check or control them (I am referring to an ad in USA "Chess Life" magazine about it; you may use my personal e-mail to discuss book aspects, especially if you are mathematician and/or fond of math). But that is optional.
2. Legality of position is its ability to form a game - as a sequence (of positions) from the beginning, the original position. The given position, on the other hand, as a configuration of pieces (let somebody take chess pieces from the case and put them on the board, even reasonably) may be legal or illegal. The main criterion of legality, I think, is a construction of a game from the original position to the given one. One could use in this way reverse, retro method, in this case it is enough to reach position, which is definitely legal.
3. Retro solver uses this reverse method, but here some situations are possible. If he/she solves the given problem, already proved by the composer, then we know (knew) for sure that the position is (was) legal, only the solver cannot to find legality.
But let a solver be the solver in the stage of defining legality for the arbitrary position. An arbitrary position (or simply: any position) is a position from the side ("from the case" or when composer is creating something and is vulnerable himself about emerging positions…- below). In this situation two results are theoretically possible. If he (we, trying to build a game by the reverse method, backwards, or using "retraction") reaches obviously legal position then the given position is also legal. Otherwise, the question is open, and mathematically it is impossible to say about legality (or illegality!). 
4. This idea came in my mind when I saw some difficult retro-problems (of  Petrovich, Plaksin and others: AP rule, strange sequences, logic lists of statements for the reasoning  of legality, etc…) I want to specify: a conclusion that "there might exist position, which cannot be proved to be legal or illegal" does not mean that such a position is illegal. It means that we cannot establish its legality. Some ideas about logic and set theory paradoxes come in mind (...) but I have some arguments in defense of it. 
5. At first, I found (and proved), that the movement backward (as retro topic calls "move retracting") from the given position does not necessarily mean really the movement to the original position. The point is that all positions in a tree form levels not by any simple moves, but by type structures (moves, which change types, approaching us to the structures where pawns are less advanced, some pieces still are not captured, etc.). For example, it is obvious, that in position with bared Kings there are retracting moves which do not actually useful for us in reaching the original (or other, with more pieces)  position. Simply: it is possible cycling, ("recycling"?), which we have to overcome (but how to do this?)
  At second, there are positions which belong to another type, even when we do not move pawns and/or capture pieces. It is an answer for those who object to me that in retracting it is enough to create positions with pawn less advanced locations or appearance of captured peaces - in this situation we take a risk not to find all levels - look below. I have proved this too (constructed the position which has moves not by pawns and not by captured after which this position will never occur again!)
  At third. I found that in a movement in the tree by direct method (forwards to  final positions) and reverse method (retracting) the following rule is in effect: from legal positions by direct movement only legal positions
can be obtained; from illegal - both legal and illegal; using reverse method: from legal positions both legal and illegal position can be obtained; from illegal - only illegal ones. It means that we cannot apply both methods simultaneously (or not attentively) for the given position. Example: I have constructed illegal position where each move (!) leads to the legal position. Another example: I have constructed the position where some retracting moves lead to the legal positions and some others - to illegal ones. In this last case I even constructed positions of the same type: it means there is a set of illegal positions, connected by cyclic tread, so the further retracting movement results in only illegal positions (only due to specific features of positions we can say that they are illegal; at first sight they look very "usual"). Please recall what I said little above: how can we overcome cycling or round trip; and even if we do we take a risk to build a game where some parts
 consist of illegal position!…) 
    
I forgot about this powerful argument: it is not so simple to build a game from
the original position to the given one (we have to overcome "dead", blokade positions, which never leads to the final). Mathematically it is better to say: it is possible that there exists a position relatively which we cannot build a game even by direct method of choosing all moves (like in Math: there are irrational numbers but we cannot tell what is a given one is - or something like this...)
There are some other arguments in my favor, but I suspect that somebody have something to say… I will be very pleased to answer.
I may give chess positions in gif (jpeg, bmp) files. Is it OK?
Yefim Treger. 08/21/2004
my e-mail: tregeryefim at aol.com 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.pairlist.net/pipermail/retros/attachments/20040822/eecb09cf/attachment.htm>