cells. A massively multi-agent Python programming game.

Posted on by Thomas

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.

Introduction

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.

The World

  • 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.

The cells

  • 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.

Published by Thomas

53 thoughts on “cells. A massively multi-agent Python programming game.”

  1. This seems really interesting. I’d be very interested in seeing the programming aspect of it — instructing the cells how to behave.

  3. I’m REALLY interested in this. I’d love to help out in any way I can. I’m reading through the source right now.

  11. I think you would need to specify the parameters for the programming of each cell (or cell colony). Hope you create an email list or some such because I’d love to contribute (given limited time).

    1. The best way to keep updated is to watch the project on github. I’ll probably also be posting about this on here in the near future. The feedback I’ve been getting has given me a real motivation boost.

  12. I love the idea of gaming, but I don’t have enough time to really dig into any serious games, so I am always dreaming ideas for programming games.

    I’d love to play a great programming game, so get on it 😉

  14. Really reminds me of Core Wars, had a play with that a while back, was really interesting stuff. I look forwards to messing about with this.

  16. So basically you’ve created a sophisticated version of “the Game of Life” invented on 1970?

  17. A pheromone trail would be fun; you could drop some marker at a location, and I guess it would decay in intensity over time or something. It might make it possible to coordinate an attack or something — send out a scout, and the moment it sees the enemy it runs away putting out a scent indicating danger (either to be attacked or avoided).

    1. I was thinking exactly the same thing. This algorithm is generic, and you can do a lot of things with it: http://en.wikipedia.org/wiki/Ant_colony_optimization )

      You can emulate pheromone trails using the communation layer, but it’s an ugly approach. Maybe we can remove global team communication (communication only allowed between neighbours cells) and add a pheromone trails as a core mechanism of hints between cells.

  18. “How does the game end?”

    How does Conway’s game of life end? How does SimCity end? 🙂

  19. This is one awesome idea.. I was doing some Generic Algorithms visualization during my grad.. I compiled the coordinates of the population into a video… it looked like an army of ants trying to find something on a rocky terrain and gradually converging to a solution… it looked awesome !!!
    This one is gonna be a killer… this is like Robowars, except much much better and amazing to watch

  21. Hi – thought I’d link you to a project I’ve been playing with for many years, that isn’t a game but has many similarities: http://qtbugs.googlecode.com . In mine the bugs evolve via genetic algorithm. The plan was to produce some interesting images, and maybe provide a tool for studying genetics. I might pinch your idea of elevations 🙂

  26. Interesting… I have written a similar program, although the cells in my program is selfsustaining.
    Most is similar, BUT when they reproduce there often is errors, meaning evolution.

  27. I recently released a simple Robocode-like library (you know, tank-bots fighting in a battlefield), but it seems something like “cells” has more potential due to the interactions of so many individuals working together.

    http://code.google.com/p/langbots/

    Though written in Python, the core idea of langbots is to allow writing bots in any programming language (it uses stdin/stdout with YAML structures to talk to the bots). I leave this just as an idea for “cells”.

    Of course, this kind of modularity has its costs (it’s definitely slower, and the bots are somewhat harder to write, unless a -small- interface library is written for the language).

  28. I like this a lot. I know it’s a draft, of course, but the things I’m missing most in terms of minimal functionality are:

    1. An elevation map in the WorldView
    2. Some kind of feedback for a cell when its action has failed.

    In any case, great fun, thanks!

  29. Hi Thomas,

    I wrote a pretty good one, I think — at least, it holds up against the minds that I got when I downloaded everything earlier today. 😉 Can I send it to you to throw in? I assume you can see my email address — drop me an email with how to get it to you.

  30. Really nice concept!

    A few ideas:

    – Cells are not aware of where they are.
    – Cells lay down pheromones, these contain direction: any cells on the same side can see it. The pheromone can have multiple flavors (integer).
    – Pheromones overwrite each other (only one per landscape block).
    – Cells have unlimited memory space.
    – Cells can not see the entire playing field – only a 6×6 view of their surroundings.
    – Cells can not communicate with anybody – only cells in a 6×6 view of their surroundings.
    – On receiving communication a cell gains one more chance to communicate in that turn. It is not allowed to reply to the same cell during that turn.

    – The landscape is generated using fractals :D.

    1. The pheromone idea is something I have played around with, and decided against it. Fractal terrain generation is on the todo list.

    1. Working on a ladder server you can send them to. For now, you can send me a pull request on github and i’ll add it to the repository if you like.

  33. A couple of practice things come to mind. From the word “massively” in the title I wonder exactly how big this world is expected to be. While there is no mention of a maximum world size or maximum players I believe that memory and computational constraints will quickly crop up. Minimally each cell in the world will need to store it’s elevation, fixed energy supply, renewable energy supply and renewable energy rate. Assuming the fixed and renewable sources are rare’ish the elevation could be stored in a one or two dimensional array, while the energy info could be stored in an indexed list (dictionary) … probably best to stored fixed and renewable in separate structures since fixed energy could presumably be consumed and not need to be tracked.

    Assuming some sort of “reasonable interesting” case we could assume a 1,000 x 1,000 array of bytes for the elevation values, 10% overhead for fixed energy and 10% overhead for renewable giving 1,000,000 cells with a ~1.2 MB memory overhead (not much for today’s hardware). Now assume 100 players each with 1,000 starting cells, or 100,000 cells (10% of the total world space). Now you have 100 source code programs, which probably aren’t large, but there is always that one guy who creates a state machine and embeds a huge data table to drive it . Let’s be generous and assume 100 KB for each source program or 10,000 KB (10 MB) total, giving us ~13 MB (always round up when estimating and down when comparing/buying :-D). Still not much on today’s hardware. At the same time I consider this “reasonable interesting” and not massive.

    Here is where it gets interesting. While all instances of a particular agent shares source, each cell will need to have a unique context. At a minimum a stack and instruction pointer. If we assume a 256K stack (which is rather small) then the 100,000 cells require 26,214,400,000 bytes or 26 GB, which is getting kind’a large. Normally, a thread (conceptually) is used for this type of activity, however, due to possible inequitable allocation of cycles you can’t really do that. You want it to appear that all agents execute simultaneously. So that if a cell of agent A enters location X at time T and also at time T a cell of agent B enters location X, you want to be able to know this and apply appropriate rules. This means somehow throttling all 100,000 cells so that each time ‘click’ actions can be assessed (this might also be helpful, by allowing better stack control allowing cells to start with small stacks and dynamically adjust them…but that’s also a time sink). There was an old game called “C-Robots” where the “robots” were written in C and complied to an intermediate language, the simulator would then run a single (intermediate language) instruction for each robot, assessing results each simulated clock cycle. Such an approach with 100,000 cells might be slow (very slow).

    My advice is to immediate set limits that are tractable for today’s common PC hardware. Figure out a good way to get multiple cells to sync at each time cycle (keeping multi-core cpus in mind, because this sort of application can really benefit from parallel execution). Some sort of event list might be useful here, since I believe only location to location transition will require synchronization. Consider having an abstraction layer where the programs generate “cell instructions” (move, eat, reproduce, kill, build …) rather than interact directly with the environment. This should help with the sync issue and allow you to support languages other than Python. The program (agent) could get the status of its cell do some processing then react. It may in fact be better to let the agent coordinate all its cells as a group rather than independently. Think of it as a type of uber chess game. If someone want to write their agent to treat cells independently they could, if they wanted to use central control they could. That way both code and philosophy could be tested in competition.

    Good luck with this, I hope you will be able to find the time to work with your ideas in the future.

    1. You are overestimating a bit the complexity of the draft game version, where the world is 300×300 and there are 2 players.

      However, the danger of somebody writing code that stores a huge amount of data is very real, especially if they are lazy about it. At the moment, there are no penalties to having every bot send out everything it knows at every moment, and then having every bot store all that data from the others. Probably eventually there will have to be limits on the number of messages sent and on the amount of data stored per bot. Python is not so good for enforcing the latter, but it could be done with common sense.

    2. Thanks for your very thoughtful comment. Right now I would be happy with about 10k cells in a game. That is a pretty “massive” amount of agents compared to other games I have seen so far.

      Theres no threading going on at the moment, that is tricky in python anyway. The decisions are just made and then executed sequentially.

      256K per cell is way too much for the stack. what do you want to store in there? I think 1K should do. But of course, any number you pick will eventually reach its limits with todays hardware.

      I encourage you to have a look at the code, if you are interested. Maybe you have some suggestions where performance can be improved. The abstraction for actions already exists, for example.

      Coordinating all the cells with one mind defeats the purpose. As I stated in the article, it is theoretically possible to implement that in the current game, but the design doesn’t encourage it.

      1. I think you will find that you need more stack than you expect. Most languages place local variables on the stack. Python might not be this way, but I think that you will find 1K way too small. I came up with 256K, but looking at .NET threads. They start with a 1M stack.

        I’ve written a small bit of Python, but I’m in no way a Python programmer. Still I’ll see if I can find some time to peek at the code. Not sure I can help, but I find the idea interesting and couldn’t resist a bit of “back of the envelope” tinkering.

        I don’t see allowing the coordination of cells as opposed to your stated purpose. I would see it as an extention that would allow a comparison of approaches and possible hybrid approaches. I don’t see one as preventing the other, I think of it more of an implementation detail (and optimization). A ‘player’ who wishes to have independent agents could use the ‘root process’/central mind as an agent factory.

  34. A side-project of mine is similar to this. A few tips from experience:

    stackless python, multithreading for free

    pyrex to compile python to C++

    GPU computing, CUDA or OpenCL (PyCUDA)

    visual programming for cells – helps beginners understand, and easier to enforce constraints

    tutorial-like series of ‘levels’

Leave a comment