Parabelle
Parabelle,
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. In particular addressing search overhead and communication overhead, the speedup of principal variation splitting with various setups was investigated, later revised by Tim Breitkreutz et al. to run Parabelle under network multiprocessor package (NMP), a PVM-like message passing library [2]. Parabelle was initially based on Ken Thompson's program TinkerBelle [3] [4] , and was itself base for further projects such as the program Abyss, which was subject of research on selective search extensions in the domain of Chinese Chess, and also played tournaments [5] .
Description
The basis of both the sequential and parallel chess programs was an iterative deepening (ID) framework with transposition table and refulation table performing a principal variation search. The test framework was a 68000 based MIMD system [6] with under today's standards extremely slow interprocess communication through serial lines at 4800 or 9600 baud.
In principal variation splitting, all processors recursively analyze the first move, with the remaining moves being examined using a 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 global (stored in the supervisor processor increasing communication overhead) or local basis.
Performance
The program was tested performing 5- and 6-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 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 standard deviation (σ) as given in the 1983 paper [7] .
| # | 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
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, pdf
- Tony Marsland, Fred Popowich (1985). Parallel Game-Tree Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 7, No. 4, pp. 442-452. 1984 pdf (Draft)
- Tony Marsland, Fred Popowich (1985). Corrections to "Parallel Game Tree-Search". 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. pdf
External Links
- para- - Wiktionary
- belle - Wiktionary
- Parabelle - Reassembling The Icons (2010), YouTube Video
References
- ↑ Armstrong Whitworth F.K.10 (1916) a British two-seat quadruplane, image from Wikimedia Commons
- ↑ 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. pdf
- ↑ The original name for Belle was T.Belle (the US Chess Federation required an initial). TinkerBelle was the "invention" of Tony Marsland, and nothing Ken Thompson knew about or approved
- ↑ Tinker Bell from Wikipedia a fictional character from J. M. Barrie's 1904 play and 1911 novel Peter and Wendy
- ↑ Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
- ↑ B.A. Bowen, R.J.A. Buhr (1980). The Logical Design of Multiple Microprocessor Systems. Prentice Hall, amazon
- ↑ Fred Popowich, Tony Marsland. (1983) Parabelle: Experience with a Parallel Chess Program. Technical Report 83-7. Computing Science Department, University of Alberta, pdf, pp. 6
