dbsearch - An inefficient search program with 3D state transition diagrams
Posted: July 16th, 2022, 5:22 pm
(the db is an initialisation of decay branch search :-)
Context: Since February, I have mainly been programming my chess tablebase program in Python, which supports reduction by eightfold symmetry on square boards and vertex transitivity on topological manifold boards. However, its most notable feature is its ability to render state transition diagrams (inspired by my previous Scratch program (in the same repository) that did this for moves for single pieces (and some other graphs for modelling phenomena I liked) and Stephen Wolfram's demonstration script that did it for Wolfram rules in toroidal tapes (of which I had made an oscillator-searching variant to try to find a p13 one in b34kz5e7c8s23-a4ityz5k's W150 emulator (for which I had found a stable always-on end), a task to which yujh beat me by manual discovery of period-dividing mechanisms)).
I have today added a mode to the tablebase program for generating states in 2D cellular automata, converting INT rules to internal MAP ones and simulating an iteration and indexing the result to create the state transition diagram. Next, I will add cycle searching (to enumerate still lifes and oscillators) and automatic disqualification of states which escape the bounding box (for bounded boards, though it already works with the same topological manifolds (cylinders, Möbius strips, toruses, Klein bottles and real projective planes) as the tablebase part, so it works correctly for agars).
In chess tablebases, eightfold symmetry reduction is easy, because you can reflect every state such that the white king is in the bottom-right half diagonally of the bottom-left quadrant, and use the black king as a tiebreaker if it lies upon a line of symmetry (only the diagonal one in even-width boards), and compare the pieces on either side and flip the first disparity to the lower-indiced location if both kings lie upon the same one. Because the kings can't occupy the same square, only one can be in the centre and the other reduces the problem to deciding on the orientation in a single axis. Vertex transitivity reduction for toroidal boards is similarly easy, you only need to scroll it in both axes such that the white king is in the bottom-left.
However, in cellular automata, there are no unique cells like there are kings.
You would imagine that for an n*n board, it would require generating all eight reflected states for each n**2-bit binary number and use whichever is lexicographically minimal, but I had an idea for a faster algorithm for generating canonical representations, by splitting it into layers of cells with the same "absolute displacement" (ie. (-1,2) and (2,1) being the same) from the centre and, with the outermost one (the corner cells), incrementing its cells in binary and adding the current state of all layers to the list of states, skipping over configurations that have their first disparity (in lexicographical order) on the higher-indiced side. Once the outermost one is comprised entirely of 1s, the next increment carries the 1 to the second-outermost one (the cells displaced by 1 orthogonally from the corners) and the outermost one continues its counting. However, each time the second-outermost one is incremented, if it has a higher-indiced first disparity, it will increment itself again, skipping all states that vary only in the outermost layer but have an "illegal" disparity in the second-outermost one (which is given higher precedence). This works for generating the 102 (the number of INT transitions) canonical representations of distinct 3*3 configurations, but for higher values this number begins to diverge from the OEIS sequence (which, very interestingly, includes closed-form equations for the nth term, allowing you to see that it's wrong within the program itself), assumedly due to something being wrong in oblique layers. (If anyone knows of existing algorithms for this that do work, I would be very interested to know.)
The state transition diagram viewing mode begins with the nodes representing states all in a line (with slight random lateral velocities), however they repel from each other with the inverse-square law and states' nodes are pulled towards their descendants with one-way absolute springs with Hooke's law. You can rotate with the arrow keys or clicking and dragging with the mouse, and Q and E for local pitch and roll, and move with standard WASD and R and F for local up and down, press shift to stop moving.
However, be warned, if viewing them yourself (for which Pygame is necessary), the simulation is in O(n**2) time due to the naïve implementation of n-body repulsion (because I currently know too little maths to understand the fast multipole method), so 3*3 may be the limit for feasibility for now, press the z key (hold it for at least a frame) to pause the simulation to fly around in real time. (I would also like to know of any more efficient 3D graph immersion/embedding algorithms than this, though I think it's quite soulful.)
Without further ado, here are the images of the 102 eightfold-reduced 3*3 states' transition diagram unfurling.
Context: Since February, I have mainly been programming my chess tablebase program in Python, which supports reduction by eightfold symmetry on square boards and vertex transitivity on topological manifold boards. However, its most notable feature is its ability to render state transition diagrams (inspired by my previous Scratch program (in the same repository) that did this for moves for single pieces (and some other graphs for modelling phenomena I liked) and Stephen Wolfram's demonstration script that did it for Wolfram rules in toroidal tapes (of which I had made an oscillator-searching variant to try to find a p13 one in b34kz5e7c8s23-a4ityz5k's W150 emulator (for which I had found a stable always-on end), a task to which yujh beat me by manual discovery of period-dividing mechanisms)).
I have today added a mode to the tablebase program for generating states in 2D cellular automata, converting INT rules to internal MAP ones and simulating an iteration and indexing the result to create the state transition diagram. Next, I will add cycle searching (to enumerate still lifes and oscillators) and automatic disqualification of states which escape the bounding box (for bounded boards, though it already works with the same topological manifolds (cylinders, Möbius strips, toruses, Klein bottles and real projective planes) as the tablebase part, so it works correctly for agars).
In chess tablebases, eightfold symmetry reduction is easy, because you can reflect every state such that the white king is in the bottom-right half diagonally of the bottom-left quadrant, and use the black king as a tiebreaker if it lies upon a line of symmetry (only the diagonal one in even-width boards), and compare the pieces on either side and flip the first disparity to the lower-indiced location if both kings lie upon the same one. Because the kings can't occupy the same square, only one can be in the centre and the other reduces the problem to deciding on the orientation in a single axis. Vertex transitivity reduction for toroidal boards is similarly easy, you only need to scroll it in both axes such that the white king is in the bottom-left.
However, in cellular automata, there are no unique cells like there are kings.
You would imagine that for an n*n board, it would require generating all eight reflected states for each n**2-bit binary number and use whichever is lexicographically minimal, but I had an idea for a faster algorithm for generating canonical representations, by splitting it into layers of cells with the same "absolute displacement" (ie. (-1,2) and (2,1) being the same) from the centre and, with the outermost one (the corner cells), incrementing its cells in binary and adding the current state of all layers to the list of states, skipping over configurations that have their first disparity (in lexicographical order) on the higher-indiced side. Once the outermost one is comprised entirely of 1s, the next increment carries the 1 to the second-outermost one (the cells displaced by 1 orthogonally from the corners) and the outermost one continues its counting. However, each time the second-outermost one is incremented, if it has a higher-indiced first disparity, it will increment itself again, skipping all states that vary only in the outermost layer but have an "illegal" disparity in the second-outermost one (which is given higher precedence). This works for generating the 102 (the number of INT transitions) canonical representations of distinct 3*3 configurations, but for higher values this number begins to diverge from the OEIS sequence (which, very interestingly, includes closed-form equations for the nth term, allowing you to see that it's wrong within the program itself), assumedly due to something being wrong in oblique layers. (If anyone knows of existing algorithms for this that do work, I would be very interested to know.)
The state transition diagram viewing mode begins with the nodes representing states all in a line (with slight random lateral velocities), however they repel from each other with the inverse-square law and states' nodes are pulled towards their descendants with one-way absolute springs with Hooke's law. You can rotate with the arrow keys or clicking and dragging with the mouse, and Q and E for local pitch and roll, and move with standard WASD and R and F for local up and down, press shift to stop moving.
However, be warned, if viewing them yourself (for which Pygame is necessary), the simulation is in O(n**2) time due to the naïve implementation of n-body repulsion (because I currently know too little maths to understand the fast multipole method), so 3*3 may be the limit for feasibility for now, press the z key (hold it for at least a frame) to pause the simulation to fly around in real time. (I would also like to know of any more efficient 3D graph immersion/embedding algorithms than this, though I think it's quite soulful.)
Without further ado, here are the images of the 102 eightfold-reduced 3*3 states' transition diagram unfurling.