{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:50:14Z","timestamp":1760233814083,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2021,2,24]],"date-time":"2021-02-24T00:00:00Z","timestamp":1614124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Custodian capture occurs when a player has placed two of his pieces on the opposite sides of an orthogonal line of the opponent\u2019s men. Each piece moves like the rook in Chess. Different cultures played it from pre-modern times in two-player strategy board games, Ludus Latrunculorum (Kowalski\u2019s reconstruction), Hasami shogi in Japan, Mak-yek in Thailand and Myanmar, Ming Mang in Tibet, and so on. We prove that a custodian capture game on n\u00d7n square board is EXPTIME hard if the first player to capture five or more men in total wins.<\/jats:p>","DOI":"10.3390\/a14030070","type":"journal-article","created":{"date-parts":[[2021,2,24]],"date-time":"2021-02-24T20:53:21Z","timestamp":1614200001000},"page":"70","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["EXPTIME Hardness of an n by n Custodian Capture Game"],"prefix":"10.3390","volume":"14","author":[{"given":"Fumitaka","family":"Ito","sequence":"first","affiliation":[{"name":"Department of Science and Engineering, Tokyo Denki University, Tokyo 120-8551, Japan"}]},{"given":"Masahiko","family":"Naito","sequence":"additional","affiliation":[{"name":"Department of Science and Engineering, Tokyo Denki University, Tokyo 120-8551, Japan"}]},{"given":"Naoyuki","family":"Katabami","sequence":"additional","affiliation":[{"name":"Department of Science and Engineering, Tokyo Denki University, Tokyo 120-8551, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7997-6633","authenticated-orcid":false,"given":"Tatsuie","family":"Tsukiji","sequence":"additional","affiliation":[{"name":"Graduate School of Advanced Science and Technology, Tokyo Denki University, Tokyo 120-8551, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,24]]},"reference":[{"key":"ref_1","unstructured":"Bell, R.C. (1979). Board and Table Games from Many Civilizations, Courier Corporation."},{"key":"ref_2","unstructured":"Parlett, D. (1999). The Oxford History of Board Games, Oxford University Press."},{"key":"ref_3","unstructured":"Murray, H.J.R. (1913). A History of Chess, Clarendon Press."},{"key":"ref_4","unstructured":"Murray, H.J.R. (1952). A History of Board-Games Other than Chess, Clarendon Press."},{"key":"ref_5","unstructured":"Franklin, M.J. (2000). Asiatick Researches, Or, Transactions of the Society Instituted in Bengal, for Inquiring Into the History and Antiquities, the Arts, Sciences, and Literature of Asia, Taylor & Francis."},{"key":"ref_6","unstructured":"Shotwell, P. (2021, February 23). A Form of Tibetan Mig-Mang From the West. Available online: https:\/\/studylib.net\/doc\/6753073\/a-form-of-tibetan-mig-mang-from-the-west."},{"key":"ref_7","unstructured":"Helmfrid, S. (2021, February 23). Hnefatafl-the Strategic Board Game of the Vikings. Available online: http:\/\/hem.bredband.net\/b512479\/."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0097-3165(81)90016-9","article-title":"Computing a perfect strategy for n\u00d7 n chess requires time exponential in n","volume":"31","author":"Fraenkel","year":"1981","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/0213018","article-title":"N by N checkers is Exptime complete","volume":"13","author":"Robson","year":"1984","journal-title":"SIAM J. Comput."},{"key":"ref_10","unstructured":"Robson, J.M. (1983, January 19\u201323). The complexity of Go. Proceedings of the IFIP 9th World Computer Congress, Paris, France."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Arora, S., and Barak, B. (2009). Computational Complexity: A Modern Approach, Cambridge University Press.","DOI":"10.1017\/CBO9780511804090"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Hearn, R.A., and Demaine, E.D. (2009). Games, Puzzles, and Computation, CRC Press.","DOI":"10.1201\/b10581"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1145\/322186.322201","article-title":"Go is polynomial-space hard","volume":"27","author":"Lichtenstein","year":"1980","journal-title":"J. ACM (JACM)"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Cr\u00e2\u015fmaru, M., and Tromp, J. (2000, January 26\u201328). Ladders are PSPACE-complete. Proceedings of the International Conference on Computers and Games, Hamamatsu, Japan.","DOI":"10.1007\/3-540-45579-5_16"},{"key":"ref_15","first-page":"125","article-title":"Go endgames are PSPACE-hard","volume":"42","author":"Wolfe","year":"2002","journal-title":"More Games No Chanc."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Saffidine, A., Teytaud, O., and Yen, S.J. (2015). Go Complexities. Advances in Computer Games, Springer.","DOI":"10.1007\/978-3-319-27992-3_8"},{"key":"ref_17","unstructured":"Zhang, Z. (2019). A Note on Computational Complexity of Kill-all Go. arXiv."},{"key":"ref_18","unstructured":"Robson, J.M. (1984, January 3\u20137). Combinatorial games with exponential space complete decision problems. Proceedings of the International Symposium on Mathematical Foundations of Computer Science, Praha, Czechoslovakia."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., and Stockmeyer, L.J. (1976, January 25\u201327). Alternation. Proceedings of the 17th Annual Symposium on Foundations of Computer Science (sfcs 1976), Houston, TX, USA.","DOI":"10.1109\/SFCS.1976.4"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1137\/0208013","article-title":"Provably difficult combinatorial games","volume":"8","author":"Stockmeyer","year":"1979","journal-title":"SIAM J. Comput."},{"key":"ref_21","first-page":"1843","article-title":"Shogi on n \u00d7 n board is complete in exponential time","volume":"70","author":"Adachi","year":"1987","journal-title":"Trans. IEICE"},{"key":"ref_22","unstructured":"Zhang, Z. (2019). A Note on Hardness Frameworks and Computational Complexity of Xiangqi and Janggi. arXiv."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Mishiba, S., and Takenaga, Y. (2020). QUIXO is EXPTIME-complete. Inf. Process. Lett., 162.","DOI":"10.1016\/j.ipl.2020.105995"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s00224-003-1105-7","article-title":"Games with uniqueness properties","volume":"37","author":"Aida","year":"2004","journal-title":"Theory Comput. Syst."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/70\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:27:56Z","timestamp":1760160476000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,24]]},"references-count":24,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["a14030070"],"URL":"https:\/\/doi.org\/10.3390\/a14030070","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,2,24]]}}}