World Physics

[Andrey Levushkin]

Hello everyone, the first meetup to for this project is on 11th of December but before then it would be good start the discussion on the architecture of this project. 

So i guess the first question is what will be our game world physics. Are we just copying the ones at robocode http://robowiki.net/wiki/Robocode/Game_Physics?

 

Andrey

[Attila Sztupák]

Hi,

The two major ways I see on how the arena physics can be modeled are either a turn-based or a continuous, event-based model.

A simple turn-based model can be that each bot is providing a value of something like 'newtype Step = Step { runStep :: Input -> (Command, Step) }', where Input is the state of the arena and/or the effects of our commands from last turn, Command is a list (or other monoid) representing the action(s) the bot is to take during next step, like accelerate, turn, fire, do a radar scan on a given arc, etc. After each bot returned its answer, the arena applies the commands, advances time, and feed back the result of the turn to the snd of the retval of each bot (thereby the bots can keep an internal state by passing it on between their Steps).

In the event-based model  the bots could send in actions (like start/end turning; change acceleration; start scanning), and could register callbacks to certain events (time 'ticks', timeouts, results of scanning, turned to given heading, etc.). The callbacks may change the state of the bot, send in new actions, register new callbacks (or unregister old ones). The engine would maintain the state of the arena and synchronize it with the timeline, either by jumping to the next 'point of interest' on the timeline or by trying to simulate the events in 'real time'.

IMHO the turn based model would be simpler and easier to understand/write bots against, but the event-based feels like having more realism. 

Beside the basic physics model, IMO the other decision that has to be made upfront is the hosting/communication model between the arena (engine) and the 'bots. This include interesting questions, like how do we make sure that the contest is 'fair', so that all bots have access to the same CPU resources, or latency or to isolate them from the environment and each other, etc.

If I see it correctly, should we choose to implement the game only in terms of pure computations, so that the same game setup (initial bot placements, same arena, etc) will always lead to the very same result (including the 'log' of the game), it wouldn't be possible to guarantee fairness. There's no way (without introducing side effects) to limit the space or time needed to evaluate a pure function. Also, a badly written or malicious bot may bring the whole game down (consumes all memory, runs into infinite computation). This approach would also limit the execution model to in-process (loading the bots as plugins). 

Pros: simple engine model, repeatable game runs. Cons: effective bot algorithms wouldn't be rewarded

If we give up repeatable games, our options may include:

- running the bots in-proc, sequentially, but the bot functions wrapped in timeouts: fair regarding time taken, but would depend too much on the execution environment performance

- running the bots in-proc in their own thread, communicating through channels: may only fit the event-based model, delayed/partial reactions possible

- running the bots as external processes, communicating through sockets: process isolation takes care about memory issues, relies on OS to provide fair scheduling; makes non-Haskell bots possible

- running the bots each on their own virtual environment, like on EC2 instances: virtualization may provide fairness on both memory and CPU; latency could be an issue; most complex deployment/execution model

Of course an alternative way to provide fairness would be that we implement our own virtual machine for the bots, with a haskell-to-lambdawars-VM compiler, but that might be just slightly far-fetched :)

Attila

[Attila Sztupák]

There seem to be quite a few programming arena games (RoboCode definitely seems like the most known): http://www.programminggames.org/AllPages.aspx?Cat=Arena%20Games

This list could be a good pool of ideas for both the game engine and for algorithms of bots.

Attila

On Wednesday, December 5, 2012 8:32:53 PM UTC, Andrey Levushkin wrote:

[Andrey Levushkin]

Hi, I broadly agree with what you said. The turn based approach would be much simpler and it will allow us to keep the bot code pure if we execute the bots in the same process as the arena. It will also make the bots much easier to implement.

The step idea you suggest is pretty much what i was thinking of as well. But rather then pass in input to the step it may be cleaner to use the Reader monad so the bot can read in any parameters about the world it needs (position, radar scan results, etc). So the bot become something like the following: 

newtype Bot = Bot { runBot :: Reader World Command }.

If we want to selectively hide properties about the world from the bots to create a 'fog of war' we can wrap the Reader monad.

So every turn the arena runs all the bots with the current state of the world, composes the resulting Commands to create a new world pruning out defeated bots and repeats until only the winner is left.

I've put a suggestion of what the main types involved may look like here: https://gist.github.com/4241491 . Feel free to edit it, it's a very rough first pass.

In terms of running the bots i think the easiest thing to do would be to run everything in the same process using timeouts as you suggest. This can still be parallel as the bots don't need to communicate during a single turn so we can use a parallel map to get commands from all the bots for the current state of the world.

Also if we run everything in process it will be easier to create a web front-end for this, probably based on something like http://tryhaskell.org/. If the bots need to be in the IO monad to run then executing untrusted code without compromising security becomes pretty difficult. 

Andrey

[Tim Williams]

Hi Andrey,

One problem with the "Reader World Command" type is that the Bots are not able to maintain any state unless it is represented in the (assumed public) World type.  Attila's "simple automata" type however, does allow bots to maintain their own private state using private types.

Well done for getting started though!

Tim

[Andrey Levushkin]

Hi Tim, yes good point. The bots will need to be able to store state. My thinking behind the suggestion was to create an easy to use API for people building the bots. i appriciate that this is subjective but I think that having the bot execute in a monad where they can read the state of the world will be clearer then explicitly returning the Step.
we could make the Arena monad an instance of MonadState to deal with state. Possibly by using StateT with the Reader monad. Thoughts ?

Andrey

[Andrey Levushkin]

[Tim Williams]

Hi all,

I've uploaded an example of how we can use Haskell's continuation monad transformer to interleave an arbitrary monadic computation, which in this case will be Andrey's Reader monad for the Bot environment. In the example below though, I've wrapped IO for simplicity. Note that although the Bot processes are an infinite stream of commands, we can step through them as appropriate, which will be useful for rendering, debugging etc. 

https://gist.github.com/4271543

If we all agree on this approach, we can start to develop it.

Tim

[Tim Williams]

Hi all,

I've updated the code to be less general and much more applicable. The Bot monad produces a suspended stream of computations yielding a command value and the rest of the stream. The monad also provides a reader environment for "dashboard" readings, which is demonstrated.

https://gist.github.com/4280132

Tim