Project 4: Amoeba

You control an amoeba-like creature that occupies a connected set of cells in a 100x100 grid. The grid wraps around in both the horizontal and vertical dimensions. To move, the amoeba retracts a cell anywhere on its periphery, then extends to another cell on the periphery. A cell is on the periphery if it borders (orthogonally) a cell that is not occupied by the amoeba. The amoeba can have internal "holes", but once these holes are closed by movement, they cannot be reopened internally. The grid contains bacteria that are the food of the amoeba. The amoeba can grow by eating these bacteria.

Bacteria are sensitive to their immediate surroundings, i.e., whether there is an amoeba, another bacterium, or nothing in each orthogonally neighboring cell. If they are surrounded on 3 sides by bacteria and/or amoeba, they become immobile. If they are surrounded by empty cells, they stay put. If they are surrounded by one occupied cell, they try to move in the opposite direction to the occupied cell. If they are surrounded on two sides, they move to one of the two remaining vacant cells at random. Bacterial movement is done by the simulator one bacterium at a time, so that a bacterium responds to the state it observes just before it is selected to move by the simulator.

The amoeba movement is governed by a parameter called the metabolism, m where $0<m\leq 1$. On any turn, the amoeba can retract from up to a proportion m of its cells, and grow the same number of new cells on the amoeba periphery. So m=0.5 means an amoeba gets to move up to half of its cells (rounded up) per turn. Retracted cells must have been on the periphery at the start of the turn. Any move must ensure that the amoeba remains connected at the end of the turn. If the simulator detects disconnection, it will reject the moves and the amoeba will stay put. Before and after the amoeba moves, it receives information about the occupancy of every non-amoeba cell adjacent to the amoeba periphery. So it might discover that there is a bacterium adjacent to a cell onto which it has moved. Note that by the time the amoeba gets to move again, the bacterium might itself have moved. The amoeba has limited memory. It can remember the adjacent cells with bacteria from the end of the previous turn, in addition to one state variable consisting of a single byte (which is initialized to zero at the start).

An amoeba eats an adjacent bacterium by moving onto the bacterium's cell. This kind of eating move occurs before the regular moves, and does not require an offsetting retraction. So eating makes the amoeba grow. An amoeba can eat an arbitrarily large number of bacteria on a turn, if they are adjacent to the amoeba at the start of the turn. However, a newly occupied cell (due to eating) cannot be used for movement on the same turn.

The bacteria get to move first. Then the amoeba has a turn, and the bacteria and amoeba alternate from that point on.

There are two additional parameters to this game. The parameter A is the size of the amoeba at the beginning of the game. We'll assume $A \geq 9$ is a square number and that the initial amoeba configuration is a square region in the center of the grid.

The parameter d is the density of bacteria that the environment can support. If we let s represent the number of cells not occupied by the amoeba (at the start, s=10000-A) then there will be $\lfloor ds \rfloor$ bacteria placed at random by the simulator. The simulator will not place two bacteria on the same cell, or a bacterium on a cell initially occupied by the amoeba. When a bacterium is consumed by the amoeba, the simulator will recalculate ds and spawn an additional bacterium at a random location if the environment can support it. d=1 would mean that all non-amoeba cells would be covered by bacteria, while d=0.01 would mean that about 1% of cells would contain bacteria. While the amoeba knows m, it does not know d.

The goal of the amoeba is to quadruple in size. The score will be the number of turns that it takes to achieve that goal; the smaller the score, the better. The simulator will timeout after a large number of turns, and players who timeout will be ranked by the size of the amoeba at that time. We'll discuss in class what a suitable "large number of turns" might be.

Some initial things to think about:

• What can a big amoeba do that a small amoeba can't?
• The timing goal requires your amoeba to be time-efficient. How would you measure and/or optimize efficiency?
• How might your strategy differ in a bacteria-rich enviromnent versus a bacteria-sparse environment? How would your amoeba tell the difference given that it does not know d?