Developing a Game Over 9 Years

It began with a flight that was delayed for over five hours in the Boston airport after the 2010 US Nationals. At the time, I only really knew C++ and basic terminal interaction. I cannot recall where the idea came from besides manipulating array elements. There was a 1 by 3 row of “bits”, and the player would select a bit and it would be increments by 1, the bits adjacent to it would be incremented by 2. The goal was to get all the array elements to equal a certain number. It was oddly fun and the game as a concept would be embedded in my head for the next 9 years, I called it BitFlipper.

At the time, my programming skills were not sufficient to bring the idea beyond the terminal. After writing the first version of FiveTimer in 2011 I took a crack at using the Cinder framework to bring the game to iOS. I didn’t get far, not knowing enough about graphics programming and not knowing where to learn more.

I knew some web development though, a paradigm where you don’t need to worry about how to draw things to the monitor, just create some <div>’s and style them with CSS and use JavaScript for interaction. With that in mind I made a basic prototype of the game I had imagined a few years prior. I even added a replay feature for the puzzles that would take a particularly long time to solve.

Fast forward to 2015, I was pursuing web development more and everyone was going wild over ES6 (later formalized as ECMAScript15). The changes to the language (mostly syntactic sugar in retrospect) made JavaScript more versatile and easy to understand. I rewrote the proof of concept using ES6 and even got the chance to present it at the Albuquerque Game Developers Guild (AGDG) where it was received warmly.

That same year the first version of Apple’s Swift language was released and I immediately recognized some syntactic similarities with ES6. It therefore wasn’t a difficult task to carry over the existing code into Swift and make it a new fully native game on iOS. I knew a bit more about graphics drawing now, to draw components on the screen I took advantage of the fairly new SpriteKit. Later that year, the Apple Watch was also announced and BitFlipper seemed like a perfect game to play on your wrist. At this point I had spent my innovation tokens, that is, using a lot of unproven technologies and in this case also on some unproven platforms. After some modest development of the game I discovered a memory leak involving the physics engine of SpriteKit (even though the physics engine wasn’t being used). Development was put on hold indefinitely because the leak would hard crash the game.

This period was discouraging not just because of the uncertainty if the bug would ever be fixed but also because I discovered that some of BitFlipper’s game mechanics were similar to LightsOut. In time I came to realize that despite the similarities, my game improved on the similar mechanics with more light states, game modes, and versatility.

Two years later, it’s 2018 now, after a few years of updating the Swift syntax to the latest versions the bug was suddenly no longer there. There was still a modest list of things left to do: create puzzle levels, add some sounds, and figure out a monetization scheme. There’s a saying that the last 20% of a project takes 80% of the time, this feels like a prime example. Working intermittently on the BitFlipper in 2018 and fully in the summer of 2019 it was finally completed and released on the AppStore in August 2019, almost exactly 9 years from the initial version I wrote in the Boston airport.

And so, I’m happy to finally write that you can download and play BitFlipper on the iPhone, iPad and Apple Watch. I hope you like it.

Processing Many Small Files with Apache Spark

Apache Spark is straight-forward to use when there are large files that need to be chunked up and read, but what about when you have many small files? In this post we’ll look at a way to address many small files and some parameter tuning to speed that up.

The sample data we’ll be looking at is the Million Song Dataset(MSD), the entire dataset is about 273 GB, more than enough for Spark to take a bite out of. (If you wish to try this at home the site offers a sample of 10,000 songs at a more digestible size of 1.8GB.) The entire dataset can be downloaded in 26 A-Z partitions, each partition contains between 38,109 and 39,100 songs. Each of these songs is stored as a file in the HDF5 format and is between 180kb to 900kb in size, much too small to split up for a Spark job. The small file size is the crux of our problem.

So we need to make large files, this will be as lists of all the files. It is these lists that will be partitioned among Spark jobs. A job will read the file list and extract important song information in the HDF5 files and aggregate it into larger CSV files which Spark will consume. To create a CSV for every partition:

for X in {A..Z}
    ls -1 ${X}/*/*/*.h5 > ${X}_file_list.csv

From each file in the file list, we want to aggregate the relevant information. A script that extracts the title, artist name, and year follows. For reading the MSD HDF5 files there exists a library which makes the reading easier: It’s referred to as mill below.

import glob
import re
import sys
from functools import partial
from pyspark import SparkConf, SparkContext
import hdf5_getters as mill

# simple wrapper for the hdf5_getters, just be sure the string 'func' exists
def call_mill(m, func, fi):
    return getattr(m, 'get_' + func)(fi)

# gather 'fcns' attributes and return them as a comma separated string.
def parse_h5(file_path, fcns):
    # read the file
    fi = mill.open_h5_file_read('/home/ubuntu/' + file_path)
    vals    = []
    str_format = []
    sep     = '\t'
    # for each getter in fcns
    for f in fcns.value:
        format = f['format']
        val = call_mill(mill, f['func'], fi)
        # if string, cast it to utf-8 string
        if format == '%s':
            # there's a better way to do this but we have to import numpy
            if str(type(val)) == "<class 'numpy.ndarray'>":
                val = ','.join([x.decode('utf-8') for x in val])
                val = val.decode('utf-8')
            val = re.sub(r'\t', ' ', val)
    # close the file
    return (sep.join(str_format) % tuple(vals))

def get_headers(fcns, sep='\t'):
    headers = []
    for f in fcns:
    return sep.join(headers)

if __name__ == '__main__':
    start_letter = None
    length = None
    if len(sys.argv) < 4:
        print('Expected arguments: start_letter, length, workers')

    start = file_prefixes.index(start_letter)
    end_letter = file_prefixes[start+length-1] # -1 for inclusive

    conf = SparkConf() \
            .setMaster('spark://spark_ip') \
            .set('spark.hadoop.validateOutputSpecs', False) \
            .setAppName('h5_to_csv:%s to %s' % (start_letter, end_letter))
    sc = SparkContext(conf = conf)

    # the fields to get from the hdf5 files
    get_fcns = [
        {'func': 'title',           'format': '%s'},
        {'func': 'artist_name',     'format': '%s'},
        {'func': 'year',            'format': '%d'},
    # let the workers know about them
    fcns = sc.broadcast(get_fcns)

    # get all file listings
    file_list = glob.glob('file_lists/*.csv')
    file_list.sort() # alphabetize
    job_list = file_list[start:start+length]

    # concatenate the file lists
    files = sc.textFile(','.join(job_list)).cache()
    # process and collect the data from all the files
    rdd_output =, fcns=fcns)).collect()

    # write the aggregated data as csv.
    outname = 'entries-%s-%s.csv' % (start_letter, end_letter)
    with open('results/' + outname, 'w') as fi:
        fi.write(get_headers(get_fcns) + '\n')

If we zip our dependencies and run this on a cluster with something like:

spark-submit --py-files A B 4 # start, end, workers

The results will be underwhelming. If we go to the Spark dashboard and watch the jobs run we’ll see a performance bottleneck because the data is partitioned across only one or two partitions. This is due to the many small file sizes. Per the Spark RDD Programming Guide:

“typically you want 2–4 partitions for each CPU in your cluster.”

Let’s say the cluster is 4 cores, we should want about 8–16 partitions however we’re not seeing that due to size of the files that are being read from the file lists. We can force a number of minimum partitions with the minPartitions argument, changing the files = sc.textFile(...) line to be:

files = sc.textFile(','.join(job_list), minPartitions=8).cache()

When working with this many small files 8 partitions still presents a bit of a bottleneck. A better minPartitions can be found by doing some timed runs with a multiplier variable m.

minPartitions = workers * cores * m

As the graph below shows a multiplier of 8 seems reasonable with diminishing returns thereafter. Unless there are any other common bottlenecks there will be noticeably better performance. With six workers, and m = 8 the entire 273 GB can is processed in roughly 24 minutes! On the cluster I was using this is minPartitions=256.


The cluster itself setup and run on the Swedish National Infrastructure for Computing (SNIC). In total the cluster consisted of seven nodes with eight CPU’s and 16 GB of RAM each. One of these was the dedicated master node responsible for resource allocation while the remaining six where pure worker nodes, using all their CPUs for data processing.

Optimal Catan

Settlers of Catan (SoC) is a German board game from the mid 90’s that found mainstream success in America in the late–00’s. To summarize the game: the board consists of 19 hexagonal resources tiles and these tiles get numbered markers (2–12). There are five resources, lumber, sheep, ore, brick, and wheat. These are used to build towns, roads, cities; or earn “development cards” with special abilities or points. The gameplay consists of placing towns and roads on the vertices and edges of the tiles. Dice are rolled each turn and any player who has a town on a vertex adjacent to a numbered marker collects the resource of that marker. Players earn points by expanding their settlements, the first player to ten points wins.

An element of the game that greatly affects how it plays is the resource tile layout and the distribution of the numbered markers on the resources. By the mid to late game it becomes evident that some players have some significant leverage on game-winning resources and others are severely constrained by the lack of a resource. This likely comes through their initial town placement and subsequent expansions.

Manually balancing the board is inherently difficult as you have to keep in mind resource proximity through tile layout and resource scarcity through marker placement. Players who recognize an imbalance in the board are likely to win or handicap others from winning by blocking others from building on important vertices. If only there was a way to make a board with evenly distributed markers and where no two of the same resources are adjacent and the markers were evenly distributed. Roads are a significant source of points in the game, with two points going to the player with the longest road greater than five segments. It would be nice if roads, which cost one lumber and one brick, were a little harder to build. With these constraints in mind let’s look at a way to solve this.

Constraint programming

I was recently introduced to constraint modeling and constraint programming (CP) through one of my graduate courses. In short, CP is the closest thing to magic in the realm of computer science that I know of. You can use it in a low-level language like C++ (GeCode and Chuffed) or you can use it on a higher abstraction where the syntax is concise and neat. One such abstracted language is called MiniZinc.

MiniZinc is a declarative constraint programming language which uses lower level constraint solvers through a common abstracted layer called FlatZinc. Once you grasp the syntax, complicated problems can be solved in mere lines of code. A simple example that I think demonstrates the power of MiniZinc is the magic square problem.

The magic square is a puzzle where with numbers 1 through 9 fill a 3 by 3 grid so that the sums of all rows, columns, and 3-length diagonals are equal. In MiniZinc we declare such a grid as an array of decision variables:

array [1..9] of var 1..9: sq;

where square is the array, for simplicity it is 1-dimensional. The contents of sq will be modified in the search for a valid puzzle solution. Now the constraints which describe the puzzle:

constraint alldifferent(s);

This lets the solver know that every number in sq must be distinct. Otherwise solutions like ([1,1,1,1,1,1,1,1,1] would be generated. Next constraining the row and column sums: (arrays in MiniZinc are 1-indexed):

% rows
constraint sum(sq[1..3]) = sum(sq[4..6]);
constraint sum(sq[4..6]) = sum(sq[7..9]);

% columns
constraint sq[1]+sq[4]+sq[7] = sq[2]+sq[5]+sq[8];
constraint sq[2]+sq[5]+sq[8] = sq[3]+sq[6]+sq[9];

% diagonals
constraint sq[1]+sq[5]+sq[9] = sq[3] + sq[5] + sq[7];

Finally, MiniZinc needs to know what the objective is, for other problems we can maximize or minimize some value. Here we just want any solution:

solve satisfy;

and that’s it! Running the program gives this result:

Compiling magic-square.mzn
Running magic-square.mzn
sq = array1d(1..9, [8, 1, 6, 3, 5, 7, 4, 9, 2]);
Finished in 169msec

Just to make it more readable:

output[ "\(sq[1..3])\n" ];
output[ "\(sq[4..6])\n" ];
output[ "\(sq[7..9])\n" ];

and rerunning it:

[8, 1, 6]
[3, 5, 7]
[4, 9, 2]
Finished in 163msec

If you’re following along in the MiniZinc IDE and this is your first time using MiniZinc take a moment to reflect on all the time you may have spent solving this by hand and feel the wind on your face as you stand on the shoulders of giants. But wait, there’s more!

There are some improvements to be made. Firstly, this square can be rotated and reflected to create seven other solutions. This is called symmetry and it is a large component of constraint problem/programming research. In the configuration editor in the MiniZinc IDE change output settings: check ‘Output statistics for solving’ and under ‘User-defined behavior’ check ‘Print intermediate solutions’. Also change ‘Stop after this many solutions’ to 0. Rerun the model.

%%%mzn-stat initTime=0.000778
%%%mzn-stat solveTime=0.007776
%%%mzn-stat solutions=8
%%%mzn-stat variables=9
%%%mzn-stat propagators=6
%%%mzn-stat propagations=19399
%%%mzn-stat nodes=2659
%%%mzn-stat failures=1322
%%%mzn-stat restarts=0
%%%mzn-stat peakDepth=14

This is more information that we may want, the key line is 8 solutions. To elaborate on the rest of the output nodes reflect the count of nodes in the search tree and peakDepth refers to the depth of the tree. propagators and propagations refers to how the solver is iterating through this problem. Propagation is the mechanism by which the solution space is reduced each step and is another large part of CP research. Redundant solutions can be cut down by adding more constraints. By removing redundant solutions we also remove redundant non-solutions and reduce the overall search space. Let’s make it so that the number in the top left corner is 9.

constraint sq[1] = 2;
[2, 9, 4]
[7, 5, 3]
[6, 1, 8]
[2, 7, 6]
[9, 5, 1]
[4, 3, 8]
%%%mzn-stat solutions=2

These final two solutions are diagonal reflections of each other, how can this be limited to just a single solution? Of course, just constrain the position of another corner.

constraint sq[3] = 4;
[2, 9, 4]
[7, 5, 3]
[6, 1, 8]
%%%mzn-stat solutions=1
%%%mzn-stat nodes=31
%%%mzn-stat peakDepth=5

Through the addition of our symmetry breaking constraints the search space has been drastically reduced. The nodes statistic has been reduced from 2659 to just 31 and the overall search tree has also been reduced from peakDepth of 14 to 5. The magic square is a toy problem but is useful in demonstrating the concepts of symmetry breaking to reduce the search space and using constraints to solve some layout puzzle.

If you’re following along and want to keep playing with this model, what do solutions look like when the diagonal constraint isn’t necessary? What is a good way to get that down to just one solution?  And, what does a 4×4 magic square look like? This model is just scratching the surface of what is possible in MiniZinc, they have some great documentation if you would like to read more. Let’s go back to our Settlers of Catan problem.

Optimal board layout

It should be clear that MiniZinc can be used to generate more balanced boards and markers for Settlers of Catan. To review the desired constraints:

  • No two of the same resources are adjacent
  • Lumber and brick are not adjacent
  • Markers distributed such that 6 and 8 are not next to one another
  • The four 6 and 8 markers are each on different resources

This is much more than the magic square problem. For simplicity this should be two separate models, one for the tiles and another for the markers. Otherwise, the board will stay the same and the markers will cycle through every possible permutation before a different board is generated, so they will be addressed one at a time.


To start, some decision variables and constants are declared.

% Parameters

% Board size
int: nRows = 5;
int: nCols = 5;
set of int: Rows = 1..nRows;
set of int: Cols = 1..nCols;

% Resources
%               1      2       3      4      5      6      7
% enum Resource={Water, Desert, Brick, Grain, Sheep, Stone, Lumber};
set of int: Resources = 1..7;
array[Resources] of int: ResourceCounts = [6, 1, 3, 4, 4, 3, 4];

Resources are represented on the board as numbers 1 through 7. ResourceCounts is the number of that resource to be placed on the board. The board is square so we need to represent water as a resource, there are six of them. There is the desert, resource lacking, tile which the thief starts on. The rest of the array is the count for the primary resources.

% Decision Variables
array[Rows, Cols] of var Resources: Board;

This is the decision variable the model will be modifying in the search for a solution. Now for constraints.

% Resource counts
constraint forall(re in Resources)(
  sum(r in Rows)(count(Board[r,..], re)) = ResourceCounts[re]

The forall predicate is being used here to constrain that for each resource re the sum of the count of the re on the board is equal to the count in ResourceCount.

% No two of the same resources are adjacent
constraint forall(r in 1..nRows-1) (
  forall(c in 1..nCols-1) (
    alldifferent_except_0([Board[r,c]-1, Board[r, c+1]-1,
                           Board[r+1, c]-1, Board[r+1,c+1]-1])

This one is more complicated. There are two forall predicates here with an alldifferent_except_0 constraint. The foralls iterate and constrain over every element in the board until the second to last row and column. Recall that this is declarative, forall is shorthand for generating multiple constraints at once. For each tile, its value is constrained so that it is different than its neighboring tiles unless the value–1 is 0 (recall that oceans are 1). To constrain lumber and brick from neighboring each other the alldifferent_except_0 constraint cannot be used.

% Lumber and brick cannot be adjacent

% constraint right and bottom right diagonal
constraint forall(r in 1..nRows - 1)(
  forall(c in 1..nCols where Board[r,c] in {3, 7}) (
    not(Board[r+1, c] in {3, 7})
  /\ % and
  forall(c in 1..nCols - 1 where Board[r,c] in {3, 7})(
    not(Board[r+1, c+1] in {3, 7})

% constraint bottom
constraint forall(r in 1..nRows) (
  forall(c in 1..nCols - 1 where Board[r,c] in {3, 7})(
    not(Board[r, c+1] in {3, 7})

Two features called reification and set notation are used here. Reification can be a performance foot shotgun sometimes and makes the lower-level models more complex, use this carefully. The set is used to check that a tile value is not in the set {brick(3), lumber(7)}. Reification is used in the inner foralls with where Board[r,c] in {3, 7}. This is saying only “iterate over tiles which are lumber and brick.” The inner-most constraint not(Board[r+1, c] in {3, 7}) checks that a neighboring tile is neither lumber nor brick.

If the model is run now ocean tiles will be everywhere, they need to be on the edges.

% Place the water on the edges
constraint Board[1,4] = 1;
constraint Board[1,5] = 1;
constraint Board[2,5] = 1;

constraint Board[4,1] = 1;
constraint Board[5,2] = 1;
constraint Board[5,1] = 1;

To reduce the search space three corners of the island are constrained to be descending in value.

% break rotational symm
constraint Board[1,1] < Board[3,5];
constraint Board[1,1] < Board[5,3];
constraint Board[3,5] < Board[5,3];

And finally, solve to satisfaction and output the board:

% Objective
solve satisfy;

% output[show2d(Board)];

output[ "   \(Board[1,1..3])\n" ];
output[ " \(Board[2,1..4])\n" ];
output[ "\(Board[3,..])\n" ];
output[ " \(Board[4,2..])\n" ];
output[ "   \(Board[5,3..])\n" ];

The output is staggered to look like how the tiles are actually laid out. Let’s see what it gives us!

   [2, 7, 5]
 [3, 4, 6, 7]
[6, 5, 3, 5, 4]
 [7, 4, 6, 3]
   [5, 7, 4]
% time elapsed: 0.13 s
%%%mzn-stat initTime=0.013395
%%%mzn-stat solveTime=0.12374
%%%mzn-stat solutions=96
%%%mzn-stat variables=110
%%%mzn-stat propagators=135
%%%mzn-stat propagations=610914
%%%mzn-stat nodes=12549
%%%mzn-stat failures=6179
%%%mzn-stat restarts=0
%%%mzn-stat peakDepth=21

96 “optimal” boards to chose from! With output[show2d(Board)]; the raw 2D array is output. Did I mention MiniZinc can be run from the command line and can output to JSON? This output can easily be piped and interpreted in Python. With some matplotlib hacking the board can be visualized.

For those who have just learned about SoC, the colors may be unfamiliar. Above, brick is red, sheep is green, wheat is yellow, ore is gray, forest is dark green, and the desert is orange. One interesting attribute for this solution is that for this set of constraints the desert tile is (almost) always in a corner. This seems to be a by product of the lumber/brick adjacency constraints.


The markers model is largely the same and won’t be repeated here. Instead of tiles it makes sure that no two numbers are adjacent and the 6’s and 8’s—the most probable resource gaining numbers—are also not adjacent.

set of int: Number = 1..12;
                                    % 1 2 3 4 5 6  7  8 9 10 11 12
array[Number] of int: MarkerCounts = [6,1,2,2,2,2, 1, 2,2, 2, 2, 1];

1’s cannot be rolled so they will be assigned to oceans, 7 will be assigned to the desert tile. This model takes Board from the previous model as input to make sure that the 7 is placed on the desert.

% Place the 7 on the Desert
constraint forall(r in Rows)(
  forall(c in Cols where Board[r,c] = 2) (
    Marker[r,c] = 7

Since Board is a parameter not a decision variable there is no refification going on here. When writing constraints stating the constraint in simple English and they codifying it is often the best approach. For example: “each resource of each type must have have all different markers.” Which is translated as so:

% All resources have different markers
constraint forall(res in {3,4,5,6,7}) (
  % all markers different
  all_different([Marker[r,c] | r in Rows, c in Cols where Board[r,c] = res ])
  % only one 6 or 8 per resource
  count([Marker[r,c] | r in Rows, c in Cols where Board[r,c] = res ], 8) +
  count([Marker[r,c] | r in Rows, c in Cols where Board[r,c] = res ], 6) <= 1
   [7, 8, 11]
 [6, 12, 10, 5]
[3, 9, 11, 8, 9]
 [10, 6, 5, 4]
   [4, 3, 2]

The all_different constraint is being applied to the array of decision variables Marker.

The marker distribution can be improved more. Something to note about the marker solutions above is how there are some very weak vertices on the board. I’m looking at 5,4,2, and the 12,10,11 vertices, can the number of these vertices reduced? Let’s try setting a threshold on the sum of neighboring values.

% distribute markers
constraint forall(r in 1..nRows-1)(
  forall(c in 1..nCols-1 where Marker[r,c] > 1) (
    Marker[r,c] + Marker[r+1,c] + Marker[r+1, c+1] < 23
    Marker[r,c] + Marker[r,c+1] + Marker[r+1, c+1] < 23
   [7, 11, 8]
 [6, 4, 3, 9]
[10, 5, 12, 4, 8]
 [6, 3, 2, 9]
   [11, 5, 10]

This iterates over each tile checking the vertices with two other neighbors. The threshold is sensitive. If it’s 21 or less there exist no solutions, when it’s 22 there is just 1 solution. In about half a minute with a threshold of 23 I can find that there are 11,753 solutions. Most vertices are improved but some weak ones remain such as 3,2,5 and 2,4,12. There are 11,752 other configurations that might have more even vertices.

It may be impractical to reduce the search space without forcing certain markers on certain tiles. Unlike the five types of tiles there are ten (2–12, excluding 7) types of markers to shuffle around. That said I think the marker permutations this last constraint generates looks a little better than before. A little more matplotlib hacking and we get the board in a neat picture, markers included.

With a board layout and markers distributed across them there’s only one thing left to do: play the game!

Play testing

I got some friends together to play using a board generated with these models. With an optimal tile and marker layout and I couldn’t have been more excited to truly see what a balanced Settlers of Catan game feels like.

The pace of the game can only be described as glacial. The game was declared a draw three hours in due to nobody having much fun, for reference most games are usually around 60 minutes. The advantages each player had were marginal due to such equal access to resources. I recall the highest pointed player had seven points and most of it was through development cards.

This is an illustrative example of how fun in games emerges from complexity and competition rather than strict rigidity and equality. For example professional Starcraft or DotA would not be as interesting if everyone was forced to play the same race or the same standard set of five heroes.

It turns out that tournament SoC maps frequently have common resources adjacent as well as 6’s and 8’s on common resources. 6’s and 8’s are never adjacent though. I could not find a site for tournament boards for this post (if they are published please reach out to me) but browsed through a few final games on YouTube. This Reddit thread has some comments from tournament goers on board setup, this comment from implosionsinapie is interesting:

For the U.S. national qualifiers the boards are what I like to call semi-constructed. They completely randomize numbers and resources and then adjust accordingly so there aren’t any 6–8–5 spots or too heavy a concentration of a certain resource. It’s all up to whoever is running the tournament, though, they can make boards as simple or as difficult as they like. […]

Further work

Ports are an important part of gameplay. Ports allow players to trade two resources of a certain type for one of any other resource (a 2:1 ratio), there are also open ports where the ratio is 3 of the same type for 1. In the several dozen games I have ever played only in a handful did port access win the game, it is something that has to be planned from turn one. Strictly speaking though, it is a part of the board layout and so this model is incomplete without port placement and port placement is left up to us humans.

There exist several expansions for SoC which increase the board size, make a whole separate island, and introduce new tiles. I have actually never played them though and so I cannot speak for what sort of imbalances CP could address or if they are worthwhile to.


In summary, optimal boards are not more fun. CP can certainly create a board with the desired constraints but the boards aren’t fun to play on, extending the total game time more than two-fold. To modify the question: what sorts of constraints make more fun board layouts?

Source code

All presented MiniZinc code available in this GitHub repository.