{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T16:06:25Z","timestamp":1773331585019,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540424963","type":"print"},{"value":"9783540446835","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_3","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"18-33","source":"Crossref","is-referenced-by-count":42,"title":["Playing Games with Algorithms: Algorithmic Combinatorial Game Theory"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"E. Berlekamp. The Dots and Boxes Game: Sophisticated Child\u2019s Play. A. K. Peter\u2019s Ltd., 2000.","DOI":"10.1201\/b14452"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"E. Berlekamp and D. Wolfe. Mathematical Go: Chilling Gets the Last Point. A. K. Peters, Ltd., 1994.","DOI":"10.1201\/9781439863558"},{"key":"3_CR3","volume-title":"Winning Ways","author":"E. R. Berlekamp","year":"1982","unstructured":"E. R. Berlekamp, J. H. Conway, and R. K. Guy. Winning Ways. Academic Press, London, 1982."},{"key":"3_CR4","unstructured":"T. C. Biedl, E. D. Demaine, M. L. Demaine, R. Fleischer, L. Jacobsen, and J. I. Munro. The complexity of Clickomania. In R. J. Nowakowski, ed., More Games of No Chance, 2001. To appear."},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2307\/1967631","volume":"3","author":"C. L. Bouton","year":"1901","unstructured":"C. L. Bouton. Nim, a game with a complete mathematical theory. Ann. of Math. (2), 3:35\u201339, 1901-02.","journal-title":"Ann. of Math. (2)"},{"key":"3_CR6","unstructured":"D. Bremner, J. O\u2019Rourke, and T. Shermer. Motion planning amidst movable square blocks is PSPACE complete. Draft, June 1994."},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"M. Buro. Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs. In Proc. 2nd Internat. Conf. Computers and Games, 2000.","DOI":"10.1007\/3-540-45579-5_17"},{"key":"3_CR8","volume-title":"On Numbers and Games","author":"J. H. Conway","year":"1976","unstructured":"J. H. Conway. On Numbers and Games. Academic Press, London, 1976."},{"key":"3_CR9","unstructured":"J. H. Conway. The angel problem. In R. J. Nowakowski, ed., Games of No Chance, pp. 1\u201312. Cambridge University Press, 1996."},{"key":"3_CR10","unstructured":"J. Culberson. Sokoban is PSPACE-complete. In Proc. Internat. Conf. Fun with Algorithms, pp. 65\u201376, Elba, Italy, June 1998."},{"key":"3_CR11","unstructured":"S. de Vries and R. Vohra. Combinatorial auctions: A survey. Manuscript, Jan. 2001. http:\/\/www-m9.ma.tum.de\/~devries\/combauctionsupplement\/comauction.pdf ."},{"key":"3_CR12","unstructured":"E. D. Demaine. Playing games with algorithms: Algorithmic combinatorial game theory. Preprint cs.CC\/0106019, Computing Research Repository. http:\/\/www.arXiv.org\/abs\/cs.CC\/0106019 ."},{"key":"3_CR13","unstructured":"E. D. Demaine, M. L. Demaine, and D. Eppstein. Phutball endgames are NP-hard. In R. J. Nowakowski, ed., More Games of No Chance, 2001. To appear. http:\/\/www.arXiv.org\/abs\/cs.CC\/0008025 ."},{"key":"3_CR14","unstructured":"E. D. Demaine, M. L. Demaine, and J. O\u2019Rourke. PushPush and Push-1 are NP-hard in 2D. In Proc. 12th Canadian Conf. Comput. Geom., pp. 211\u2013219, 2000. http:\/\/www.cs.unb.ca\/conf\/cccg\/eProceedings\/26.ps.gz ."},{"key":"3_CR15","unstructured":"E. D. Demaine, M. L. Demaine, and H. Verrill. Coin-moving puzzles. In MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 2000."},{"key":"3_CR16","unstructured":"E. D. Demaine and M. Hoffmann. Pushing blocks is NP-complete for noncrossing solution paths. In Proc. 13th Canadian Conf. Comput. Geom., 2001. To appear."},{"key":"3_CR17","unstructured":"A. Dhagat and J. O\u2019Rourke. Motion planning amidst movable square blocks. In Proc. 4th Canadian Conf. Comput. Geome., pp. 188\u2013191, 1992."},{"key":"3_CR18","unstructured":"D. Eppstein. Computational complexity of games and puzzles. http:\/\/www.ics.uci.edu\/~eppstein\/cgt\/hard.html ."},{"key":"3_CR19","unstructured":"J. Erickson. New Toads and Frogs results. In R. J. Nowakowski, ed., Games of No Chance, pp. 299\u2013310. Cambridge University Press, 1996."},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"G. W. Flake and E. B. Baum. Rush Hour is PSPACE-complete, or \u201cWhy you should generously tip parking lot attendants\u201d. Manuscript, 2001. http:\/\/www.neci.nj.nec.com\/homepages\/flake\/rushhour.ps .","DOI":"10.1016\/S0304-3975(01)00173-6"},{"key":"3_CR21","unstructured":"A. S. Fraenkel. Combinatorial games: Selected bibliography with a succinct gourmet introduction. Electronic Journal of Combinatorics, 1994. Dynamic Survey DS2, http:\/\/www.combinatorics.org\/Surveys\/ ."},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"A. S. Fraenkel, M. R. Garey, D. S. Johnson, T. Schaefer, and Y. Yesha. The complexity of checkers on an N \u00d7 N board-preliminary report. In Proc. 19th IEEE Sympos. Found. Comp. Sci., pp. 55\u201364, 1978.","DOI":"10.1109\/SFCS.1978.36"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0097-3165(81)90016-9","volume":"31","author":"A. S. Fraenkel","year":"1981","unstructured":"A. S. Fraenkel and D. Lichtenstein. Computing a perfect strategy for n \u00d7 n chess requires time exponential in n. J. Combin. Theory Ser. A, 31:199\u2013214, 1981.","journal-title":"J. Combin. Theory Ser. A"},{"key":"3_CR24","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979."},{"key":"3_CR25","first-page":"6","volume":"2","author":"P. M. Grundy","year":"1939","unstructured":"P. M. Grundy. Mathematics and games. Eureka, 2:6\u20138, Oct. 1939.","journal-title":"Eureka"},{"key":"3_CR26","unstructured":"R. K. Guy. Unsolved problems in combinatorial games. In R. J. Nowakowski, ed., Games of No Chance, pp. 475\u2013491. Cambridge University Press, 1996."},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1017\/S0305004100031509","volume":"52","author":"R. K. Guy","year":"1956","unstructured":"R. K. Guy and C. A. B. Smith. The G-values of various games. Proc. Cambridge Philos. Soc., 52:514\u2013526, 1956.","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"3_CR28","unstructured":"M. Hoffmann. Push-* is NP-hard. In Proc. 12th Canadian Conf. Comput. Geom., pp. 205\u2013210, 2000. http:\/\/www.cs.unb.ca\/conf\/cccg\/eProceedings\/13.ps.gz ."},{"key":"3_CR29","unstructured":"E. Hordern. Sliding Piece Puzzles. Oxford University Press, 1986."},{"issue":"2","key":"3_CR30","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF03025367","volume":"22","author":"R. Kaye","year":"2000","unstructured":"R. Kaye. Minesweeper is NP-complete. Math. Intelligencer, 22(2):9\u201315, 2000.","journal-title":"Math. Intelligencer"},{"key":"3_CR31","unstructured":"M. Lachmann, C. Moore, and I. Rapaport. Who wins domineering on rectangular boards? In MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 2000."},{"issue":"2","key":"3_CR32","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1145\/322186.322201","volume":"27","author":"D. Lichtenstein","year":"1980","unstructured":"D. Lichtenstein and M. Sipser. GO is polynomial-space hard. J. Assoc. Comput. Mach., 27(2):393\u2013401, Apr. 1980.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou. Algorithms, games, and the Internet. In Proc. 33rd ACM Sympos. Theory Comput., Crete, Greece, July 2001.","DOI":"10.1145\/380752.380883"},{"key":"3_CR34","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0747-7171(08)80001-6","volume":"10","author":"D. Ratner","year":"1990","unstructured":"D. Ratner and M. Warmuth. The (n 2-1)-puzzle and related relocation problems. J. Symbolic Comput., 10:111\u2013137, 1990.","journal-title":"J. Symbolic Comput."},{"key":"3_CR35","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00288964","volume":"15","author":"S. Reisch","year":"1981","unstructured":"S. Reisch. Hex ist PSPACE-vollst\u00e4ndig. Acta Inform., 15:167\u2013191, 1981.","journal-title":"Acta Inform."},{"key":"3_CR36","unstructured":"J. M. Robson. The complexity of Go. In Proceedings of the IFIP 9th World Computer Congress on Information Processing, pp. 413\u2013417, 1983."},{"key":"3_CR37","doi-asserted-by":"crossref","unstructured":"J. M. Robson. N by N Checkers is EXPTIME complete. SIAM J. Comput. 13(2):252\u2013267, May 1984.","DOI":"10.1137\/0213018"},{"key":"3_CR38","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0021-9800(66)80005-4","volume":"1","author":"C. A. B. Smith","year":"1966","unstructured":"C. A. B. Smith. Graphs and composite games. J. Combin. Theory, 1:51\u201381, 1966.","journal-title":"J. Combin. Theory"},{"key":"3_CR39","first-page":"438","volume":"41","author":"R. Sprague","year":"1935","unstructured":"R. Sprague. \u00dcber mathematische Kampfspiele. Tohoku Mathematical Journal, 41:438\u2013444, 1935-36.","journal-title":"Tohoku Mathematical Journal"},{"issue":"1","key":"3_CR40","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BF01530890","volume":"3","author":"G. Wilfong","year":"1991","unstructured":"G. Wilfong. Motion planning in the presence of movable obstacles. Ann. Math. Artificial Intelligence, 3(1):131\u2013150, 1991.","journal-title":"Ann. Math. Artificial Intelligence"},{"key":"3_CR41","unstructured":"D. Wolfe. Go endgames are PSPACE-hard. In R. J. Nowakowski, ed., More Games of No Chance, 2001. To appear."},{"key":"3_CR42","unstructured":"S. Wolfram. Cellular Automata and Complexity: Collected Papers. Perseus Press, 1994."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:27:47Z","timestamp":1556818067000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}