Slime mould games based on rough set theory

Pancerz, K. ; Schumann, A.

International Journal of Applied Mathematics and Computer Science, Tome 28 (2018) no. 3, pp. 531-544.

Résumé

We define games on the medium of plasmodia of slime mould, unicellular organisms that look like giant amoebae. The plasmodia try to occupy all the food pieces they can detect. Thus, two different plasmodia can compete with each other. In particular, we consider game-theoretically how plasmodia of Physarum polycephalum and Badhamia utricularis fight for food. Placing food pieces at different locations determines the behavior of plasmodia. In this way, we can program the plasmodia of Physarum polycephalum and Badhamia utricularis by placing food, and we can examine their motion as a Physarum machine—an abstract machine where states are represented as food pieces and transitions among states are represented as movements of plasmodia from one piece to another. Hence, this machine is treated as a natural transition system. The behavior of the Physarum machine in the form of a transition system can be interpreted in terms of rough set theory that enables modeling some ambiguities in motions of plasmodia. The problem is that there is always an ambiguity which direction of plasmodium propagation is currently chosen: one or several concurrent ones, i.e., whether we deal with a sequential, concurrent or massively parallel motion. We propose to manage this ambiguity using rough set theory. Firstly, we define the region of plasmodium interest as a rough set; secondly, we consider concurrent transitions determined by these regions as a context-based game; thirdly, we define strategies in this game as a rough set; fourthly, we show how these results can be interpreted as a Go game.

Détail

Keywords: slime mould game, Physarum machine, transition system, rough set theory, simulation software
Mots-clés : system przejściowy, teoria zbiorów przybliżonych, oprogramowanie symulacyjne

Bibliographie

[1] Abramsky, S. and Jagadeesan, R. (1994). Games and full completeness for multiplicative linear logic, The Journal of Symbolic Logic 59(2): 543–574.

[2] Abramsky, S. and Mellies, P.-A. (1999). Concurrent games and full completeness, Proceedings of the 14th Symposium on Logic in Computer Science, Trento, Italy, pp. 431–442.

[3] Aczel, P. (1988). Non-Well-Founded Sets, Cambridge University Press, Cambridge.

[4] Adamatzky, A. (2007a). Physarum machine: Implementation of a Kolmogorov–Uspensky machine on a biological substrate, Parallel Processing Letters 17(04): 455–467.

[5] Adamatzky, A. (2007b). Physarum machines: Encapsulating reaction–diffusion to compute spanning tree, Die Naturwissenschaften 94(12): 975–980.

[6] Adamatzky, A. (2010). Physarum Machines: Computers from Slime Mould, World Scientific, Singapore.

[7] Baillot, P., Danos, V., Ehrhard, T. and Regnier, L. (1997). Believe it or not, AJM’s games is a model of classical linear logic, Proceedings of the 12th Symposium on Logic in Computer Science, Warsaw, Poland, pp. 68–75.

[8] Bouyer, P., Brenguier, R., Markey, N. and Ummels, M. (2011). Nash equilibria in concurrent games with Büchi objectives, Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Mumbai, India, pp. 375–386.

[9] Bouyer, P., Brenguier, R., Markey, N. and Ummels, M. (2012). Concurrent games with ordered objectives, in L. Birkedal (Ed.), Foundations of Software Science and Computational Structures, Springer, Berlin, pp. 301–315.

[10] Brenguier, R. (2013). PRALINE: A tool for computing Nash equilibria in concurrent games, in N. Sharygina and H. Veith (Eds.), Computer Aided Verification, Springer, Berlin, pp. 890–895.

[11] Clempner, J. (2006). Modeling shortest path games with Petri nets: A Lyapunov based theory, International Journal of Applied Mathematics and Computer Science 16(3): 387–397.

[12] Henzinger, T.A., Manna, Z. and Pnueli, A. (1992). Timed transition systems, in J.W. de Bakker et al. (Eds.), REX 1991, Lecture Notes in Computer Science, Vol. 600, Springer, Berlin/Heidelberg, pp. 226–251.

[13] Khrennikov, A. and Schumann, A. (2014). Quantum non-objectivity from performativity of quantum phenomena, Physica Scripta 2014(T163): 014–020.

[14] Kim, J. and Jeong, S. (1994). Learn to Play Go, Good Move Press, New York, NY.

[15] Nakagaki, T., Yamada, H. and Toth, A. (2000). Maze-solving by an amoeboid organism, Nature 407(6803): 470–470.

[16] Neubert, H., Nowotny, W., Baumann, K. and Marx, H. (1995). Die Myxomyceten Deutschlands und des angrenzenden Alpenraumes unter besonderer Berücksichtigung Österreichs. Band 2: Physarales, Karlheinz Baumann Verlag, Gomaringen.

[17] Pancerz, K. and Schumann, A. (2015). Rough set models of Physarum machines, International Journal of General Systems 44(3): 314–325.

[18] Pancerz, K. and Schumann, A. (2017). Rough set description of strategy games on Physarum machines, in A. Adamatzky (Ed.), Advances in Unconventional Computing, Volume 2: Prototypes, Models and Algorithms, Emergence, Complexity and Computation, Vol. 23, Springer, Cham, pp. 615–636.

[19] Pawlak, Z. (1991). Rough Sets. Theoretical Aspects of Reasoning about Data, Kluwer, Dordrecht.

[20] Petri, R.J. (1887). Eine kleine modification des Koch’schen Plattenverfahrens, Centralblatt f¨ur Bakteriologie und Parasitenkunde 1: 279–280.

[21] Saipara, P. and Kumam, P. (2016). Fuzzy games for a general Bayesian abstract fuzzy economy model of product measurable spaces, Mathematical Methods in the Applied Sciences 39(16): 4810–4819.

[22] Schumann, A. (2014). Payoff cellular automata and reflexive games, Journal of Cellular Automata 9(4): 287–313.

[23] Schumann, A. (2016). Syllogistic versions of Go games on Physarum, in A. Adamatzky (Ed.), Advances in Physarum Machines: Sensing and Computing with Slime Mould, Emergence, Complexity and Computation, Vol. 21, Springer, Cham, pp. 651–685.

[24] Schumann, A. and Pancerz, K. (2015). A rough set version of the Go game on Physarum machines, Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies, New York, NY, USA, pp. 446–452.

[25] Schumann, A., Pancerz, K., Adamatzky, A. and Grube, M. (2014). Bio-inspired game theory: The case of Physarum polycephalum, Proceedings of the 8th International Conference on Bio-inspired Information and Communications Technologies, Boston, MA, USA, pp. 9–16.

[26] Trejo, K., Clempner, J. and Poznyak, A. (2015). Computing the Stackelberg/Nash equilibria using the extraproximal method: Convergence analysis and implementation details for Markov chains games, International Journal of Applied Mathematics and Computer Science 25(2): 337–351, DOI: 10.1515/amcs-2015-0026.

[27] Winskel, G. and Nielsen, M. (1995). Models for concurrency, in S. Abramsky et al. (Eds.), Handbook of Logic in Computer Science, Vol. 4, Oxford University Press, Oxford, pp. 1–148.

[28] Yao, Y. and Lin, T. (1996). Generalization of rough sets using modal logics, Intelligent Automation and Soft Computing 2(2): 103–120.

[29] Yao, Y.Y., Wong, S.K.M. and Lin, T.Y. (1997). A review of rough set models, in T.Y. Lin and N. Cercone (Eds.), Rough Sets and Data Mining: Analysis of Imprecise Data, Kluwer, Dordrecht, pp. 47–75.

[30] Ziarko, W. (1993). Variable precision rough set model, Journal of Computer and System Sciences 46(1): 39–59.