Parallel lifesrc search with genetic algorithm

For scripts to aid with computation or simulation in cellular automata.
Post Reply
User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Parallel lifesrc search with genetic algorithm

Post by simsim314 » April 21st, 2020, 7:45 pm

lifesrc is implementing A* tree search specified for different CA to find spaceships and oscillators (or parents etc.).

This is basically a tree search which tests unknown cells by converting them to 1 and 0 in some order. Another operation the search does is converting 1 or 0 into unknown and backtrace the search branch and jump to another branch. Now you can think of it in genetic terms. Once the algorithm is unsure instead of placing 1 then 0 then backtrace, think of it as generating two copies of the current state i.e. two offspring one with 1 and the other with 0. When one of the offspring is discovering it's illegal it will backtrace to the last branch (and if all parent branch is explored up the root it will die). The only thing left is to choose which offspring will generate more offspring and which will not, as each generation has limited amount of computational power. This can be done by very shallow criteria like the length of the variation which hasn't failed yet (or the length + the probability to end the spaceship without adding the next column - as we don't want the longest variation but the one that ends, the length is just heuristic for success).

Post Reply