Some code from a computer science pioneer

[claudeb]

This is mostly of interest to computer history nerds.

Nils Aals Barricelli was an early computer scientist. Among other accomplishments, he pioneered what we now call genetic algorithms. I've learned about him from my friend sandwolf5, who uses a fictional version of his work as the origin story of L.A.I.R.A., from the eponymous trilogy of novels (and the epic saga it spawned).

Now for the fun part: Barricelli's page on the chess programming wiki (turns out he also pioneered computer chess) lists this algorithm for "symbiogenetic" reproduction. It looks more like a cellular automaton to me, but whatever:

integer array this generation, next generation [1 :512];
begin
 loop: for i : = 1 step 1 until 512 do 
       begin 
       n := j := this generation[i];
reproduce: if j = 0 then goto next i;
       k := modulo 512 of (i) plus: (j);
       if next generation[k] > 0 then 
       goto mutation else 
       next generation[k] := n;
       j := this generation[k];
       goto reproduce;
  mutation:
  next i: end;

  copy next generation into this generation;

  print this generation;

  goto loop;
end;

The description is fairly incomplete. For one thing, it says this is Algol code. Um, which version? I'll assume Algol 60, the ancestor of Pascal. It also doesn't state the range of integers (10-bit?) or what the next generation array is initialized to. So my C++ port makes some assumptions:

// C++ port of the symbiogenetic algorithm by Nils Aals Barricelli.
// Source: https://www.chessprogramming.org/Nils_Barricelli

#include <cstdlib>
#include <ctime>
#include <cstdio>

int this_gen[512];
int next_gen[512];

int main() {
	std::srand(std::time(0));

	// Guess at the absent init code from the original page.
	for (size_t i = 0; i < 512; i++) {
		// Turns out it only works with very small numbers.
		this_gen[i] = std::rand() % 3 - 1;
		// Not sure if this is needed or correct here.
		next_gen[i] = 0;
	}

	do {
		for (size_t i = 0; i < 512; i++) {
			printf("%3d ", this_gen[i]);
			if (i % 16 == 15)
				printf("\n");
		}

		for (size_t i = 0; i < 512; i++) {
			int j = this_gen[i];
			int n = j;
			while (j != 0) {
				int k = (i + j) % 512;
				if (next_gen[k] > 0)
					break;
				else
					next_gen[k] = n;
				j = this_gen[k];
			}
		}
		for (size_t i = 0; i < 512; i++)
			this_gen[i] = next_gen[i];
		puts("Press Ctrl-C to stop or Enter for next gen:");
	} while (std::getchar() != EOF);
}

(I picked C++ due to its ubiquity; most people who will read this far are likely to have a compiler installed. And yes, identifiers in Algol 68 at least could have spaces in them.)

Well, it kinda works for a couple of generations, on some runs. Maybe I'm doing something wrong. In any event I don't see any pattern in the numbers of anything. Maybe someone more informed can enlighten me? But it's good practice.

Edit: this page says you're supposed to start with integers from -1 to +1, but now it doesn't seem to work at all anymore, not even by chance. I remain baffled.

Edit 2: Just in case, I also made a version of the code that reproduces the original tangle of goto statements. It still doesn't work.