25,161
edits
Changes
Created page with "'''Home * Engines * PawnKing''' border|right|thumb|[[Arts#Klee|Paul Klee - Collection of figurines, 1926 <ref>..."
'''[[Main Page|Home]] * [[Engines]] * PawnKing'''
[[File:NY Met klee collection figurines.JPG|border|right|thumb|[[Arts#Klee|Paul Klee]] - Collection of figurines, 1926 <ref>[[Arts#Klee|Paul Klee]] - Collection of figurines, 1926, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref>]]
'''PawnKing''',<br/>
a [[Knowledge|knowledge]] based chess program by [[Helmut Horacek]] for the domain of [[Pawn Endgame|pawn endgames]]. PawnKing was written in [[Pascal]] and subject of research in Horacek's Ph.D. thesis, co-supervised by [[Wilhelm Barth]] from [[Vienna University of Technology]] and [[Mathematician#CChristian|Curt Christian]] from [https://en.wikipedia.org/wiki/University_of_Vienna University of Vienna] <ref>[[Helmut Horacek]] ('''1982'''). ''Ein Modell für Schachbauernendspiele mit menschlichen Problemlösungstechniken''. Ph.D. thesis, Department of Computer Science, [https://en.wikipedia.org/wiki/University_of_Vienna University of Vienna], supervisors [[Mathematician#CChristian|Curt Christian]] (University of Vienna) and [[Wilhelm Barth]] ([[Vienna University of Technology]])</ref>. Patterns serve to recognize important positional components in a given position, and the presence of several configurations of positional elements suggests application of [[Evaluation|evaluation]] and appropriate plans selecting useful moves to be [[Search|searched]].
=Pattern Matching=
A pattern is composed of three boards, a '''fixed-board''', a '''not-board''', and a '''variable-board'''. In the pawn endgame, a [[Quad-Bitboards|quad-bitboard]] for pawns and kings of both sides is sufficient. For a pattern match, the fixed-board must be subset of the current board, the intersection of the current board with the not-board must be empty, with the variable-board not empty.
<pre>
bool QBB::match(const QBB & fix, const QBB & not, const QBB & var) const {
if ((*this & fix) != *this) return false;
if ((*this & not) != QBB(0)) return false;
if ((*this & var) == QBB(0)) return false;
return true;
}
</pre>
The pattern match generally is performed for both sides (with appropriate changes for the black side) as well as various parts of the board (shifting the pattern by some ranks and files). Finally, some important pawns and key squares of a successfully matched pattern are given identities for further reference by piece paths and evaluation. A square can receive several identities, e.g. a pawn can be both [[Passed Pawn|passed]] and [[Protected Passed Pawn|protected]]. However, instead of such generalized pattern matching, it seems appropriate to predetermine set-wise instances of [[Passed Pawns (Bitboards)|passed pawns]], [[Candidates (Bitboards)|candidates]], [[Backward Pawns (Bitboards)|backward pawns]] etc. with the help of [[Pawn Spans|pawn-]] and [[Attack Spans|attack spans]].
=Evaluation=
==Partial==
The knowledge discovered by patterns alone is not sufficient to obtain a value which accurately enough represents a certain positional element. Classifications are performed for all relevant positional elements, such as [[Passed Pawn|passed pawns]], [[Candidate Passed Pawn|candidate pawns]], [[Weak Pawns|weak pawns]] and [[Pawn Levers (Bitboards)|levers]] inside a '''partial''' evaluation. The basic elements building up a partial evaluation are [[Distance|distances]] between pairs of squares which are referenced by the identities created by the patten match. A well defined set of distance types is available, [[Ranks#RankDistance|rank]], [[Files#FileDistance|file]], diagonal, [[Pawn Fills|pawn path]] and [[All Shortest Paths|king path]] distance. A so called '''sensitive value''' expresses to what extend the most important distance values may change without hurting the successful check of the conditions. A '''goal distance''' represents the necessary number of moves to accomplish the goal, which is the aim of the partial evaluation. The best hierarchical values per classifications, a tuple of the conditions along with its sensitive value and goal distance, are saved for the '''global''' evaluation.
==Global==
In contradiction to conventional evaluation, PawnKing's value range consists of a few discrete values: decisive, big and slight advantage for White or Black respectively, as well as equality. To satisfy attributes like ''unclear'', ''with compensation'', and the dynamics not yet evaluable by static means, '''two''' values of that kind are included in the global value, an optimistic and a pessimistic, with a special defined set of relational operators considering average of optimistic and pessimistic value and further best hierarchical values.
=Search=
PawnKing uses a [[Depth-First|depth-first]] [[Alpha-Beta|alpha-beta]] minimax search without [[Iterative Deepening|iterations]]. Except core restrictions, a [[Depth|depth]] limit is not applied. [[Move Ordering|Move ordering]] considers [[Promotions|promotions]], [[Captures|captures]], moves protecting a hung pawn, or an evasion with such a pawn, as well as a classification, sensitivity value and goal distance which where calculated from the square the plan of the move belongs to. All created positions including their value, as well as the sensibility of the key squares all over the board, are saved in a [[Transposition Table|table]], so when it arises again due to a [[Transposition|transposition]], its value is taken directly from the table. If only the same pawn structure occurs, it is checked whether the king locations does not hurt the sensibility of any key square.
=See also=
* [[Chunker]]
* [[King Pattern]]
* [[Pawn Pattern and Properties]]
* [[Pattern Recognition]]
* [[Peasant]]
=Publications=
* [[Helmut Horacek]] ('''1982'''). ''Ein Modell für Schachbauernendspiele mit menschlichen Problemlösungstechniken''. Ph.D. thesis, Department of Computer Science, [https://en.wikipedia.org/wiki/University_of_Vienna University of Vienna], supervisors [[Mathematician#CChristian|Curt Christian]] (University of Vienna) and [[Wilhelm Barth]] ([[Vienna University of Technology]]).
* [[Helmut Horacek]] ('''1982'''). ''Construction of Planned Move Trees for Chess Pawn Endings''. Sigart Newsletter 80, pp. 163-168.
* [[Helmut Horacek]] ('''1983'''). ''Knowledge-Based Move Selection and Evaluation to Guide the Search in Chess Pawn Endings''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]
* [[David E. Welsh]], [[Boris Baczynskyj]] ('''1985'''). ''[http://www.amazon.com/Computer-Chess-II-David-Welsh/dp/0697099113 Computer Chess II]''. William C Brown Publications, ISBN-13: 978-0697099112 <ref>[https://www.stmintz.com/ccc/index.php?id=24696 PAWNKING] by José de Jesús García Ruvalcaba, [[CCC]], August 14, 1998</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=39455 An interesting book with some insights on Bob's Cray Blitz] by [[Julien Marcel]], [[CCC]], June 23, 2011</ref>
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=24696 PAWNKING] by José de Jesús García Ruvalcaba, [[CCC]], August 14, 1998
=References=
<references />
'''[[Engines|Up one Level]]'''
[[Category:Paul Klee]]
[[Category:Engine]]
[[File:NY Met klee collection figurines.JPG|border|right|thumb|[[Arts#Klee|Paul Klee]] - Collection of figurines, 1926 <ref>[[Arts#Klee|Paul Klee]] - Collection of figurines, 1926, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref>]]
'''PawnKing''',<br/>
a [[Knowledge|knowledge]] based chess program by [[Helmut Horacek]] for the domain of [[Pawn Endgame|pawn endgames]]. PawnKing was written in [[Pascal]] and subject of research in Horacek's Ph.D. thesis, co-supervised by [[Wilhelm Barth]] from [[Vienna University of Technology]] and [[Mathematician#CChristian|Curt Christian]] from [https://en.wikipedia.org/wiki/University_of_Vienna University of Vienna] <ref>[[Helmut Horacek]] ('''1982'''). ''Ein Modell für Schachbauernendspiele mit menschlichen Problemlösungstechniken''. Ph.D. thesis, Department of Computer Science, [https://en.wikipedia.org/wiki/University_of_Vienna University of Vienna], supervisors [[Mathematician#CChristian|Curt Christian]] (University of Vienna) and [[Wilhelm Barth]] ([[Vienna University of Technology]])</ref>. Patterns serve to recognize important positional components in a given position, and the presence of several configurations of positional elements suggests application of [[Evaluation|evaluation]] and appropriate plans selecting useful moves to be [[Search|searched]].
=Pattern Matching=
A pattern is composed of three boards, a '''fixed-board''', a '''not-board''', and a '''variable-board'''. In the pawn endgame, a [[Quad-Bitboards|quad-bitboard]] for pawns and kings of both sides is sufficient. For a pattern match, the fixed-board must be subset of the current board, the intersection of the current board with the not-board must be empty, with the variable-board not empty.
<pre>
bool QBB::match(const QBB & fix, const QBB & not, const QBB & var) const {
if ((*this & fix) != *this) return false;
if ((*this & not) != QBB(0)) return false;
if ((*this & var) == QBB(0)) return false;
return true;
}
</pre>
The pattern match generally is performed for both sides (with appropriate changes for the black side) as well as various parts of the board (shifting the pattern by some ranks and files). Finally, some important pawns and key squares of a successfully matched pattern are given identities for further reference by piece paths and evaluation. A square can receive several identities, e.g. a pawn can be both [[Passed Pawn|passed]] and [[Protected Passed Pawn|protected]]. However, instead of such generalized pattern matching, it seems appropriate to predetermine set-wise instances of [[Passed Pawns (Bitboards)|passed pawns]], [[Candidates (Bitboards)|candidates]], [[Backward Pawns (Bitboards)|backward pawns]] etc. with the help of [[Pawn Spans|pawn-]] and [[Attack Spans|attack spans]].
=Evaluation=
==Partial==
The knowledge discovered by patterns alone is not sufficient to obtain a value which accurately enough represents a certain positional element. Classifications are performed for all relevant positional elements, such as [[Passed Pawn|passed pawns]], [[Candidate Passed Pawn|candidate pawns]], [[Weak Pawns|weak pawns]] and [[Pawn Levers (Bitboards)|levers]] inside a '''partial''' evaluation. The basic elements building up a partial evaluation are [[Distance|distances]] between pairs of squares which are referenced by the identities created by the patten match. A well defined set of distance types is available, [[Ranks#RankDistance|rank]], [[Files#FileDistance|file]], diagonal, [[Pawn Fills|pawn path]] and [[All Shortest Paths|king path]] distance. A so called '''sensitive value''' expresses to what extend the most important distance values may change without hurting the successful check of the conditions. A '''goal distance''' represents the necessary number of moves to accomplish the goal, which is the aim of the partial evaluation. The best hierarchical values per classifications, a tuple of the conditions along with its sensitive value and goal distance, are saved for the '''global''' evaluation.
==Global==
In contradiction to conventional evaluation, PawnKing's value range consists of a few discrete values: decisive, big and slight advantage for White or Black respectively, as well as equality. To satisfy attributes like ''unclear'', ''with compensation'', and the dynamics not yet evaluable by static means, '''two''' values of that kind are included in the global value, an optimistic and a pessimistic, with a special defined set of relational operators considering average of optimistic and pessimistic value and further best hierarchical values.
=Search=
PawnKing uses a [[Depth-First|depth-first]] [[Alpha-Beta|alpha-beta]] minimax search without [[Iterative Deepening|iterations]]. Except core restrictions, a [[Depth|depth]] limit is not applied. [[Move Ordering|Move ordering]] considers [[Promotions|promotions]], [[Captures|captures]], moves protecting a hung pawn, or an evasion with such a pawn, as well as a classification, sensitivity value and goal distance which where calculated from the square the plan of the move belongs to. All created positions including their value, as well as the sensibility of the key squares all over the board, are saved in a [[Transposition Table|table]], so when it arises again due to a [[Transposition|transposition]], its value is taken directly from the table. If only the same pawn structure occurs, it is checked whether the king locations does not hurt the sensibility of any key square.
=See also=
* [[Chunker]]
* [[King Pattern]]
* [[Pawn Pattern and Properties]]
* [[Pattern Recognition]]
* [[Peasant]]
=Publications=
* [[Helmut Horacek]] ('''1982'''). ''Ein Modell für Schachbauernendspiele mit menschlichen Problemlösungstechniken''. Ph.D. thesis, Department of Computer Science, [https://en.wikipedia.org/wiki/University_of_Vienna University of Vienna], supervisors [[Mathematician#CChristian|Curt Christian]] (University of Vienna) and [[Wilhelm Barth]] ([[Vienna University of Technology]]).
* [[Helmut Horacek]] ('''1982'''). ''Construction of Planned Move Trees for Chess Pawn Endings''. Sigart Newsletter 80, pp. 163-168.
* [[Helmut Horacek]] ('''1983'''). ''Knowledge-Based Move Selection and Evaluation to Guide the Search in Chess Pawn Endings''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]
* [[David E. Welsh]], [[Boris Baczynskyj]] ('''1985'''). ''[http://www.amazon.com/Computer-Chess-II-David-Welsh/dp/0697099113 Computer Chess II]''. William C Brown Publications, ISBN-13: 978-0697099112 <ref>[https://www.stmintz.com/ccc/index.php?id=24696 PAWNKING] by José de Jesús García Ruvalcaba, [[CCC]], August 14, 1998</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=39455 An interesting book with some insights on Bob's Cray Blitz] by [[Julien Marcel]], [[CCC]], June 23, 2011</ref>
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=24696 PAWNKING] by José de Jesús García Ruvalcaba, [[CCC]], August 14, 1998
=References=
<references />
'''[[Engines|Up one Level]]'''
[[Category:Paul Klee]]
[[Category:Engine]]
