Abstract
Previous studies of the Iterated Prisoner’s Dilemma Game (IPDG) focus on the optimal strategies for accumulating points against another player or the evolution of cooperation. Instead, this paper expands upon the possible complexity in interactions by using a Cellular Automaton (CA) model to simulate large numbers of players competing within a limited space. Unlike previous works, we introduce a method for creating a wide variety of deterministic rules by mapping each possible interaction to a binary number. We then prove the computational universality of the resulting IPDG CA. An analysis of the number of interactions leads to the discovery of interesting properties when allowing only enough iterations for a strategy to use its “transient” instructions. The implications of universal computation (UC) are also discussed.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Dresher, M.: Games of Strategy: Theory and Applications. Pren Hal. Appl. Math. Pren. Hal. (1961)
Axelrod, R.: The Evolution of Cooperation. Basic Books (1984)
Wolfram, S.: A New Kind of Science. Wolfram Media (2002)
Nowak, M.A., May, R.M., Sigmund, K.: The arithmetics of mutual help. Sci. Am. 272(6), 76 (1995)
Nakamaru, M., Matsuda, H., Iwasa, Y.: The evolution of cooperation in a lattice-structured population. J. of Theor. Bio. 184(1), 65–81 (1997)
Brauchli, K., Killingback, T., Doebeli, M.: Evolution of cooperation in spatially structured populations. J. Theor. Bio. 200(4), 405–417 (1999)
Szabó, G., Antal, T., Szabó, P., Droz, M.: Spatial evolutionary prisoners dilemma game with three strategies and external constraints. Phys. Rev. E 62(1), 1095 (2000)
Newth, D., Cornforth, D.: Asynchronous spatial evolutionary games. Biosystems 95(2), 120–129 (2009)
Tanimoto, J., Sagara, H.: A study on emergence of alternating reciprocity in a 2 ×2 game with 2-length memory strategy. Biosystems 90(3), 728–737 (2007)
Gelimson, A., Cremer, J., Frey, E.: Mobility, fitness collection, and the breakdown of cooperation. Phys. Rev. E 87(4), 042711 (2013)
Alonso-Sanz, R.: The historic prisoner’s dilemma. Int. J. Bifurcat. Chaos 9(06), 1197–1210 (1999)
Alonso-Sanz, R.: Memory versus spatial disorder in the support of cooperation. Biosystems 97(2), 90–102 (2009)
Pereira, M.A., Martinez, A.S.: Pavlovian prisoner’s dilemma-analytical results, the quasi-regular phase and spatio-temporal patterns. J. Theor. Biol. 265(3), 346–358 (2010)
Berlekamp, E., Conway, J., Guy, R.: Winning Ways for Your Mathematical Plays, vol. 4. A.K. Peters (2004)
Nakayama, B.: Universal computation in the prisoner’s dilemma game. Undergraduate honors thesis, Regis U (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Nakayama, B., Bahr, D. (2014). Universal Computation in the Prisoner’s Dilemma Game. In: Ibarra, O., Kari, L., Kopecki, S. (eds) Unconventional Computation and Natural Computation. UCNC 2014. Lecture Notes in Computer Science(), vol 8553. Springer, Cham. https://doi.org/10.1007/978-3-319-08123-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-08123-6_24
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08122-9
Online ISBN: 978-3-319-08123-6
eBook Packages: Computer ScienceComputer Science (R0)