Older Version
Newer Version
GerdIsenberg
Jul 28, 2017
**[[Home]] * [[Engines]] * Parabelle** || [[image:Armstrong_Whitworth_F.K.10.jpg link="https://commons.wikimedia.org/wiki/File:Armstrong_Whitworth_F.K.10.jpg"]] ||~ || **Parabelle**, an experimenatal chess program of the early 1980s developed by [[Fred Popowich]] and [[Tony Marsland]] at [[University of Alberta]], written in [[C]], to research on [[Parallel Search|parallel search]]. In partcicular addressing search overhead and communication overhead, the [[Parallel Search#Speedup|speedup]] of [[Parallel Search#PrincipalVariationSplitting|principal variation splitting]] with various setups was investigated, later revised by [[Tim Breitkreutz]] et al. to run Parabelle under //network multiprocessor package// (NMP), a [[https://en.wikipedia.org/wiki/Parallel_Virtual_Machine|PVM]]-like [[https://en.wikipedia.org/wiki/Message_passing|message passing]] library <ref>[[Tony Marsland]], [[Tim Breitkreutz]], [[Steve Sutphen]] (**1991**). //A Network Multiprocessor for Experiments in Parallelism.// Concurrency: Practice and Experience, Vol. 3, No. 3, pp. 203-219. [[https://webdocs.cs.ualberta.ca/~tony/RecentPapers/cpe.pdf|pdf]]</ref>. Parabelle was initially based on [[Ken Thompson|Ken Thompson's]] program [[Belle|TinkerBelle]] <ref>The original name for [[Belle]] was T.Belle (the [[https://en.wikipedia.org/wiki/United_States_Chess_Federation|US Chess Federation]] required an initial). TinkerBelle was the "invention" of [[Tony Marsland]], and nothing [[Ken Thompson]] knew about or approved</ref> <ref>[[https://en.wikipedia.org/wiki/Tinker_Bell|Tinker Bell from Wikipedia]] a fictional character from [[https://en.wikipedia.org/wiki/J._M._Barrie|J. M. Barrie's]] 1904 play and 1911 novel [[https://en.wikipedia.org/wiki/Peter_and_Wendy|Peter and Wendy]]</ref> , and was itself base for further projects such as the program [[Abyss]], which was subject of research on [[Extensions|selective search extensions]] in the domain of [[Chinese Chess]], and also played tournaments <ref>[[Chun Ye]] (**1992**). //Experiments in Selective Search Extensions//. M.Sc. thesis, Department of Computing Science, [[University of Alberta]], [[https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1|pdf]]</ref> . || || Quadruplane <ref>[[https://en.wikipedia.org/wiki/Armstrong_Whitworth_F.K.10|Armstrong Whitworth F.K.10]] (1916) a British two-seat [[https://en.wikipedia.org/wiki/Multiplane_(aeronautics)#Quadruplanes|quadruplane]], [[https://commons.wikimedia.org/wiki/File:Armstrong_Whitworth_F.K.10.jpg|image]] from [[https://en.wikipedia.org/wiki/Wikimedia_Commons|Wikimedia Commons]]</ref> ||~ ||^ || [[toc]] =Description= The basis of both the sequential and parallel chess programs was an [[Iterative Deepening|iterative deepening]] (ID) framework with [[Transposition Table|transposition table]] and [[Refutation Table|refulation table]] performing a [[Principal Variation Search|principal variation search]]. The test framework was a [[68000]] based [[https://en.wikipedia.org/wiki/MIMD|MIMD]] system <ref>B.A. Bowen, R.J.A. Buhr (**1980**). //The Logical Design of Multiple Microprocessor Systems//. [[https://en.wikipedia.org/wiki/Prentice_Hall|Prentice Hall]], [[https://www.amazon.com/Logical-Design-Multiple-Microprocessor-Systems/dp/0135399084|amazon]]</ref> with under today's standards extremely slow [[https://en.wikipedia.org/wiki/Inter-process_communication|interprocess communication]] through [[https://en.wikipedia.org/wiki/Serial_communication|serial lines]] at 4800 or 9600 [[https://en.wikipedia.org/wiki/Baud|baud]]. In [[Parallel Search#PrincipalVariationSplitting|principal variation splitting]], all processors recursively analyze the first move, with the remaining moves being examined using a [[Null Window|null window]] by individual processors using a local refutation table that is updated after each iteration of the ID search. The transposition table can be accessed either on a [[Shared Hash Table|global]] (stored in the supervisor processor increasing communication overhead) or local basis. =Performance= The program was tested performing 5- and 6-[[Ply|ply]] searches on 24 positions of the [[Bratko-Kopec Test]] with various transposition table implementations. Despite huge savings in nodes visited using the global table, the increased communication overhead by far decreased the net result, and only a [[Depth|depth]] limited shared table (depth < 3) came close to the performance of a local, depth limited transposition table, which turned out best for this hardware configuration - speedup with [[https://en.wikipedia.org/wiki/Standard_deviation|standard deviation]] (σ) as given in the 1983 paper <ref>[[Fred Popowich]], [[Tony Marsland]]. (**1983**) //Parabelle: Experience with a Parallel Chess Program.// Technical Report 83-7. Computing Science Department, [[University of Alberta]], [[https://webdocs.cs.ualberta.ca/~tony/TechnicalReports/TR83-7.pdf|pdf]], pp. 6</ref> . ||~ # ||~ ||||||~ 5 Ply ||||||~ 6 Ply || ||~ Proc ||~ ||~ Speedup ||~ ||~ σ ||~ Speedup ||~ ||~ σ || ||~ 2 ||~ ||> 1.89 ||~ ||> 0.10 ||> 1.92 ||~ ||> 0.33 || ||~ 3 ||~ ||> 2.59 ||~ ||> 0.29 ||> 2.66 ||~ ||> 0.51 || ||~ 4 ||~ ||> 3.10 ||~ ||> 0.52 ||> 3.27 ||~ ||> 0.75 || =See also= * [[Abyss]] * [[Belle]] * [[Bratko-Kopec Test]] * [[Parallel Search#PrincipalVariationSplitting|Principal Variation Splitting]] =Publications= * [[Tony Marsland]], [[Fred Popowich]] (**1983**). //A Multiprocessor Tree-searching System Design.// Technical Report TR 83-6, Department of Computing Science, [[University of Alberta]] * [[Fred Popowich]], [[Tony Marsland]]. (**1983**) //Parabelle: Experience with a Parallel Chess Program.// Technical Report 83-7. Computing Science Department, [[University of Alberta]], [[https://webdocs.cs.ualberta.ca/~tony/TechnicalReports/TR83-7.pdf|pdf]] * [[Tony Marsland]], [[Fred Popowich]] (**1985**). //Parallel Game-Tree Search.// [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 7, No. 4, pp. 442-452. [[http://webdocs.cs.ualberta.ca/~tony/OldPapers/parallel.pdf|1984 pdf]] (Draft) * [[Tony Marsland]], [[Fred Popowich]] (**1985**). //Corrections to "Parallel Game Tree-Search"//. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 7, No. 6 * [[Tony Marsland]], [[Tim Breitkreutz]], [[Steve Sutphen]] (**1991**). //A Network Multiprocessor for Experiments in Parallelism.// Concurrency: Practice and Experience, Vol. 3, No. 3, pp. 203-219. [[https://webdocs.cs.ualberta.ca/~tony/RecentPapers/cpe.pdf|pdf]] =External Links= * [[https://en.wikipedia.org/wiki/Parabelle|Parabelle]] - [[https://en.wikipedia.org/wiki/Reassembling_the_Icons|Reassembling The Icons]] (2010), [[https://en.wikipedia.org/wiki/YouTube|YouTube]] Video > [[media type="youtube" key="KEtNsw8g5Qg" width="560" height="315"]] =References= <references /> =What links here?= [[include page="Parabelle" component="backlinks" limit="20"]] **[[Engines|Up one Level]]**