25,161
edits
Changes
Created page with "'''Home * Search * Move Ordering * Guard Heuristic''' FILE:Bob Cousy NYWTS.jpg|border|right|thumb|Point guard <ref>Point guards [https://en.wikipedia...."
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Guard Heuristic'''
[[FILE:Bob Cousy NYWTS.jpg|border|right|thumb|Point guard <ref>Point guards [https://en.wikipedia.org/wiki/Bob_Cousy Bob Cousy] (left) and [https://en.wikipedia.org/wiki/Bob_McNeill Bob McNeill] (center) chase after the ball. Cousy won six [https://en.wikipedia.org/wiki/National_Basketball_Association NBA] championships with the [https://en.wikipedia.org/wiki/Boston_Celtics Boston Celtics], Description: "[http://www.loc.gov/pictures/item/94505330/ Life in the old Cousy yet]", [https://en.wikipedia.org/wiki/New_York_World-Telegram New York World-Telegram & Sun] photo by Wm. C. Greene, 1960, [https://en.wikipedia.org/wiki/Library_of_Congress Library of Congress], Prints and Photographs Division, [https://en.wikipedia.org/wiki/Point_guard Point guard from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Guard Heuristic''',<br/>
a move ordering and [[Pruning|pruning]] heuristic introduced by [[Yi-Fan Ke]] and [[Tai-Ming Parng]] in the 1993 [[ICGA Journal#16_2|ICCA Journal, Vol. 16, No. 2]] <ref>[[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1993'''). ''The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning''. [[ICGA Journal#16_2|ICCA Journal, Vol. 16, No. 2]]</ref> . The guard heuristic was successfully applied in [[Chinese Chess|chinese chess]] and compared with the other heuristics such as the [[Killer Heuristic|killer heuristic]], and also proposed for chess. A similar move ordering algorithm was mentioned by [[Carl Ebeling]] in his 1986 Ph.D. thesis ''All the Right Moves'' <ref>[[Carl Ebeling]] ('''1986'''). ''[http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=7692 All the Right Moves: A VLSI Architecture for Chess]''. Ph.D. thesis, [[Carnegie Mellon University]], [https://en.wikipedia.org/wiki/MIT_Press MIT Press]</ref> , utilizing the [[Point Value|value]] of the moving piece, the value of the captured piece if any, and the value of the piece and pawn guards. In contrast, the guard heuristics is based on the '''guard value''' of each [[Squares|square]], and considers those values not only for [[Target Square|target squares]] but also for [[Origin Square|origin squares]] of moves to decide whether the move is searched at all, with a [[Reductions|reduced]] [[Depth|depth]], or when.
=Guard Values=
The guard value of a square is the sum of the capture strengths (CS) of those pieces that are able to capture a potential opponent piece on that square. The capture strength of a piece is roughly inverse proportional to its [[Point Value|point value]], in white point of view metric, positive values for white and negative values for black. Further, if the square is occupied by a defended black piece, and target of a capture, the (negative) capture strength of that piece is added to the guard value as well.
==Pseudo-Code==
<pre>
int guardValueWPOV(enumSquare sq) {
isAttacked = false;
isDefended = false;
int gv = 0;
for ( all Pieces p controlling sq ) {
gv += captureStrength[p];
if ( isWhitePiece (p) )
isAttacked = true;
else
isDefended = true;
}
if ( isAttacked && isDefended ) {
p = board[sq];
if ( isBlackPiece (p) )
gv += captureStrength[p];
}
return gv;
}
</pre>
==Capture Strength==
===Chess===
{| class="wikitable"
|-
!
! King
! Queen
! Rook
! Bishop
! Knight
! Pawn
|-
! White
| style="text-align:center;" | +1
| style="text-align:center;" | +1
| style="text-align:center;" | +2
| style="text-align:center;" | +5
| style="text-align:center;" | +6
| style="text-align:center;" | +9
|-
! Black
| style="text-align:center;" | -1
| style="text-align:center;" | -1
| style="text-align:center;" | -2
| style="text-align:center;" | -5
| style="text-align:center;" | -6
| style="text-align:center;" | -9
|}
===Chinese Chess===
{| class="wikitable"
|-
!
! General
! Guard
! Elephant
! Warrior
! Horse
! Cannon
! Soldier
|-
! White
| style="text-align:center;" | +1
| style="text-align:center;" | +9
| style="text-align:center;" | +9
| style="text-align:center;" | +2
| style="text-align:center;" | +5
| style="text-align:center;" | +4
| style="text-align:center;" | +9
|-
! Black
| style="text-align:center;" | -1
| style="text-align:center;" | -9
| style="text-align:center;" | -9
| style="text-align:center;" | -2
| style="text-align:center;" | -5
| style="text-align:center;" | -4
| style="text-align:center;" | -9
|}
=Pruning and Ordering=
The guard heuristic aims at both rejecting moves at deep nodes and ordering moves to reduce the search time. Moves with unsafe target squares, that is negative guard values less some margin, are pruned near the tips and the remaining moves are ordered by the '''Escape-first-if-origin-unsafe''', giving priority for most valuable piece, and '''Capture-first-if-target-safe''' rules, considering [[MVV-LVA]].
=See also=
* [[Chessmaps Heuristic]]
* [[Killer Heuristic]]
* [[MVV-LVA]]
* [[Pruning]]
* [[Square Attacked By]]
* [[Square Control]]
* [[Static Exchange Evaluation]]
=Publications=
* [[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1993'''). ''The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning''. [[ICGA Journal#16_2|ICCA Journal, Vol. 16, No. 2]]
* [[Mei-En Chen]], [[Yo-Ping Huang]] ('''1995'''). ''[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=527751 Guard heuristic by dynamic fuzzy reasoning model for Chinese chess]''. Proceedings of ISUMA-NAFIPS '95
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=57346 Bonus for "null move SEE"] by [[Matthew Lai]], [[CCC]], August 23, 2015
=External Links=
* [https://en.wikipedia.org/wiki/Guard Guard from Wikipedia]
* [[Videos#JohnMcLaughlin|John McLaughlin]] and [[Videos#JonasHellborg|Jonas Hellborg]] - Guardian Angel - [[Knowledge#youknow|You Know You Know]], [https://en.wikipedia.org/wiki/Fabrik_%28Hamburg%29 Fabrik Hamburg], February 19, 1987, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=pe4xtKuIKB0|alignment=left|valignment=top}}
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
[[FILE:Bob Cousy NYWTS.jpg|border|right|thumb|Point guard <ref>Point guards [https://en.wikipedia.org/wiki/Bob_Cousy Bob Cousy] (left) and [https://en.wikipedia.org/wiki/Bob_McNeill Bob McNeill] (center) chase after the ball. Cousy won six [https://en.wikipedia.org/wiki/National_Basketball_Association NBA] championships with the [https://en.wikipedia.org/wiki/Boston_Celtics Boston Celtics], Description: "[http://www.loc.gov/pictures/item/94505330/ Life in the old Cousy yet]", [https://en.wikipedia.org/wiki/New_York_World-Telegram New York World-Telegram & Sun] photo by Wm. C. Greene, 1960, [https://en.wikipedia.org/wiki/Library_of_Congress Library of Congress], Prints and Photographs Division, [https://en.wikipedia.org/wiki/Point_guard Point guard from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Guard Heuristic''',<br/>
a move ordering and [[Pruning|pruning]] heuristic introduced by [[Yi-Fan Ke]] and [[Tai-Ming Parng]] in the 1993 [[ICGA Journal#16_2|ICCA Journal, Vol. 16, No. 2]] <ref>[[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1993'''). ''The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning''. [[ICGA Journal#16_2|ICCA Journal, Vol. 16, No. 2]]</ref> . The guard heuristic was successfully applied in [[Chinese Chess|chinese chess]] and compared with the other heuristics such as the [[Killer Heuristic|killer heuristic]], and also proposed for chess. A similar move ordering algorithm was mentioned by [[Carl Ebeling]] in his 1986 Ph.D. thesis ''All the Right Moves'' <ref>[[Carl Ebeling]] ('''1986'''). ''[http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=7692 All the Right Moves: A VLSI Architecture for Chess]''. Ph.D. thesis, [[Carnegie Mellon University]], [https://en.wikipedia.org/wiki/MIT_Press MIT Press]</ref> , utilizing the [[Point Value|value]] of the moving piece, the value of the captured piece if any, and the value of the piece and pawn guards. In contrast, the guard heuristics is based on the '''guard value''' of each [[Squares|square]], and considers those values not only for [[Target Square|target squares]] but also for [[Origin Square|origin squares]] of moves to decide whether the move is searched at all, with a [[Reductions|reduced]] [[Depth|depth]], or when.
=Guard Values=
The guard value of a square is the sum of the capture strengths (CS) of those pieces that are able to capture a potential opponent piece on that square. The capture strength of a piece is roughly inverse proportional to its [[Point Value|point value]], in white point of view metric, positive values for white and negative values for black. Further, if the square is occupied by a defended black piece, and target of a capture, the (negative) capture strength of that piece is added to the guard value as well.
==Pseudo-Code==
<pre>
int guardValueWPOV(enumSquare sq) {
isAttacked = false;
isDefended = false;
int gv = 0;
for ( all Pieces p controlling sq ) {
gv += captureStrength[p];
if ( isWhitePiece (p) )
isAttacked = true;
else
isDefended = true;
}
if ( isAttacked && isDefended ) {
p = board[sq];
if ( isBlackPiece (p) )
gv += captureStrength[p];
}
return gv;
}
</pre>
==Capture Strength==
===Chess===
{| class="wikitable"
|-
!
! King
! Queen
! Rook
! Bishop
! Knight
! Pawn
|-
! White
| style="text-align:center;" | +1
| style="text-align:center;" | +1
| style="text-align:center;" | +2
| style="text-align:center;" | +5
| style="text-align:center;" | +6
| style="text-align:center;" | +9
|-
! Black
| style="text-align:center;" | -1
| style="text-align:center;" | -1
| style="text-align:center;" | -2
| style="text-align:center;" | -5
| style="text-align:center;" | -6
| style="text-align:center;" | -9
|}
===Chinese Chess===
{| class="wikitable"
|-
!
! General
! Guard
! Elephant
! Warrior
! Horse
! Cannon
! Soldier
|-
! White
| style="text-align:center;" | +1
| style="text-align:center;" | +9
| style="text-align:center;" | +9
| style="text-align:center;" | +2
| style="text-align:center;" | +5
| style="text-align:center;" | +4
| style="text-align:center;" | +9
|-
! Black
| style="text-align:center;" | -1
| style="text-align:center;" | -9
| style="text-align:center;" | -9
| style="text-align:center;" | -2
| style="text-align:center;" | -5
| style="text-align:center;" | -4
| style="text-align:center;" | -9
|}
=Pruning and Ordering=
The guard heuristic aims at both rejecting moves at deep nodes and ordering moves to reduce the search time. Moves with unsafe target squares, that is negative guard values less some margin, are pruned near the tips and the remaining moves are ordered by the '''Escape-first-if-origin-unsafe''', giving priority for most valuable piece, and '''Capture-first-if-target-safe''' rules, considering [[MVV-LVA]].
=See also=
* [[Chessmaps Heuristic]]
* [[Killer Heuristic]]
* [[MVV-LVA]]
* [[Pruning]]
* [[Square Attacked By]]
* [[Square Control]]
* [[Static Exchange Evaluation]]
=Publications=
* [[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1993'''). ''The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning''. [[ICGA Journal#16_2|ICCA Journal, Vol. 16, No. 2]]
* [[Mei-En Chen]], [[Yo-Ping Huang]] ('''1995'''). ''[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=527751 Guard heuristic by dynamic fuzzy reasoning model for Chinese chess]''. Proceedings of ISUMA-NAFIPS '95
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=57346 Bonus for "null move SEE"] by [[Matthew Lai]], [[CCC]], August 23, 2015
=External Links=
* [https://en.wikipedia.org/wiki/Guard Guard from Wikipedia]
* [[Videos#JohnMcLaughlin|John McLaughlin]] and [[Videos#JonasHellborg|Jonas Hellborg]] - Guardian Angel - [[Knowledge#youknow|You Know You Know]], [https://en.wikipedia.org/wiki/Fabrik_%28Hamburg%29 Fabrik Hamburg], February 19, 1987, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=pe4xtKuIKB0|alignment=left|valignment=top}}
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
