25,161
edits
Changes
Created page with "'''Home * Engines * Parabelle''' FILE:Armstrong Whitworth F.K.10.jpg|border|right|thumb| Quadruplane <ref>[https://en.wikipedia.org/wiki/Armstrong_Whitwo..."
'''[[Main Page|Home]] * [[Engines]] * Parabelle'''
[[FILE:Armstrong Whitworth F.K.10.jpg|border|right|thumb| 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> ]]
'''Parabelle''',<br/>
an experimental 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> .
=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> .
{| class="wikitable"
|-
! #
! colspan="2" | 5 Ply
! colspan="2" | 6 Ply
|-
! Proc
! Speedup
! σ
! Speedup
! σ
|-
! 2
| style="text-align:right;" | 1.89
| style="text-align:right;" | 0.10
| style="text-align:right;" | 1.92
| style="text-align:right;" | 0.33
|-
! 3
| style="text-align:right;" | 2.59
| style="text-align:right;" | 0.29
| style="text-align:right;" | 2.66
| style="text-align:right;" | 0.51
|-
! 4
| style="text-align:right;" | 3.10
| style="text-align:right;" | 0.52
| style="text-align:right;" | 3.27
| style="text-align:right;" | 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.wiktionary.org/wiki/para- para- - Wiktionary]
* [https://en.wiktionary.org/wiki/belle belle - Wiktionary]
* [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
: {{#evu:https://www.youtube.com/watch?v=KEtNsw8g5Qg|alignment=left|valignment=top}}
=References=
<references />
'''[[Engines|Up one Level]]'''
[[Category:Experimental]]
[[Category:Music]]
[[FILE:Armstrong Whitworth F.K.10.jpg|border|right|thumb| 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> ]]
'''Parabelle''',<br/>
an experimental 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> .
=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> .
{| class="wikitable"
|-
! #
! colspan="2" | 5 Ply
! colspan="2" | 6 Ply
|-
! Proc
! Speedup
! σ
! Speedup
! σ
|-
! 2
| style="text-align:right;" | 1.89
| style="text-align:right;" | 0.10
| style="text-align:right;" | 1.92
| style="text-align:right;" | 0.33
|-
! 3
| style="text-align:right;" | 2.59
| style="text-align:right;" | 0.29
| style="text-align:right;" | 2.66
| style="text-align:right;" | 0.51
|-
! 4
| style="text-align:right;" | 3.10
| style="text-align:right;" | 0.52
| style="text-align:right;" | 3.27
| style="text-align:right;" | 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.wiktionary.org/wiki/para- para- - Wiktionary]
* [https://en.wiktionary.org/wiki/belle belle - Wiktionary]
* [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
: {{#evu:https://www.youtube.com/watch?v=KEtNsw8g5Qg|alignment=left|valignment=top}}
=References=
<references />
'''[[Engines|Up one Level]]'''
[[Category:Experimental]]
[[Category:Music]]
