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.

If you are a professional mathematician and you are asked whether 2 + 2 = 4, the only answer you should give is “Yes, obviously.”