Guard Heuristic
Home * Search * Move Ordering * Guard Heuristic
Guard Heuristic,
a move ordering and pruning heuristic introduced by Yi-Fan Ke and Tai-Ming Parng in the 1993 ICCA Journal, Vol. 16, No. 2 [2] . The guard heuristic was successfully applied in chinese chess and compared with the other heuristics such as the 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 [3] , utilizing the 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 square, and considers those values not only for target squares but also for origin squares of moves to decide whether the move is searched at all, with a reduced depth, or when.
Contents
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, 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
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;
}
Capture Strength
Chess
| King | Queen | Rook | Bishop | Knight | Pawn | |
|---|---|---|---|---|---|---|
| White | +1 | +1 | +2 | +5 | +6 | +9 |
| Black | -1 | -1 | -2 | -5 | -6 | -9 |
Chinese Chess
| General | Guard | Elephant | Warrior | Horse | Cannon | Soldier | |
|---|---|---|---|---|---|---|---|
| White | +1 | +9 | +9 | +2 | +5 | +4 | +9 |
| Black | -1 | -9 | -9 | -2 | -5 | -4 | -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. ICCA Journal, Vol. 16, No. 2
- Mei-En Chen, Yo-Ping Huang (1995). Guard heuristic by dynamic fuzzy reasoning model for Chinese chess. Proceedings of ISUMA-NAFIPS '95
Forum Posts
- Bonus for "null move SEE" by Matthew Lai, CCC, August 23, 2015
External Links
- Guard from Wikipedia
- John McLaughlin and Jonas Hellborg - Guardian Angel - You Know You Know, Fabrik Hamburg, February 19, 1987, YouTube Video
References
- ↑ Point guards Bob Cousy (left) and Bob McNeill (center) chase after the ball. Cousy won six NBA championships with the Boston Celtics, Description: "Life in the old Cousy yet", New York World-Telegram & Sun photo by Wm. C. Greene, 1960, Library of Congress, Prints and Photographs Division, Point guard from Wikipedia, Wikimedia Commons
- ↑ Yi-Fan Ke, Tai-Ming Parng (1993). The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning. ICCA Journal, Vol. 16, No. 2
- ↑ Carl Ebeling (1986). All the Right Moves: A VLSI Architecture for Chess. Ph.D. thesis, Carnegie Mellon University, MIT Press
