QuFince is a CUDA tool written by apg to conduct brute-force Game of Life searches on the cartesian product of two sets of configurations. That is, each configuration from set A is combined with each configuration from set B, and run until stabilised. Not every result is reported, only those where certain criteria are met. Right now the options are either that the result has some interesting periodInteresting period here typically means period not dividing 120, to rule out blinkers, pulsars, pentadecathlons and figure eights, among other things.

(to hunt for glider syntheses of oscillators), or that the result contains a specified pattern (to hunt for synthesis components for specific still lifes).

One thing that can’t be done currently is have QuFince report any combination that results in an interesting still life, but without knowing which still life you want in advance. It’s not so obvious what “interesting still life” should mean exactly, but here are some randomly chosen examples of things that should qualify:

We can’t use a population threshold as our criterion for interestingness, because the typical result of one of these QuFince trials is a bunch of uninteresting junk. One option is to do proper object separation, like apgsearch, and then report any object that is sufficiently rare. But a QuFince search can conceivably test hundreds of billions of configurations, and full object separation is simply too slow.

Here I’ll present an alternative, a simple heuristic that works well enough.

As a second foray into CUDA, I’ve written a simple program to hunt for crawlers in the Game of Life. The kernel itself is too revolting to make public, but the supporting LifeStateCU code may be useful for others. (This could be seen as the first step in a GPU version of CatForce/LightCone…)

Officers is a two-player “take-and-break” game played with heaps of coins (or if you prefer, piles of beans, or officers and their subordinates, or groups of people who form indivisible couplesIn the equivalent game Couples-are-Forever, a move is to choose a heap and split it into two, with the proviso that you may not split a heap of size 2. An Officers heap of size n is equivalent to a Couples-are-Forever heap of size n+1.

, or …). The two players alternate turns, and every turn consists of removing a coin from a heap and leaving the remainder in either one or two heaps. In particular, taking away a lone coin is not a valid move. The winner is the last player who can make a move.

For example, a game starting with a single pile of 10 coins might proceed

[10] \xrightarrow{\mathcal{L}} [3, 6] \xrightarrow{\mathcal{R}} [3, 1, 4] \xrightarrow{\mathcal{L}} [1, 1, 1, 4] \xrightarrow{\mathcal{R}} [1, 1, 1, 1, 2] \xrightarrow{\mathcal{L}} [1, 1, 1, 1, 1]

at which point player \mathcal{R} is stuck, so player \mathcal{L} has won.In fact, he was following the winning strategy.

Although the total number of coins decreases by 1 each turn, the outcome of the game is not determined simply by the parity of the starting number of coins: the moment that the game ends also depends on how many piles are created by the players making splitting moves. As we will soon see, the winning move from any given position is extremely unpredictable.

We can solve a game of this kind by calculating the Grundy value for each position, and in this post I’m going to discuss my attempt at calculating these values for Officers as fast as possible.

Conduits are a central piece of technology in Conway’s Game of Life, especially when engineering new pieces of stable circuitry. A conduit moves an active pattern (like a Herschel or B-heptomino) from one location to another by allowing it to react with a collection of stable catalysts. Along the way, it may release some gliders, produce additional active patterns or perform some other useful interaction, and so new pieces of machinery can be constructed by chaining conduits together.

As one very famous example we have the Fx77 conduit discovered by Dave Buckingham, which moves a Herschel forwards in 77 generations, also flipping it.

Many software tools have been written to search for new conduits: ptbsearch by Paul Callahan, Catalyst by Gabriel Nivasch, catgl by Dave Greene, CatForce by Michael Simkin and LocalForce by Nico Brown, to name a few. Typically these tools are handed an active pattern and a collection of catalysts, and spit out all placements of catalysts that interact with the active pattern and recover. At this point, hundreds of conduits are known, converting to and from various active patterns. But the more the merrier!

I’ve been working on yet another search tool, called Lightcone. Lightcone is pretty speedy: it can find apg’s Spartan G-to-W on this input file in just a couple of seconds. In this post I’ll explain some of the tricks it uses to cut down the search time.

Code available on GitHub.

For a little while I have been working on this port of Kenzo from Common Lisp to Haskell. Kenzo is a collection of algorithms for explicit constructions on simplicial sets: the README in the repository gives a list of what’s implemented and what should be possible. The algorithms and implementations in Kenzo were created by Francis Sergeraert, Julio Rubio Garcia, Xavier Dousson, Ana Romero and many collaborators.

My goal was to implement just enough to compute \pi_4 S^3, and I reached it today.

...
> let x = totalSpace s3 (Wbar kz1) fibration
> putStrLn $ "π₄ S³ is: " ++ show (homology x !! 4)
π₄ S³ is: ℤ/2

A fun capability it picked up along the way is calculating the homology of Eilenberg-MacLane spaces K(ℤ/m,n), for example, here is K(ℤ/3,2).This makes my laptop get hot pretty quickly.

> homology (Wbar (WbarDiscrete (Zmod 3)))
[ℤ,0,ℤ/3,0,ℤ/3,0,ℤ/(3^2),ℤ/3,ℤ/3,ℤ/3,ℤ/3 ⊕ ℤ/3,^C

I have a lot of ideas for improvements and additional features if anybody is interested in joining in, so please email me if that’s you or you know a student for whom this would make a good project. For example, adding the construction of loop spaces and their homology would be nice, as would homotopy pushouts in general.

On the implementation side, I have not spent any time optimising the code and there are some obvious places to start, like using a proper integer matrix library instead of a homemade one. These sorts of optimisations would also make a good project for an undergraduate, with not much mathematical background required.

Below, I’ve copy-pasted a quick introduction I wrote to the ideas behind Kenzo.