Papa

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Papa

Papa,
an early computer chess program written by George Rajna and B. Almasi, in the 70s affiliated with the Hungarian Academy of Sciences. Papa applies the concept of entropy based on own and opponent mobility. It participated at the First World Computer Chess Championship, 1974 in 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.

Entropy

Rajna

In 2012, George Rajna has re-published a short paper on entropy in chess [2], which already appeared in The World Computer-Chess Championship by Hayes and Levy [3]:

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 gas, it is the logarithm of the number of those microscopic states compatible with the macroscopic parameters of the gas.
What does this mean in terms of chess? A common characteristic of every piece is that it could move to certain squares, including by capture. In any given 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 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 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 [4] :

 Freedom and Papa both use mobility as their primary term in their evaluation functions. As with Wita, both use the ratio of computer's moves / opponent moves. Papa and Wita also multiply by the ratio of the 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 [5].

PapaNegaLog.jpg

Binary Logarithm

The definition of the amount of self-information and information entropy involves the binary logarithm. On x86 or x86-64, Log2 (lb) may be applied using MMX or SSE2 instructions [6] [7], with vectors of two or four floats.

PapaLog2.jpg
Plot of Log2 (lb) [8]

Selected Games

WCCC 1974, round 3, Papa - Ribbit [9] :

[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

See also

External Links

Chess Program

Papa

Entropy

References

  1. Maori carving depicting a woman and a man embracing. From the pataka (food storehouse) belonging to Te Pokiha Taranui of Ngati Pikiao, Te Arawa. The storehouse was completed in the 1870s, and stood at Maketu, Bay of Plenty, New Zealand. It is now at Auckland Museum, Rangi and Papa from Wikipedia
  2. George Rajna (1976, 2012). Information – Entropy theory of Artificial Intelligence. pdf
  3. Jean E. Hayes, David Levy (1976). The world computer chess championship, Stockholm 1974. University Press (Edinburgh) ISBN 0852242859
  4. wita-awit#19-box2.pdf from Wita Notes by Tony Marsland
  5. log(w/b) instead of w-b? by Gerd Isenberg, CCC, May 02, 2012
  6. Simple SSE and SSE2 optimized sin, cos, log and exp
  7. Approximate Math Library - Devmaster, January 25, 2007
  8. Plot of Log2 from Binary logarithm from Wikipedia
  9. Stockholm 1974 - Chess - Round 3 - Game 2 (ICGA Tournaments)

Up one Level