25,161
edits
Changes
Created page with "'''Home * Engines * Peasant''' FILE:Unbekannter Meister 18-19 Jh Feiernde Bauern.jpg|border|right|thumb| Celebrating Peasants <ref>[http://commons.wikimed..."
'''[[Main Page|Home]] * [[Engines]] * Peasant'''
[[FILE:Unbekannter Meister 18-19 Jh Feiernde Bauern.jpg|border|right|thumb| Celebrating Peasants <ref>[http://commons.wikimedia.org/wiki/File:Unbekannter_Meister_18-19_Jh_Feiernde_Bauern.jpg Celebrating Peasants], artist unknown, 18th or 19th century, [http://www.duesseldorfer-auktionshaus.de/en/welcome/index Duesseldorfer Auktionshaus], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Peasant''',<br/>
a [[Pawn Endgame|pawn endgame]] chess program written by [[Monroe Newborn]] as research project started in 1973 at [https://en.wikipedia.org/wiki/Technion_%E2%80%93_Israel_Institute_of_Technology Technion], [https://en.wikipedia.org/wiki/Haifa Haifa], Israel, where the author had a visiting appointment. The goal was to examine whether the poor endgame play of the chess programs of that time was due to a basic weakness of [[Minimax|minimax]] as suggested by [[Larry Harris]] <ref>[[Larry Harris]] ('''1977'''). ''The heuristic search: An alternative to the alpha-beta minimax procedure.'' [[Chess Skill in Man and Machine]]</ref>, or simply because of [[Evaluation|evaluation functions]] used were not intended for those endings.
=Description=
Supported by [[Israel Gold]] at Technion, and later by [https://en.wikipedia.org/wiki/FIDE_titles#International_Master_.28IM.29 International Master] [[Leon Piasetski]] at [[McGill University]], Peasant was implemented as conventional fixed [[Depth|depth]] [[Alpha-Beta|alpha-beta]] searcher with evaluation and [[Pruning|pruning]] heuristics tailored for pawn endings, using an [[8x8 Board|8x8 board]] array as internal representation. [[Moves]] were [[Move Ordering|sorted]] so that [[Captures|captures]] and promotions came first - the [[Killer Heuristic|killer heuristic]] was used to further improve the effectiveness of alpha-beta. The ONEPAWN algorithm by Newborn and Piasetski evaluated [[KPK]] positions, TWOPAWN by Piasetski, KPPK. Peasant employed forward pruning of many king moves near the tips, reaching a search depth of around 10 [[Ply|ply]] with 3 or 4 pawns. Written in [[Fortran|Fortran IV]] for the [[IBM 360]]/[[IBM 370|370]], it searched around 18,000 [[Terminal Node|terminal positions]] per minute on a 370/158 <ref>[[Monroe Newborn]] ('''1977'''). ''PEASANT: An endgame program for kings and pawns''. [[Chess Skill in Man and Machine]]</ref>.
In his 1978 B.Sc. thesis on [[Corresponding Squares|co-ordinate squares]] in pawn endings, reprinted 1988 in [[David Levy|David Levy's]] [[Computer Chess Compendium]], [[Kenneth W. Church]] mentions the [[Lasker-Reichhelm Position]] (Fine #70) and Newborn's assessment solving it with Peasant would require 25,000 hours, and further gives a description of Peasant in a leading footnote <ref>[[Kenneth W. Church]] ('''1978'''). ''[http://dl.acm.org/citation.cfm?id=67030 Co-ordinate Squares: A Solution to Many Chess Pawn Endgames]''. B.Sc. thesis, [[Massachusetts Institute of Technology]], advisor [[Richard Greenblatt]], reprinted 1988 in [[Computer Chess Compendium]]</ref>. Following list of terminal node conditions and static [[Evaluation|evaluation]] features are based on Church's note.
==Terminal Nodes==
A position is defined to be a [[Terminal Node|terminal node]] if one of the following conditions holds:
# The maximum preset [[Depth|depth]] is met
# One side has one or two pawns and the other has none (special static evaluator).
# There is a queen on the board and the last move was not a promotion.
# There is a [[Passed Pawn|passed pawn]] which [[Unstoppable Passer|cannot be caught by the enemy king]] and can [[Pawn Race|outrace]] all enemy pawns with a move to spare.
# The depth is equal to that of a node where a win can be guaranteed. (This appears to be a special case of alpha-beta.)
# The same position has occurred previously at the same depth in the [[Tree|tree]] <ref>[[Kenneth W. Church]] in his Co-ordinate Squares footnote on Peasant: "most serious design error is that rule six is too weak. A better condition is to terminate if the position has been reached in the tree search at any depth. Especially in these endgames, this is a very serious error"</ref>.
# [[Stalemate]]
# The position is equivalent to a parent position which occurs four plies higher in the tree.
# The winning side allows [[Draw|draw]] by [[Repetitions|repetition]]
==Evaluator==
The static Evaluator is:
: ''<span style="font-size: 120%;">10*MAT + 5*PP - PRO + K<span style="vertical-align: sub;">1</span> + K<span style="vertical-align: sub;">2</span> + R</span>''
with
* MAT ≡ the difference between the number of white pieces and the number of black pieces
* PP ≡ the difference between the number of white [[Passed Pawn|passed pawns]] and the number of black passed pawns
* PRO ≡ the number of moves the most advanced white pawn must take before promotion minus the number of moves for the most advanced black pawn
* K<span style="font-size: 70%;vertical-align: sub;">1</span> ≡ factor measuring [[King Pawn Tropism|king distance from the pawns]]: five points deducted for every space that separates the king from the "center of gravity" of the pawns
* K<span style="font-size: 70%;vertical-align: sub;">2</span> ≡ three points if the king has [[Opposition|opposition]]
* R ≡ ten points times the rank of each pawn that is passed and [[Unstoppable Passer|cannot be stopped]] by the defending king
=Modified Rules=
The [[Rules of Chess|rules of chess]] were modified in a way, that only [[Promotions|promotions]] to a [[Queen|queen]] were possible, and to avoid later queen moves, the [[Side to move|side to move]] had a win if one queen ahead and a draw if both sides had same number of queens (> 0), and no queening actually possible.
=See also=
* [[Chunker]]
* [[PawnKing]]
=Publications=
* [[Monroe Newborn]] ('''1977'''). ''PEASANT: An endgame program for kings and pawns''. [[Chess Skill in Man and Machine]]
* [[Monroe Newborn]], [[Robert Hyatt]] ('''2014'''). ''Computer Chess Endgame Play with Pawns: Then and Now''. [[ICGA Journal#37_4|ICGA Journal, Vol. 37, No. 4]] » [[Crafty]]
=External Links=
* [https://en.wikipedia.org/wiki/Peasant Peasant from Wikipedia]
* [https://en.wikipedia.org/wiki/Peasant_%28disambiguation%29 Peasant (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Peasant_movement Peasant movement from Wikipedia]
* [https://en.wikipedia.org/wiki/Peasants%27_Party Peasants' Party from Wikipedia]
: [https://en.wikipedia.org/wiki/Via_Campesina Via Campesina from Wikipedia]
* [https://en.wikipedia.org/wiki/Peasants%27_Revolt Peasants' Revolt from Wikipedia]
: [https://en.wikipedia.org/wiki/List_of_peasant_revolts List of peasant revolts from Wikipedia]
=References=
<references />
'''[[Engines|Up one Level]]'''
[[FILE:Unbekannter Meister 18-19 Jh Feiernde Bauern.jpg|border|right|thumb| Celebrating Peasants <ref>[http://commons.wikimedia.org/wiki/File:Unbekannter_Meister_18-19_Jh_Feiernde_Bauern.jpg Celebrating Peasants], artist unknown, 18th or 19th century, [http://www.duesseldorfer-auktionshaus.de/en/welcome/index Duesseldorfer Auktionshaus], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Peasant''',<br/>
a [[Pawn Endgame|pawn endgame]] chess program written by [[Monroe Newborn]] as research project started in 1973 at [https://en.wikipedia.org/wiki/Technion_%E2%80%93_Israel_Institute_of_Technology Technion], [https://en.wikipedia.org/wiki/Haifa Haifa], Israel, where the author had a visiting appointment. The goal was to examine whether the poor endgame play of the chess programs of that time was due to a basic weakness of [[Minimax|minimax]] as suggested by [[Larry Harris]] <ref>[[Larry Harris]] ('''1977'''). ''The heuristic search: An alternative to the alpha-beta minimax procedure.'' [[Chess Skill in Man and Machine]]</ref>, or simply because of [[Evaluation|evaluation functions]] used were not intended for those endings.
=Description=
Supported by [[Israel Gold]] at Technion, and later by [https://en.wikipedia.org/wiki/FIDE_titles#International_Master_.28IM.29 International Master] [[Leon Piasetski]] at [[McGill University]], Peasant was implemented as conventional fixed [[Depth|depth]] [[Alpha-Beta|alpha-beta]] searcher with evaluation and [[Pruning|pruning]] heuristics tailored for pawn endings, using an [[8x8 Board|8x8 board]] array as internal representation. [[Moves]] were [[Move Ordering|sorted]] so that [[Captures|captures]] and promotions came first - the [[Killer Heuristic|killer heuristic]] was used to further improve the effectiveness of alpha-beta. The ONEPAWN algorithm by Newborn and Piasetski evaluated [[KPK]] positions, TWOPAWN by Piasetski, KPPK. Peasant employed forward pruning of many king moves near the tips, reaching a search depth of around 10 [[Ply|ply]] with 3 or 4 pawns. Written in [[Fortran|Fortran IV]] for the [[IBM 360]]/[[IBM 370|370]], it searched around 18,000 [[Terminal Node|terminal positions]] per minute on a 370/158 <ref>[[Monroe Newborn]] ('''1977'''). ''PEASANT: An endgame program for kings and pawns''. [[Chess Skill in Man and Machine]]</ref>.
In his 1978 B.Sc. thesis on [[Corresponding Squares|co-ordinate squares]] in pawn endings, reprinted 1988 in [[David Levy|David Levy's]] [[Computer Chess Compendium]], [[Kenneth W. Church]] mentions the [[Lasker-Reichhelm Position]] (Fine #70) and Newborn's assessment solving it with Peasant would require 25,000 hours, and further gives a description of Peasant in a leading footnote <ref>[[Kenneth W. Church]] ('''1978'''). ''[http://dl.acm.org/citation.cfm?id=67030 Co-ordinate Squares: A Solution to Many Chess Pawn Endgames]''. B.Sc. thesis, [[Massachusetts Institute of Technology]], advisor [[Richard Greenblatt]], reprinted 1988 in [[Computer Chess Compendium]]</ref>. Following list of terminal node conditions and static [[Evaluation|evaluation]] features are based on Church's note.
==Terminal Nodes==
A position is defined to be a [[Terminal Node|terminal node]] if one of the following conditions holds:
# The maximum preset [[Depth|depth]] is met
# One side has one or two pawns and the other has none (special static evaluator).
# There is a queen on the board and the last move was not a promotion.
# There is a [[Passed Pawn|passed pawn]] which [[Unstoppable Passer|cannot be caught by the enemy king]] and can [[Pawn Race|outrace]] all enemy pawns with a move to spare.
# The depth is equal to that of a node where a win can be guaranteed. (This appears to be a special case of alpha-beta.)
# The same position has occurred previously at the same depth in the [[Tree|tree]] <ref>[[Kenneth W. Church]] in his Co-ordinate Squares footnote on Peasant: "most serious design error is that rule six is too weak. A better condition is to terminate if the position has been reached in the tree search at any depth. Especially in these endgames, this is a very serious error"</ref>.
# [[Stalemate]]
# The position is equivalent to a parent position which occurs four plies higher in the tree.
# The winning side allows [[Draw|draw]] by [[Repetitions|repetition]]
==Evaluator==
The static Evaluator is:
: ''<span style="font-size: 120%;">10*MAT + 5*PP - PRO + K<span style="vertical-align: sub;">1</span> + K<span style="vertical-align: sub;">2</span> + R</span>''
with
* MAT ≡ the difference between the number of white pieces and the number of black pieces
* PP ≡ the difference between the number of white [[Passed Pawn|passed pawns]] and the number of black passed pawns
* PRO ≡ the number of moves the most advanced white pawn must take before promotion minus the number of moves for the most advanced black pawn
* K<span style="font-size: 70%;vertical-align: sub;">1</span> ≡ factor measuring [[King Pawn Tropism|king distance from the pawns]]: five points deducted for every space that separates the king from the "center of gravity" of the pawns
* K<span style="font-size: 70%;vertical-align: sub;">2</span> ≡ three points if the king has [[Opposition|opposition]]
* R ≡ ten points times the rank of each pawn that is passed and [[Unstoppable Passer|cannot be stopped]] by the defending king
=Modified Rules=
The [[Rules of Chess|rules of chess]] were modified in a way, that only [[Promotions|promotions]] to a [[Queen|queen]] were possible, and to avoid later queen moves, the [[Side to move|side to move]] had a win if one queen ahead and a draw if both sides had same number of queens (> 0), and no queening actually possible.
=See also=
* [[Chunker]]
* [[PawnKing]]
=Publications=
* [[Monroe Newborn]] ('''1977'''). ''PEASANT: An endgame program for kings and pawns''. [[Chess Skill in Man and Machine]]
* [[Monroe Newborn]], [[Robert Hyatt]] ('''2014'''). ''Computer Chess Endgame Play with Pawns: Then and Now''. [[ICGA Journal#37_4|ICGA Journal, Vol. 37, No. 4]] » [[Crafty]]
=External Links=
* [https://en.wikipedia.org/wiki/Peasant Peasant from Wikipedia]
* [https://en.wikipedia.org/wiki/Peasant_%28disambiguation%29 Peasant (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Peasant_movement Peasant movement from Wikipedia]
* [https://en.wikipedia.org/wiki/Peasants%27_Party Peasants' Party from Wikipedia]
: [https://en.wikipedia.org/wiki/Via_Campesina Via Campesina from Wikipedia]
* [https://en.wikipedia.org/wiki/Peasants%27_Revolt Peasants' Revolt from Wikipedia]
: [https://en.wikipedia.org/wiki/List_of_peasant_revolts List of peasant revolts from Wikipedia]
=References=
<references />
'''[[Engines|Up one Level]]'''
