Cells. A massively multi-agent Python programming game.
phonons.wordpress.com
phonons.wordpress.com
I'll be looking at the source soon, but in the meantime I'm curious to see if other people would be interested in playing this. There could be a repository of genomes/tribes you can download and compete against, or perhaps this would be done server-side so your tribe's genome couldn't be cloned?
As a side note, it seems to me that (unless cells can be aware of their comrades' positions) global position needs to be availible in order to build walls, which is damn cool.
Cheers!
>As a side note, it seems to me that (unless cells can be aware of their comrades' positions) global position needs to be availible in order to build walls, which is damn cool.
I don't think so. All global position tells you is "how far away are the boundaries of the map?" Unless there's something I'm missing, you can get everything else just by keeping track of "offset from where I started".
As another side note, restricting messages to integers seems pointless, since arbitrary information can be uniquely encoded as an integer given enough ingenuity. It's a problem that would get solved once and then just irritates people instead of actually constraining solutions. (I assume python integers are only bounded by available memory space.)
Limiting them to n-bit integers, where n = 4 or 8 for example, would be more pointful, but again I think it would probably only make a particular behaviour harder to implement, not significantly limit the set of behaviours that are possible to implement.
Concerning the integer vs bit, that was what I meant, was still thinking in terms of C ints. An even more extreme version would be to force the agents to store their state in a similar manner, but I think that would be taking it too far.
> ladder-server, too, where you submit your tribe and it > enters into a perpetual tournament and gets ranked
That would be too cool. I'd love to see this happen. I wonder what kind of market there is for something like this.
EDIT: I'm going to be looking through the code more today, though right now I am going through finals at college. I don't want to promise anything, but this is something I could see myself contributing to, if you'd want (though now might not be the time so early in the process). Shoot me an email (in profile), if you'd like to be in touch.
Documentation is nonexistent, sorry for that. That was the first thing that came to mind when I saw that this hit the front page, should have thought of that earlier.
I'll go through and comment it though, this resonance has given me a big boost in motivation.
May I recommend Microsoft's TrueSkill algorithm for ranking genomes? There's C#[1] and Java[2] implementations available. Full disclosure, I have no association with Microsoft Research, but I am the author of JSkills.
[1] github.com/moserware/skills [2] github.com/nsp/jskills
Lisp vs. Python would be most interesting if cells could pass arbitrary information to each other. This would make it easy for Lisp cells to modify their own code. Cells signalling each other and querying each other's information would enable interesting interactions. Some sort of sand boxing would seem to be desirable.
2. Python cells could modify their own code just as easily (if not easier) than Lisp cells.
I'm not expert on the topic, but what do you mean by easier ? By using eval ? Is it really easier than altering an expression tree stored in a list ?
Python doesn't even begin to match it's abilities in this arena.
(intro: http://www.fact-index.com/s/se/self_modifying_code.html)
No, I'm not. Give your example.
> Python doesn't even begin to match it's abilities in this arena.
Sure it does. Give your example. To quote your (useless) link: "TODO an example and discussion of 'high-level' self-modifying code such as in LISP."
The problem is:
Replacing functions at runtime in Python is just as easy as replacing them at runtime in Lisp.
Is not the be all and end all of self-modifying code :)
EDIT: this is a pretty good intro to Lisp Macro's http://www.apl.jhu.edu/~hall/Lisp-Notes/Macros.html The code examples on there are fairly simple though (but it starts you in the right direction).
For example one thing Python is currently unable to do is modify a line in a function to do something completely arbitrary (well, theoretically you could code a specific line to be able to do that, but it wouldn't be trivial to make an entire function that could be trivially modified on the fly).
[we are now at the extent of my Lisp knowledge]
So you're making claims without firsthand knowledge? Awesome.
> Is not the be all and end all of self-modifying code :)
It's the vast majority of what people actually do in Lisp, and Python supports it just fine.
> EDIT: this is a pretty good intro to Lisp Macro's http://www.apl.jhu.edu/~hall/Lisp-Notes/Macros.html
Macros have nothing to do with self-modifying code. You clearly have no idea what you're talking about. Macros are compile-time transformations of code: they have no runtime effect whatsoever.
> The code examples on there are fairly simple though (but it starts you in the right direction).
Dude, I've got PG's ANSI Common Lisp on my bookshelf and I've read On Lisp multiple times. I understand macros. What I don't understand is this Lisp worship evinced by people who actually have no idea what they're talking about with respect to self-modifying code.
> For example one thing Python is currently unable to do is modify a line in a function to do something completely arbitrary (well, theoretically you could code a specific line to be able to do that, but it wouldn't be trivial to make an entire function that could be trivially modified on the fly).
Provide a Lisp example of "modifying a line in a function" that runs in SBCL and I'll show you the same code in Python. Seriously: you're the one making a claim here, you need to be backing it up.
P.S. I remain utterly unimpressed by the anonymous coward downmodding me, upmodding you, but clearly either unwilling or (more likely) unable to defend your claim. More semi-religious Lisp fanaticism <yawn>.
I have to admit your posts came across as the old "My Language is As Good As Yours" argument, but it appears your a Lisper too? I have to also admit everything I have seen/heard says Lisp is the original self-modifying language and is damn good at it :) but in retrospect that wasn't the point you were making.
(I was hoping a Lisper would step in with some code... but apparently not...)
Handshake?
Thanks, I appreciate that.
> I have to admit your posts came across as the old "My Language is As Good As Yours" argument, but it appears your a Lisper too?
I'm well-versed in Lisp, but I don't typically choose it for personal or professional tasks for a number of reasons.
> I have to also admit everything I have seen/heard says Lisp is the original self-modifying language and is damn good at it :)
The original self-modifying code was assembly language (or, really, machine code). It's a useful trick when you're working with extremely constrained computers whose memories are measured in single digit kilobytes, but long ago was recognized as really difficult to use in writing quality software. Real self-modifying code, which means code that actually overwrites the instructions the processor will execute, makes it incredibly hard to reason about programs and debug the resulting software. Real self-modifying code was long ago relegated to the likes of Mel (<http://www.cs.utah.edu/~elb/folklore/mel.html>). As I understand it, most Lisp programmers simply mean that their system properly handles the replacement of most (all?) functions/methods/definitions at runtime, which is in large part true of Python as well.
I open to being corrected by a Lisp programmer using a modern Lisp (hence my request for SBCL) to show an example of real self-modifying code, but I really don't expect that any will, because I don't think anyone's seriously written such code since I was out of elementary school.
After all, most of your APM in a game like Starcraft is going toward things that you could replace with a very small shell script. Although I can't argue with success, it's always felt silly to me that a big part of the game is just building enough intuition and reflex so that you can actually spare your mind to think about the interesting parts. If you can simplify the reflexive pieces at "game-time" while keeping them interesting in a different way, that might leave you with a game that's even deeper strategically.
However, it would be a difficult exercise to make an RTS that was dynamic enough that some folks with a lot of spare time didn't just write "ultimate" AI for all the units that is close-enough-to-perfect, and distribute that to all lazy players. Perhaps one might establish limitations on the resources or length of scripts you can write, so that it's difficult to write a script that is simultaneously effective for strategy A and different strategy B, and you need to specialize your code based on your style of play.
Interestingly, Core Wars is from the age of multiple threads running on a single processor, sharing memory, whereas the more recent Cells represents a share-nothing distributed system with autonomous agents.
EDIT: my fork also cleans up a couple real issues, including letting the game run properly when psyco's not installed and allowing the user to specify minds on the command-line (albeit in a hacky way).
[link redacted]
Here is a video (sorry using Quicktime which only grabs the whole screen and not a window) of evolving_chaos v.s. ben which is fun to watch http://www.youtube.com/watch?v=Zy_-4rRmOCc
[link redacted]
http://github.com/markoconnor/cells/blob/master/minds/benmar...
File "cells.py", line 205, in get_view
next(had to patch the math.copysign() in the original version as well, as it only exists from 2.6 on)
Edit: works with continue.
As I searched for a link, I discovered that there's a newer version out just 2 years ago. [2]
[1] http://www.devhood.com/tutorials/tutorial_details.aspx?tutor...
It would be cool if you could drop pheremone trails too. I'm thinking like a programmable Sim Ant
That's what ICFP 2004 was. Here's the specification, if you want ideas:
http://alliance.seas.upenn.edu/~plclub/cgi-bin/contest/ants....
http://alliance.seas.upenn.edu/~plclub/cgi-bin/contest/index...
As an aside, to those of you who are interested in this sort of game AI, you might want to look at the growing (AI sub)field of General Game Playing. The idea is to write a basic game AI that can take in arbitrary rules, "think" about them a little, and then play the game against one or more opponents. The author of the played favored to win this year's championship, Turbo Turtle, has open-sourced his infrastructure on Google Code (ggp-base), which makes it orders of magnitude easier to participate. More info: http://games.stanford.edu, http://cs227b.stanford.edu.
I'm thinking each player would submit an AI to start the game. At any point during the game players could "check-in" code (VCS-style) and cells created from that point on (via the splitting described in the article) would have this new code. Players would be allow, for instance, 2 check-ins per game. The upgraded cells would be represented by different shades of the player's color so that they could be kept track of.
I see this being useful for times when a player drastically misuses his cells initially or for an entirely different style of play (a different bracket on the ladder server).
Your code then looks at the strategy variable to see which code path to execute.
It would sound like it would be smart to start off with the extremities. Say, start off with the same amount of 100% agressive and 100% defensive cells. They mate, get a 50/50-cell, which is partly both. If a combination of 10% agressive and 90% defensive is "the secret", then the cells will eventually all become that combination in the end.
Now, the question's whether this is a tactical approach or not...
Why are you using accessor methods? If it's because you might want to change them later, you could just use a property if that unlikely event happens. There is a real cost to accessors in Python. They also add a lot of visual noise.
Why did you make an enum class (ActionType)? That adds an extra hash table lookup for not much benefit over
ACT_SPAWN, ACT_MOVE, ACT_EAT, ACT_ATTACK, ACT_LIFT, ACT_DROP = range(6)
If this is a core feature requirement, then as far as I know your only option is to change languages to something where you can rigidly sandbox. Your nearest option in programming space would be Perl and some variant of Safe (that's a CPAN module name). Otherwise, if you can live with a gentleman's agreement, you're fine. This may make the automatic-online-matchup really tricky, though.
Another option I was thinking about for this purpose is parsing the python to make sure they don't get up to anything fishy, but I have no idea how hard a Python parser would be. My guess is very.
Or we put them into separate proceses, as swolchok suggested.
If that was safe, it would have been bundled up into a module. This is a Frequently Asked Question for Python, and the answer is, you can't.
I thought of process separation, but it won't work. The best performance would be one persistent process that runs the cell computations, but it's too easy for Python code to find places to hide data persistently for communication above and beyond what you expect.
For example, would you have thought to block the following?
Python 2.4.3 (...)
Type "help", ...
>>> def f():
... f.i = f.i + 1
... print f.i
...
>>> f.i = 1
>>> f()
2
>>> f()
3
And mind you, that's one example, and not a very sophisticated one. If you're answer was "no", or indeed anything other than "duh, of course, I've known about that for years", then you don't stand a chance at the sophisticated stuff.
You can't fork at cell-run-time, because while a process couldn't write anything back out to the parent, it could still grovel over the parent's data space which could still be used to advantage, and depending on the rest of your code may still make an out-of-band channel available.
You could fork a process per cell before anything "incriminating" has been instantiated in the parent process, but that's got a lot of problems even on one machine (including the 32K process limit), let alone a hosted service, and you'd still end up with the possibility of a "cell history" being recorded that could be potentially exploited.
Python does not give you the necessary primitives to accomplish this task. I see three options: Live with it (a viable option except online), spawn one process per team and officially bless that level of communication (though it radically changes the nature of the game), or change languages.
To be honest, Python is going to cause you other problems on your online server too, such as the extreme difficulty you're going to face in isolating Python functions to a certain amount of CPU time. (Same problem, as long as the Python code cooperates it might be possible (and it might not really) but if it starts hostilely modifying the parent code you lose.) Other languages have support for that too.
Unfortunately, you're really bashing on Python's weaknesses here.
Forking and execing prevents this.
And will be uselessly slow, which is why I dismissed it with hardly any thought.
# time bash -c "for i in {1..1000}; do python -c '1'; done"
real 0m9.351s
user 0m6.439s
sys 0m2.868s
Probably for now the best solution would be to make this form of cheating a bit hard, and then living with it, and having provisions on the ladder server to erase all scores based on a cheating genome if it is detected.
And given that you are willing to live with that, Python is otherwise a pretty good language, very easy to pick up, etc. I love this in general, I'm explaining this so you don't end up burning time in a tarpit and instead use it to build something that will actually work. :)
If you sandboxed the Python process running agent code to limit the mischief to that particular process, that would go a pretty long way, and that sort of thing is certainly possible by restricting syscalls at the OS level.
I would wait to say PyPy has "perfect" sandboxing until it has been attacked for a while, though. CPython used to have a sandbox module, too. But at least PyPy has been designed with this use case in mind.
It might not be ready for prime-time in some very critical systems (like a web browser for example) but it's honestly probably good enough for this, especially in combination with process jailing as you suggest. I might consider trying to patch Cells up to use PyPy's sandbox instead of the non-solution currently implemented (I cried (okay, groaned) when I heard about it-- yeagh), when I have time, and if nobody else does it first. I'm a bit worried anything I write now would get lost or broken in the incoming tide of patches/changes anyway.
The main problems with using PyPy's sandboxing is probably with communication to/out of the sandbox, which is apparently problematic. I also anticipate some complaints about relying on PyPy in the first place, which is rather abnormal compared to using CPython-- using and relying on PyPy-specific features is pretty much unheard of.
I've tried their binaries, their source (including using the SDL.Framework which was suggesting in the SuperUser link another commenter posted.)
If someone would like to port this to something a little more usable, I'd be obliged. If not, I'll be spending a bit of late June doing that.
http://superuser.com/questions/43531/installing-pygame-on-sn...
Worked great for me.
Here is a short list of open-source MMO servers we could start with: http://www.reddwarfserver.org/ http://opensimulator.org/wiki/Main_Page http://www.next-gen.cc/
I would WAY rather do this than go to a movie or play videogames. I mean think of all the programming you would learn and get good at. After playing video games I just feel tired and my fingers hurt.
Let me know if anyone wants to help me organize something like this.
http://news.ycombinator.com/item?id=1395513
One cell per core? Ah, the future...
http://groups.google.com/group/cells-game-users http://groups.google.com/group/cells-game-devs
I built a bot for it once: http://github.com/akkartik/brooks-ruby-warrior
I bet I'm not the only one who's excited and would love to contact you about this!
Edit: even better to contact me through github though.
What do you people think about such games being made commercially? (indie ofcourse)
http://www.gamerz.net/c++robots/
I've got a robot "on the hill" and it's great fun.
I might be blunt, but I'm not trying to be rude on purpose
Yes.