Corresponding Squares

From Chessprogramming wiki
Revision as of 12:07, 7 November 2018 by GerdIsenberg (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Home * Evaluation * Game Phases * Endgame * Pawn Endgame * Corresponding Squares

6k1/3p4/3p4/3P4/4P1p1/6P1/8/K7 w - -

Corresponding Squares, also called Co-ordinate Squares is a concept to analyse pawn endgames. Using retrograde analysis, Zugzwang positions and Critical Squares are found. Corresponding Squares Systems were one of the first human attempts of finding formulas and finally solving certain chess positions. This concept is only possible due to the limited mobility in pawn endgames. King-oppositions and Zugzwangs are the main motives arising.

Theory

To get an idea, the concept is described using an example position by Charles Dealtry Lockock, 1892 [1] :

Finding Critical Squares

In the presented position there exist two critical squares. First when the white king reaches d4, white threatens 1. e5 dxe5 2. Kxe5 (threatening attacking both Pd7 and Pg4 in the next move). To defend this threat the black king must be able to move to f6 after Kd4. Secondly when the white king reaches e3, white threatens 1. Kf4 ... 2. Kxg4. In order to avoid this the black king must stand on g5.

To summarize, the two critical squares are e5 and f4. The according corresponding squares where both sides have mutual zugzwang are Kd4 - Kf6 and Ke3 - Kg5.

Constructing Corresponding Square System

CoSq2.png

This particular example, where two Corresponding Squares are connected diagonally and there is enough space for a 3x3 square, Averbakh called the eight-square system. The construction of this Corresponding Square System starts with numbering the first two Corresponding Squares 1 and 2 accordingly. The square connecting the two receives the number 3. The outer squares of the 3x3 field receive the numbers 4 to 8. Further outside the numbering can continue by using the number of a square exactly two squares away either diagonally, horizontally or vertically. The image below should exemplify this process.

Using the Corresponding Square System

The numbers tell us that if the white king manages to step on a square with the same number as the square on which the black king is standing, he automatically wins the fight for the critical squares. The same case occurs if the white king can step on a square the black king can not reach in the next move. The contrary is also possible. As soon as the black king moves on the same numbered square as the white king he can automatically defend the Corresponding Squares.

The way to take advantage of the Corresponding Square System is easy now. White must move towards the critical squares, never stepping on squares the black king can defend. 

1. Kb1! (steps on 3, the black king can not reach any 3-squares) Kg7
2. Kc1 (steps on the same number as the black king: 5) Kg6
3. Kd1 Kg5 4. Kc2 Kh5 5. Kc3 Kg5 6. Kc4 Kg6 7. Kd3 Kg5 8. Ke3

Computer Chess Implementation

First of all it must be noted that the concept of Corresponding Squares was designed to give the human chess player a tool to efficiently analyze a complex pawn endgame. Computers can very easily solve such positions using their Transposition Tables. Just as an example it takes Computers only a couple of seconds to reach > depth 20 in the Lasker-Reichhelm position, also referred as Fine #70 [2] and thus find the opponent's Zugzwang. Nevertheless Computers also have some disadvantages. The main problem is the point where the chess engine has to decide whether to enter a certain pawn ending or not. Usually these positions offer a lot more mobility, thus conducting a deep enough search seems infeasible.

The first attempt of tackling Corresponding Squares with a computer chess engine was made by Rafael B. Andrist and his chess program Wilhelm [3] [4]. More recent research was done by Edmund Moshammer:

Algorithm by Moshammer

In principle this approach is quite similar to an Endgame Tablebase Generation process. The main difference is its optimization to be used on the fly in chess engines. To represent the Corresponding Squares 64 bitboards are used, which for every position of the attacking king represent the squares where the opponent king must stand to prevent the attacker from achieving a predefined objective.

Definitions: 

U64 legalSq[2]; // stores the squares where attacking/defending king may move to
                //     (ie.: not attacked by a pawn or occupied by a own pawn)
U64 coSq[64];   // stores the Corresponding Squares for each attacking king position
U64 bbSQ[64];   // bbSQ[i] = 1 << i;
int kingmoves[8] = {-9, -8, -7, -1, 1, 7, 8, 9};  // used for move generation later

U64 mgen_fill_KING(U64 squares);  // shifts squares one step in all 8 directions

The main retrograde routine to build the Corresponding Square system:

  • initialize coSq: for every position of the attacking king, the defending one may not stand on neighboring squares or squares previously defined illegal (attacked by attacker's pawns or occupied by own pawns)
  • set changes to a full bitboard - ie: all squares have to be looked at in the first pass
  • loop until all Zugzwang situations have been resolved:changes == 0
  • loop through all unresolved positions of the board
    • reset the square on 'changes', as the position is being examined now
    • initialize Katt: squares from which the attacking King can move to attack the current square
    • initialize Kdef: squares from which the defending King can defend the attacking king to reach the current square - ie: the neighboring squares of the current square and the squares one king move away from the corresponding squares of the current position
    • for each of the attacking king moves
      • checks that the move is on the board and is part of the legal moves (Katt)
      • if coSq is changed on the resulting position, set 'changes' accordingly, so that the changes are considered in the next pass
      • the Corresponding Squares of each neighboring attacking King position have to collide with the Corresponding Squares one Kingmove away from this position
// attacker .. attacking side
// coSq ...... pointer to the Corresponding Squares Bitboards

void coSq_setupSystem(int attacker, U64 * coSq) {
  for (int i=0; i<64; i++) 
    coSq[i] &= ~mgen_fill_KING(bbSQ[i]) & ~bbSQ[i] & legalSq[!attacker];

  U64 changes = 0xFFFFFFFFFFFFFFFF;
  while (changes) {
    for (int i=0; i<64; i++) {
      if (changes & bbSQ[i]) {
        changes ^= bbSQ[i];
        U64 Katt = mgen_fill_KING(bbSQ[i]) & legalSq[attacker];
        U64 Kdef = mgen_fill_KING(bbSQ[i]) | mgen_fill_KING(coSq[i]);

        for (int j=0; j<8; j++) {
          int Ksq = i + kingmoves[j];
          if (!(Ksq & ~0x3F) && (bbSQ[Ksq] & Katt)) {
            changes |= bbSQ[Ksq] * ((coSq[Ksq] & ~Kdef) != 0);
            coSq[Ksq] &= Kdef;
          }
        }
      }
    }
  }
}

Before the function above is called, the Corresponding Squares must be initialized. Therefore all bits in the coSq-bitboards get set. Then the first Critical Squares are defined by setting the bitboard of the attacking king at the Critical Square to 0. In other words, if the king manages to occupy the square the defending king has no squares to stand on from which he can defend the threat.

The setupSystem function itself does nothing else than looping through the bitboards and uses the rule that the defending king may only stand on a square from which he can reach all corresponding squares the attacking king may create within one move. This is done as long as no further changes are made to the bitboard.

The time it takes to analyze a position is about linear. For the Lasker-Reichhelm position (Fine #70), it took 10 cycles through the 64 squares of the board to find out that the black king can impossibly defend all of its pawns.

There is however one open question - the definition of the Critical Square. A straight forward approach would be to set the critical Squares to capturing the opponent's pawns. If in the end alpha > 0 and the defending king is standing on a Corresponding Square one can safely fail low at that point. A more complex approach would be necessary to find out whether a position is won or drawn.

Publications

Paris-Brussels 1932, German Edition 2001 Opposition und Schwesterfelder, ISBN 3-932170-35-0

Postings

External Links

References

  1. ↑ Position by Charles Dealtry Lockock, 1892, from Yuri Averbakh, Ilia Maizelis (1987). Comprehensive Chess Endings Vol 4: PawnEndings. Cadogan Books
  2. ↑ Reuben Fine (1941). Basic Chess Endings
  3. ↑ chess program "Wilhelm" released by Rafael B. Andrist, CCC, August 19, 2001
  4. ↑ Gegenfeldsysteme und Schachprogramm by Rafael B. Andrist, ChessBits Forum, August 19, 2001 (German)

Up one level

Retrieved from "https://www.chessprogramming.org/index.php?title=Corresponding_Squares&oldid=8282"