- #1
HrvojeDjurdjevic
- 23
- 4
- TL;DR Summary
- Series of articles authored by Maliković, Janičić, Marić and Čubrilo demonstrate computer-aided proofs of KRK theorem, here I present pen and paper one
The articles:
https://lmcs.episciences.org/5328/pdf
http://argo.matf.bg.ac.rs/publications/2013/2013-icga-krk-sat.pdf
http://archive.ceciis.foi.hr/app/public/conferences/1/papers2012/dkb3.pdf
KRK endgame is a win for white regardless of starting position, with the trivial drawing exception in case when black moves first and is able to capture the rook, or is stalemated in the corner.
Proving that requires describing at least one winning strategy for white, and proving its correctness, either by computer aided method or by pen and paper non-computer-aided method.
Auxiliary Definition 1: two kings stand in opposition if they are on the same line two squares away.
Corollary 1: two kings in opposition prevent each other to move to three squares adjacent to both of them, ie to move to the line that separates them, and is perpendicular to the line they both stand on. Proof: trivially follows from Definition 1 and from the game rules.
Corollary 2: when king is not placed at the edge of the board, and is not constrained by other pieces, it has access to three lines parallel to the same edge, ie to three ranks and to three files. Proof: trivally follows from the game rules.
Obviously, these two are not corollaries of the main theorem, but of the game rules, they are also lemmas to main theorem, so I could have named them also that way.
Lemma 1: in KRK endgame checkmate is possible if and only if BK is at the edge of the board. Proof:
BK is checkmated if WK stands in opposition on the line perpendicular to the edge at which both BK and WR stand, with d(BK,WR)>1, if BK is in the corner, WK can also stand one square away from the previously described opposition square, two lines away from the edge at which both BK and WR stand, with Chebyshev d(WK,BK)=2.
In both cases WK denies BK access to penultimate line parallel to the edge BK stands on, in case of opposition according to Corrolary 1, and in the other case corner placement helps due to the fact that the third square not guarded by WK does not exist, and WR covers the edge. No other checkmate position is possible, because there are no other pieces that could prevent BK from accessing the third line BK would have access to, according to Corollary 2, had BK not been placed at the edge, and this proves Lemma 1.
Now, in order to prove the main theorem, one has to prove two more lemmas:
Lemma 2: in KRK endgame it is always possible to force BK to one edge
Lemma 3: in KRK endgame, if BK is constrained to one edge by WR standing on the penultimate line which is parallel to that edge and separates two kings, it is always possible to force position in which it is white to move and deliver checkmate, by achieving position described in Lemma 1.
Proof of Lemma 3:
In order to prepare that mate in 1 position, white will make three kinds of moves:
1.) decreasing Manhattan d(WK,BK), approaching with king without ever stepping onto penultimate line or into opposition
2.) shifting rook from one edge to another staying safe on the same penultimate line when BK threatens its capture
3.) waiting move with rook when 1.) is not possible and 2.) is not necessary, this is any move on penultimate line which does not change the ordering of pieces and keeps WR safe from capturing
It is obvious that applying 2.) white can always obtain tempo to approach with the king to a line adjacent to that which rook holds, two lines away from the edge where BK stands, from any other line further away, and to transpose to a position in which WK stands between BK and WR in terms of lines perpendicular to the edge where BK stands, although WR stands all the time between WK and BK in terms of lines parallel to that edge.
From that position, black has two choices moving king along the edge, either to increase or decrease Manhattan d(WK,BK). If it tries to increase it, white will follow with 1.), but black is limited in this strategy with the corner, if it tries to decrease it, white will either follow with 1.) if possible, or 3.) otherwise, limit to this strategy is black stepping into opposition, when white follows with checkmate, which proves Lemma 3.
In the same vein, one can prove Lemma 2, and complete the theorem:
It is always possible to place safely from capturing WR on the line that separates two kings, that conclusion is rather trivial. From there white will apply exactly the same strategy as in Lemma 3, the only difference is that instead of checkmate it will result in squeezing BK one line nearer the edge, the limit of this strategy is BK ending at the edge.
Questions:
how rigorous
how original
is this proof?
https://lmcs.episciences.org/5328/pdf
http://argo.matf.bg.ac.rs/publications/2013/2013-icga-krk-sat.pdf
http://archive.ceciis.foi.hr/app/public/conferences/1/papers2012/dkb3.pdf
KRK endgame is a win for white regardless of starting position, with the trivial drawing exception in case when black moves first and is able to capture the rook, or is stalemated in the corner.
Proving that requires describing at least one winning strategy for white, and proving its correctness, either by computer aided method or by pen and paper non-computer-aided method.
Auxiliary Definition 1: two kings stand in opposition if they are on the same line two squares away.
Corollary 1: two kings in opposition prevent each other to move to three squares adjacent to both of them, ie to move to the line that separates them, and is perpendicular to the line they both stand on. Proof: trivially follows from Definition 1 and from the game rules.
Corollary 2: when king is not placed at the edge of the board, and is not constrained by other pieces, it has access to three lines parallel to the same edge, ie to three ranks and to three files. Proof: trivally follows from the game rules.
Obviously, these two are not corollaries of the main theorem, but of the game rules, they are also lemmas to main theorem, so I could have named them also that way.
Lemma 1: in KRK endgame checkmate is possible if and only if BK is at the edge of the board. Proof:
BK is checkmated if WK stands in opposition on the line perpendicular to the edge at which both BK and WR stand, with d(BK,WR)>1, if BK is in the corner, WK can also stand one square away from the previously described opposition square, two lines away from the edge at which both BK and WR stand, with Chebyshev d(WK,BK)=2.
In both cases WK denies BK access to penultimate line parallel to the edge BK stands on, in case of opposition according to Corrolary 1, and in the other case corner placement helps due to the fact that the third square not guarded by WK does not exist, and WR covers the edge. No other checkmate position is possible, because there are no other pieces that could prevent BK from accessing the third line BK would have access to, according to Corollary 2, had BK not been placed at the edge, and this proves Lemma 1.
Now, in order to prove the main theorem, one has to prove two more lemmas:
Lemma 2: in KRK endgame it is always possible to force BK to one edge
Lemma 3: in KRK endgame, if BK is constrained to one edge by WR standing on the penultimate line which is parallel to that edge and separates two kings, it is always possible to force position in which it is white to move and deliver checkmate, by achieving position described in Lemma 1.
Proof of Lemma 3:
In order to prepare that mate in 1 position, white will make three kinds of moves:
1.) decreasing Manhattan d(WK,BK), approaching with king without ever stepping onto penultimate line or into opposition
2.) shifting rook from one edge to another staying safe on the same penultimate line when BK threatens its capture
3.) waiting move with rook when 1.) is not possible and 2.) is not necessary, this is any move on penultimate line which does not change the ordering of pieces and keeps WR safe from capturing
It is obvious that applying 2.) white can always obtain tempo to approach with the king to a line adjacent to that which rook holds, two lines away from the edge where BK stands, from any other line further away, and to transpose to a position in which WK stands between BK and WR in terms of lines perpendicular to the edge where BK stands, although WR stands all the time between WK and BK in terms of lines parallel to that edge.
From that position, black has two choices moving king along the edge, either to increase or decrease Manhattan d(WK,BK). If it tries to increase it, white will follow with 1.), but black is limited in this strategy with the corner, if it tries to decrease it, white will either follow with 1.) if possible, or 3.) otherwise, limit to this strategy is black stepping into opposition, when white follows with checkmate, which proves Lemma 3.
In the same vein, one can prove Lemma 2, and complete the theorem:
It is always possible to place safely from capturing WR on the line that separates two kings, that conclusion is rather trivial. From there white will apply exactly the same strategy as in Lemma 3, the only difference is that instead of checkmate it will result in squeezing BK one line nearer the edge, the limit of this strategy is BK ending at the edge.
Questions:
how rigorous
how original
is this proof?
Last edited: