{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,11]],"date-time":"2025-03-11T04:20:20Z","timestamp":1741666820663,"version":"3.38.0"},"reference-count":44,"publisher":"SAGE Publications","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIC"],"published-print":{"date-parts":[[2024,6,19]]},"abstract":"<jats:p>We present an epistemic language for representing an artificial player\u2019s beliefs and actions in the context of the Y\u014dkai board game. Y\u014dkai is a cooperative game which requires a combination of Theory of Mind (ToM), temporal and spatial reasoning to be played effectively by an artificial agent. We show that the language properly accounts for these three dimensions and that its satisfiability problem is NP-complete. This opens up the possibility of exploiting SAT techniques for automating reasoning of an artificial player in the context of the Y\u014dkai board-game.<\/jats:p>","DOI":"10.3233\/aic-230050","type":"journal-article","created":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T16:37:11Z","timestamp":1701189431000},"page":"265-298","source":"Crossref","is-referenced-by-count":0,"title":["A logical modeling of the Y\u014dkai board game"],"prefix":"10.1177","volume":"37","author":[{"given":"Jorge","family":"Fernandez","sequence":"first","affiliation":[{"name":"IRIT, Universit\u00e9 de Toulouse, CNRS, Toulouse INP, UT3, France"}]},{"given":"Dominique","family":"Longin","sequence":"additional","affiliation":[{"name":"IRIT, Universit\u00e9 de Toulouse, CNRS, Toulouse INP, UT3, France"}]},{"given":"Emiliano","family":"Lorini","sequence":"additional","affiliation":[{"name":"IRIT, Universit\u00e9 de Toulouse, CNRS, Toulouse INP, UT3, France"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Maris","sequence":"additional","affiliation":[{"name":"IRIT, Universit\u00e9 de Toulouse, CNRS, Toulouse INP, UT3, France"}]}],"member":"179","reference":[{"key":"10.3233\/AIC-230050_ref1","doi-asserted-by":"crossref","unstructured":"S.\u00a0Ahmad, A.\u00a0Bryant, E.\u00a0Kleinman, Z.\u00a0Teng, T.-D.\u00a0Nguyen and M.S.\u00a0El-Nasr, Modeling individual and team behavior through spatio-temporal analysis, in: Proceedings of the Annual Symposium on Computer-Human Interaction in Play (CHI PLAY 2019), ACM, 2019, pp.\u00a0601\u2013612.","DOI":"10.1145\/3311350.3347188"},{"issue":"3","key":"10.3233\/AIC-230050_ref2","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1093\/logcom\/exq056","article-title":"Private announcement and belief expansion: An internal perspective","volume":"22","author":"Aucher","year":"2012","journal-title":"Journal of Logic and Computation"},{"key":"10.3233\/AIC-230050_ref3","unstructured":"G.\u00a0Aucher and T.\u00a0Bolander, Undecidability in epistemic planning, in: Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), AAAI Press, 2013, pp.\u00a027\u201333."},{"key":"10.3233\/AIC-230050_ref4","unstructured":"G.\u00a0Aucher and F.\u00a0Schwarzentruber, On the complexity of dynamic epistemic logic, in: Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013), 2013."},{"key":"10.3233\/AIC-230050_ref5","unstructured":"A.\u00a0Baltag, L.\u00a0Moss and S.\u00a0Solecki, The logic of public announcements, common knowledge and private suspicions, in: Proceedings of the Seventh Conference on Theoretical Aspects of Rationality and Knowledge (TARK\u201998), I.\u00a0Gilboa, ed., Morgan Kaufmann, San Francisco, CA, 1998, pp.\u00a043\u201356."},{"key":"10.3233\/AIC-230050_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2019.103216"},{"key":"10.3233\/AIC-230050_ref7","unstructured":"T.\u00a0Bolander, Seeing is believing: Formalising false-belief tasks in dynamic epistemic logic, in: Proceedings of the European Conference on Social Intelligence (ECSI-2014), A.\u00a0Herzig and E.\u00a0Lorini, eds, 2014, pp.\u00a087\u2013107."},{"issue":"1","key":"10.3233\/AIC-230050_ref8","doi-asserted-by":"publisher","first-page":"656","DOI":"10.3166\/jancl.21.9-34","article-title":"Epistemic planning for single- and multi-agent systems","volume":"21","author":"Bolander","year":"2011","journal-title":"Journal of Applied Non-Classical Logics"},{"issue":"1","key":"10.3233\/AIC-230050_ref9","doi-asserted-by":"publisher","first-page":"9","DOI":"10.3166\/jancl.21.9-34","article-title":"Epistemic planning for single- and multi-agent systems","volume":"21","author":"Bolander","year":"2011","journal-title":"Journal of Applied Non-Classical Logics"},{"key":"10.3233\/AIC-230050_ref10","unstructured":"T.\u00a0Bolander, M.\u00a0Holm Jensen and F.\u00a0Schwarzentruber, Complexity results in epistemic planning, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), AAAI Press, 2015, pp.\u00a02791\u20132797."},{"issue":"1","key":"10.3233\/AIC-230050_ref11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10849-015-9234-3","article-title":"Announcements to attentive agents","volume":"25","author":"Bolander","year":"2015","journal-title":"Journal of Logic, Language and Information"},{"issue":"6374","key":"10.3233\/AIC-230050_ref12","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1126\/science.aao1733","article-title":"Superhuman AI for heads-up no-limit poker: Libratus beats top professionals","volume":"359","author":"Brown","year":"2018","journal-title":"Science"},{"issue":"6456","key":"10.3233\/AIC-230050_ref13","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1126\/science.aay2400","article-title":"Superhuman AI for multiplayer poker","volume":"365","author":"Brown","year":"2019","journal-title":"Science"},{"issue":"1\u20132","key":"10.3233\/AIC-230050_ref14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0004-3702(01)00129-1","article-title":"Deep blue","volume":"134","author":"Campbell","year":"2002","journal-title":"Artificial Intelligence"},{"issue":"2","key":"10.3233\/AIC-230050_ref15","first-page":"215","article-title":"TD-gammon, a self-teaching backgammon program, achieves master-level play","volume":"6","author":"Campbell","year":"2002","journal-title":"Neural Computation"},{"key":"10.3233\/AIC-230050_ref16","doi-asserted-by":"crossref","unstructured":"T.\u00a0Caridroit, J.-M.\u00a0Lagniez, D.\u00a0Le Berre, T.\u00a0de\u00a0Lima and V.\u00a0Montmirail, A SAT-based approach for solving the modal logic S5-satisfiability problem, in: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), AAAI Press, 2017, pp.\u00a03864\u20133870.","DOI":"10.1609\/aaai.v31i1.11128"},{"key":"10.3233\/AIC-230050_ref17","unstructured":"M.C.\u00a0Cooper, A.\u00a0Herzig, F.\u00a0Maffre, F.\u00a0Maris and P.\u00a0R\u00e9gnier, A simple account of multi-agent epistemic planning, in: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), 2016, pp.\u00a0193\u2013201."},{"key":"10.3233\/AIC-230050_ref18","doi-asserted-by":"crossref","unstructured":"L.\u00a0Dissing and T.\u00a0Bolander, Implementing theory of mind on a robot using dynamic epistemic logic, in: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI 2020), ijcai.org, 2020, pp.\u00a01615\u20131621.","DOI":"10.24963\/ijcai.2020\/224"},{"key":"10.3233\/AIC-230050_ref19","doi-asserted-by":"crossref","unstructured":"M.\u00a0Eger and C.\u00a0Martens, Practical specification of belief manipulation in games, in: Proceedings of the Thirteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE-17), B.\u00a0Magerko and J.P.\u00a0Rowe, eds, AAAI Press, USA, 2017, pp.\u00a030\u201336.","DOI":"10.1609\/aiide.v13i1.12921"},{"key":"10.3233\/AIC-230050_ref20","doi-asserted-by":"publisher","DOI":"10.1109\/CIG.2017.8080417"},{"key":"10.3233\/AIC-230050_ref21","doi-asserted-by":"crossref","unstructured":"R.\u00a0Fagin, J.\u00a0Halpern, Y.\u00a0Moses and M.\u00a0Vardi, Reasoning About Knowledge, MIT Press, Cambridge, 1995.","DOI":"10.7551\/mitpress\/5803.001.0001"},{"key":"10.3233\/AIC-230050_ref22","unstructured":"J.N.\u00a0Foerster, H.F.\u00a0Song, E.\u00a0Hughes, N.\u00a0Burch, I.\u00a0Dunning, S.\u00a0Whiteson, M.M.\u00a0Botvinick and M.\u00a0Bowling, Bayesian action decoder for deep multi-agent reinforcement learning, in: Proceedings of the 36th International Conference on Machine Learning, (ICML 2019), Proceedings of Machine Learning Research, Vol.\u00a097, PMLR, 2019, pp.\u00a01942\u20131951."},{"key":"10.3233\/AIC-230050_ref23","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1023\/A:1008222603071","article-title":"Reasoning about information change","volume":"6","author":"Gerbrandy","year":"1997","journal-title":"Journal of Logic, Language, and Information"},{"issue":"2","key":"10.3233\/AIC-230050_ref24","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0004-3702(92)90049-4","article-title":"A guide to completeness and complexity for modal logics of knowledge and belief","volume":"54","author":"Halpern","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.3233\/AIC-230050_ref25","doi-asserted-by":"crossref","unstructured":"F.\u00a0Kominis and H.\u00a0Geffner, Beliefs in multiagent planning: From one agent to many, in: Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), R.I.\u00a0Brafman, C.\u00a0Domshlak, P.\u00a0Haslum and S.\u00a0Zilberstein, eds, AAAI Press, 2015, pp.\u00a0147\u2013155.","DOI":"10.1609\/icaps.v25i1.13726"},{"key":"10.3233\/AIC-230050_ref26","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i05.6208"},{"issue":"3","key":"10.3233\/AIC-230050_ref27","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1007\/s11229-015-0960-5","article-title":"A minimal logic for interactive epistemology","volume":"193","author":"Lorini","year":"2016","journal-title":"Synthese"},{"key":"10.3233\/AIC-230050_ref28","doi-asserted-by":"crossref","unstructured":"E.\u00a0Lorini, In praise of belief bases: Doing epistemic logic without possible worlds, in: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), AAAI Press, USA, 2018, pp.\u00a01915\u20131922.","DOI":"10.1609\/aaai.v32i1.11560"},{"key":"10.3233\/AIC-230050_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103233"},{"key":"10.3233\/AIC-230050_ref30","unstructured":"E.\u00a0Lorini and F.\u00a0Romero, Decision procedures for epistemic logic exploiting belief bases, in: Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), IFAAMAS, USA, 2019, pp.\u00a0944\u2013952."},{"issue":"4","key":"10.3233\/AIC-230050_ref31","doi-asserted-by":"publisher","first-page":"478","DOI":"10.3390\/g1040478","article-title":"A modal logic of epistemic games","volume":"1","author":"Lorini","year":"2010","journal-title":"Games"},{"key":"10.3233\/AIC-230050_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24130-7_13"},{"key":"10.3233\/AIC-230050_ref33","doi-asserted-by":"publisher","DOI":"10.1145\/1160633.1160657"},{"issue":"6624","key":"10.3233\/AIC-230050_ref34","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1126\/science.ade9097","article-title":"Human-level play in the game of Diplomacy by combining language models with strategic reasoning","volume":"378","author":"Bakhtin","year":"2022","journal-title":"Science"},{"key":"10.3233\/AIC-230050_ref35","doi-asserted-by":"crossref","unstructured":"C.\u00a0Muise, V.\u00a0Belle, P.\u00a0Felli, S.A.\u00a0McIlraith, T.\u00a0Miller, A.R.\u00a0Pearce and L.\u00a0Sonenberg, Planning over multi-agent epistemic states: A classical planning approach, in: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), AAAI Press, 2015, pp.\u00a03327\u20133334.","DOI":"10.1609\/aaai.v29i1.9665"},{"key":"10.3233\/AIC-230050_ref37","unstructured":"H.\u00a0Osawa, Solving hanabi: Estimating hands by opponent\u2019s actions in cooperative game with incomplete information, in: Papers from the 2015 AAAI Workshop on Computer Poker and Imperfect Information, AAAI Technical Report, Vol. WS-15-07, AAAI Press, 2015."},{"key":"10.3233\/AIC-230050_ref38","unstructured":"J.A.\u00a0Plaza, Logics of public communications, in: Proceedings of the 4th International Symposium on Methodologies for Intelligent Systems, M.\u00a0Emrich, M.\u00a0Pfeifer, M.\u00a0Hadzikadic and Z.\u00a0Ras, eds, 1989, pp.\u00a0201\u2013216."},{"issue":"6","key":"10.3233\/AIC-230050_ref39","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/s10992-009-9116-8","article-title":"Logical theories of intention and the database perspective","volume":"38","author":"Shoham","year":"2009","journal-title":"Journal of Philosophical Logic"},{"issue":"7587","key":"10.3233\/AIC-230050_ref40","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1038\/nature16961","article-title":"Mastering the game of Go with deep neural networks and tree search","volume":"529","author":"Silver","year":"2016","journal-title":"Nature"},{"issue":"7676","key":"10.3233\/AIC-230050_ref41","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1038\/nature24270","article-title":"Mastering the game of Go without human knowledge","volume":"550","author":"Silver","year":"2017","journal-title":"Nature"},{"issue":"1","key":"10.3233\/AIC-230050_ref42","doi-asserted-by":"publisher","first-page":"52","DOI":"10.3390\/g2010052","article-title":"Toward a theory of play: A logical perspective on games and interaction","volume":"2","author":"van Benthem","year":"2011","journal-title":"Games"},{"key":"10.3233\/AIC-230050_ref43","doi-asserted-by":"crossref","unstructured":"M.J.H.\u00a0van den Bergh, A.\u00a0Hommelberg, W.A.\u00a0Kosters and F.M.\u00a0Spieksma, Aspects of the cooperative card game Hanabi, in: Proceedings of the 28th Benelux Conference on Artificial Intelligence (BNAIC 2016), Revised Selected Papers, Communications in Computer and Information Science, Vol.\u00a0765, Springer, 2016, pp.\u00a093\u2013105.","DOI":"10.1007\/978-3-319-67468-1_7"},{"key":"10.3233\/AIC-230050_ref44","doi-asserted-by":"crossref","unstructured":"H.P.\u00a0van Ditmarsch, W.\u00a0van der Hoek and B.\u00a0Kooi, Dynamic Epistemic Logic, Kluwer Academic Publishers, N.-Y, 2007. ISBN 1402058381.","DOI":"10.1007\/978-1-4020-5839-4"},{"key":"10.3233\/AIC-230050_ref45","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2017.7969465"}],"container-title":["AI Communications"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/AIC-230050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T14:55:25Z","timestamp":1741618525000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.medra.org\/servlet\/aliasResolver?alias=iospress&doi=10.3233\/AIC-230050"}},"subtitle":[],"editor":[{"given":"Zied","family":"Bouraoui","sequence":"additional","affiliation":[]},{"given":"Ana\u00eblle","family":"Wilczynski","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2024,6,19]]},"references-count":44,"journal-issue":{"issue":"3"},"URL":"https:\/\/doi.org\/10.3233\/aic-230050","relation":{},"ISSN":["1875-8452","0921-7126"],"issn-type":[{"type":"electronic","value":"1875-8452"},{"type":"print","value":"0921-7126"}],"subject":[],"published":{"date-parts":[[2024,6,19]]}}}