25,161
edits
Changes
Papa
,Created page with "'''Home * Engines * Papa''' [[FILE:WahineTane.jpg|border|right|thumb|200px| [https://en.wikipedia.org/wiki/Rangi_and_Papa Papa and Rangi] <ref>[https://en.w..."
'''[[Main Page|Home]] * [[Engines]] * Papa'''
[[FILE:WahineTane.jpg|border|right|thumb|200px| [https://en.wikipedia.org/wiki/Rangi_and_Papa Papa and Rangi] <ref>[https://en.wikipedia.org/wiki/M%C4%81ori_culture Maori] carving depicting a woman and a man embracing. From the pataka (food storehouse) belonging to [https://en.wikipedia.org/wiki/Te_Pokiha_Taranui Te Pokiha Taranui] of [https://en.wikipedia.org/wiki/Ng%C4%81ti_Pikiao Ngati Pikiao], [https://en.wikipedia.org/wiki/Te_Arawa Te Arawa]. The storehouse was completed in the 1870s, and stood at [https://en.wikipedia.org/wiki/Maketu Maketu], [https://en.wikipedia.org/wiki/Bay_of_Plenty Bay of Plenty], [https://en.wikipedia.org/wiki/New_Zealand New Zealand]. It is now at [https://en.wikipedia.org/wiki/Auckland_War_Memorial_Museum Auckland Museum], [https://en.wikipedia.org/wiki/Rangi_and_Papa Rangi and Papa from Wikipedia]</ref> ]]
'''Papa''',<br7>
an early computer chess program written by [[George Rajna]] and [[B. Almasi]], in the 70s affiliated with the [https://en.wikipedia.org/wiki/Hungarian_Academy_of_Sciences Hungarian Academy of Sciences]. Papa applies the concept of [[Papa#Entropy|entropy]] based on own and opponent [[Mobility#Papa|mobility]]. It participated at the [[WCCC 1974|First World Computer Chess Championship]], 1974 in [https://en.wikipedia.org/wiki/Stockholm Stockholm], unfortunately loosing all its three games due to tactical blunders. Based on preliminary results or expectations, Papa was seeded third, ahead of later winner [[Kaissa]] seeded fifth.
<span id="Entropy"></span>
=Entropy=
==Rajna==
In 2012, [[George Rajna]] has re-published a short paper on [https://en.wikipedia.org/wiki/Entropy entropy] in chess <ref>[[George Rajna]] ('''1976, 2012'''). ''Information – Entropy theory of Artificial Intelligence''. [http://vixra.org/pdf/1201.0063v1.pdf pdf]</ref>, which already appeared in ''[[WCCC 1974|The World Computer-Chess Championship]]'' by [[Jean Hayes Michie|Hayes]] and [[David Levy|Levy]] <ref>[[Jean Hayes Michie|Jean E. Hayes]], [[David Levy]] ('''1976'''). ''[http://www.getcited.org/pub/101724802 The world computer chess championship, Stockholm 1974]''. University Press (Edinburgh) ISBN 0852242859</ref>:
The basic theory on which one chess program can be constructed is that there exists a general characteristic of the game of chess, namely the concept of entropy. This concept has been employed in physics for a long time. In the case of a [https://en.wikipedia.org/wiki/Gas gas], it is the [https://en.wikipedia.org/wiki/Logarithm logarithm] of the number of those [https://en.wikipedia.org/wiki/Microstate_%28statistical_mechanics%29 microscopic states] compatible with the [https://en.wikipedia.org/wiki/Macroscopic_scale macroscopic] parameters of the gas.
What does this mean in terms of chess? A common characteristic of every [[Pieces|piece]] is that it could move to certain [[Squares|squares]], including by [[Captures|capture]]. In any given [[Chess Position|position]], therefore, the pieces by the rules of the game possess certain states, only one of which will be realized on the next move. The difference of the logarithm of the numbers of such states for Black and White respectively is the "entropy of the position". The task of the computer is then to increase this value for its own benefit.
...
Entropy is a principle of [https://en.wikipedia.org/wiki/Statistical_physics statistical physics] and therefore is only applicable in statistical contexts. The number of microstates of a confined gas is very large and therefore the statistical approach is valid. In chess, however, the number of pieces, a macroscopic parameter, is very small and therefore in this context the "value" of a position cannot be an exact function of entropy. For example, it is possible to [[Checkmate|checkmate]] with a total force of a single pawn despite the fact that the opponent has many pieces and various positions available.
==Marsland==
[[Tony Marsland]] mentioned Papa and other programs participating the [[WCCC 1974]] in his handwritten notes on the Hayes and Levy book <ref>[http://webdocs.cs.ualberta.ca/~tony/Public/Awit-Wita-ComputerChess/Wita-base/WitaNotes/wita-awit%2319-box2.pdf wita-awit#19-box2.pdf] from [http://webdocs.cs.ualberta.ca/~tony/Public/Awit-Wita-ComputerChess/Wita-base/WitaNotes/ Wita Notes] by [[Tony Marsland]]</ref> :
[[Freedom]] and [[Papa]] both use [[Mobility|mobility]] as their primary term in their [[Evaluation function|evaluation functions]]. As with [[Awit|Wita]], both use the ratio of computer's moves / opponent moves. Papa and Wita also multiply by the ratio of the [[Square Control|squares controlled]] and Papa goes one step further and takes the logarithm of this product to form the "entropy" of the position. The true merit of this entropy over the product ratio was not made clear, but it does ensure that in extreme situations the evaluation remains more closely bounded.
==The Merit==
The merit of this entropy over the product ratio probably is that it makes a product a sum and a quotient a difference, resulting in [[Negamax]] compatible symmetric values around zero in relation to [[Side to move|side to move]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=43545 log(w/b) instead of w-b?] by [[Gerd Isenberg]], [[CCC]], May 02, 2012</ref>.
[[FILE:PapaNegaLog.jpg|none|text-bottom]]
=Binary Logarithm=
The definition of the amount of [https://en.wikipedia.org/wiki/Self-information self-information] and [https://en.wikipedia.org/wiki/Entropy_%28information_theory%29 information entropy] involves the [https://en.wikipedia.org/wiki/Binary_logarithm binary logarithm]. On [[x86]] or [[x86-64]], Log2 (lb) may be applied using [[MMX]] or [[SSE2]] instructions <ref>[http://gruntthepeon.free.fr/ssemath/ Simple SSE and SSE2 optimized sin, cos, log and exp]</ref> <ref>[http://devmaster.net/forums/topic/6679-approximate-math-library/page__p__39242#entry39242 Approximate Math Library - Devmaster], January 25, 2007</ref>, with vectors of two or four [[Float|floats]].
[[FILE:PapaLog2.jpg|none|text-bottom]]
[[FILE:Binary logarithm plot.png|none|border|text-bottom|Plot of Log2 (lb) <ref>Plot of Log2 from [https://en.wikipedia.org/wiki/Binary_logarithm Binary logarithm from Wikipedia]</ref> ]]
<span id="PapaRibbit"></span>
=Selected Games=
[[WCCC 1974]], round 3, [[Papa]] - [[Ribbit]] <ref>[https://www.game-ai-forum.org/icga-tournaments/round.php?tournament=7&round=3&id=2 Stockholm 1974 - Chess - Round 3 - Game 2 (ICGA Tournaments)]</ref> :
<pre>
[Event "WCCC 1974"]
[Site "Stockholm, Sweden"]
[Date "1974.08.07"]
[Round "3"]
[White "Papa"]
[Black "Ribbit"]
[Result "0-1"]
1.Nf3 d5 2.d4 Nc6 3.Ne5 Nxe5 4.dxe5 e6 5.e4 dxe4 6.Bb5+ Bd7 7.Bxd7+ Qxd7
8.Qxd7+ Kxd7 9.O-O f5 10.Rd1+ Kc6 11.Be3 Bc5 12.Bxc5 Kxc5 13.Rd7 Nh6
14.Rxc7+ Kb6 15.Rxg7 Ng4 16.f4 exf3 17.gxf3 Nxe5 18.Nd2 Rag8 19.Nc4+ Nxc4
20.Rg6 hxg6 21.Rd1 Rgd8 22.Rxd8 Rxd8 23.a3 Nxb2 24.a4 Nxa4 25.c3 Nxc3
26.f4 Nd5 27.Kf2 Nxf4 28.Kf3 e5 29.h4 Rd4 30.Kg3 Nh5+ 31.Kf2 Rxh4 0-1
</pre>
=See also=
* [[Eden]]
* [[Gaia]]
* [[Genesis AR|Genesis]] by [[Claudio Bollini]]
* [[Genesis IL|Genesis]] by [[Omid David]]
* [[Genesis NL|Genesis]] by [[Eric van Riet Paap]]
* [[Various Classifications#Mythology|Mythology]]
* [[Paradise]]
* [[Terra]]
=External Links=
==Chess Program==
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=52 Papa's ICGA Tournaments]
* [http://www.chessgames.com/perl/chessplayer?pid=48723 The chess games of Papa (Computer)] from [http://www.chessgames.com/index.html chessgames.com]
==Papa==
* [https://en.wikipedia.org/wiki/Papa Papa (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Rangi_and_Papa Rangi and Papa from Wikipedia]
* [https://en.wikipedia.org/wiki/Earth_Mother Earth Mother from Wikipedia]
* [https://en.wikipedia.org/wiki/Creation_myth Creation myth from Wikipedia]
* [[Videos#JohnnyWinter|Johnny Winter]] - [https://en.wikipedia.org/wiki/Captured_Live! Sweet Papa John], September 14, 1975, at [https://en.wikipedia.org/wiki/Swing_Auditorium Swing Auditorium], [https://en.wikipedia.org/wiki/San_Bernardino,_California San Bernardino, California], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=0bumF2HKCto|alignment=left|valignment=top}}
==Entropy==
* [https://en.wikipedia.org/wiki/Entropy Entropy from Wikipedia]
* [https://en.wikipedia.org/wiki/Entropy_%28disambiguation%29 Entropy (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Entropy_%28statistical_thermodynamics%29 Entropy (statistical thermodynamics) from Wikipedia]
* [https://en.wikipedia.org/wiki/Entropy_%28information_theory%29 Entropy (information theory) from Wikipedia]
* [https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory Entropy in thermodynamics and information theory from Wikipedia]
* [https://en.wikipedia.org/wiki/Principle_of_maximum_entropy Principle of maximum entropy from Wikipedia]
* [https://en.wikipedia.org/wiki/Maximum_entropy_probability_distribution Maximum entropy probability distribution from Wikipedia]
=References=
<references />
'''[[Engines|Up one Level]]'''
[[FILE:WahineTane.jpg|border|right|thumb|200px| [https://en.wikipedia.org/wiki/Rangi_and_Papa Papa and Rangi] <ref>[https://en.wikipedia.org/wiki/M%C4%81ori_culture Maori] carving depicting a woman and a man embracing. From the pataka (food storehouse) belonging to [https://en.wikipedia.org/wiki/Te_Pokiha_Taranui Te Pokiha Taranui] of [https://en.wikipedia.org/wiki/Ng%C4%81ti_Pikiao Ngati Pikiao], [https://en.wikipedia.org/wiki/Te_Arawa Te Arawa]. The storehouse was completed in the 1870s, and stood at [https://en.wikipedia.org/wiki/Maketu Maketu], [https://en.wikipedia.org/wiki/Bay_of_Plenty Bay of Plenty], [https://en.wikipedia.org/wiki/New_Zealand New Zealand]. It is now at [https://en.wikipedia.org/wiki/Auckland_War_Memorial_Museum Auckland Museum], [https://en.wikipedia.org/wiki/Rangi_and_Papa Rangi and Papa from Wikipedia]</ref> ]]
'''Papa''',<br7>
an early computer chess program written by [[George Rajna]] and [[B. Almasi]], in the 70s affiliated with the [https://en.wikipedia.org/wiki/Hungarian_Academy_of_Sciences Hungarian Academy of Sciences]. Papa applies the concept of [[Papa#Entropy|entropy]] based on own and opponent [[Mobility#Papa|mobility]]. It participated at the [[WCCC 1974|First World Computer Chess Championship]], 1974 in [https://en.wikipedia.org/wiki/Stockholm Stockholm], unfortunately loosing all its three games due to tactical blunders. Based on preliminary results or expectations, Papa was seeded third, ahead of later winner [[Kaissa]] seeded fifth.
<span id="Entropy"></span>
=Entropy=
==Rajna==
In 2012, [[George Rajna]] has re-published a short paper on [https://en.wikipedia.org/wiki/Entropy entropy] in chess <ref>[[George Rajna]] ('''1976, 2012'''). ''Information – Entropy theory of Artificial Intelligence''. [http://vixra.org/pdf/1201.0063v1.pdf pdf]</ref>, which already appeared in ''[[WCCC 1974|The World Computer-Chess Championship]]'' by [[Jean Hayes Michie|Hayes]] and [[David Levy|Levy]] <ref>[[Jean Hayes Michie|Jean E. Hayes]], [[David Levy]] ('''1976'''). ''[http://www.getcited.org/pub/101724802 The world computer chess championship, Stockholm 1974]''. University Press (Edinburgh) ISBN 0852242859</ref>:
The basic theory on which one chess program can be constructed is that there exists a general characteristic of the game of chess, namely the concept of entropy. This concept has been employed in physics for a long time. In the case of a [https://en.wikipedia.org/wiki/Gas gas], it is the [https://en.wikipedia.org/wiki/Logarithm logarithm] of the number of those [https://en.wikipedia.org/wiki/Microstate_%28statistical_mechanics%29 microscopic states] compatible with the [https://en.wikipedia.org/wiki/Macroscopic_scale macroscopic] parameters of the gas.
What does this mean in terms of chess? A common characteristic of every [[Pieces|piece]] is that it could move to certain [[Squares|squares]], including by [[Captures|capture]]. In any given [[Chess Position|position]], therefore, the pieces by the rules of the game possess certain states, only one of which will be realized on the next move. The difference of the logarithm of the numbers of such states for Black and White respectively is the "entropy of the position". The task of the computer is then to increase this value for its own benefit.
...
Entropy is a principle of [https://en.wikipedia.org/wiki/Statistical_physics statistical physics] and therefore is only applicable in statistical contexts. The number of microstates of a confined gas is very large and therefore the statistical approach is valid. In chess, however, the number of pieces, a macroscopic parameter, is very small and therefore in this context the "value" of a position cannot be an exact function of entropy. For example, it is possible to [[Checkmate|checkmate]] with a total force of a single pawn despite the fact that the opponent has many pieces and various positions available.
==Marsland==
[[Tony Marsland]] mentioned Papa and other programs participating the [[WCCC 1974]] in his handwritten notes on the Hayes and Levy book <ref>[http://webdocs.cs.ualberta.ca/~tony/Public/Awit-Wita-ComputerChess/Wita-base/WitaNotes/wita-awit%2319-box2.pdf wita-awit#19-box2.pdf] from [http://webdocs.cs.ualberta.ca/~tony/Public/Awit-Wita-ComputerChess/Wita-base/WitaNotes/ Wita Notes] by [[Tony Marsland]]</ref> :
[[Freedom]] and [[Papa]] both use [[Mobility|mobility]] as their primary term in their [[Evaluation function|evaluation functions]]. As with [[Awit|Wita]], both use the ratio of computer's moves / opponent moves. Papa and Wita also multiply by the ratio of the [[Square Control|squares controlled]] and Papa goes one step further and takes the logarithm of this product to form the "entropy" of the position. The true merit of this entropy over the product ratio was not made clear, but it does ensure that in extreme situations the evaluation remains more closely bounded.
==The Merit==
The merit of this entropy over the product ratio probably is that it makes a product a sum and a quotient a difference, resulting in [[Negamax]] compatible symmetric values around zero in relation to [[Side to move|side to move]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=43545 log(w/b) instead of w-b?] by [[Gerd Isenberg]], [[CCC]], May 02, 2012</ref>.
[[FILE:PapaNegaLog.jpg|none|text-bottom]]
=Binary Logarithm=
The definition of the amount of [https://en.wikipedia.org/wiki/Self-information self-information] and [https://en.wikipedia.org/wiki/Entropy_%28information_theory%29 information entropy] involves the [https://en.wikipedia.org/wiki/Binary_logarithm binary logarithm]. On [[x86]] or [[x86-64]], Log2 (lb) may be applied using [[MMX]] or [[SSE2]] instructions <ref>[http://gruntthepeon.free.fr/ssemath/ Simple SSE and SSE2 optimized sin, cos, log and exp]</ref> <ref>[http://devmaster.net/forums/topic/6679-approximate-math-library/page__p__39242#entry39242 Approximate Math Library - Devmaster], January 25, 2007</ref>, with vectors of two or four [[Float|floats]].
[[FILE:PapaLog2.jpg|none|text-bottom]]
[[FILE:Binary logarithm plot.png|none|border|text-bottom|Plot of Log2 (lb) <ref>Plot of Log2 from [https://en.wikipedia.org/wiki/Binary_logarithm Binary logarithm from Wikipedia]</ref> ]]
<span id="PapaRibbit"></span>
=Selected Games=
[[WCCC 1974]], round 3, [[Papa]] - [[Ribbit]] <ref>[https://www.game-ai-forum.org/icga-tournaments/round.php?tournament=7&round=3&id=2 Stockholm 1974 - Chess - Round 3 - Game 2 (ICGA Tournaments)]</ref> :
<pre>
[Event "WCCC 1974"]
[Site "Stockholm, Sweden"]
[Date "1974.08.07"]
[Round "3"]
[White "Papa"]
[Black "Ribbit"]
[Result "0-1"]
1.Nf3 d5 2.d4 Nc6 3.Ne5 Nxe5 4.dxe5 e6 5.e4 dxe4 6.Bb5+ Bd7 7.Bxd7+ Qxd7
8.Qxd7+ Kxd7 9.O-O f5 10.Rd1+ Kc6 11.Be3 Bc5 12.Bxc5 Kxc5 13.Rd7 Nh6
14.Rxc7+ Kb6 15.Rxg7 Ng4 16.f4 exf3 17.gxf3 Nxe5 18.Nd2 Rag8 19.Nc4+ Nxc4
20.Rg6 hxg6 21.Rd1 Rgd8 22.Rxd8 Rxd8 23.a3 Nxb2 24.a4 Nxa4 25.c3 Nxc3
26.f4 Nd5 27.Kf2 Nxf4 28.Kf3 e5 29.h4 Rd4 30.Kg3 Nh5+ 31.Kf2 Rxh4 0-1
</pre>
=See also=
* [[Eden]]
* [[Gaia]]
* [[Genesis AR|Genesis]] by [[Claudio Bollini]]
* [[Genesis IL|Genesis]] by [[Omid David]]
* [[Genesis NL|Genesis]] by [[Eric van Riet Paap]]
* [[Various Classifications#Mythology|Mythology]]
* [[Paradise]]
* [[Terra]]
=External Links=
==Chess Program==
* [https://www.game-ai-forum.org/icga-tournaments/program.php?id=52 Papa's ICGA Tournaments]
* [http://www.chessgames.com/perl/chessplayer?pid=48723 The chess games of Papa (Computer)] from [http://www.chessgames.com/index.html chessgames.com]
==Papa==
* [https://en.wikipedia.org/wiki/Papa Papa (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Rangi_and_Papa Rangi and Papa from Wikipedia]
* [https://en.wikipedia.org/wiki/Earth_Mother Earth Mother from Wikipedia]
* [https://en.wikipedia.org/wiki/Creation_myth Creation myth from Wikipedia]
* [[Videos#JohnnyWinter|Johnny Winter]] - [https://en.wikipedia.org/wiki/Captured_Live! Sweet Papa John], September 14, 1975, at [https://en.wikipedia.org/wiki/Swing_Auditorium Swing Auditorium], [https://en.wikipedia.org/wiki/San_Bernardino,_California San Bernardino, California], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=0bumF2HKCto|alignment=left|valignment=top}}
==Entropy==
* [https://en.wikipedia.org/wiki/Entropy Entropy from Wikipedia]
* [https://en.wikipedia.org/wiki/Entropy_%28disambiguation%29 Entropy (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Entropy_%28statistical_thermodynamics%29 Entropy (statistical thermodynamics) from Wikipedia]
* [https://en.wikipedia.org/wiki/Entropy_%28information_theory%29 Entropy (information theory) from Wikipedia]
* [https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory Entropy in thermodynamics and information theory from Wikipedia]
* [https://en.wikipedia.org/wiki/Principle_of_maximum_entropy Principle of maximum entropy from Wikipedia]
* [https://en.wikipedia.org/wiki/Maximum_entropy_probability_distribution Maximum entropy probability distribution from Wikipedia]
=References=
<references />
'''[[Engines|Up one Level]]'''
