Parabelle

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Parabelle

Quadruplane [1]

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

External Links

References

  1. Armstrong Whitworth F.K.10 (1916) a British two-seat quadruplane, image from Wikimedia Commons
  2. 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
  3. 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
  4. Tinker Bell from Wikipedia a fictional character from J. M. Barrie's 1904 play and 1911 novel Peter and Wendy
  5. Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf
  6. B.A. Bowen, R.J.A. Buhr (1980). The Logical Design of Multiple Microprocessor Systems. Prentice Hall, amazon
  7. 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

Up one Level