The Game of Life (GoL) is a cellular automaton characterised by non-linear evolution and emergent complexity. Its global state transition function is non-injective and irreversible, leading to information loss. Consequently, the Reverse GoL, i.e., finding a predecessor that evolves into a given target after a given number of generations, is an NP-complete task. In this paper, we introduce a differentiable GoL transition function within a convolutional neural network-based model to reconstruct the probability distribution, i.e. a heatmap, of a possible initial state associated with the given final board. In this study, the models are validated on \(15\times 15\) boards after one generation by analysing structure-based metrics on the heatmaps of the predicted initial states. In particular, we computed the fuzziness index to measure the degree of binarisation, the Earth Mover’s Distance, to evaluate the accuracy of the spatial mass distribution, and the percentage of high uncertainty cells within a range, to quantify prediction confidence. Our results demonstrate that integrating the differentiable layer reduces the fuzziness index by approximately 40% compared to the baseline approach. Furthermore, the analysis indicate that pixel-wise metrics, such as Mean Squared Error, can be misleading in this context, as they ignore the spatial context of cells. In contrast, the use of structural metrics reveals that the proposed architecture effectively captures the underlying physics and spatial organisation of the automaton.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A CNN-Based Approach to the Reverse Game of Life Problem

  • Ángel F. Caravaca,
  • David Guijo-Rubio,
  • Víctor M. Vargas

摘要

The Game of Life (GoL) is a cellular automaton characterised by non-linear evolution and emergent complexity. Its global state transition function is non-injective and irreversible, leading to information loss. Consequently, the Reverse GoL, i.e., finding a predecessor that evolves into a given target after a given number of generations, is an NP-complete task. In this paper, we introduce a differentiable GoL transition function within a convolutional neural network-based model to reconstruct the probability distribution, i.e. a heatmap, of a possible initial state associated with the given final board. In this study, the models are validated on \(15\times 15\) boards after one generation by analysing structure-based metrics on the heatmaps of the predicted initial states. In particular, we computed the fuzziness index to measure the degree of binarisation, the Earth Mover’s Distance, to evaluate the accuracy of the spatial mass distribution, and the percentage of high uncertainty cells within a range, to quantify prediction confidence. Our results demonstrate that integrating the differentiable layer reduces the fuzziness index by approximately 40% compared to the baseline approach. Furthermore, the analysis indicate that pixel-wise metrics, such as Mean Squared Error, can be misleading in this context, as they ignore the spatial context of cells. In contrast, the use of structural metrics reveals that the proposed architecture effectively captures the underlying physics and spatial organisation of the automaton.