Difference between revisions of "User:AW/guideToRobocode"

From Robowiki
Jump to navigation Jump to search
(Wave Surfing)
 
(4 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
==The rules of the game==
 
==The rules of the game==
  
In robocode 1v1, there are two robots fighting on a 600 by 800 pixel battlefield.  Pixels are measured from the bottom left, as in a Cartesian coordinate system.  Each robot starts with a certain amount of energy (usually 100 energy).  When the energy runs out, the robot dies.  The objective is to destroy the enemy by as large a margin as possible.
+
In robocode 1v1, there are two robots fighting each other.  Each robot starts with a certain amount of energy (usually 100 energy).  When the energy runs out, the robot dies.  The objective is to destroy the enemy by as large a margin as possible.
 +
 
 +
To do this, robots have certain abilities:
  
To do this, robots have certain:
 
 
==Abilities==
 
==Abilities==
  
Line 40: Line 41:
 
#If a robot hits a wall, the robot stops instantly and takes damage equal to abs(velocity) * 0.5 - 1 if abs(velocity) > 2.0  
 
#If a robot hits a wall, the robot stops instantly and takes damage equal to abs(velocity) * 0.5 - 1 if abs(velocity) > 2.0  
 
#If a robot hits another robot, it takes 0.6 damage and instantly stops if it is moving towards the other robot.
 
#If a robot hits another robot, it takes 0.6 damage and instantly stops if it is moving towards the other robot.
 +
 +
===The Battlefield===
 +
1v1 is generally played on a 600 by 800 pixel battlefield, pixels are measured from the bottom left, as in a Cartesian coordinate system.  There are walls at the edges of the battlefield and you cannot move through these walls.  Other than that, the only obstacle is the other robot.
  
 
And one final bit of details:
 
And one final bit of details:
Line 72: Line 76:
  
  
[[Image:GilgaladWaves.png|800px|thumb|right|[[Gilgalad]] painting waves for [[Raiko]]'s shots.]]
+
[[Image:GilgaladWaves.png|800px|thumb|right|[[Gilgalad]] painting waves for [[Raiko]]'s shots.  The little green and red circles lie within the range of guess factors for a bullet of the power [[Raiko]] shot.]]
  
 
For a detailed article, see [[Waves]].
 
For a detailed article, see [[Waves]].
Line 87: Line 91:
  
 
Waves and guess factors are the core of the current top robots.
 
Waves and guess factors are the core of the current top robots.
 +
 +
===Wall Smoothing===
 +
The final aspect to cover before getting into targeting and movement is wall avoidance.  When robots hit walls, they will stop and depending on their velocity, they will lose energy.  In order to avoid hitting walls, several algorithms have been developed--the most prevalent being wall smoothing.  In wall smoothing, the robot projects a "blind man's stick" to a certain distance, usually about 160 pixels, ahead of itself.  If the end of this stick is outside the walls, the robot turns to adjust for that.  This algorithm has the advantage of being extremely fast and allowing the robot to move along a "reasonably intelligent" path in the clockwise and counter-clockwise directions.  In attempting to make a competative robot that uses wall smoothing, it is important that one makes an efficient implementation.  See [[Wall_Smoothing/Implementations/Non-Iterative | non-iterative wall smoothing]] for a detailed description of one such implementation.
  
 
==Theory of Targeting==
 
==Theory of Targeting==
 +
 +
At first glance, it may appear that moving randomly would work well, and to a degree it does.  Orbiting the enemy and randomly changing direction allows you to dodge most of the bullets fired at you.  However, people soon found ways to hit random movements more accurately than random guessing.  How?  In robocode, your bullet's travel relatively slowly, and you can often fire another bullet before your first bullet would have hit the enemy.  There are frequently, two, three, or even four bullets travelling towards you at a time.  Suppose that you decided to randomly move to a certain angle when the first bullet was fired.  Before you could get there, a second bullet would be fired.  If you move to that angle, the enemy has a better idea of where you will be when the second bullet's wave breaks (the bullet's wave passes you).  If, you don't move to that angle, but instead choose another one randomly from your options on the second wave, you are more likely to end up near guess factor 0 on the first wave. 
 +
 +
It turns out, that it is very difficult, if not impossible, to create a random movement whose probability of reaching any given guess factor is uniform.  As such, guns can be designed to pick up on certain statistical trends in movements.
 +
 +
The general idea, among most robots, is to choose certain attributes that describe a certain situation.  These can be things such as your distance from the target robot, how fast the target robot is going, whether the target robot is accelerating or decelerating, etc.  Whenever you need to fire, you find some similar situations from the past and assume that they will move in a similar way.  If you find enough situations that are sufficiently similar, you may be able to find statistical trends and predict their movement.
  
 
==Theory of Movement==
 
==Theory of Movement==
 +
 +
Because of the success of targeting methods against random-movement, a new type of movement developed.  [[WaveSurfing]] is a category of movement where the robot attempts to adapt to its enemy's targeting strategy.  When an enemy fires a bullet at you, he loses energy which you can detect.  By tracking your opponent's energy level, you can tell, with a few exceptions, when they fire a bullet and what power they used for that bullet.  Since you know the fire time, bullet power (which translates into speed), and fire location of the bullet, you can construct a wave containing all possible locations of that bullet.  If you assume that the robot you are facing employs a reasonable strategy, you know that the bullet is somewhere between GF -1 and GF 1 on that wave.  Whenever you find the location of an enemy bullet (which happens when it hits you or hits one of your bullets) you can find which GF they fired at.  Assuming that they use a GF based gun, which the majority of "competitive" robots do, you can keep track of where they fired in certain situations, using attributes just as they are used for targeting, but reversing the calculations so that they are gathered from your enemy's perspective.  By tracking these situations and analysing them, you can predict where their gun will shoot in a given situation.  Constructing a probability density function for where their bullets will be, you can then simulate a variety of possible movement paths you could take over the next N turns.  If you estimate the probability that you will be hit by calculating the intersection of your path with their waves and using your generated probability density function, you can then choose the path with the lowest danger and move along that path.

Latest revision as of 19:05, 18 May 2013

The rules of the game

In robocode 1v1, there are two robots fighting each other. Each robot starts with a certain amount of energy (usually 100 energy). When the energy runs out, the robot dies. The objective is to destroy the enemy by as large a margin as possible.

To do this, robots have certain abilities:

Abilities

  1. Move forwards or backwards at up to 8 pixels per turn (a turn in robocode is also called a tick)
  2. Accelerate at up to 1 pixel per turn squared
  3. Deccelerate at up to 2 pixels per turn squared
  4. Turn their body at up to (10 - 0.75 * abs(velocity)) degrees peer turn and get their orientation (relative to "north" on the battle field, going clockwise like a compass.)
  5. Turn their gun at up to 20 degrees per turn and get their gun's orientation relative to the body of the tank
  6. Turn their radar at up to 45 degrees per turn and get the radar's orientation
  7. Fire bullets ranging with powers ranging from 0.1 to 3.0
  8. Firing bullets creates gun heat of 1 + firePower / 5.0; if gunHeat > 0, the robot cannot fire.
  9. A robot's hit box is a non-rotating square. Each side is 36 pixels in length.

Bullets

  1. Firing a bullet costs energy equal to the power of the bullet;
  2. A bullet has a velocity of 20 - 3 * bulletPower;
  3. When a bullet hits, it does 4 * firePower damage to an enemy robot if firePower < 1;
  4. if firePower >= 1 the bullet does 4 * firepower + 2 * (firePower - 1). You cannot be hit by your own bullets.
  5. When a bullet hits an enemy, the firing robot receives a bonus in energy of 3 * bulletPower.
  6. When two bullets collide, both of them are destroyed.
  7. When a bullet hits the wall, it is destroyed.

Radar

A robot can receive the following information about his enemy via radar:

  1. Enemy's heading (the heading is the direction the robot is facing, this is measured from );
  2. Enemy's distance;
  3. Enemy's bearing (the angle from our heading to the enemy);
  4. Enemy's speed;
  5. Enemy's energy;

Robot collisions

  1. If a robot hits a wall, the robot stops instantly and takes damage equal to abs(velocity) * 0.5 - 1 if abs(velocity) > 2.0
  2. If a robot hits another robot, it takes 0.6 damage and instantly stops if it is moving towards the other robot.

The Battlefield

1v1 is generally played on a 600 by 800 pixel battlefield, pixels are measured from the bottom left, as in a Cartesian coordinate system. There are walls at the edges of the battlefield and you cannot move through these walls. Other than that, the only obstacle is the other robot.

And one final bit of details:

Robocode Processing Loop

The order that Robocode runs is as follows:

  1. Battle view is (re)painted.
  2. All robots execute their code until they take action (and then paused).
  3. Time is updated (time = time + 1).
  4. All bullets move and check for collisions. This includes firing bullets.
  5. All robots move (gun, radar, heading, acceleration, velocity, distance, in that order).
  6. All robots perform scans (and collect team messages).
  7. All robots are resumed to take new action.
  8. Each robot processes its event queue.


That's it. You now know how robocode works. If you ever need to refresh your memory, you can go to the Physics page.

Strategy

Given the above abilities, how do you destroy the other robot? Over the years, several techniques have developed.

Here are the key concepts:

Waves

You may have noticed above that the list of things your radar can detect does not include bullets. This is part of what makes robocode so interesting. Because firing costs energy and you can detect the enemy's energy, you can tell when they fired and what power bullet they shot. With the power, you can find the velocity of the bullet, and because you can find the location of the enemy robot, you know where the bullet was fired from. Therefore you have three pieces of information: 1) Where the bullet was fired from. 2) How fast it is going. 3) How long it has been moving.

From these, you can find a circle that contains the set of possible positions of a bullet. The radius of this circle increases each turn (tick). This "object" (the circle of increasing radius that contains all possible points where a bullet can be) is called a wave. Whenever you fire, you too create a wave of possible points your bullet could be. Of course you know what angle you used so you know where the bullet is, but the wave shows all points where the bullet could have been.


Gilgalad painting waves for Raiko's shots. The little green and red circles lie within the range of guess factors for a bullet of the power Raiko shot.

For a detailed article, see Waves.

Guess Factors

When people think of tanks shooting at each other, they generally assume these tanks are realistic. In real life, tanks shoot projectiles at about 1500 m/s, while the tanks move at a speed of at most 0.03 m/s. In real life, you can't dodge. In robocode, however, bullets travel at less than three times the maximum speed of a tank. Dodging works in robocode. Eventually, a mechanic called guess factors emerged. When targeting, you have to choose an angle to fire at, with the hope of hitting the enemy. The enemy can reach a certain range of angles, which can be proved to be at most asin(8/bulletSpeed) in either direction from the ray drawn from the firing robot through the target robot (see MEA for the proof). Since this range of angles contains all the angles that the enemy could reach, the angles in this range are also the only angles that are reasonable to fire at. Let's normalize these angles from -1 to 1, with 0 being straight at the target. We could define 1 to be the maximum possible angle in the clockwise direction (assuming our robot is the center of the universe), but instead, let's make it the maximum angle in the direction the enemy robot is "orbiting" us.

We now have a unambiguous way of referring to each reasonable firing angle. This notation gives angle in an offset from "head on" (the ray from our robot through their robot) and normalized by bullet power, so that 1.0 is the "maximum" angle they could reach "orbiting" us in the direction they are going now, and -1.0 is the "maximum" angle could reach if they changed directions.

For more information, see GF


Waves and guess factors are the core of the current top robots.

Wall Smoothing

The final aspect to cover before getting into targeting and movement is wall avoidance. When robots hit walls, they will stop and depending on their velocity, they will lose energy. In order to avoid hitting walls, several algorithms have been developed--the most prevalent being wall smoothing. In wall smoothing, the robot projects a "blind man's stick" to a certain distance, usually about 160 pixels, ahead of itself. If the end of this stick is outside the walls, the robot turns to adjust for that. This algorithm has the advantage of being extremely fast and allowing the robot to move along a "reasonably intelligent" path in the clockwise and counter-clockwise directions. In attempting to make a competative robot that uses wall smoothing, it is important that one makes an efficient implementation. See non-iterative wall smoothing for a detailed description of one such implementation.

Theory of Targeting

At first glance, it may appear that moving randomly would work well, and to a degree it does. Orbiting the enemy and randomly changing direction allows you to dodge most of the bullets fired at you. However, people soon found ways to hit random movements more accurately than random guessing. How? In robocode, your bullet's travel relatively slowly, and you can often fire another bullet before your first bullet would have hit the enemy. There are frequently, two, three, or even four bullets travelling towards you at a time. Suppose that you decided to randomly move to a certain angle when the first bullet was fired. Before you could get there, a second bullet would be fired. If you move to that angle, the enemy has a better idea of where you will be when the second bullet's wave breaks (the bullet's wave passes you). If, you don't move to that angle, but instead choose another one randomly from your options on the second wave, you are more likely to end up near guess factor 0 on the first wave.

It turns out, that it is very difficult, if not impossible, to create a random movement whose probability of reaching any given guess factor is uniform. As such, guns can be designed to pick up on certain statistical trends in movements.

The general idea, among most robots, is to choose certain attributes that describe a certain situation. These can be things such as your distance from the target robot, how fast the target robot is going, whether the target robot is accelerating or decelerating, etc. Whenever you need to fire, you find some similar situations from the past and assume that they will move in a similar way. If you find enough situations that are sufficiently similar, you may be able to find statistical trends and predict their movement.

Theory of Movement

Because of the success of targeting methods against random-movement, a new type of movement developed. WaveSurfing is a category of movement where the robot attempts to adapt to its enemy's targeting strategy. When an enemy fires a bullet at you, he loses energy which you can detect. By tracking your opponent's energy level, you can tell, with a few exceptions, when they fire a bullet and what power they used for that bullet. Since you know the fire time, bullet power (which translates into speed), and fire location of the bullet, you can construct a wave containing all possible locations of that bullet. If you assume that the robot you are facing employs a reasonable strategy, you know that the bullet is somewhere between GF -1 and GF 1 on that wave. Whenever you find the location of an enemy bullet (which happens when it hits you or hits one of your bullets) you can find which GF they fired at. Assuming that they use a GF based gun, which the majority of "competitive" robots do, you can keep track of where they fired in certain situations, using attributes just as they are used for targeting, but reversing the calculations so that they are gathered from your enemy's perspective. By tracking these situations and analysing them, you can predict where their gun will shoot in a given situation. Constructing a probability density function for where their bullets will be, you can then simulate a variety of possible movement paths you could take over the next N turns. If you estimate the probability that you will be hit by calculating the intersection of your path with their waves and using your generated probability density function, you can then choose the path with the lowest danger and move along that path.