Puzzle: Game of Life

In Conway's game of life, we place lifelings on a board of squares. These lifelings survive, procreate, and die according to very specific rules:

Our client bought a piece of land with 4x4 squares. She wants to buy some lifelings, then place these on her 4x4 board in the first cycle, let these procreate (and die) for another two cycles, and then harvest the lifelings at the end of the 3rd cycle. Our client is friends with the neighbors, so the lifelings may grow outside the initial piece of land, but our breeder lady may not place them outside her 4x4 board initially.

How should she place the lifelings if the objective is to maximize the number of lifelings she harvests at the end minus the lifelings she bought at the beginning?

See if you can optimize the returns using this GoL simulator: https://playgameoflife.com/

Here is a possible solution:

Initially, we place 12 lifelings, and at the end of Cycle 3, our breeder gets to harvest 24 in return, giving a profit of 12 lifelings overall. We may want to warn her, though, not to harvest the lifelings too late.

Optimization Freedom in Seeker

The real world can be strange sometimes. You may need to keep track of coffee layers in cooling siloes, for example, where adding new coffee on top reheats a certain amount of coffee below. Or you may want to optimize the location of warehouses, with no predetermined set of locations, according to the Haversine distance to the respective clients served from the warehouses. Or maybe you need to maximize the norm of a covariance matrix which is somehow dependent on the decisions you need to optimize.

In all these cases, you do not want to be limited by the expressiveness of the solver you use to do the optimization for you. That is why, in Seeker, we allow you to write your own operators.

How does it work?

If you want to create your own user defined operator that takes in a list of Terms and returns a list of Terms, you define a class that is derived from Seeker::UserEvalVector. Such as our GoL class:

import seeker as skr

class GoL(skr.UserEvalVector):
    def __init__(self, board_size):
        skr.UserEvalVector.__init__(self)
        self.n = board_size

    def recompute(self, board):
        old_board = make_2d(board, self.n)
        new_board = next_generation(old_board)
        board = flatten(new_board, self.n)
        return board

    def incremental(self):
        return False

You need to write three functions:

1. The initialization where you call the constructor for the UserEvalVector.
2. The recompute function which, given a list of doubles, returns a new list of doubles.
3. A function called incremental that simply returns False.

In the example above, we first turn our list of values back into a 2 dimensional board, then apply one cycle, and return the flattened new board.

In the Seeker model, we use this class as follows:

n = 12
m = n//3
iterations = 3
gol_operator = GoL(n)

# Create environment and create decision variables in small board in the middle
# of a larger board 
env = skr.Env("license.sio")
central_board = make_2d([env.categorical(0, 1) for i in range(m*m)], m)
large_board_2d = make_2d([env.convert(0) for i in range(n*n)], n)

# Place the small board in the center of the large board
start_row = start_col = n // 2 - n // 6
for i in range(m):
    for j in range(m):
        large_board_2d[start_row + i][start_col + j] = central_board[i][j]

# Run the cycles
boards = [flatten(large_board_2d, n)]
for it in range(1, iterations):
    boards.append(env.user_defined_vector(boards[it-1], gol_operator, n*n))

# Compute the net gain of lifelings
obj = env.sum(boards[iterations-1]) - env.sum(boards[0])

# Maximize
env.maximize(obj, 5)

The critical line in this model is:

boards.append(env.user_defined_vector(boards[it-1], gol_operator, n*n))

As you can see, we tell the solver to apply a user defined operator on the board obtained after the last cycle using an instance to GoL. The n*n parameter lets Seeker know how long the list is that the operator provides as output.

With this model, we can also solve larger problems, such as a 13x13 board inside a 40x40 board, where we let the lifelings roam for 20 generations before we harvest them. In this case, the solver decided to place 37 lifelings initially so that we have 219 in the end, leading to a net profit of 182 lifelings.

Can your solver do better?