Talk:Minimum Risk Movement

Credits - Minimum Risk Movement Old wiki page: MinimumRiskMovement Original author(s): Kawigi

I have tried this but it's very hard to set the importance of each parameters. I used the following parameters :

• Cornered or close to wall
• would I intersect an estimated ennemi bullet and the power of that bullet
• distance to other bot
• reversing or not direction
• lateral angle

I think setting the importance of each parameter could be a job for a genetic search. I read something about it that can be found here http://computing.dcu.ie/~humphrys/ in the abstract paper (not the whole thesis). The article is about action selection and each point can be considered as an action. I didn't implement the Genetic Algorithm as I had no simple idea on how to do it (how to build fitness... and if you must implements a robocode controller it's quite hard to do and take much time) but if you have one... --Synnalagma

I may try to put FloodHT's melee system into a Mini one of these times, and then it may help to see some code for it. I start with energy/distance² for each enemy and then multiply it by constants if that robot has shot me recently, or if I would become the closest enemy to them... Then I add something divided by the distance to the center squared and the distance from me squared. Then I multiply by some function of distance from me to avoid picking points in an opposite corner. In the dev version of FloodHT, if I'm picking a point close to me (meaning that I'm as concerned about not getting hit as much as with getting to the best place), I also multiply the number for each enemy by the cosine of the difference of the angles or something like that, which seems to get me oscillating laterally to the closest/most dangerous enemies. -- Kawigi

Just some though : The problem with this is that in some case you don't really choose between action : imagine a bot that has two task putting out fire and collecting trash there's a fire in the north east and a trash in the south west maybe with this you'll go to north-west or south-east since it maximise your function but this it's not a choice. It's better to go to the fire and then to the trash (or inverse). So I though about that imagine each parameter is an agent rating each action then you choose to execute the agent that will suffer the most if it is not choosen. suffering is BestAction - currentAction so there a place for opportunism and you really make a choice. main idea found on the article cited. --Synnalagma

So are you thinking of something like a maximum-benefit thing rather than minimum risk? -- Kawigi

Suffering selection

I think maximum-benefit is very close to minimum risk in this case. I gave an exemple with maximum-benefit because it was the way I implemented it. But the things goes exactly the same way. No I was thinking on another way to select the best action (or point) to take. If you sum every benefit and/or risk you take an average action or a compromise one. I don't think this is good, it could be in one case I explain later. The idea was this :

Each parameter can be regarded as a subtask of the movement. You can also call it an agent. This agent can tell us wich action would be the best in a particular case. This agent only observe a part of the current state (by state I mean description of the current situation). P. ex. if we know that there's a Bullet in the north direction and the agent only sens bullet it can tell us that we must go to south. Maybe if the agent sens bullet position and bullet heading it can tell us we must go to the west.

Now we have this agent. This agent can rate each action by telling us if it's a good or a bad action in their way. An agent percepting the distance to the other bot can't tell us about lateral angle or anything else.

What you are doing here is to sum the rating of each agent for each action and maximize (or minimize) this function. But in this case you may choose an action that no agent would have choose as the best one and take a compromize action. take a look at that, it's a bot that must collect trash and put out fire :

     a     b     c     d     e
  |-----|-----|-----|-----|-----|
1 |  F  |     |     |     |  T  |    F = fire T = trash B = Bot
  |-----|-----|-----|-----|-----|
3 |     |     |     |     |     |
  |-----|-----|-----|-----|-----|
4 |     |     |  B  |     |     |
  |-----|-----|-----|-----|-----|

We have two agent one percepting trash and the other one percepting fire. If we make the sum there's a lot of chance that we go to direction of c1 since the fire agent find this action not so bad and the same for the trash agent(since we are going closer. But it would be better to go to a1 or e1 directly and then to the other one. This situation appear because the 2 agent enter in competition here. Picking up the sum you take a compromise. So the sum can be successfull if you have agent going in the same way.

An another way to choose the action to execute is to compute the suffering of this agent if it's not choosen. the suffering is computed this way take the difference of the bettest action for this agent and the value for it's current action. Then you choose the action of the agent wich will have the biggest suffering if it's not executed. In this case you choose a real action as it's one proposed by one of the agent. Here going to fire or trash before. There's also a place for opportunism since an agent could not really suffer by not be executed.

Hope that was understandable but i've got a poor english. --Synnalagma

I'm trying to implement something like this right now. How can you tell if a bot fires on you?-Andrew

In melee? GlowBlowMelee nows it when he gets hit:). I just mean that you can't really now it before if you turn your radar all the time (because you have to compare the energy-difference between two ticks to now that the other bot is firing). But in some situations you can do it like in a OneOnOne battle if an other bot is very close (in this case you can also be pretty sure that he is shooting in your direction). -- rozu

Even if you lock your radar on a particular enemy, you won't know when he fires because the energy drop can come from another bot's bullet hitting him. Maybe a statistical algorithm could calculate the probability of a bot firing each tick, but I don't know if that info would be of much use... A melee battle is packed with bullets flying all over, a good movement is one that looks like it is dodging them as if it would know where they are. :) -- ABC

Though the energy drop from a bullet hit is often larger than 3. -- PEZ

If the bullet hitting the target is power between .1 and .75 inclusive it'll be in the range where it can be mistaken for a shot, otherwise it won't be. On the plus side, bullets this weak are kind of rare, and in OneOnOne you can know for sure if there are any bullets this weak in the air (at least ones that can hit your target) since they would've had to come from you. In melee you're probably better off not trying to dodge too much or you'll find yourself quickly ruling out all the possible directions of movement (if you assume every bot is firing at you you'll get to try to dodge all the 20-30 bullets that are in the air at any one time). -- Kuuran

Can you tell me if this finds the angle i should turn to get to point (destinationx,destinationy)? I came up with: setTurnRightRadians(Math.PI/2-Math.atan((destinationy-getY())/(getX()-destinationx))); --Andrew

I think it's setTurnRightRadians(robocode.util.Utils.normalRelativeAngle(Math.atan2(destinationx-getX(), destinationy-getY())-getHeadingRadians())); that you're looking for. Of course, if the turn is more than 90 degrees, it makes sense to adjust it by 180 degrees and go backward. -- Kawigi

this seems to vaguely work. but not be accurate enough. i am using it to go to a destination point i choose --andrew

You need to continiously (every tick or so) do it to actually arrive at the destination point. Look at GoToBot for some more code and discussion on the subject. -- PEZ

thanks. what exactly is atan2 though? --andrew

atan2() returns the base angle of a triangle with the sides X and Y. It could be used as a way to find out the absolute bearing between two points. You could use plain atan() for this too, but you'll have to account for the sign of the Y distance yourself then. -- PEZ

Just beware that the sintaxe is: atan2(Y,X), and not X,Y as usual... I'm saying that because i've got myself trapped in that a lot of times... -- Axe

you mean the other way around--andrew

The syntax is Math.atan2(Y, X) unless you're dealing with robocode. -- Kuuran

=) Looks like Axe trapped himself over again! Because of this peculiarity of ClockMath I recommend you to implement these two functions in all your bots.

    static double absoluteBearing(Point2D source, Point2D target) {
        return Math.atan2(target.getX() - source.getX(), target.getY() - source.getY());
    }

    static Point2D vectorToLocation(Point2D sourceLocation, double angle, double length) {
        return new Point2D.Double(sourceLocation.getX() + Math.sin(angle) * length,
            sourceLocation.getY() + Math.cos(angle) * length);
    }

Look in the source of any of my bots to see how they're used. The second function is ill named, but I have never figured out what the name should be. =)

-- PEZ

Coriantumr calls the latter function projectPoint() - projects a point starting from sourceLocation, length pixels in the direction of angle. -- Kawigi

Yes, that's better. Maybe

static Point2D project(Point2D sourceLocation, double angle, double length)

is a good signature. -- PEZ

can someone help me come up with a way to move sinusoidaly to a point. so instead of moving in a strait line in a point it osscilates to it. this math is to complicated for me --andrew

I guess the easiest way is to face the point, and then do this:

setAhead(Double.POSITIVE_INFINITY); turnLeft(30); while (!nearDestination()) {

 turnRight(60);
 turnLeft(60);

} stop();

You will need to write some code to work out when you have passed the destination point (prehaps something along the lines of the desitination being between your starting point and your current point), but it should work ok. -- Tango

Is this Even implantmentable into a Normal Robot? - Error

In theory: yes, but I don't think it would be as effective as an EAR bot --UnderDark

import robocode.*;
import robocode.util.Utils;
import java.awt.Color;
import java.util.Hashtable;
import java.util.Enumeration;
import java.awt.geom.*;

/** Smash - a robot by Starrynte
*/

public class Smash extends AdvancedRobot
{
	static Hashtable enemies = new Hashtable();
	static Enemy target;
	static Point2D.Double nextDestination;
	static Point2D.Double lastPosition;
	static Rectangle2D.Double field;
	static double myEnergy;	
	static double myX;
	static double myY;
	static double timeSinceLastScan=0;	

	public void run()
	{
		field=new Rectangle2D.Double(36,36,getBattleFieldWidth()-72,getBattleFieldHeight()-72);
		nextDestination=lastPosition=new Point2D.Double(getX(),getY());
		target=new Enemy();
		setAdjustGunForRobotTurn(true);
		setAdjustRadarForGunTurn(true);
		while(true){
			doMovement();
			doGunning();
			doRadar();
			myEnergy=getEnergy();
			myX=getX();
			myY=getY();
			timeSinceLastScan++;
			execute();
		}	
	}
	public void onScannedRobot(ScannedRobotEvent e){
		Enemy en=(Enemy)enemies.get(e.getName());
		if(en==null){
			en=new Enemy();
			enemies.put(e.getName(),en);
		}
		en.energy=e.getEnergy();
		en.live=true;
		double x=myX + Math.sin(e.getBearingRadians()+getHeadingRadians())*e.getDistance();
		double y=myY + Math.cos(e.getBearingRadians()+getHeadingRadians())*e.getDistance();
		en.location=new Point2D.Double(x,y);
		en.distance=e.getDistance();
		en.velocity=e.getVelocity();
		en.heading=e.getHeadingRadians();
		en.bearing=e.getBearingRadians();
		en.name=e.getName();
		if(!target.live || (en.distance<target.distance*0.8 && en.energy<=target.energy*1.1) || (en.energy<target.energy*0.8 && en.distance<=target.distance*1.15)){
			target=en;
		}
		if(target.name.equals(e.getName())){
			timeSinceLastScan=0;
		}
	}
	public void onRobotDeath(RobotDeathEvent e) {
		Enemy en=(Enemy)enemies.get(e.getName());
		if(en!=null){
			en.live=false;
		}
	}
	public void onHitRobot(HitRobotEvent e){
		Enemy en=(Enemy)enemies.get(e.getName());
		if(en==null){
			en=new Enemy();
			enemies.put(e.getName(),en);
		}
		en.energy=e.getEnergy();
		en.live=true;
		en.bearing=e.getBearingRadians();
		en.name=e.getName();
		target=en;
		setTurnGunRightRadians(en.bearing+getHeadingRadians()-getGunHeadingRadians());
		setFire(3);
	}
	void doMovement(){
		for(int i=0;i<250;i++){
			if(target!=null){
				double ang=2*Math.PI*Math.random();
				double dist=150+250*Math.random();
				double testX=myX+Math.sin(ang)*dist;
				double testY=myY+Math.cos(ang)*dist;
				if(field.contains(testX,testY)){
					if(evaluate(new Point2D.Double(testX,testY))<evaluate(nextDestination)){
						nextDestination.setLocation(testX,testY);
					}
				}
			}
		}
		double ang=calcAngle(new Point2D.Double(myX,myY),nextDestination)-getHeadingRadians();
		double dist=nextDestination.distance(myX,myY);
		setTurnRightRadians(Utils.normalRelativeAngle(ang));
		setAhead(dist);
		setMaxVelocity((Math.abs(Utils.normalRelativeAngle(ang))>1) ? 2.25 : 8);
	}
	void doGunning(){
		if(getGunTurnRemainingRadians()<0.01){
			setTurnGunRightRadians(Utils.normalRelativeAngle(target.bearing+getHeadingRadians()-getGunHeadingRadians()));
			
		}
		if(getGunHeat()==0 && getEnergy()>5){
			double firePower=Math.min(Math.min(myEnergy/10,1300/target.distance),target.energy/4);			
			setFire(firePower);
		}
	}
	void doRadar(){
		if(timeSinceLastScan<10 && getOthers()==1){
			setTurnRadarRightRadians(Utils.normalRelativeAngle(target.bearing+getHeadingRadians()-getRadarHeadingRadians())*2);
		}else{
			setTurnRadarRightRadians(Double.POSITIVE_INFINITY);
		}
	}
	double evaluate(Point2D.Double destination){
		double risk=0;
		Enumeration e=enemies.elements();
		while(e.hasMoreElements()){
			Enemy en=(Enemy)e.nextElement();
			if(en.live){
				double eratio=Math.min((en.energy*2)/myEnergy,2.5);
				double perp=Math.abs(Math.cos(calcAngle(destination,new Point2D.Double(myX,myY))-calcAngle(destination,en.location)));
				risk+=(eratio*(1+perp))/destination.distance(en.location);
			}
		}
		return risk;
	}
	double calcAngle(Point2D.Double s,Point2D.Double t){
		return Math.atan2(t.getX()-s.getX(),t.getY()-s.getY());
	}
	class Enemy{
		boolean live;
		Point2D.Double location;
		double energy;
		double distance;
		double velocity;
		double heading;
		double bearing;
		String name;
	}
}

The robot doesn't seem to "recognize" that setAdjustGunForRobotTurn(true); is there and setAdjustRadarForGunTurn(true); is there either. The firepower is also strange. (Try it in a battle with sittingduck). But if i comment out the "doGunning()" it does seem to adjust the gun. Does anyone know why? --Starrynte

Why don't you think it recognizes those commands? When I run this tank, it looks pretty clear to me that the radar stays focused on the enemy independent of the tank's movement, and the gun doesn't turn with the tank or the radar. Are you seeing something different, or what did you think those commands should do? Also, what is it about the fire power that seems strange? I ran it against SittingDuck, and the fire power seemed right, generally the 1300 / distance being the minimum in that expression. Note that fire power maxes out at 3.0, so it will be 3.0 if you set it to more than that. -- Voidious

The problem isn't with the setAdjust() commands. You're not taking into accout that the bearing to the enemy changes as your robot's position changes. This means target.bearing won't be accurate because your bot will be using the bearing from when it last scanned the target instead the real one. A simple fix would be changing the doGunning() method to:

if(target.location != null){
	double absoluteBearing = Math.atan2(target.location.getX() - getX(), target.location.getY() - getY());
	setTurnGunRightRadians(Utils.normalRelativeAngle(absoluteBearing - getGunHeadingRadians()));
	if(getGunHeat() == 0 && getEnergy() > 5){
		double firePower=Math.min(Math.min(myEnergy/10, 1300/target.distance), target.energy/4);			
		setFire(firePower);
	}
}

I hope this helps -- Kev

That is the problem. Thnx! --Starrynte

void doMeleeMovement(){
		if(nextDestination.distanceSq(myX,myY)<1000 || (target.distance<70 && (target.energy>0.5 || myEnergy<=0.6))){
			for(int i=0;i<250;i++){
				double ang=(2*Math.PI)*Math.random();
				double dist=Math.min((closestEn==null ? 10000:closestEn.distance*0.7),100+200*Math.random());
				double testX=myX+Math.sin(ang)*dist;
				double testY=myY+Math.cos(ang)*dist;
				if(field.contains(testX,testY)){
					if(evaluate(new Point2D.Double(testX,testY))<evaluate(nextDestination)){
						nextDestination.setLocation(testX,testY);
					}
				}
			}			
			if(timeSinceLastScan>100){
				nextDestination.setLocation(18+((getBattleFieldWidth()-54)*Math.random())+18,18+((getBattleFieldHeight()-54)*Math.random())+18);
			}
			lastPosition.setLocation(myX,myY);							
		}else{
			double dir=1;
			double ang=calcAngle(new Point2D.Double(myX,myY),nextDestination)-getHeadingRadians();
			double dist=nextDestination.distance(myX,myY);
			if(Math.cos(ang)<0){
				dir=-1;
				ang+=Math.PI;
			}
			ang=Utils.normalRelativeAngle(ang);
			setTurnRightRadians(ang);
			setAhead(dist*dir);		
			setMaxVelocity((Math.abs(ang)>1) ? Math.max(Math.random(),0.1)*1 : 8);						
		}
	}


double evaluate(Point2D.Double destination){
		double risk=1/destination.distanceSq(myX,myY) + 1/destination.distanceSq(getBattleFieldWidth()/2,getBattleFieldHeight()/2) + 1/destination.distanceSq(lastPosition);
		Enumeration e=enemies.elements();
		while(e.hasMoreElements()){
			Enemy en=(Enemy)e.nextElement();
			if(en.live && en.location!=null){
				double eratio=(en.energy*2*Math.max(en.fearFactor,1))/myEnergy;
				double perp=Math.abs(Math.cos(calcAngle(destination,new Point2D.Double(myX,myY))-calcAngle(destination,en.location)));
				//double perp=Math.abs(en.distance-destination.distance(en.location));
				double closeEnCount=0;
				double eval=(eratio*(1+perp))/destination.distanceSq(en.location);
				Enumeration enEnemies=enemies.elements();
				while(enEnemies.hasMoreElements()){
					Enemy enEn=(Enemy)enEnemies.nextElement();
					if(!enEn.name.equals(en.name)){
						if(enEn.location.distanceSq(en.location)<destination.distanceSq(en.location)*0.9){
							closeEnCount++;
						}
					}
				}
				if(closeEnCount<2){
					eval*=2;					
				}
				risk+=eval;
			}
		}
		return risk;
	}

Above is my movement code and risk function. When I run my bot, it doesn't move at all. If i remove the lastPosition line in the doMovement() and evaluate(), then it does move. Does anyone know how to fix??? --Starrynte

If just the lastPosition.setLocation(myX,myY) line in doMovement() isn't commented out, it doesn't move. --Starrynte

Everything is weird! The gun can't hit sample.Fire! The gun uses linear targeting when the target's 'headDelta' is less than 0.0001, otherwise it uses HOT. The above problem also still exists. The code can be found at Starrynte/Smash. --Starrynte

OK, I think what you need to do is normalize headDelta to between pi and -pi (using normalRelativeAngle) then check if Math.abs(headDelta) < .0001. --wcsv

It doesn't help the gun or the movement. It still can't hit sample.Fire, and the movement is still weird. --Starrynte

Basically what happens when it's 1v1 against Fire is that the 'bot will "vibrate" (turning a little past perpendicular one way, then the other way, etc, etc) and the gun "vibrates" with the 'bot. It's almost as is

setAdjustGunForRobotTurn(true);

did not exist, and the bearing to the enemy changes every tick. Notice i've commented out the lastPosition line in doMovement() and evaluate(), because there is still a problem (see above)--Starrynte

Does it go wrong on everyone's computer or is it just my comp? --Starrynte

This probably isn't the problem, but you should make sure to update your info (your position, energy etc) before you use it each tick. Right now you are using your old position to calculate the enemy position (remember that events are processed before your run loop executes each tick). I've got no time to test this code right now, but maybe later in the week.--wcsv

I just figured it out last week, but I think FloodHT has this bug in its wave surfer. -- Kawigi

Where should I update the info? If i update it after execute() it doesn't do anything. --Starrynte

At the beginning of whatever event handler the information is needed in (probably onScannedRobot). When execute() returns, all the event handlers for that turn will already have been called. -- Kawigi

Thnx wcsv and Kawigi, the gun problem is fixed. Now, the movement problem from above is left --Starrynte

Whenever my bot hits another bot that rams, like Spinbot or RamFire, it gets disabled because it makes too many calls to getXXX() methods. The only getXXX() method I call is e.getVelocity(). It gets really annoying because RamFire just rams it for a few ticks then it gets disabled. If anyone knows how to fix...thnx (code will be posted at Starrynte/Smash) --Starrynte

Ramming problem from above fixed. Now for the movement problem. --Starrynte

I used lastPosition in another bot, and it worked, but when i use it in this bot, it sits still. --Starrynte

According to http://java.sun.com/j2se/1.3/docs/api/java/awt/geom/Rectangle2D.Double.html, when you make a Rectangle2D.Double, the x,y coordinate is the upper-left corner of the rectangle. Is that different in robocode? If not, is this the right way to construct it:

field=new Rectangle2D.Double(36,getBattleFieldHeight()-36,getBattleFieldWidth()-72,getBattleFieldHeight()-72);

--Starrynte

I made a new bot called Lightning, it's based on Smash, but it doesn't move at all when i run it! Also, in the first round, it says

You cannot call fire(NaN)

--Starrynte/Lightning

Does it say that near the beginning of the round, or toward the end? -- Kawigi

fire(NaN) happens because you have called fire with a NaN parameter. Looking at your firepower evaluation algoritum, it looks like the base, getTime()-target.ctime, is causing you problems, as there may be a time when you fire on the same tick as you scan, causing the base to be 0, and therefore a NaN. One solution is to do getTime()-target.ctime+1 instead, or use another base. --Nfwu

Ok, I will change it to Math.max(getTime()-target.ctime,1); --Starrynte

Is distance from current location good or bad?

Am I the only person that has noticed that if you rate a point badly for being far away because you have to move in the same direction for a long time, and rate it good for being far away because you don't want to stay in the same spot, the distance a point is from you has no effect? I do agree that moving the same direction for a long period of time is bad, and that not staying in the same place is good. But it is pointless to rate on those two things based only on your current position. What I do in Ice is I keep track of the places I've been recently and repel an average position, rather than my current position. Does that make more sense, or am I crazy? -- A.h.russ

It makes perfect sense =) I did a similar thing in some of my melee experiments, what I did was repel from the last X positions, with the weighting tapering off as the points got older. --Skilgannon 07:19, 20 October 2010 (UTC)

Definitely not crazy. =) I do much the same as Skilgannon, except I've since removed the weighting by time and I randomize the locations a bit. --Voidious 12:12, 20 October 2010 (UTC)

Indeed definitely not crazy. While I don't do the same as Voidious or Skilgannon in Glacier, in simpler melee experiments I have done so to good effect. Edit: I imagine it's coincidence, but interesting that you name a melee bot "Ice" when one high ranking one is "Glacier" =) --Rednaxela 23:09, 20 October 2010 (UTC)

I was just making sure, because it would be just like me to think something like that but be totally wrong. I hadn't noticed that our names are so similar, that is funny. I think that the old point evaluation section belongs somewhere dedicated to FloodHT, not in a page just describing MR movement. Do you agree that most bots using this strategy do almost the same thing as it? --A.h.russ 04:37, 21 October 2010 (UTC)

Can wave surfing be considered a special case of minimal risk movement? I see there are a lot in common, and especially in melee (e.g. melee wave surfing).

Both wave surfing and minimal risk movement involves

• Point/Path generation
• Risk evaluation

Anyway, most surfers evaluate risk on paths, not points, and vice versa. And most surfer's point generation is "path-oriented", instead of "point-oriented", which is especially true for multi-wave surfing true-surfers.

Nevertheless, minimal risk movement can also evaluate paths, e.g. use a line from start to end and calculate distance to that line, instead of simply end points.

As points in minimal risk movement are finally used for go-to (movement), and paths in wave surfing are finally used for movement as well, if we combine points and paths into movement option, both minimal risk movement and wave surfing can be combined into a generic framework:

• Movement option generation
• Risk evaluation

What do you think will be a suitable name for this generic movement framework?

Wave surfing and MRM have a lot in common, and depending on the implementation they might be similar to each other. Of course evaluating paths or points is a big difference. Another difference that stands out between the two is that wave surfing primarily looks at waves and then generates movement options accordingly, whereas MRM primarily generates movement options and then afterwards may take waves into account. That's why I would regard those two approaches as completely different from each other.

Thanks, that’s the point! Although they look similar, they are still different enough that they should be considered as different things.

Anyway, I found implementing (single wave, or CC style) wavesurfing in MRM way easier ;)

Btw, what do you think about Neuromancer’s movement? Maybe that’s something between MRM and wavesurfing ;)