Wednesday, June 16, 2021

Hexploration



Over the past little while we've been exploring an alternative to the Game of Life with a hexagonal board. You can see the rules here. This led us to some super interesting discoveries that we'd like to share.

1. Verifying Sequences

The interesting part of the Game of Life is how it evolves over time. We wanted to write tests that could help us verify how the board changes frame to frame. You can do this by mapping time to space and creating a text file that prints out each frame one after the other, much like a comic book. Instead we decided to take advantage of the animated gif format, and play out the evolution much like a short film.

Here's an example of one of those calls displaying the initial board plus 33 additional frames:

verifySequence(board, 33, f -> board.advance())

which produces:

2. Exploratory Testing with Property-Based tests

Once we could verify sequences, we could start hunting for initial layouts that produce interesting sequences. There are lots of documented scenarios in a traditional square board (blinkers, guns and flyers, etc.), but we couldn't find any for hexagonal space. We decided to search on our own.

2A. Generating Random Boards

We took a page from property-based testing, and created a generator to randomly generate a board with a given number of live cells. We also printed out the board in a way that allowed us to capture and reproduce the ones we liked.

Here's an example of a board we reproduced.

new HexGameOfLife(_(2, 4), _(2, 6), _(1, 9), _(1, 3), _(5, 5), _(5, 1), _(3, 1))

This generated lots of results, and most of them were booooring.

2B. Filtering for "Interesting"

Taking another page from property-based testing, we created a filter to remove boring results. To do this, we had to ask

Q. What does interesting mean?
A. We can see cells in every frame.

Fortunately, coding this was quite simple.

  1. Generate a board
  2. Advance a turn, and check that cells still exist
  3. Repeat until you get to the end of the frames
  4. If you make it to the end, return, otherwise GOTO 1

With these steps, we found this board:

2C. The Blinker Search

In this process, we saw a simple blinker, but lost the board before we could capture it. We tried to get lucky again, but couldn't, so we decided to define what the properties of a blinker were, and then find one automatically.

Fortunately, coding this was quite simple.

  1. Generate a board
  2. Advance 12 turns, and check that the board is the same as the initial board.
  3. If it is, you have found something that repeats every 1,2,3,4,6, or 12 frames. Otherwise GOTO 1

In just under 300,000 randomized searches, this returned: 

If you would like to check out the full code, start here