Parallel Search of Strongly Ordered Game Trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel Search of Strongly Ordered Game Trees

Full text

Pdf (1.55 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 14 , Issue 4 (December 1982) table of contents

Pages: 533 - 551

Year of Publication: 1982

ISSN:0360-0300

Authors

T. A. Marsland	Department of Computing Science, University of Alberta, Edmonton, Canada T6G 2H1
M. Campbell	Department of Computing Science, University of Alberta, Edmonton, Canada T6G 2H1

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 86, Citation Count: 22

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/356893.356895 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AKL81	AKL, S., AND DORAN, R. "A comparison of parallel implementations of the alphabeta and scout tree search algorithms using the game of checkers." Tech. Rep. 81- 121, Computing and Information Science Dep., Queen's Univ., Kingston, Canada, 1981.
	AKL82	Ag, L, S., BARNARD, D., AND DORAN, R. "Design, analysis, and implementation of a parallel tree search algorithm." IEEE Trans Pattern Anal Mach. Intell. PAMI-4, 2 (1982), 192-203.
	BAUD78	Gerard Maurice Baudet, The design and analysis of algorithms for asynchronous multiprocessors., 1978
	BIRD80	R. S. Bird, Tabulation Techniques for Recursive Programs, ACM Computing Surveys (CSUR), v.12 n.4, p.403-417, Dec. 1980 [doi>10.1145/356827.356831]
	CAMP81	CAMPBELL, M. "Algorithms for the parallel search of game trees," M.Sc. thesis, Tech. Rep. 81-8, Computing Science Dep., Univ. of Alberta, Edmonton, Canada, Aug. 1981.
	CAMP83	CAMPBELL, M., AND MARSLAND, T. A. "A comparison of minimax tree search algorithms." Art~f lntell. (to appear).
	CICH73	CICHELLt, R.J. "Research progress report in computer chess." SIGART Newsl 41 (Aug. 1973), 32-36.
	COND82	CONDON, J. H., AND THOMPSON, K. "Belle chess hardware." In M. R. B. Clarke (Ed.), Advances m Computer Chess, vol. 3. Pergamon Press, Elmsford, N. Y., 1982, pp. 45-54.
	DEGR65	OE GROOT, A.D. Thought and Choice m Chess. Mouton, The Hague, 1965.
	ENSL74	ENSLOW, P. Multiprocessors and Parallel Processing. Wiley, New York, 1974.
	FISH80	FISHBURN, j., AND FINKEL, R. "Parallel alpha-beta search on Arachne." Tech. Rep. 394, Computer Science Dep., Univ. of Wisconsin, Madison, Wis, July, 1980.
	FISH81	John Philip Fishburn, Analysis of speedup in distributed algorithms, 1981
	FULL73	FULLER, S., GASCHNIG, J., AND GILLOGLY, J. "Analysis of the alpha-beta pruning algorithm." Computer Science Dep., Carnegie-Mellon Univ, Pittsburgh, Pa., 1973.
	GILL72	GiLLOGLY, J. "The technology chess program." Art~f Intell. 3 (1972), 145-163.
	GILL78	James John Gillogly, Performance analysis of the technology chess program., 1978
	GREE67	GREENBLATT, R. D., EASTLAKE, D. E., ANO CROCKER, S. D. "The Greenblatt chess program." In Fall J. Computer Conf. Proc., vol. 31, Thompson Books, Washington, D C., 1967, pp. 801-810.
	GRIF76	GRIFFITH, A.K. "EmpJxical exploration of the performance of the alpha-beta treesearching heuristic." II~I~E Trans. Com. put. C-25, 1 (1976), 6-11.
	KNUT75	KNUTH, D., A~O MOORE, R. "An analysis of alpha-beta pruning." Artif IntelL 6 (1975), 293-326.
	MARS74	MARSLAND, T. A., AND RUSHTON, P. G. "A study of techniques for gameplaying programs." In j. Rose (Ed.) Advances in Cybernetics and Systems, vol. 1. Gordon and Breach, London, 1974, pp. 363-371.
	MARS81	T. A. Marsland , M. Campbell, A survey of enhancements to the alpha-beta algorithm, Proceedings of the ACM '81 conference, p.109-114, January 1981 [doi>10.1145/800175.809846]
	NEWB77	NEWBOaN, M.M. "The efficiency of the alpha-beta search in trees with branch dependent terminal node scores." Art~f Intell. 8 (1977), 137-153.
	NEWB79	NEWBORN, M.M. "Recent progress in computer chess." In M. C. Yovits (Ed.), Advances in Computers, vol. 18. Academic Press, New York, 1979, pp. 59-114.
	NILS80	N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
	PEAR80	PEARL, j. "Asymptotic properties of minimax trees and game searching procedures." Artif. lntell. 14 (1980), 113-138.
	SLAG69	James R. Slagle , John E. Dixon, Experiments With Some Programs That Search Game Trees, Journal of the ACM (JACM), v.16 n.2, p.189-207, April 1969 [doi>10.1145/321510.321511]
	SLAT77	SLATE, D., ANO A?K~, L. "CHESS, 4.5--The Northwestern University chess program." in P. Prey (Ed.), Chess Skill m Man and Machine, chap. 4. Springer Verlag, New York, 1977, pp. 82-118.
	SORE78	SORENSEN, P. O., TREMBLAY, J. P., AND DEUTSC}IER, R. F. "Key-to-address transformation techniques." INFOR 16, 1 (1978), 1-34.
	STOC79	STOCKMAN, O. "A minimax algorithm better than alpha-beta?" Artif Intell. 12 (1979), 179-196.
	THOM81	THOMPSON, K. Private communications, Oct.-Nov. 1981.
	THOM82	THOMPSON, K. "Computer chess strength." In M. R. B. Clarke (Ed.), Advances in Computer Chess, vol. 3. Pergamon Press, Elmsford, N.Y., 1982, pp. 55-56.
	TRUS81	TRUSCOTT, T. R. "Techniques used in minimax game-playing programs." Master's thesis, Computer Science Dep., Duke Univ., Durham, N.C., Apr. 1981.
	WEIT80	Cay Weitzman, Distributed Micro Minicomputer Systems: Structure, Implementation and Application, Prentice Hall PTR, Upper Saddle River, NJ, 1980
	ZOBR70	ZOBRIST, A.L. "A hashing method with applications for game playing." Tech. Rep. 88, Computer Science Dep., Univ. of Wisconsin, Madison, Wis., Apr. 1970.

CITED BY 22

	Jean-Christophe Weill, The ABDADA distributed minimax search algorithm, Proceedings of the 1996 ACM 24th annual conference on Computer science, p.131-138, February 15-18, 1996, Philadelphia, Pennsylvania, United States
	Nicholas Carriero , David Gelernter, How to write parallel programs: a guide to the perplexed, ACM Computing Surveys (CSUR), v.21 n.3, p.323-357, Sep. 1989
	Andrew S. Tanenbaum , Robbert van Renesse , Hans van Staveren , Gregory J. Sharp , Sape J. Mullender, Experiences with the Amoeba distributed operating system, Communications of the ACM, v.33 n.12, p.46-63, Dec. 1990
	Bruce Abramson, Control strategies for two-player games, ACM Computing Surveys (CSUR), v.21 n.2, p.137-161, Jun. 1989
	Monroe Newborn, A parallel search chess program, Proceedings of the 1985 ACM annual conference on The range of computing : mid-80's perspective: mid-80's perspective, p.272-277, October 1985, Denver, Colorado, United States
	T. A. Marsland , N. Srimani, Phased state space search, Proceedings of 1986 ACM Fall joint computer conference, p.514-518, November 1986, Dallas, Texas, United States
	Ranier Feldmann , Peter Mysliwiete , Burkhard Monien, Studying overheads in massively parallel MIN/MAX-tree evaluation, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.94-103, June 27-29, 1994, Cape May, New Jersey, United States
	Robert M. Hyatt , Harry L. Nelson, Chess and supercomputers: details about optimizing Cray Blitz, Proceedings of the 1990 conference on Supercomputing, p.354-363, October 1990, New York, New York, United States
	E. Gabber, VMMP: A Practical Tool for the Development of Portable and Efficient Programs for Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.304-317, July 1990
	Jonathan Schaeffer, Improved parallel alpha-beta search, Proceedings of 1986 ACM Fall joint computer conference, p.519-527, November 1986, Dallas, Texas, United States
	Richard M. Karp , Yangun Zhang, On parallel evaluation of game trees, Journal of the ACM (JACM), v.45 n.6, p.1050-1075, Nov. 1998
	M. Newborn, Unsynchronized Iteratively Deepening Parallel Alpha-Beta Search, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.5, p.687-694, September 1988
	B Wah , G J Li, Survey on special purpose computer architectures for AI, ACM SIGART Bulletin
	Jonathan Schaeffer, Long-range planning in computer chess, Proceedings of the 1983 annual conference on Computers : Extending the human resource, p.170-179, January 1983
	Hermann Kaindl , Reza Shams , Helmut Horacek, Minimax Search Algorithms With and Without Aspiration Windows, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.12, p.1225-1235, December 1991
	Ananth Grama , Vipin Kumar, State of the Art in Parallel Search Techniques for Discrete Optimization Problems, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.28-35, January 1999
	Keith Wiley , Lance R. Williams, Representation of interwoven surfaces in 2 1/2 D drawing, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada
	Ian Parsons, Evaluation of distributed communication systems, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: distributed computing, October 24-28, 1993, Toronto, Ontario, Canada
	Claude G. Diderich, A bibliography on minimax trees, ACM SIGACT News, v.24 n.4, p.82-89, Dec. 1993
	Alexander Reinefeld , Jonathan Schaeffer , T. A. Marsland, Information acquisition in minimal window search, Proceedings of the 9th international joint conference on Artificial intelligence, p.1040-1043, August 18-23, 1985, Los Angeles, California
	T. A. Marsland, Relative efficiency of alpha-beta implementations, Proceedings of the Eighth international joint conference on Artificial intelligence, p.763-766, August 08-12, 1983, Karlsruhe, West Germany
	Reza Shams , Hermann Kaindl , Helmut Horacek, Using aspiration windows for minimax algorithms, Proceedings of the 12th international joint conference on Artificial intelligence, p.192-197, August 24-30, 1991, Sydney, New South Wales, Australia