25,161
edits
Changes
Created page with "'''Home * Evaluation * Game Phases * Endgame * Pawn Endgame * Blockage Detection''' {| |- style="vertical-align:top;" | rowspan="2" | '''Blockag..."
'''[[Main Page|Home]] * [[Evaluation]] * [[Game Phases]] * [[Endgame]] * [[Pawn Endgame]] * Blockage Detection'''
{|
|- style="vertical-align:top;"
| rowspan="2" | '''Blockage Detection''',<br/>
a [[Pattern Recognition|pattern recognition]] technique to statically discover [[Pawn Rams (Bitboards)|rammed positions]] in [[Pawn Endgame|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|search]], when a [[Draw|draw]] by [[Fifty-move Rule|fifty-move rule]] rises the horizon. Best not only applied in [[Leaf Node|leaf node]] [[Evaluation|evaluation]], but as [[Interior Node Recognizer|interior node recognizer]] within the [[Search|search]], a detected blockade either [[Pruning|prunes]] forward or narrows the [[Window|search window]].
| <fentt border="double" style="font-size:24pt">4k3/8/3pPp2/1p1P1P1p/1P5P/5P2/3K4/8</fentt>
|- 4k3/8/3pPp2/1p1P1P1p/1P5P/5P2/3K4/8 w - -
|}
=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>:
<pre>
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 */
}
</pre>
=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 (Bitboards)|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 Algorithms|fill based]] proposal deals with [[Bitboards|bitboards]] and should only take none [[Pawn Levers (Bitboards)|lever pawns]] into account to prove the fence is impenetrable. First cheap condition is the presence of at least three [[Pawn Rams (Bitboards)|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|zugzwang]] issues, is omitted.
A [[King Pattern#FloodFillAlgorithms|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' [[General Setwise Operations#LS1BSeparation|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 [[General Setwise Operations#OneStepOnly|One Step]], [[Population Count]] and [[BitScan]]''
<pre>
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;
}
</pre>
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 [[Pawn Levers (Bitboards)|lever]], the most obvious case of a blockage is recognized.
<pre>
. . . 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
</pre>
=Blockage with Dynamic Pawns=
Otherwise, one has to consider dynamic pawns of the "winning" side, able to [[Pawn Push|push forward]] or to [[Captures|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|protected]]) [[Passed Pawn|passed pawn]], with the defending king on its [[Pawn Spans|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 Pawn|backward pawns]].
<pre>
. . . . 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
</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>.
=See also=
* [[Corresponding Squares]]
* [[Draw Evaluation]]
* [[King Pattern#FloodFillAlgorithms|Flood Fill Algorithm]]
* [[Fortress]]
* [[Interior Node Recognizer]]
* [[Pattern Recognition]]
* [[Chunking]]
=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]]
* [[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]
* [[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=
* [https://www.stmintz.com/ccc/index.php?id=269253 Endgame Blockage Positions] by [[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
* [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=41740 To users of Chiron] by [[Richard Vida]], [[CCC]], January 02, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=42385&start=16 Details about Critter 1.4a.] by [[Jesús Muñoz]], [[CCC]], February 10, 2012 » [[Critter]]
=References=
<references />
'''[[Pawn Endgame|Up one level]]'''
{|
|- style="vertical-align:top;"
| rowspan="2" | '''Blockage Detection''',<br/>
a [[Pattern Recognition|pattern recognition]] technique to statically discover [[Pawn Rams (Bitboards)|rammed positions]] in [[Pawn Endgame|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|search]], when a [[Draw|draw]] by [[Fifty-move Rule|fifty-move rule]] rises the horizon. Best not only applied in [[Leaf Node|leaf node]] [[Evaluation|evaluation]], but as [[Interior Node Recognizer|interior node recognizer]] within the [[Search|search]], a detected blockade either [[Pruning|prunes]] forward or narrows the [[Window|search window]].
| <fentt border="double" style="font-size:24pt">4k3/8/3pPp2/1p1P1P1p/1P5P/5P2/3K4/8</fentt>
|- 4k3/8/3pPp2/1p1P1P1p/1P5P/5P2/3K4/8 w - -
|}
=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>:
<pre>
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 */
}
</pre>
=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 (Bitboards)|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 Algorithms|fill based]] proposal deals with [[Bitboards|bitboards]] and should only take none [[Pawn Levers (Bitboards)|lever pawns]] into account to prove the fence is impenetrable. First cheap condition is the presence of at least three [[Pawn Rams (Bitboards)|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|zugzwang]] issues, is omitted.
A [[King Pattern#FloodFillAlgorithms|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' [[General Setwise Operations#LS1BSeparation|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 [[General Setwise Operations#OneStepOnly|One Step]], [[Population Count]] and [[BitScan]]''
<pre>
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;
}
</pre>
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 [[Pawn Levers (Bitboards)|lever]], the most obvious case of a blockage is recognized.
<pre>
. . . 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
</pre>
=Blockage with Dynamic Pawns=
Otherwise, one has to consider dynamic pawns of the "winning" side, able to [[Pawn Push|push forward]] or to [[Captures|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|protected]]) [[Passed Pawn|passed pawn]], with the defending king on its [[Pawn Spans|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 Pawn|backward pawns]].
<pre>
. . . . 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
</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>.
=See also=
* [[Corresponding Squares]]
* [[Draw Evaluation]]
* [[King Pattern#FloodFillAlgorithms|Flood Fill Algorithm]]
* [[Fortress]]
* [[Interior Node Recognizer]]
* [[Pattern Recognition]]
* [[Chunking]]
=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]]
* [[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]
* [[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=
* [https://www.stmintz.com/ccc/index.php?id=269253 Endgame Blockage Positions] by [[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
* [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=41740 To users of Chiron] by [[Richard Vida]], [[CCC]], January 02, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=42385&start=16 Details about Critter 1.4a.] by [[Jesús Muñoz]], [[CCC]], February 10, 2012 » [[Critter]]
=References=
<references />
'''[[Pawn Endgame|Up one level]]'''
