Header

UZH-Logo

Maintenance Infos

A cellular automaton for blocking queen games


Cook, Matthew; Larsson, Urban; Neary, Turlough (2017). A cellular automaton for blocking queen games. Natural Computing, 16(3):397-410.

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-1k-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. This paper extends a previous study (Cook et al. in Cellular automata and discrete complex systems, AUTOMATA 2015, Lecture Notes in Computer Science, vol 9099, pp 71–84, 2015), containing further analysis and new insights into the long term behaviour and structures generated by our blocking queen cellular automaton.

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-1k-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. This paper extends a previous study (Cook et al. in Cellular automata and discrete complex systems, AUTOMATA 2015, Lecture Notes in Computer Science, vol 9099, pp 71–84, 2015), containing further analysis and new insights into the long term behaviour and structures generated by our blocking queen cellular automaton.

Statistics

Citations

Altmetrics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Neuroinformatics
Dewey Decimal Classification:570 Life sciences; biology
Language:English
Date:2017
Deposited On:01 Mar 2018 11:54
Last Modified:14 Mar 2018 18:01
Publisher:Springer
Number of Pages:14
ISSN:1567-7818
OA Status:Closed
Publisher DOI:https://doi.org/10.1007/s11047-016-9581-2
Related URLs:http://www.zora.uzh.ch/id/eprint/121806/

Download

Full text not available from this repository.
View at publisher