Constraints on user programs? ("rules")
Scott Wolchok
leave whether and how they should be enforced for another discussion.
Here are some that I think fit with a "foraging cells" theme. O(1) is
w.r.t. every parameter of the game. N = # cells, S = world size in
squares, P = # plants, etc.
- O(1) state per cell between actions, other than that passed in the
WorldView and messages
- Cells may not modify or access each other's state except through
messages
- No global state
- Cells may only access things that are "supposed to be visible" in
WorldView
- Cells may send only O(1) messages of constant size
Let's assume that people try to abide by these rules in a gentlemanly
fashion, except that they use the message queue. The problem is that
the current message queue can be used to implement O(N) state just by
having every cell send a message containing its state every turn.
Moreover, N quickly approaches a large fraction of S for the current
value of P, which means that you can use the message queue to build a
(admittedly out-of-date w.r.t other cells) global map and make
decisions based on that. Therefore, if you like this ruleset, the
message queue should be restricted.
On the other hand, it is probably pretty hard to obey these rules in
Python, and they pretty much restrict cells to being finite state
machines. We could make them Turing complete by letting them mark the
ground, but then this turns into ICFP 2004 (http://
alliance.seas.upenn.edu/~plclub/cgi-bin/contest/ants.html), and I like
the idea of fully-programmable but myopic cells.
What should we do, then? The answer is probably to restrict inter-cell
communication somehow. Perhaps cells should be able to communicate
only within a limited range?
(By the way, I've started to view the behavior of the cells as less
like cells and more like robots colonizing space with the aid of
instantaneous communication as a result of ben.py and my work on
benvolution.py. Make of that what you will.)
Thomas McColgan
> I'd like to have a discussion of the rules for user programs. Let's
> leave whether and how they should be enforced for another discussion.
- We should differentiate between rules that we want for
fairness/interestingness and the ones we want for the sake of speed.
Rules for speed:
- I think once we have a ladder server going, there will be several
classes. One will be a free-for-all, where O(N^2) or worse for the
game overall will probably not be avoided. Another class will be
geared towards really big battles with as many agents as possible.
Here restrictive rules will be enforced, hopefully getting the games
to scale with O(N).
Rules for fairness:
> Here are some that I think fit with a "foraging cells" theme. O(1) is
> w.r.t. every parameter of the game. N = # cells, S = world size in
> squares, P = # plants, etc.
>
> - O(1) state per cell between actions, other than that passed in the
> WorldView and messages
This seems too restrictive, since it effectively prohibits having an
internal representation of the world in the cellm which is required
for many interesting behaviours.
> - Cells may not modify or access each other's state except through
> messages
> - No global state
> - Cells may only access things that are "supposed to be visible" in
> WorldView
I agree
> - Cells may send only O(1) messages of constant size
I think this is good, because it brings a bit of the positive aspects
of the first rule, but i don't find it quite as restrictive. Also, it
is a lot easier to enforce.
As a rif on that, perhaps we should replace the queue by a kind of PO
Box system, each box can hold one message at a time. perhaps even
without being cleaned out every turn. Each team would have a fixed
number of boxes throughout the match.
> What should we do, then? The answer is probably to restrict inter-cell
> communication somehow. Perhaps cells should be able to communicate
> only within a limited range?
If we do aim for O(N) in the speed-devil class, I think this precludes
localized and directed message queues(unless there is some kind of
location-hashing with O(N) that I am unaware of). Limited queue length
seems like a possibility.
Another, less direct way might be to make sending of messages cost
energy. For sufficiently large costs that would make strategies that
rely on heavy messaging unviable.
> (By the way, I've started to view the behavior of the cells as less
> like cells and more like robots colonizing space with the aid of
> instantaneous communication as a result of ben.py and my work on
> benvolution.py. Make of that what you will.)
One of the ideas I have toyed with before was actually something a bit
like that, a space colonization programming game. The cool thing about
that would be that you can actually do non-instantaneous ie
relativistic communication, time passing at different paces for
different bots. That would be pretty much impossible for a human vs
human game.
So to recap: I think O(1) messaging is good, O(1) state is not, at
least not for the free-for-all type tribes. The other rules, as
already touched upon in CHEATING, hold.