Changes

Jump to: navigation, search

Prophet

10,977 bytes added, 14:32, 11 February 2019
Created page with "'''Home * Engines * Prophet''' [[FILE:Nostradamus by Cesar.jpg|border|right|thumb| [https://en.wikipedia.org/wiki/Nostradamus Nostradamus] <ref>The Portrait..."
'''[[Main Page|Home]] * [[Engines]] * Prophet'''

[[FILE:Nostradamus by Cesar.jpg|border|right|thumb| [https://en.wikipedia.org/wiki/Nostradamus Nostradamus] <ref>The Portrait of [https://en.wikipedia.org/wiki/Nostradamus Michel de Nostredame] (Nostradamus), a French Renaissance Medicine & Astrologer, painted by his son [https://fr.wikipedia.org/wiki/C%C3%A9sar_de_Nostredame César de Nostredame] (1553-1630?) about 1614 A.D. 16cm x 18cm. (cf. Jean Boyer, “Deux peintres oubliés du XVIe siècle: Etienne Martellange et César de Nostredame”, Bulletin de la Société de l’Histoire de l’art français, Année 1971 (1972), pp.13-20)</ref> ]]

'''Prophet''',<br/>
a [[Chess Engine Communication Protocol]] compliant [[:Category:Open Source|open source chess engine]] under the [[Free Software Foundation#GPL|GNU General Public License]], written by [[James Swafford]] in [[Cpp|C++]] as a better [[C]]. As successor of [[Galahad]], Prophet is a traditional [[Bitboards|bitmap]] based program. Prophet was used in experiments with [[Temporal Difference Learning#TDLeaf|TD-Leaf]] <ref> [[James Swafford]] ('''2002'''). ''Optimizing Parameter Learning using Temporal Differences''. [http://www.aaai.org/Conferences/AAAI/aaai02.php AAAI-02], Student Abstracts, [http://www.jamesswafford.com/wp-content/uploads/2015/02/AAAI02-150.pdf pdf]</ref> when James Swafford was undergraduate at [https://en.wikipedia.org/wiki/East_Carolina_University East Carolina University] <ref>[http://www.jamesswafford.com/prophet/ prophet | James Swafford]</ref>, and testbed for [[Parallel Search|parallel search]] algorithms as topic of its author's Masters project <ref>[[James Swafford]] ('''2008'''). ''A Survey of Parallel Search Algorithms over Alpha-Beta Search Trees using Symmetric Multiprocessor Machines''. Masters Project, [https://en.wikipedia.org/wiki/East_Carolina_University East Carolina University], advisor [http://www.cs.ecu.edu/rws/ Ronnie Smith], [http://www.jamesswafford.com/wp-content/uploads/2015/02/jfs-masters.pdf pdf]</ref>. In September 2017, Prophet3 was released as open source under the [[Massachusetts Institute of Technology#License|MIT License]], using [[Magic Bitboards|magic bitboards]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65345 prophet3 released with source code] by [[James Swafford]], [[CCC]], September 30, 2017</ref>.

=Description=
==Bitboard Infrastructure==
===Rotated Bitboards===
Prophet2 uses [[Rotated Bitboards|rotated bitboards]] with 1/2 MiB lookup tables, indexed by square and [[Occupancy of any Line|8-bit line occupancy]], to determine [[Sliding Piece Attacks|sliding piece attacks]], ignoring the possible fourfold reduction excluding the redundant [[First Rank Attacks#TheOuterSquares|outer squares]] <ref>prophet-20b1-ja.zip, globals.cpp, bitmaps.cpp</ref>.
<pre>
Bitmap diag_a1h8_attacks[64][256];
Bitmap diag_h1a8_attacks[64][256];
Bitmap file_attacks[64][256];
Bitmap rank_attacks[64][256];

Bitmap GenBishopMap(Position* p,int sq) {
Bitmap b=0;
// find index for a1->h8 diagonal
int ind = (p->allpieces45 >> diag_a1h8_shift[sq]) & diag_a1h8_mask[sq];
b = diag_a1h8_attacks[sq][ind];
// find index for h1->a8 diagonal
ind = (p->allpieces315 >> diag_h1a8_shift[sq]) & diag_h1a8_mask[sq];
b |= diag_h1a8_attacks[sq][ind];
return b;
}
</pre>
<span id="BitScan"></span>
===BitScan & PopCount===
Similar to [[Amundsen#BitScan|Amundsen]], the [[Memory|memory]] bacchanal is attended by [[Population Count|population count]], [[BitScan#Bitscanforward|bitscan forward]] (GetLSBFast) and [[BitScan#Bitscanreverse|reverse]] (GetMSBFast) with three 16-bit indexed, 64K lookup tables of [[Double Word|double word]] integers, another 3/4 MiB competing for the caches <ref>prophet-20b1-ja.zip, globals.cpp, bitmaps.cpp</ref>:
<pre>
int num_bits[65536];
int lsb[65536];
int msb[65536];

/*****************************************************************************
* *
* int GetLSBFast(Bitmap b) *
* *
* Returns the least significant bit in a bitmap (1-64), or 0 if no bit set. *
* Assumes lsb[] is initialized. Much faster than GetLSBSlow(). *
* *
*****************************************************************************/

int GetLSBFast(Bitmap b) {
int r = lsb[(int)(b & 65535)];
if (r) return r;
b >>= 16;
r = lsb[(int)(b & 65535)];
if (r) return r+16;
b >>= 16;
r = lsb[(int)(b & 65535)];
if (r) return r+32;
b >>= 16;
r = lsb[(int)b];
if (r) return r+48;
return 0;
}
</pre>

==Search==
Prophet's [[Search|search]] is [[Alpha-Beta|alpha-beta]] [[Principal Variation Search|PVS]] with [[Transposition Table|transposition table]] inside an [[Iterative Deepening|iterative deepening]] framework with [[Depth#FractionalPlies|fractional plies]] and [[Aspiration Windows|aspiration windows]] of ± 1/3 pawn value. [[Selectivity]] is due to [[Null Move Pruning#AdaptiveNullMovePruning|adaptive null move pruning]], [[Futility Pruning|futility]] and [[Futility Pruning#Extendedfutilitypruning|extended futility pruning]], and [[Extensions#FractionalExtensions|fractional extensions]] on [[Check Extensions|checks]], [[One Reply Extensions|single replies]], [[Passed Pawn Extensions|passed pawn advances]] and [[Recapture Extensions|recaptures]]. Beside TT and keeping a [[Linked List|linked list]] of [[Triangular PV-Table#LinkedListontheStack|PVs on the Stack]], [[Move Ordering|Move ordering]] considers [[Killer Heuristic|killer]] and [[History Heuristic|history heuristic]], as well as [[MVV-LVA]] and [[Static Exchange Evaluation|SEE]] for [[Captures|captures]].

==Evaluation==
The [[Evaluation|evaluation]] in [[Centipawns|centipawn resolution]] determines a [[Score|score]] based on [[Material|material balance]] and [[Piece-Square Tables|piece-square tables]], and further considers various positional features, such as [[Development|development]], [[Mobility|mobility]], [[King Safety|king safety]] and [[Pawn Structure|pawn structure]], and [[Trapped Pieces|trapped pieces]].

=Tournament Play=
Prophet played five [[CCT Tournaments]], from [[CCT7]] in 2005, until [[CCT11]] in 2009, three [[ACCA Americas' Computer Chess Championship|ACCA Americas' Computer Chess Championships]], [[ACCA 2006]], [[ACCA 2007]] and [[ACCA 2008]], and the [[WCRCC 2008]] Second Annual ACCA World Computer Rapid Chess Championship.

=Selected Games=
[[CCT11]], round 2, [[Prophet]] - [[NoonianChess]] <ref>[https://cctchess.com/previous-events/cct-11/results/ CCT11 results and games]</ref>
<pre>
[Event "CCT11"]
[Site "Internet Chess Club"]
[Date "2009.03.21"]
[Round "2"]
[White "Prophet"]
[Black "NoonianChess"]
[Result "1-0"]

1.c4 g6 2.Nc3 Bg7 3.g3 c5 4.Bg2 Nc6 5.Nf3 d6 6.O-O Nf6 7.d4 cxd4 8.Nxd4
Bd7 9.Nc2 O-O 10.b3 a6 11.Bb2 Ng4 12.h3 Nh6 13.Rb1 Bf5 14.e4 Be6 15.Nd5
f6 16.a4 Re8 17.Qd2 Bf7 18.Bc3 g5 19.a5 Rb8 20.Nb6 Bh5 21.Kh1 e5 22.Ne3
Qe7 23.f4 gxf4 24.gxf4 Qd8 25.Ned5 Kh8 26.Bf3 Bxf3+ 27.Rxf3 f5 28.exf5
Nxf5 29.fxe5 Nh4 30.Rf7 Nxe5 31.Bxe5 Rxe5 32.Nd7 Qe8 33.Nxe5 dxe5 34.Rbf1
Qe6 35.Qe3 Ng6 36.R1f6 Qc8 37.Rd6 e4 38.Rdd7 Ne5 39.Rxg7 Qxd7 40.Rxd7 Nxd7
41.Qd4+ Kg8 42.Ne7+ Kf7 43.Qxd7 Rf8 44.Nf5+ Kf6 45.Qe7+ Kxf5 46.Qxf8+ Kg5
47.Qf1 e3 48.c5 e2 49.Qxe2 Kf4 50.Qe7 h6 51.Qxb7 h5 52.Kg2 Ke3 53.Qd5 Ke2
54.c6 Ke3 55.c7 Kf4 56.Kh1 Ke3 57.c8=Q Kf2 58.Qd4+ Ke2 59.Qxa6+ Ke1
60.Qe6+ Kf1 61.Qdf6# 1-0
</pre>

=See also=
* [[chess4j]]
* [[Galahad]]
* [[Tristram]]

=Publications=
* [[James Swafford]] ('''2002'''). ''Optimizing Parameter Learning using Temporal Differences''. [http://www.aaai.org/Conferences/AAAI/aaai02.php AAAI-02], Student Abstracts, [http://www.jamesswafford.com/wp-content/uploads/2015/02/AAAI02-150.pdf pdf]
* [[James Swafford]] ('''2008'''). ''A Survey of Parallel Search Algorithms over Alpha-Beta Search Trees using Symmetric Multiprocessor Machines''. Masters Project, [https://en.wikipedia.org/wiki/East_Carolina_University East Carolina University], advisor [http://www.cs.ecu.edu/rws/ Ronnie Smith], [http://www.jamesswafford.com/wp-content/uploads/2015/02/jfs-masters.pdf pdf]

=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=409524 It's Prophet] by [[James Swafford]], [[CCC]], February 04, 2005 » [[CCT7]]
* [http://www.talkchess.com/forum/viewtopic.php?t=13426&start=10 Re: Speedup with bitboards on 64-bit CPUs] by [[James Swafford]], [[CCC]], April 28, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=14114 pthread weirdness] by [[James Swafford]], [[CCC]], May 29, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=24808 Prophet ACCA PanAm 2008 tournament notes] by [[James Swafford]], [[CCC]], November 10, 2008 » [[ACCA 2008]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65345 prophet3 released with source code] by [[James Swafford]], [[CCC]], September 30, 2017

=External Links=
==Chess Engine==
* [http://www.jamesswafford.com/prophet/ prophet | James Swafford]
* [https://github.com/jswaff/prophet3 GitHub - jswaff/prophet3: a C based chess engine]
* [http://web.archive.org/web/20090627211250/http://chessprogramming.org/prophet/ Prophet Chess by James Swafford], [https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine]
* [http://kirr.homeunix.org/chess/engines/Jim%20Ablett/PROPHET/ Index of /chess/engines/Jim Ablett/PROPHET] by [[Jim Ablett]], hosted by [[Kirill Kryukov]]
* [http://www.jamesswafford.com/category/computer-chess/ James Swafford » Computer Chess]
==Misc==
* [https://en.wikipedia.org/wiki/Prophet Prophet from Wikipedia]
* [https://en.wikipedia.org/wiki/Prophet_%28disambiguation%29 Prophet (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Prophecy Prophecy from Wikipedia]
* [https://en.wikipedia.org/wiki/Prophecy_%28disambiguation%29 Prophecy (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Nostradamus:_The_Last_Prophecy Nostradamus: The Last Prophecy from Wikipedia]
* [https://en.wikipedia.org/wiki/Jazz_Is_Dead Jazz is Dead] - [https://en.wikipedia.org/wiki/Terrapin_Station Estimated Prophet], [https://en.wikipedia.org/wiki/Fox_Theatre_(Boulder,_Colorado) Fox Theatre], [https://en.wikipedia.org/wiki/Boulder,_Colorado Boulder, Colorado], April 13, 1999, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: lineup: [https://en.wikipedia.org/wiki/Jimmy_Herring Jimmy Herring], [https://en.wikipedia.org/wiki/T_Lavitz T Lavitz], [[:Category:Alphonso Johnson|Alphonso Johnson]], [[:Category:Billy Cobham|Billy Cobham]]
: {{#evu:https://www.youtube.com/watch?v=l12qhww9izM|alignment=left|valignment=top}}

=References=
<references />
'''[[Engines|Up one level]]'''
[[Category:Open Source]]
[[Category:GPL]]
[[Category:WinBoard]]
[[Category:XBoard]]
[[Category:Metaphysics]]
[[Category:Alphonso Johnson]]
[[Category:Billy Cobham]]

Navigation menu