PawnKing

From Chessprogramming wiki

Home *Engines * PawnKing

Paul Klee - Collection of figurines, 1926^[1]

PawnKing,
aknowledge based chess program byHelmut Horacek for the domain ofpawn endgames. PawnKing was written inPascal and subject of research in Horacek's Ph.D. thesis, co-supervised byWilhelm Barth fromVienna University of Technology andCurt Christian fromUniversity of Vienna^[2]. Patterns serve to recognize important positional components in a given position, and the presence of several configurations of positional elements suggests application ofevaluation and appropriate plans selecting useful moves to besearched.

Pattern Matching

A pattern is composed of three boards, afixed-board, anot-board, and avariable-board. In the pawn endgame, aquad-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.

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;}

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 bothpassed andprotected. However, instead of such generalized pattern matching, it seems appropriate to predetermine set-wise instances ofpassed pawns,candidates,backward pawns etc. with the help ofpawn- andattack 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 aspassed pawns,candidate pawns,weak pawns andlevers inside apartial evaluation. The basic elements building up a partial evaluation aredistances between pairs of squares which are referenced by the identities created by the patten match. A well defined set of distance types is available,rank,file, diagonal,pawn path andking path distance. A so calledsensitive value expresses to what extend the most important distance values may change without hurting the successful check of the conditions. Agoal 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 theglobal 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 likeunclear,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 adepth-first alpha-beta minimax search withoutiterations. Except core restrictions, adepth limit is not applied.Move ordering considerspromotions,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 atable, so when it arises again due to atransposition, 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.

Publications

Helmut Horacek (1982).Ein Modell für Schachbauernendspiele mit menschlichen Problemlösungstechniken. Ph.D. thesis, Department of Computer Science,University of Vienna, supervisorsCurt Christian (University of Vienna) andWilhelm 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.ICCA Journal, Vol. 6, No. 3
David E. Welsh,Boris Baczynskyj (1985).Computer Chess II. William C Brown Publications, ISBN-13: 978-0697099112^[3]^[4]