Prototype & Proposal: Multiplayer Asteroids

[akarukov]

Even this simple bot has no problem avoiding asteroids. In the end I think this game is all about ship-to-ship combat, which should be very interesting as there are many possible strategies.

First thing I thought is ship-to-ship combat. I imagine that asteroids will be eliminated very fastly. After that we have ship-to-ship combat. Ship-to-ship combat can be predicted in terms of game theory "differential game".
It is like playing criss-cross. You make first step and then I can say that I already won.
I think we should avoid case when all asteroids are eliminated.
Actually I think the game should became harder at the end. It should more and more asteroids appear.

My proposition is:
Bullet has a mass (m) and speed (v), so bullet has impulse (p).
P(bullet)= M(bullet) * V(bullet)
Asteroid has mass and speed, so asteroid has impulse.
P(asteroid)= M(asteroid) * V(asteroid)
Size of asteroid (Radius) depends on mass. Mass = Volume * Density. Let Density = 1.
V = 4/3*Pi*(R^3), so R^3 = V*3/(4*Pi)
My proposition is to use "The law of conservation of linear momentum" and "The law of conservation of mass".
http://en.wikipedia.org/wiki/Momentum
http://en.wikipedia.org/wiki/Conservation_of_mass

That does it mean? (Actually I understand (hope) that you know it, but I will say).
When bullet collide with asteroid we will have random number of smaller asteroids with random mass and random speed.
But mass should be conservated and impulse should be conservated.
Mass(dead asteroid) = Sum( mass(newborn asteroids) )
P(dead asteroid)+P(bullet) = Sum( P(newborn asteroids) )

That is the result ?
When we attack asteroids we will have more and more asteroids.
Very small asteroids are almost invulnerable for attack.
Speed of small asteroids will be faster and faster, because impulse of bullet will be converted (added) to asteroid's impulse.
The game became finite in common case.
The game became harder and harder to the end.

Who wins? A player who killed more opponents and survived. The same as Ants.

P.S. Smiley1983, I hope you like my proposition and I hope you implement it. I hope to you.
P.S. Excuse me for my english. Too many letters in this post.

[smiley1983]

I find the idea of endlessly-splitting asteroids interesting, and think it could work well in such a game.

I probably won't be doing much more with the code, though. If I were doing more, I would first want to resolve some issues in the current code: supporting multiple ships per player (if such a thing is wanted), and working out the best sort of integrator and collision detection method to use. Currently it uses simple euler integration with a fixed step size, meaning rapidly moving objects can leap through each other when they should collide. Because there is no gravity, it may be acceptable to chop it up into several smaller steps when there are objects moving further than their own radius in a single turn (for example). Someone more enthusiastic about the mathematics would have to have a look at it if this were being used for the contest.

Also, looking at some games, I'm not at all sure that my method for adding bullet speed to ship speed is valid. Either that's wrong, or something else is going wrong on the turn the bullet is created, I think.

I'm also unsure about the suitability of this game for the contest. I think it's familiar, interesting, feasible, non-trivial, and fun to watch. However, I don't think it's easy. I would be happy to be proven wrong if someone can explain a simple set of principles for flying around without dying, but it isn't obvious to me. This may just be a reflection of my lack of maths knowledge, but I think it will put many beginners off.

That being said, I do like the idea very much. I might take another look at the code sometime, but if someone else is keen, I encourage them to fork and improve.

[eiisolver]

Not dying is not so difficult if you are able to look ahead in the future, and be able to move back. I think the following pseudo code would work quite ok for surviving (the numbers are just examples)

Code: Select all

take a snapshot of the current status of all asteroids, bullets, ships
bestOrder = random order
while not stop or max 200 times {
   for depth = 0..20 {
      order[depth] = generate a random ship order
      move my ship according to order[depth]
      move all other bullets and asteroids 1 turn
      do collision detection
      if my ship died: goto nextTry
   }
   // we survived all the way until depth 20!
   bestOrder = order[0]
   stop = true
nextTry:
   restore situation to the snapshot
}
execute bestOrder


(probably should refined a bit to make the ship not move too fast otherwise it will collide anyway)

A tutorial with example code should explain this or some similar approach, just like the ants tutorial.

I agree with you that perhaps people find this contest too difficult despite all the good qualities you mention. And perhaps on the other hand the contest is too easy, because maybe the brightest people will find ways such that their ships just never die. I think there should be a rule that if more than one ship survives at the end of the game, the winner is the one that shot most asteroids.

[akarukov]

Hi smiley1983. Hi eiisolver.
We have a good discussion !
I could never imagine monte-carlo method in so simple way. Eiisolver, your piece of code is easy and effective.
I have took a bit of knowledge!
Also I can recommend to look at advanced monte-carlo method http://www.mcts.ai/

Since we think about game-complexity of the Asteroids proposition I would comment some words.
"Supporting multiple ships per player" - does not matter for game complexity. Just additional collaboration.
"a simple set of principles for flying around without dying" - monte-carlo method + big timeout ? Just for testing game-complexity ... Contest will find a good ideas ...
"I think it will put many beginners off" - beginners in what? Students? Programming? AI? We can't predict it, until we have no final Asteroids proposition. Familiar, interesting, feasible, non-trivial, and fun to watch can involve people !
"the brightest people will find ways such that their ships just never die" - you can't find way to never die while your enemy has a gun.

Some words about bullets.
Now bullet has no size, has no mass. It is just point with energy. To be consistent with idea of conservation of mass and impulse we should choose energy for bullet. How much?

Some words about collision detection.
Asteroids does not collide. Let it be. (imho)
Let we want to check collision for one step between ship and asteroid.
Ship has radius R1 >=0 .
Asteroid has radius R2 >=0 .
Ship has position (x1,y1) and speed (sx1,sy1).
Asteroid has position (x2,y2) and speed (sx2,sy2).
So we need to find any 0<=T<=1 for inequation
[(x1+sx1*T)-(x2+sx2*T)]^2 + [(y1+sy1*T)-(y2+sy2*T)]^2 < (R1+R2)^2

Code: Select all

   // returns Time of collision in 0<=Time<1
   // returns -1 if no collision in [0..1)
   // simple check can be
   // if checkCollision()>=0 then collisionDetected();
   public static float checkCollision(
         float x1,float y1, // position
         float sx1,float sy1, // speed
         float r1, // radius
         float x2,float y2,
         float sx2,float sy2,
         float r2)
   {
      assert(r1>=0);
      assert(r2>=0);      
            // [(x1+sx1*T)-(x2+sx2*T)]^2 + [(y1+sy1*T)-(y2+sy2*T)]^2 < (R1+R2)^2
      float S = (r1+r2)*(r1+r2); //S>=0
            // [(x1+sx1*T)-(x2+sx2*T)]^2 + [(y1+sy1*T)-(y2+sy2*T)]^2 < S
            // [ (x1-x2) + (sx1-sx2)*T ]^2 + [ (y1-y2) + (sy1-sy2)*T ]^2 < S
      float dx = x1-x2;
      float dy = y1-y2;
      float dsx = sx1-sx2;
      float dsy = sy1-sy2;
            // [ dx + dsx*T ]^2 + [ dy + dsy*T ]^2 < S
            // [dx^2 + 2*dx*dsx*T + dsx^2*T^2] + [dy^2 + 2*dy*dsy*T + dsy^2*T^2] < S
            // (dsx^2+dsy^2)*T^2 + 2*(dx*dsx+dy*dsy)*T + (dx^2+dy^2)-S < 0
      float a = dsx*dsx+dsy*dsy;
      float b = 2*(dx*dsx+dy*dsy);
      float c = dx*dx+dy*dy-S;
            // a*T^2 + b*T + c <0;      
            // D = b*b-4*a*c;
            // T1 = (-b + sqrt(D)) / (2*a);
            // T2 = (-b - sqrt(D)) / (2*a);
      float D = b*b-4*a*c;
      
      // never divide by zero !
      if(Math.abs(a) < 0.000001)
      {
         // objects do not move relative to each other
         // may be they already collided ?
         if(c<=0) return 0; // yes
            else return -1; // no
      }

      if(D<0)
      {
         // never collide.          
         return -1;
      }
      
      float sqrt_D = (float)Math.sqrt(D);
      // a>0, sqrt_D>=0
      float minT = ((-b - sqrt_D) / (2*a));
      float maxT = ((-b + sqrt_D) / (2*a));
      
      if(maxT<0 || minT>=1)
      {
         // collide but not now
         return -1;
      } else
      if(minT<0) // maxT >=0
      {
         // collide now !
         return 0;
      } else
      {
         //collide at minT
         return minT;
      }
   }


P.S. I am not friendly with python. I am not friendly with github.

[McLeopold]

I'm in favor of the following mechanics:

1) Asteroids continue splitting to make survival harder in the end game. It could be a count of splits that can be configured and tuned. Asteroids is 3, we could have 10-20.
2) Ships have an energy amount that is finite and used for thrust and weapons. When out of energy you just float and can't shoot. Maybe it goes up with a kill. This gives the game a natural progression so it doesn't last forever.
3) Predictable asteroid splitting, as much as possible giving floating point accuracy.
4) Limited mobility. Large turning radius, slow accelerate and decelerate. Makes it harder to survive and requires greater precision and prediction.
5) Rank players by survival order. (We'll make the starter bots suicide or something.)

Other things I like the idea of.

1) Heat seeking missiles. This is basically a simple AI with a bad turning radius that you can easily avoid or lead to the enemy. Slightly faster than ships, so you must maneuver to avoid.
2) Disabling shot. Has a wide area of affect and would disable a ship for a few seconds.
3) If you get hit by an asteroid, you ship is pasted to it for the rest of the game.

[smiley1983]

1) Asteroids continue splitting to make survival harder in the end game. It could be a count of splits that can be configured and tuned. Asteroids is 3, we could have 10-20.

When the asteroids get too small to split sensibly (they're all going to look like points or nothing eventually) one could make the smallest grade of asteroid indestructible. They could still be moved about by bullet hits. This would add an interesting element to the strategy; trying to divert asteroids into the path of opponents as well as away from you.

2) Ships have an energy amount that is finite and used for thrust and weapons. When out of energy you just float and can't shoot. Maybe it goes up with a kill. This gives the game a natural progression so it doesn't last forever.

I like this, but I would be in favor of very slow energy recovery (including going beyond original maximum); I think that turnlimit and cutoffs (e.g nobody fired an effective shot within past 150 turns) can ensure a finite game, but the benefit of limiting energy is to reward players who accomplish their goals with less resources. If running out of energy is like a timeout in Ants, it encourages super-conservative behaviour in all players, which would be less interesting to watch.

Of the rest, I like everything except perhaps the disabling shot. Testing will tell. I particularly like the programmable missiles idea.

I would like to see multiple ships per player. I can only imagine it making the game better (and harder to find near-perfect solutions for), though it would want testing and the current asteroids.py needs some work before it can do what's needed.

I had some MC code which wasn't performing well due to errors in its simulation; I've made some corrections, but its results are not as good as those in eiisolver's youtube video, though it does far more rollouts than the pseudocode posted (thanks for that, by the way, I'm glad to see that the approach is viable). More investigation needed. At the least, it needs to be prevented from moving too fast, or it accelerates too much and dies.

If we were to use this for a contest, I would be in favour of including a very thorough tutorial for making a simulation system. Maximizing the number of effective entries and all.

[eiisolver]

I had some MC code which wasn't performing well due to errors in its simulation; I've made some corrections, but its results are not as good as those in eiisolver's youtube video, though it does far more rollouts than the pseudocode posted (thanks for that, by the way, I'm glad to see that the approach is viable). More investigation needed. At the least, it needs to be prevented from moving too fast, or it accelerates too much and dies.

Note that the bots in my video are slightly more advanced than the pseudo code listed.

But I did a test with the pseudo code and actually it worked quite ok, even only 100 simulations was not too bad. But (as predicted) the max speed must be limited, and also with few simulations the random order generation must be controlled. In my test I only used turns -1, 0, 1, and thrusts 0 and 1.

I would also be in favor of multiple ships per player; it would add to the strategic dimension of the game.

[McLeopold]

I like this, but I would be in favor of very slow energy recovery (including going beyond original maximum); I think that turnlimit and cutoffs (e.g nobody fired an effective shot within past 150 turns) can ensure a finite game, but the benefit of limiting energy is to reward players who accomplish their goals with less resources. If running out of energy is like a timeout in Ants, it encourages super-conservative behaviour in all players, which would be less interesting to watch.

Super conservative behavior would be boring. My thought was that the heat-seeking missiles would force movement, plus incoming asteroids would also force some movement.

Limiting energy was an idea to just make sure the game had to end and nothing more. The less it affects game play the better, however, I'm okay with rules that encourage quicker games to influence strategy. I wouldn't even mind each player losing 1 unit of energy per turn just to stay alive, and then when you hit 0 you self destruct. If we did do increasing energy, I would at least like to see limited ammo.

[akarukov]

Some words about McLeopold's favor mechanics:

"3) Predictable asteroid splitting, as much as possible giving floating point accuracy." - Great! Fundamental question for now.
"1) Asteroids continue splitting to make survival harder in the end game. It could be a count of splits that can be configured and tuned. Asteroids is 3, we could have 10-20." - I do not understand. McLeopold could you comment it ?
"3) If you get hit by an asteroid, you ship is pasted to it for the rest of the game." - I do not understand. McLeopold could you comment it? What will be changed in mechanics?
"4) Limited mobility. Large turning radius, slow accelerate and decelerate. Makes it harder to survive and requires greater precision and prediction." - as I tested current mobility is quite prefect (imho).
Asteroids move too slow... The number of asteroids is too low...

"Ship's energy, missiles, multiply ships, disabling shot" - It does not mean for prototype. It does mean for contest.
The first base algorithm for Ants was pathfinding.
The second base algorithm for Ants was battle engine.
The advanced algorithm for Ants was collaboration.
The most advanced algorithm for Ants was strategy. (survival strategy or attack strategy and so on...)

The barrier of entry depends of the base algorithm for Asteroids.
The behaviour of your enemies is unpredictable.
Should be splitting of asteroids predictable?
Should be splitting of asteroids PARTIALLY predictable?
I think it is fundamental question for now.

Let's form the final rules for the splitting of asteroids. Predictable / partially predictable / unpredictable ?

[delt0r]

I quite like this idea. Before ants got all the attention last year i suggested something kinda like this. The upshot is that i got a 100% integer engine working with the idea of full squads per team. So cutting it back to simpler ships would not be hard. In short, i would be prepared to sink some time into this. A engine spec and a java reference implementation for example.

For all these sort of games a finite max speed is always needed for all objects. Doing the integration is pretty easy. Let there be more math steps than game steps and stick with Euler integration. The math steps per game steps is easy to work out with smallest object and max speed.

For game play I would be strongly in favor of n ships per team that is "map" dependent. 2 types of shot --ie homing missile, normal gun. Perhaps with different energy requirements and "cool downs". Also shields are always fun. When on, you can't shoot and rather than damage, you get bumped around and lose energy.

My last suggestion would be some kind of non destructible terrain. ie asteroids you can't blow up. Possibly stationary to create a "map".

Now for my 2c worth on asteroids blowing up. Each asteroid shot gets blasted into a Poisson number of fragments with the min at 3. Momentum is conserved (yea i do physics) mass distributions is always equal, physics tells us the rest more or less. A shot adds some energy so the total velocity goes up and momentum... perhaps drag would be needed not to make it impossible later in the game.

Also do asteroids collide?

Do bots control thrust level rather than just on and off? I think they should. It permits courser "turns".