{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T18:03:07Z","timestamp":1742925787701,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319091648"},{"type":"electronic","value":"9783319091655"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09165-5_15","type":"book-chapter","created":{"date-parts":[[2014,7,11]],"date-time":"2014-07-11T13:56:50Z","timestamp":1405087010000},"page":"175-186","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Havannah and TwixT are PSPACE-complete"],"prefix":"10.1007","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[]},{"given":"Florian","family":"Jamain","sequence":"additional","affiliation":[]},{"given":"Abdallah","family":"Saffidine","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,7,12]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Anshelevich, V.V.: A hierarchical approach to computer Hex. Artif. Intell. 134 (1\u20132), 101\u2013120 (2002)","DOI":"10.1016\/S0004-3702(01)00154-0"},{"issue":"4","key":"15_CR2","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1109\/TCIAIG.2010.2067212","volume":"2","author":"B Arneson","year":"2010","unstructured":"Arneson, B., Hayward, R.B., Henderson, P.: Monte Carlo tree search in Hex. IEEE Trans. Comput. Intell. AI Games 2(4), 251\u2013258 (2010)","journal-title":"IEEE Trans. Comput. Intell. AI Games"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rnsson, Y., Hayward, R., Johanson, M., van Rijswijck, J.: Dead cell analysis in Hex and the Shannon game. In: Bondy, A., Fonlupt, J., Fouquet, J.-L., Fournier, J.-C., Alfons\u00edn, J.L.R. (eds.) Graph Theory in Paris, pp. 45\u201359. Springer-Birkh\u00e4user, Basel (2007)","DOI":"10.1007\/978-3-7643-7400-6_5"},{"key":"15_CR4","unstructured":"Bonnet, \u00c9., Jamain, F., Saffidine, A.: On the complexity of trick-taking card games. In: Rossi, F. (ed.) 23rd International Joint Conference on Artificial Intelligence (IJCAI), Beijing, China, August 2013. AAAI Press"},{"key":"15_CR5","volume-title":"Connection Games: Variations on a Theme","author":"C Browne","year":"2005","unstructured":"Browne, C.: Connection Games: Variations on a Theme. AK Peters, Natick (2005)"},{"issue":"1","key":"15_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TCIAIG.2012.2186810","volume":"4","author":"C Browne","year":"2012","unstructured":"Browne, C., Powley, E., Whitehouse, D., Lucas, S., Cowling, P., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., Colton, S.: A survey of Monte Carlo tree search methods. IEEE Trans. Comput. Intell. AI Games 4(1), 1\u201343 (2012)","journal-title":"IEEE Trans. Comput. Intell. AI Games"},{"issue":"1","key":"15_CR7","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1109\/TCT.1970.1083056","volume":"17","author":"J Bruno","year":"1970","unstructured":"Bruno, J., Weinberg, L.: A constructive graph-theoretic solution of the Shannon switching game. IEEE Trans. Circ. Theory 17(1), 74\u201381 (1970)","journal-title":"IEEE Trans. Circ. Theory"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1017\/CBO9780511807251.002","volume-title":"Games of No Chance III","author":"ED Demaine","year":"2009","unstructured":"Demaine, E.D., Hearn, R.A.: Playing games with algorithms: algorithmic combinatorial game theory. In: Nowakowski, R.J. (ed.) Games of No Chance III, pp. 3\u201356. Cambridge University Press, Cambridge (2009)"},{"issue":"4","key":"15_CR9","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1145\/321978.321989","volume":"23","author":"S Even","year":"1976","unstructured":"Even, S., Tarjan, R.E.: A combinatorial problem which is complete in polynomial space. J. ACM (JACM) 23(4), 710\u2013719 (1976)","journal-title":"J. ACM (JACM)"},{"key":"15_CR10","unstructured":"Ewalds, T.: Playing and solving Havannah. Master\u2019s thesis, University of Alberta (2012)"},{"key":"15_CR11","unstructured":"Furtak, T., Kiyomi, M., Uno, T., Buro, M.: Generalized Amazons is PSPACE-complete. In: Kaelbling, L.P., Saffiotti, A. (eds.) 19th International Joint Conference on Artificial Intelligence (IJCAI), pp. 132\u2013137 (2005)"},{"key":"15_CR12","doi-asserted-by":"crossref","DOI":"10.1201\/b10581","volume-title":"Games, Puzzles, and Computation","author":"RA Hearn","year":"2009","unstructured":"Hearn, R.A., Demaine, E.D.: Games, Puzzles, and Computation. AK Peters, Natick (2009)"},{"key":"15_CR13","unstructured":"Huber, J.R.: Computer game playing: the game of Twixt. Master\u2019s thesis, Rochester Institute of Technology (1983)"},{"key":"15_CR14","unstructured":"Kiefer, S.: Die Menge der virtuellen Verbindungen im Spiel Hex ist PSPACE-vollst\u00e4ndig. Studienarbeit Nr. 1887, Universit\u00e4t Stuttgart, July 2003"},{"issue":"2","key":"15_CR15","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1145\/322186.322201","volume":"27","author":"D Lichtenstein","year":"1980","unstructured":"Lichtenstein, D., Sipser, M.: Go is polynomial-space hard. J. ACM (JACM) 27(2), 393\u2013401 (1980)","journal-title":"J. ACM (JACM)"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-642-17928-0_10","volume-title":"Computers and Games","author":"RJ Lorentz","year":"2011","unstructured":"Lorentz, R.J.: Improving Monte\u2013Carlo tree search in Havannah. In: van den Herik, H.J., Iida, H., Plaat, A. (eds.) CG 2010. LNCS, vol. 6515, pp. 105\u2013115. Springer, Heidelberg (2011)"},{"key":"15_CR17","unstructured":"Maarup, T.: Hex: everything you always wanted to know about Hex but were afraid to ask. Master\u2019s thesis, Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark (2005)"},{"key":"15_CR18","unstructured":"Mazzoni, D., Watkins, K.: Uncrossed knight paths is NP-complete (1997). http:\/\/www.cs.cmu.edu\/~kw\/pubs\/Twixt_Proof_Draft.txt"},{"key":"15_CR19","unstructured":"Moesker, K.: Twixt: theory, analysis and implementation. Master\u2019s thesis, Maastricht University (2009)"},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00288964","volume":"15","author":"S Reisch","year":"1981","unstructured":"Reisch, S.: Hex ist PSPACE-vollst\u00e4ndig. Acta Inform. 15, 167\u2013191 (1981)","journal-title":"Acta Inform."},{"issue":"2","key":"15_CR21","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"TJ Schaefer","year":"1978","unstructured":"Schaefer, T.J.: On the complexity of some two-person perfect-information games. J. Comput. Syst. Sci. 16(2), 185\u2013225 (1978)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-642-12993-3_7","volume-title":"Advances in Computer Games","author":"F Teytaud","year":"2010","unstructured":"Teytaud, F., Teytaud, O.: Creating an upper-confidence-tree program for Havannah. In: van den Herik, H.J., Spronck, P. (eds.) ACG 2009. LNCS, vol. 6048, pp. 65\u201374. Springer, Heidelberg (2010)"},{"key":"15_CR23","unstructured":"Uiterwijk, J., Moesker, K.: Mathematical modelling in Twixt. In: L\u00f6we, B. (ed.) Logic and the Simulation of Interaction and Reasoning, pp. 29 (2009)"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"M.H.M, Winands, Bj\u00f6rnsson, Y., Saito, J.-T.: Monte Carlo tree search in lines of action. IEEE Trans. Comput. Intell. AI Games 2(4), 239\u2013250 (2010)","DOI":"10.1109\/TCIAIG.2010.2061050"}],"container-title":["Lecture Notes in Computer Science","Computers and Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09165-5_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T01:50:13Z","timestamp":1675821013000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-09165-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319091648","9783319091655"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09165-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"12 July 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}