Ich habe einen kurzen Werbevortrag für Python am Institut gehalten, an dem ich arbeite. Falls es jemanden interessiert, hier die PDF: mccolgan_python_2011
This article describes a project of mine that has been laying around my harddrive in a rough draft for a couple of months. I want to continue developing it at some point, but can’t right now for lack of time. Many of the details described here will very likely be subject to change, but the basic concept stands.
Cells is a programming game, meaning that the player programms the agents before actual gameplay starts, and then watches pits his code against that of his oponents. It features two or more teams of hundreds or even thousands of identical agents, which I call “cells”. These cells live in a 2-dimensional simulated environment, and compete for the control of resources scattered around the world.
By identical I mean that they share the same code, but since their state need not be identical, they can specialize during the course of the game, if the programmer designed it that way. There is no central controlling instance, and therefor the behavior of each team is somewhat like that of a swarm, or a tribe of ants(the original inspiration for this). While it is theoretically possible to make one cell the commander and let all the rest do its bidding, a more decentralized and emergent style is encouraged by the design.
The two main aspects of this game are the cells and the world they inhabit. A brief description of the two follows.
- Elevations: I mentioned earlier that the playing field is 2-dimensional, which is not entirely accurate. It is really 3-dimensional, because there are different elevations. These are indicated by shades of brown in the screenshot above. Cells may only cross a certain elevation difference, ie they can’t move up or down a too steep cliff. This is important, because it makes it possible to build walls.
- Energy sources: As explained below, cells need energy to survive. There are two sources of energy, one that is scattered around the whole world, and is not renewable. And the other, which is generated by plants, symbolized by green dots on the map. These produce this energy at different rates, and do so for ever.
- Coordinates: The world is divided into integer coordinates. A cell may only move to an adjacent coordinate any given turn. Elevations are also given as integers.
- Energy: Cells need a certain amount of energy every turn to survive. They can store as much energy as they want in themselves. If their energy level reaches zero, they die, and they leave behind an amount of energy at the coordinate they died in.
- Senses: Cells are very myopic. They can only sense the fields they are on, and the ones directly adjacent to them. The information they can sense is the elevation and energy of the coordinates, the presence of any cells present and the team they are on. I’m not quite sure if they should be aware of global coordinates. Right now they are.
- Communication: Cells can always communicate with each other. They send messages to each other through a global message cue(each team has one), and messages get delivered in the next turn. In the current version, they can send arbitrary information, but I might restrict that later on, to perhaps an integer.
- Fighting: Fighting in cells takes place in a very game-theory-ish way. If a cell encounters an enemy, it can either choose to attack or to do nothing. If both choose to attack, they both sustain heavy damage(read: loss of energy). If both do nothing, they walk away unharmed. If one attacks, and the other doesn’t, the defending one sustains damage, but not as much as if it had attacked. I think this opens up the decision to some interesting tactical considerations.
- Reproduce: Cells, being cells, can reproduce by splitting into 2. This requires a certain amount of energy, and the spawner can pass some arguments to the constructor of the spawnee.
- Manipulate terrain: Cells can lift one unit of earth from the ground, reducing the elevation there by one, and later dump it at a different location. The screenshot shows an example of this, the read tribe is building circular walls around the plants they control.
This is the game so far, as mentioned earlier, it is still very much in draft form. If you would like to play around with it, I have it on git here. The only requirement is pygame.
In the next post I will outline the changes and additions I would like to make in the future. If you want to participate or have any ideas please feel free to comment or contact me.
Spoiler Alert! This post contains details of how I solved this problem. If you want to try this problem yourself, I strongly recommend you don’t read on. Coming up with your own method to do this efficiently is all the fun.
It goes like this: A datacenter needs to be cooled using a duct. It is required to pass through every room of the datacenter exactly once, and some can’t be crossed(marked by a 1). It must start at the entrance(2) and end at the exit(3). The task is not to find a way of doing this, but rather counting how many ways there are to do it. I won’t reproduce the specifics, but here is a snippet:
Here is an example datacenter:2 0 0 0 0 0 0 0 0 0 3 1
There are two possible ways to run the duct here:2--0--0--0 | 0--0--0--0 | 0--0--3 1
or2 0--0--0 | | | 0 0 0--0 | | | 0--0 3 1
Write a program to compute the number of possible ways to run the duct. For the above example, the correct answer is 2.
Check their challenge page for specifics.
My first implementation was a simple forward search. Start at the entrance and iteratively grow the tubing one step at a time. I implemented this with a queue, which contained all the legal tubing variations for a given length N. From this I generated all the possibilities for length N+1 by growing by one in all possible directions.
This proved to be disastrously slow, and memory consumption was high, too. Since the branches of the search tree grow exponentially, it is highly beneficial to prune them as early as possible. I did this in 3 ways.
- Merging equivalent branches: To find new solutions it really only matters wether a given room already contains a tube or not. The direction of the tubes is irrelevant. This means that leaf nodes in a tree that have the same ending, and have passed through the same rooms can be merged into one. The number of solutions derived from this merged leaf needs to be multiplied by the number of original variants it contains.
- Prune branches that cut off areas: If a part of the datacenter is cut off and can’t be reached from current the end of the tubing, the branch will not result in valid solutions. They can be pruned.
- Dead ends: This was the last optimization I came up with, and it was surprisingly effective. Basically, to pass through a room, it must have 2 or more adjacent rooms free. If there is only one free, this means the tube can enter, but not leave any more. As a result all the branches that contain this pattern are doomed an can be pruned.
The resulting algorithm is quite speedy. I wrote it in C++, using STL containers for all my data structures. I was only really interested in the algorithmic optimizations, and didn’t worry too much about memory optimizations or other tricks to shave off milliseconds. Also, I performed all these optimizations all of the time. It might well be that their effect is beneficial in the beginning but outweighed by their cost in the final stages, when there is not much left to prune.
Another optimization I thought of but never implemented:
- Uneven number of exits: If there is an area that can only be reached by a number of bottlenecks of width one, this can only be even if the exit is on the same side as the current tube end, and uneven if they lie on different sides. Otherwise the configuration will eventually end up with a dead end as described in the third optimization.
I’m not sure how much time this would save, since the check is quite elaborate compared to the other tests I mentioned.
The reference problem with the 7×8 grid ran in about 15 seconds on my 2Ghz Core2Duo. It found 301716 solutions. Larger examples take significantly longer, so I guess the solution still has exponential scaling behavior, which is probably not surprising since it is very similar to a hamiltonian path problem.
The code is not really fit for public consumption, but if someone asks for it I might clean it up and post it here.