GO Is Polynomial-Space Hard

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

GO Is Polynomial-Space Hard

Full text

Pdf (411 KB)

Source

Journal of the ACM (JACM) archive
Volume 27 , Issue 2 (April 1980) table of contents

Pages: 393 - 401

Year of Publication: 1980

ISSN:0004-5411

Authors

David Lichtenstein	Computer Science Division, Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA
Michael Sipser	IBM Research Laboratory, 5600 Cottle Road, San Jose, CA and University of California, Berkeley, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 101, Citation Count: 16

Additional Information:

abstract 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/322186.322201 What is a DOI?

ABSTRACT

It is shown that, given an arbitrary GO position on an n × n board, the problem of determining the winner is Pspace hard. New techniques are exploited to overcome the difficulties arising from the planar nature of board games. In particular, it is proved that GO is Pspace hard by reducing a Pspace-complete set, TQBF, to a game called generalized geography, then to a planar version of that game, and finally to GO.

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.

	1	BERLEKAMP, E R, CONWAY, J, AND GUY, R Wmmng Ways Academic Press, New York. To appear
	2	BLOCK, H C Axioms for GO SIGART Newsletter (ACM), 51 (Aprd 1975), p 13
	3	CHANDRA, A K, AND STOCKMEYER, L J Alternation 17th Annual IEEE Symp Found Comptr So, Houston, Texas, 1973, pp 98-108
	4	S. Even , R. E. Tarjan, A Combinatorial Problem Which Is Complete in Polynomial Space, Journal of the ACM (JACM), v.23 n.4, p.710-719, Oct. 1976 [doi>10.1145/321978.321989]
	5	FRAENKEL, A S, GAREY, M R, JOHNSON, D.S, SCHAEFER, T J, AND YESHA, Y. The complexity of checkers on an n x n board 19th Annual IEEE Symp Found Comptr Scl, Ann Arbor, MJch, 1978, pp 55-64
	6	KARP, P M Reduoblhty among combinatorial problems In Complexny of Computer Computanons, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972
	7	LICHTENSTEIN, D Planar formulae and their uses. To appear m SlAM J Comptg
	8	LICHTENSTEIN, D, AND SIPSER, M GO is Pspace Hard. Memo No UCB/ERL M78/16, Electronics Res Lab., U of Cahfornla, Berkeley Cahf 1978.
	9	L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
	10	SCHAEFER, T J On the complexity of some two-person perfect-mformauon games. Z Comptr Syst Scz 16, 2 (April 1978), 185-225

CITED BY 16

	Darse Billings , Lourdes Peña , Jonathan Schaeffer , Duane Szafron, Learning to play strong poker, Machines that learn to play games, Nova Science Publishers, Inc., Commack, NY, 2001
	Martin Müller, Computer Go, Artificial Intelligence, v.134 n.1-2, p.145-179, January 2002
	Daphne Koller , Nimrod Megiddo , Bernhard von Stengel, Fast algorithms for finding randomized strategies in game trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.750-759, May 23-25, 1994, Montreal, Quebec, Canada
	G. E. Farr, The go polynomials of a graph, Theoretical Computer Science, v.306 n.1-3, p.1-18, 5 September 2003
	Bruno Bouzy , Tristan Cazenave, Computer Go: an AI oriented survey, Artificial Intelligence, v.132 n.1, p.39-103, October 2001
	Aviezri S. Fraenkel, Complexity, appeal and challenges of combinatorial games, Theoretical Computer Science, v.313 n.3, p.393-415, 19 February 2004
	Markus Holzer , Waltraud Holzer, Tantrix ^TM rotation puzzles are intractable, Discrete Applied Mathematics, v.144 n.3, p.345-358, 15 December 2004
	Sándor P. Fekete , Henk Meijer, The one-round Voronoi game replayed, Computational Geometry: Theory and Applications, v.30 n.2, p.81-94, February 2005
	Erik C. D. van der Werf , H. Jaap van den Herik , Jos W. H. M. Uiterwijk, Learning to score final positions in the game of Go, Theoretical Computer Science, v.349 n.2, p.168-183, 14 December 2005
	Elżbieta Sidorowicz, The game chromatic number and the game colouring number of cactuses, Information Processing Letters, v.102 n.4, p.147-151, May, 2007
	Ming Yu Hsieh , Shi-Chun Tsai, On the fairness and complexity of generalized k-in-a-row games, Theoretical Computer Science, v.385 n.1-3, p.88-100, October, 2007
	Graham Farr , Johannes Schmidt, On the number of Go positions on lattice graphs, Information Processing Letters, v.105 n.4, p.124-130, February, 2008
	Marcin Kozik, A finite set of functions with an EXPTIME-complete composition problem, Theoretical Computer Science, v.407 n.1-3, p.330-341, November, 2008
	Yasuhiko Takenaga , Shigeru Arai, PSPACE-completeness of an escape problem, Information Processing Letters, v.108 n.4, p.229-233, October, 2008
	Vincent Conitzer , Tüomas Sandholm, Complexity results about Nash equilibria, Proceedings of the 18th international joint conference on Artificial intelligence, p.765-771, August 09-15, 2003, Acapulco, Mexico
	Timothy Furtak , Masashi Kiyomi , Takeaki Uno , Michael Buro, Generalized amazons is PSPACE-complete, Proceedings of the 19th international joint conference on Artificial intelligence, p.132-137, July 30-August 05, 2005, Edinburgh, Scotland