A cellular automaton for blocking queen games

DOI10.1007/978-3-662-47221-7_6MaRDI QIDQ5500614zbMATH OpenOpenAlexFDO

Authors Matthew Cook, Urban Larsson, Turlough Neary

Publication date 7 August 2015

Published in Cellular Automata and Discrete Complex Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.01431

Cellular automata (computational aspects) (68Q80) Combinatorial games (91A46)

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 {em 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.

Recommendations

Cited in

(4)

This page was built for publication: A cellular automaton for blocking queen games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5500614)