A Cellular Automaton for Blocking Queen Games

Abstract : We show that the winning positions of a certain type of two-player game form interesting patterns which often defy analysis, yet can be computed by a cellular automaton. The game, known as Blocking Wythoff Nim, consists of moving a queen as in chess, but always towards (0,0), and it may not be moved to any of k−1 temporarily “blocked” positions specified on the previous turn by the other player. The game ends when a player wins by blocking all possible moves of the other player. The value of k is a parameter that defines the game, and the pattern of winning positions can be very sensitive to k. As k becomes large, parts of the pattern of winning positions converge to recurring chaotic patterns that are independent of k. The patterns for large k display an unprecedented amount of self-organization at many scales, and here we attempt to describe the self-organized structure that appears.
Type de document :
Communication dans un congrès
Jarkko Kari. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. Springer, Lecture Notes in Computer Science, LNCS-9099, pp.71-84, 2015, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-662-47221-7_6〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01442483
Contributeur : Hal Ifip <>
Soumis le : vendredi 20 janvier 2017 - 16:09:43
Dernière modification le : lundi 23 janvier 2017 - 15:54:48
Document(s) archivé(s) le : vendredi 21 avril 2017 - 15:57:20

Fichier

338243_1_En_6_Chapter.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Matthew Cook, Urban Larsson, Turlough Neary. A Cellular Automaton for Blocking Queen Games. Jarkko Kari. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. Springer, Lecture Notes in Computer Science, LNCS-9099, pp.71-84, 2015, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-662-47221-7_6〉. 〈hal-01442483〉

Partager

Métriques

Consultations de la notice

37

Téléchargements de fichiers

6