Difference between revisions of "Blockage Detection"

From Chessprogramming wiki
Jump to: navigation, search
m
(One intermediate revision by the same user not shown)
Line 9: Line 9:
  
 
=Search Application=
 
=Search Application=
Blockage detection is only applied for the side with advantage, proving its [[Upper Bound|upper bound]] is a [[Score#DrawScore|draw score]] <ref>Code snippet from [[Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_13 Blockage Detection in Pawn Endings]''. [[CG 2004]], [http://www.ise.bgu.ac.il/faculty/felner/newsite/publications/blockage.pdf pdf]</ref>:
+
Blockage detection is only applied for the side with advantage, proving its [[Upper Bound|upper bound]] is a [[Score#DrawScore|draw score]] <ref>Code snippet from [[Eli David|Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_13 Blockage Detection in Pawn Endings]''. [[CG 2004]], [http://www.ise.bgu.ac.il/faculty/felner/newsite/publications/blockage.pdf pdf]</ref>:
 
<pre>
 
<pre>
 
int search(int alpha, int beta, ...) {
 
int search(int alpha, int beta, ...) {
Line 92: Line 92:
 
. . . . . . . .  flood  b b b b b b b b
 
. . . . . . . .  flood  b b b b b b b b
 
</pre>
 
</pre>
More complicated cases for a successful blockage detection also with levers involved are elaborated in [[Omid David|Omid David's]] et al. 2004 [[ICGA Journal]] paper <ref>[[Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''Blockage Detection in Pawn Endgames''. [[ICGA Journal]], Vol. 27, No. 3</ref>, also published as code of [[Chiron]] by [[Ubaldo Andrea Farina]] in [[CCC]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=40748 Code of Chiron for Detection of Pawn Blockages] by [[Ubaldo Andrea Farina]], [[CCC]], October 13, 2011</ref>.
+
More complicated cases for a successful blockage detection also with levers involved are elaborated in [[Eli David|Omid David's]] et al. 2004 [[ICGA Journal]] paper <ref>[[Eli David|Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''Blockage Detection in Pawn Endgames''. [[ICGA Journal]], Vol. 27, No. 3</ref>, also published as code of [[Chiron]] by [[Ubaldo Andrea Farina]] in [[CCC]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=40748 Code of Chiron for Detection of Pawn Blockages] by [[Ubaldo Andrea Farina]], [[CCC]], October 13, 2011</ref>.
  
 
=See also=
 
=See also=
 +
* [[Arthur#Computer Judgment|Computer Judgment]]
 
* [[Corresponding Squares]]
 
* [[Corresponding Squares]]
 
* [[Draw Evaluation]]
 
* [[Draw Evaluation]]
Line 105: Line 106:
 
=Publications=
 
=Publications=
 
* [[Peter W. Frey]], [[Larry Atkin]] ('''1979'''). ''[https://archive.org/stream/byte-magazine-1979-01/1979_01_BYTE_04-01_Life_Algorithms#page/n127/mode/2up Creating a Chess-Player, Part 4: Thoughts on Strategy]''. In [http://cs.millersville.edu/~liffick/ Blaise W. Liffick] (ed.), [http://books.google.com/books/about/The_BYTE_book_of_Pascal.html?id=ofpfQgAACAAJ The Byte Book of Pascal], pp. 143-155. Byte Publications, also [[Byte Magazine#BYTE401|BYTE, Vol. 4, No. 1]]
 
* [[Peter W. Frey]], [[Larry Atkin]] ('''1979'''). ''[https://archive.org/stream/byte-magazine-1979-01/1979_01_BYTE_04-01_Life_Algorithms#page/n127/mode/2up Creating a Chess-Player, Part 4: Thoughts on Strategy]''. In [http://cs.millersville.edu/~liffick/ Blaise W. Liffick] (ed.), [http://books.google.com/books/about/The_BYTE_book_of_Pascal.html?id=ofpfQgAACAAJ The Byte Book of Pascal], pp. 143-155. Byte Publications, also [[Byte Magazine#BYTE401|BYTE, Vol. 4, No. 1]]
* [[Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_13 Blockage Detection in Pawn Endings]''. [[CG 2004]], [http://www.ise.bgu.ac.il/faculty/felner/newsite/publications/blockage.pdf pdf]
+
* [[Walter Ravenek]] ('''1995'''). ''Computer Judgment''. [[Computer Chess Reports]], Vol. 5, Nos. 3+4, pp. 124 » [[Arthur#Computer Judgment|Computer Judgment]]
* [[Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''Blockage Detection in Pawn Endgames''. [[ICGA Journal#27_3|ICGA Journal, Vol. 27, No. 3]]
+
* [[Eli David|Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_13 Blockage Detection in Pawn Endings]''. [[CG 2004]], [http://www.ise.bgu.ac.il/faculty/felner/newsite/publications/blockage.pdf pdf]
 +
* [[Eli David|Omid David]], [[Ariel Felner]], [[Nathan S. Netanyahu]] ('''2004'''). ''Blockage Detection in Pawn Endgames''. [[ICGA Journal#27_3|ICGA Journal, Vol. 27, No. 3]]
  
 
=Forum Posts=
 
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=269253 Endgame Blockage Positions] by [[Omid David]], [[CCC]], December 06, 2002
+
* [https://groups.google.com/d/msg/rec.games.chess.computer/DIrf0yWFh-c/hwz26K3gqHAJ Re: Computer Judgment] by [[Walter Ravenek]], [[Computer Chess Forums|rgcc]], October 25, 1995 » [[Arthur#Computer Judgment|Computer Judgment]]
 +
* [https://www.stmintz.com/ccc/index.php?id=269253 Endgame Blockage Positions] by [[Eli David|Omid David]], [[CCC]], December 06, 2002
 
* [https://www.stmintz.com/ccc/index.php?id=423308 Jeremiah's Wall Detection] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 28, 2005
 
* [https://www.stmintz.com/ccc/index.php?id=423308 Jeremiah's Wall Detection] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 28, 2005
 
* [http://www.talkchess.com/forum/viewtopic.php?t=40748 Code of Chiron for Detection of Pawn Blockages] by [[Ubaldo Andrea Farina]], [[CCC]], October 13, 2011
 
* [http://www.talkchess.com/forum/viewtopic.php?t=40748 Code of Chiron for Detection of Pawn Blockages] by [[Ubaldo Andrea Farina]], [[CCC]], October 13, 2011
Line 117: Line 120:
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Pattern Recognition|Up one level]]'''
 
'''[[Pattern Recognition|Up one level]]'''

Revision as of 11:37, 3 February 2019

Home * Knowledge * Pattern Recognition * Blockage Detection

Blockage Detection,

a pattern recognition technique to statically discover rammed positions in pawn endgames, and permanently prevented kings from penetrating into opponent's camp. In those positions material advantage is not sufficient to win such games, otherwise only recognizably by a very deep search, when a draw by fifty-move rule rises the horizon. Best not only applied in leaf node evaluation, but as interior node recognizer within the search, a detected blockade either prunes forward or narrows the search window.

    
    
    
    
    
    
    
    
       
        
     
    
      
       
       
        
    ♚   
        
   ♟♙♟  
 ♟ ♙ ♙ ♟
 ♙     ♙
     ♙  
   ♔    
        

Search Application

Blockage detection is only applied for the side with advantage, proving its upper bound is a draw score [1]:

int search(int alpha, int beta, ...) {
  ...
  /* blockade detection */
  if ( beta > DRAW_SCORE ) {
    if ( blockage() ) {
      if ( alpha >= DRAW_SCORE )
        return DRAW_SCORE;
      beta = DRAW_SCORE; 
    }    
  }
  /* continue regular search */
}

Ram Fence

Following sample assumes White the "winning" side to move

The blockage requires a fence consisting of own fixed pawns and opponent pawn attacks, to divide the board into two disconnected regions. There are various algorithms to deal with fence detection, and fixed and dynamic pawns, following fill based proposal deals with bitboards and should only take none lever pawns into account to prove the fence is impenetrable. First cheap condition is the presence of at least three rams. Further own pawns blocked by own rams are included successively into the fence set, and finally opponent pawn attacks. The precondition, the defending king has at least one vacant square to avoid zugzwang issues, is omitted.

A king flood starts at its base rank (1st rank for White) over the board (ignoring black passers on the 2rd rank), or all bits below the fence' least significant one bit, the potential fence as flood stopping obstruction. If, after a few cycles, the flood reaches the above area, the fence is penetrable, and the blockage test failed. Each time, the king flood drowns (undefended) opponent pawns, the ram-fence is re-calculated with the drown pawns "captured". If the flood does not grow anymore, the fence is detected.

see One Step, Population Count and BitScan

bool forms_fence4white(U64 wPawns, U64 bPawns, U64 &fence, U64 &flood) {
  fence = wPawns & soutOne( bPawns ); 
  if (popCount( fence ) < 3)
    return false;
  fence |= wPawns & soutOne( fence );
  fence |= wPawns & soutOne( fence );
  fence |= wPawns & soutOne( fence );
  fence |= wPawns & soutOne( fence );
  fence |= bPawnAttacks( bPawns );
  flood = RANK1BB | allBitsBelow[BitScanForward( fence )];
  U64 above = allBitsAbove[BitScanReverse( fence )];
  while ( true ) {
    U64 temp = flood;
    flood |= eastOne( flood ) | westOne( flood ); /* Set all 8 neighbors */
    flood |= soutOne( flood ) | nortOne( flood );
    flood &= ~fence;
    if (flood == temp) 
      break; /* Fill has stopped, blockage? */
    if (flood & above) /* break through? */
      return false; /* yes, no blockage */
    if (flood & bPawns) {
      bPawns &= ~flood;  /* "capture" undefended black pawns */
      fence = wPawns & soutOne( bPawns ); 
      if (popCount( fence ) < 3)
        return false;
      fence |= wPawns & soutOne( fence );
      fence |= wPawns & soutOne( fence );
      fence |= wPawns & soutOne( fence );
      fence |= wPawns & soutOne( fence );
      fence |= bPawnAttacks( bPawns );
    }
  } 
  return true;
}

In order to ensure that White cannot penetrate the fence, the white kings must reside in the below flood set, and the defending, black king outside the below set. If all pawns of the "winning" side are rammed without any lever, the most obvious case of a blockage is recognized.

. . . k . . . .         a a a a a a a a
. . . . . . . .  above  a a a a a a a a
. . . . . . . .         a a a a a a a a
. b . . b . . b         a a a a a a a a
. w . . w . . w  fence  F_F_F_F_F_F_F_F
. w . . . . . .         b f b b b b b b
. . . K . . . .  below  b b b b b b b b
. . . . . . . .  flood  b b b b b b b b

Blockage with Dynamic Pawns

Otherwise, one has to consider dynamic pawns of the "winning" side, able to push forward or to capture, in particular above the fence, as member of the fence (levers) and below the fence (from White's point of view). For instance, one (protected) passed pawn, with the defending king on its front span, is not sufficient to break the blockage. Similar holds for pawns below the fence not able to lever, and becoming rammed if moving forward, or with some care, most backward pawns.

. . . . k . . .         a a a a a a a a
. . . . . . . .  above  a a a a a a a a
. . . b w b . .         a a a a a a a a
. b . w . w . b         a a F_F_F_F_F a
. w . . . . . w  fence  F_F_F b b b F_F
. . . . . w . .         b b b b b b b b
. . . K . . . .  below  b b b b b b b b
. . . . . . . .  flood  b b b b b b b b

More complicated cases for a successful blockage detection also with levers involved are elaborated in Omid David's et al. 2004 ICGA Journal paper [2], also published as code of Chiron by Ubaldo Andrea Farina in CCC [3].

See also

Publications

Forum Posts

References

Up one level