Editing revision 129 of PatternMatching

Robo Home | Changes | Preferences | AllPages

Editing old revision 129. Saving this page will replace the latest revision with this text.

A method of [[Targeting]].

One quite simple strategy is to:
# Record your enemy's movements
# When estimating a future location you:
## Try to find a match in this recorded history matching the recent movements.
## Play the recorded "movie" from this match for BulletTravelTime time

I got most of the inspiration for [[Marshmallow/PatternMatcher| Marshmallows pattern matching]] from here: <strike>http://www.realj.com/robots/MogBot.html#aiming</strike>
http://web.archive.org/web/20040213005719/http://realj.com/robots/MogBot.html#aiming (- Voidious)

==== Resources ====
* See also [[SymbolicPatternMatcher|SymbolicPatternMatching]] to see how to build an specific implementation.
* For some interesting information about PatternMatching parameters, take a look to [[Parakeet]].
* For some pattern matching code, you can take a look to NanoLauLectrik and [[Moebius]]. -- [[Albert]]
* [[Marshmallow/PatternMatcher]] - code for a [[MogBot]] style implementation
* [[/PatternRating]] - how to rate the closeness of a pattern
* See the [[PatternMatcherChallenge]] for a good unit test designed by [[Vic]] to debug and clean up your pattern-matcher against.
* [[FoldedPatternMatcher]] illustrates an optimized symbolic pattern patcher.
* [[/SingleTick]] takes a slightly different approach, with some nice results.
* [[StatisticalPatternMatching]] is a combination of LogTargeting and StatisticalTargeting.

----
The starting point for pattern matching is the assumption that a bot will repeat its movements, so if you are able to find some movement in the past that is similar to the current bot's movement, you will be able to predict its future position by reproducing past movements.

Pattern matching and virtual bullets have proved the best targeting strategies so far (top 10 bots in eternal rumble use one or the other).

It has some advantages in front of virtual bullets:

(a) It takes less code to program a pattern matcher than a virtual bullets targeting system, so it makes it the best targeting solution for microbots.
(b) It is really powerful (more than virtual bullets) against bots that have repetitive behaviour, even if it is complex.

Of course, it has some disadvantages also:

(a) It needs lots of information about enemy movements, so it is more suitable for 1vs1 than for meele. 
(b) Virtual bullets work better against bots with "almost random" behaviour.

Some bots of mine using pattern matching:

- Aspid and MicroAspid use a pattern matcher that uses linear velocity and angular velocity as data series. 
- Mamba (you can only download it as a team: MambaTeam) is using an hybrid pattern matcher/virtual bullets system (need some tuning...) and uses VB or PM depending on which system has a higher success rate (ie. it is using VB to see if PM is working). The need for continuos data series is overcomed by a clever use of radars and information exchange (remember, they are a team).

-- Albert

One disadvantage of most patternmatchers is it considerable slows down your battles. Some bots cause a very low framerate, even with the [[Robocode]] window minimized. (Fermat 2.0 and NeonTetra for example slow the battles down to 30-40 frames per second on my computer).
The problem is, that a lot of bots does it's patternmatching every single frame.
One way to speed things up is to do the patternmatching only, when you are about to fire:
<pre>
if ((getGunHeat()/getGunCoolingRate()) < 4)
{
	...
	...
	(patternmatching stuff)
	...
	...
}
</pre>

That magic "4" more or less just came out of thin air, I'm afraid. ;-)
If you keep your gun aimed directly at your opponent when you're not firing, you'll usually need only one or two ticks to aim your gun at your predicted spot when you do want to fire... three just to be sure, so that's why I use
if (.... < 4).
The <pre>(getGunHeat()/getGunCoolingRate() < 4)</pre> instead of just <pre>(getGunHeat() < .4)</pre> is because the coolingrate of the gun can be set in the options menu to a different value.

-- [[Dummy]]

What do you people do to speed up the process of searching for a pattern?  I think [[Rozu]] and [[Vic Stewart]] both said they match a somewhat large window without a major performance problem.  What's your system?  -- [[Kawigi]]

With LeachPMC I use a "binary" search approach. It matches 350+ length patterns on average against PatternBot and doesn't care if I ask it to try 1000 character searches or 10 characters. If it fails matching on 1000 it tries 500, then 250 ... and if it gets a match on 500 it tries 750.. you get the picture I think. =) -- [[PEZ]]

What do you do to look for the pattern of length 1000 or 500 or whatever?  Are you using a symbolic pattern-matcher still? -- [[Kawigi]]

Yes, I build a "char" from the heading delta and velocity measures and use that for matching with the String.indexOf() functions. LeachPMC 1.2 limits itself to try for 600 chars matches. But that's not for matching performance, it's because I observed that when I got matches of 1100+ chars I was more vulnerable for when PatternBot leaves it pattern and starts over. I think [[Vic]] might have underestimated how long those rounds would be when both bots get near 100% hit rate. =) Try [[Frankie]] and you'll see that it's a fast bot even though it tries for very long search vectors. I will probably shorten that max length because real bots don't show 1100+ strings of exact repeating movement anyway. -- [[PEZ]]

[[Ender]] / EnderPMC works exactly the same as PEZ described here. I get performance problems when the patternbuffer grows beyond 15k. I also improved performance by checking each tick if the last found pattern is still valid. -- [[Vic]]

Of course I also use [[Dummy]]'s suggestion about only running the matcher when the gun is cool enough for it to be worth the bother. Though I use the magic number 3 instead of 4. -- [[PEZ]]

I use the magic number '1' and keep the gun directly at the opponent on other turns so I won't need more than that (at least in [[TeancumPMC]]).  Does anyone do a closest-match search that runs reasonably quickly (like with doubles)? -- [[Kawigi]]

I'm trying to code a patern matching gun for my bot for the first time. I know almost zero physics though. At first, I am going to use arraylist instead of string buffer w/ chars/strings and java's own mathing thing so that i can fully understand how it works. In the arraylist, do i want to store their heading to mine(absoluteheading) and their velocity? Or do i store their heading as a set of coordinates? And when i go back to analize it, how exactly does that work? How do I actuall match that? Does adding of vectors come up, because i don't really know what that is. Someone explain all this junk to me please. - Andrew

The simplest type, I believe, is storing the enemy's velocity and heading change (currentheading-lastheading). Then you match their current velocity and heading change, or say, the last 7, and search for matching patterns. Then you figure out how many ticks until your bullet would hit them and predict their position based on the matches you found. No vectors. There are a few good examples of pattern matchers. I remember Iapetus by tobe being really easy to grasp. -- [[Alcatraz]]

EDIT CONFLICT : * What I did when I wrote my PM gun was to store the *enemies* velocity and change heading on a given tick. The I would play back the last seven ticks worth of change and look for that pattern in the memory buffer. When you find a match, you play those heading changes and velocities back, projecting from the current location and heading, iteratively until a bullet could travel far enough from your current position to impact with the projected position. Take the absolute bearing to that position and shoot there. Some things to consider are how often to check your buffer (I only checked for the 4 ticks before I was absolutely going to shoot), how big should you let your buffer get, how do you handle not finding a match, how do you deal with the possibility of more than one match possibility, will/should you use a variable length pattern to match on. I am sure there are tons of other options as well ([[ABC]],[[Albert]],[[Axe]]?). I strongly suggest you look to do it symbolically first unless you are prepared to some how compare multiple array positions across mulitlpe arrays (If you only match on speed and heading change you will need to compare a 2 dimmensional array of the latest movement with the two dimmensional array of your "movie history" to look for a match. More aspects to match on means more dimmensions to compare). String matching is much easier and I think a bit easier to understand. A thought that occurs to me is that you might be able to use matirx math to compare the multi-dimmensional arrays. It might even be a fast way to do it too. -- [[jim]]

If he doesn't know anything about vectors he doesn't know anything about matrices, they're the same thing. Anyway, yes, that was all correct, just don't get too caught up in the details of this. The basic idea of a pattern matcher is that you record some part of your enemy's movement (heading, velocity, acceleration, lateral velocity, advancing velocity, etc) all the time. Then when you want to fire you look at the last few moves and find the last time it did something like those few moves. Next you go to one move after what you've already seen and start moving them according to what they did last time. Once you've moved them far enough that a bullet could get from you to their new position you figure out where you've moved them to and shoot at it. The typical example is to store your enemy's change in heading and their velocity. This lets you identify any particular move with something like "they turned left two degrees and went forward 8 units", which is a complete description of the motion. When you want to fire you look at how your opponent has been moving lately (last 7 moves was mogbot's choice, and has been emulated alot) and search through all the movements you've seen until you find ones which look the same. There are lots of options in how to determine "look the same".

Symbolically you store a string where each character is just <tt>(char)e.getVelocity()</tt> and <tt>(char)(e.getHeading - lastHeading)</tt>. Because char is only a whole number value (basically just the character's ASCII value) you're rounding all your results to whole numbers, and keeping only approximate values. This means that you can look for the last time an identical string occured and be almost guaranteed a match (only a few strings are possible when you're looking at the numbers this roughly). Once this is done you go to the end of the pattern you matched and go forward one. This is the next move you expect your enemy to make, but haven't seen yet. Using something like <tt>(int)stringRecordingOfVelocity.charAt(++endOfMatch);</tt> and <tt>(int)stringRecordingOfVelocity.charAt(endOfMatch);</tt> you can grab the next movement's heading change and velocity. If you take their current heading and add the heading change you've got the direction of the next movement, then you need to figure out where that is. The easiest way to proceed is grab their current {x, y} and then simple figure out the change in x and y from this movement. This is exactly the same as working out their coordinates, in Robocode you multiple sin(heading) by the amount they move (velocity) resulting in something like <tt>deltaX = Math.sin(e.getHeadingRadians + Math.toRadians(nextHeadingChange)) * nextVelocity;</tt> and the same but with cos(heading) for y. In the real world you'd use sin and cos in the opposite order, just so you know. Adding deltaX and deltaY to their current x and y gives you their x and y after that move. Using 20 - 3 * bulletVelocity you can determine how far the bullet can travel during that move. Check the distance of this next {x, y} and see if the bullet can travel more than that distance. On the first move this will probably be false. Next you go back to where you were when you first matched the movement and went forward one. Starting there, go forward one more. Move them forward from the new {x, y} you calculated to a still newer {x, y} and calculate if the bullet could travel that far in two ticks, and then do the same for three ticks and so forth until your bullet hits them. Aim at that point and fire. Incidentally, the adding of the deltaX and deltaY is vector addition, that's all there is to it, don't get intimidated by a term.

Using non-symbolic methods this is a bit trickier. If you're using something like doubles you have really exact numbers on how they moved, if you go back and look for the last time these exact numbers occured you're often going to find that they didn't occur before. Something very similar that represents the same move may have, however. To do this you look in the history and find the move with the least error. To calculate error you do something like <tt>(observedHeadingChange - recordedHeadingChange)/maximumPossibleHeadingChange</tt>. For a few reasons you usually want to square this number (obviously making it positive is a big issue, and any number squared is positive). Then do the same calculation for velocity and add the two numbers. This is one way to find your error for this move. You add up the error for every move in the sequence and choose the sequence with the least error, then basically proceed as above moving them forward until you could shoot them.

This is far from an exhaustive treatise, all I've outlined here is the basic idea of look at last time they did something and then assuming the next thing they do is the same. I also figure I've made at least one error, so feel free to correct and add to it. Remember also that heading change and velocity can be any values that uniquely identify the movement, so feel free to be creative.

-- [[Kuuran]]

Thanks Kuuran and everyone else-andrew (old post deleted)

Thanks Kuuran, I think I got something out of that too.  I'm working on a symbolic absolute pattern matcher (my friend submitted a relative matcher :o ).  What andrew was referring to was the mathematical vector that I always seem to be talking about (we're friends).  I don't use math vectors in shooting, I use them only in movement.  Oh yea, andrew, a vector is a representation of direction and magnitude. --Scoob

You might get some help by checking the [[LeachPMC/Code]] page. It's the gun from one of the highest ranking challengers in the PatternMatcherChallenge. Be aware that the code holds some special tricks that might fit only in the PMC. There's a discussion at the bottom of the page about it. -- [[PEZ]]

[[Andrew]], i recommend u also two pages: [[TronsGun]](it's the gun of Shadow, the #1 bot) & [[Musashi]](My bot). There you can find info about PM and some interesting ideas too. [[Musashi]]'s code is open-source, feel free to study it if u want (although it's a little bit messy). 
One important thing when developping a PM gun, is the bots that u use to test it. I recommend [[Infinity]], if you can hit it 90%+, your PM gun is working. Btw, welcome! -- [[Axe]]

Very good point, also grab a copy of [[PatternBot]]. If you ever miss it you aren't pattern matching. Ditto for [[SpinBot]]. -- [[Kuuran]]

//////////////////////
int i=0;
		while (true){
			
			projectedheading=(int)lastfourhundredheading.charAt(i+posistionheading);
			projectedvelocity= (int)lastfourhundredvelocity.charAt(i+posistionvelocity);
			delta_x=Math.sin(e.getHeadingRadians() + Math.toRadians(projectedheading)) * projectedvelocity;
			delta_y=Math.cos(e.getHeadingRadians() + Math.toRadians(projectedheading)) * projectedvelocity;
			double distance=Math.sqrt( Math.pow((e_x+delta_x)-x,2)+Math.pow((e_y+delta_y)-y,2)) ;
			if (20-3*(400/e.getDistance())>distance){
				angle = Math.atan((double)e_y+delta_y/(double)e_x+delta_x);
				break;
			}
////////////////////////// Whats wrong with this? I get continuous out of bounds errors. - andrew
			i++;
		}

You have a i++ into the an infinite loop "while(true)" so it will grow until the index is higher than the last position of your string ... -- [[Albert]]

It's probably the exit condition that doesn't guarantee that "i" doesn't grow above the boundaries. Try using a for loop instead:
<pre>
for (int i = 0; i < leastfourhundreadheading.length() - positionheading; i++) {
 projectedheading=(int)lastfourhundredheading.charAt(i+posistionheading);
 projectedvelocity= (int)lastfourhundredvelocity.charAt(i+posistionvelocity);
 delta_x=Math.sin(e.getHeadingRadians() + Math.toRadians(projectedheading)) * projectedvelocity;
 delta_y=Math.cos(e.getHeadingRadians() + Math.toRadians(projectedheading)) * projectedvelocity;
 double distance=Math.sqrt( Math.pow((e_x+delta_x)-x,2)+Math.pow((e_y+delta_y)-y,2));
 if (20 - 3 * (400 / e.getDistance()) > distance) {
 break;
 }
}
angle = Math.atan((double)e_y+delta_y/(double)e_x+delta_x);
</pre>
I'm not sure about the length() method. But a method of checking a String's name exists and it seems a reasonable name. =)

-- [[PEZ]]

It's a string buffer so length() is the correct function. - andrew
i think the problem is in by bogus calculations. trying to fix now

-----

Hi, I'm new-ish to Robocode, and I've been trying to write a pattern-matching gun recently - my bot already has a basic GuessFactor gun, as well as a circular targeting gun in a virtual guns array. I can't seem to get the pattern-matching gun to work properly, though - it fires in the general direction of the other bot (This is one-on-one), and gets about a 20% hitrate on Spinbot at the most. Can anyone see what's wrong with this?

<pre>
private class PatternVector {
		private double hchange=0;
		private double length=0;
		
		public PatternVector(double h, double l) {
			hchange=h;
			length=l;
		}
		
		public double compare(PatternVector p) {
			double hd=hchange-p.hchange;
			double ld=length-p.length;
			return hd*hd+ld*ld;
		}
		
		public double calcXPos(double x, double h) {return x+Math.sin(calcH(h))*length;}
		public double calcYPos(double y, double h) {return y+Math.cos(calcH(h))*length;}
		public double calcH(double h) {return h+hchange;}
	}
	
	private class PatternMatchingGun extends Gun {
		private ArrayList history=new ArrayList();
		private Enemy lastdata;
		
		private int findBestPattern() {
			int bestindex=history.size();
			double bestscore=PATTERN_THRESHOLD;
			double curscore=0;
			PatternVector current;
			for(int a=0;a<history.size()-PATTERN_RECENTHISTORY_LENGTH;a++) {
				curscore=0;
				for(int b=history.size()-PATTERN_RECENTHISTORY_LENGTH;b<history.size();b++) {
					current=(PatternVector) history.get(a);
					curscore+=current.compare((PatternVector) history.get(b));
				}
				if(curscore<bestscore) {bestindex=a+PATTERN_RECENTHISTORY_LENGTH+1; bestscore=curscore;}
			}
			return (int) bestindex;
		}
		
		private void addData(Enemy e) {
			if(lastdata==null) {lastdata=e;}
			history.add(new PatternVector(normalRelativeAngle(lastdata.lastheading-e.lastheading),e.velocity));
			if(history.size()>PATTERN_HISTORY_LENGTH) {history.remove(0);}
			lastdata=new Enemy(e.name,e.lastenergy,e.lastheading,e.lastscan,e.bearing,0,v);
		}
		
		private Point2D.Double calcEnemyPos(double when, Enemy e, int startofpattern) {
			double diff=when-t;
			double ix=e.ex;
			double iy=e.ey;
			double head=e.lastheading;
			PatternVector p;
			for(int a=startofpattern;a<=(diff+startofpattern);a++) {
				if(history.size()>a) {
					p=(PatternVector) history.get(a);
					ix=p.calcXPos(ix,head);
					iy=p.calcYPos(iy,head);
					head=p.calcH(head);
				}
			}
			return new Point2D.Double(ix,iy);
		}
		
		public void targeting(Enemy e, boolean virt) {	
			double time;
			double nexttime;
		
			Point2D.Double p = new Point2D.Double(e.ex, e.ey);

double px=x+Math.sin(h)*v;
			double py=y+Math.cos(h)*v;
			
			int pstart=findBestPattern();
			
			for (int i = 0; i < iterations; i++) {
				nexttime = Math.round((dist(px,py,p.x,p.y)/(20-(3*bulletpower))));
				time = t + nexttime;
 		 	 	p = pgun.calcEnemyPos(time,e,pstart); 
				pstart+=nexttime;
			}
		
			double gunoffset = getGunHeadingRadians() - (Math.PI/2 - Math.atan2(p.y - py,p.x - px));
			gunoffset=normalRelativeAngle(gunoffset);
		
			if(!virt) {
				setTurnGunLeftRadians(gunoffset);
				if(getGunHeat()==0) {log("Firing Pattern-Matching gun"); setFire(bulletpower); bulletsfired++;}
			}
			else {vbullets.add(new VBullet(getGunHeadingRadians()-gunoffset,x,y,t,bulletpower));}
		}
	}
</pre>

As you can see, it's a fairly basic non-symbolic pattern matcher. The 'virt' boolean variable is used for firing virtual bullets to find the best gun to use in various circumstances, h is my heading in radians, t is the time, x and y are my x and y loc, v is my velocity. I call addData() whenever I get a new scan of the other bot. I haven't been able to figure out why it's weirding up, but it certainly isn't pattern-matching properly. Any ideas?--[[Jp]]

Hey, Welcome! It is very important for this type of PM gun to get a new scan on every tick. The first thing i'd check is that you aren't missing any scans. If I have time later i'll take a closer look at the code. --[[wcsv]]

In calcEnemyPos(), both your x and y coordinate are calling calcXPos(). I'm assuming you want that to be calcYPos() for your y coord. Hope that helps. --[[Corbos]]

Welcome! why don't you make a page for yourself when you get a chance? In the meantime, if what [[Corbos]] suggested didn't solve it, could you post the entire bot? Or at least enough of it that I can get it to compile and run? I can't debug stuff in my head very well. =) See you in the rumble! --[[David Alves]]

I'm so embarrassed that I didn't pick that one up. It hasn't massively improved it's accuracy, though, so I've got some other bugs somewhere. I'll create a page for myself and throw the bot up there - it's fairly ugly, though, so be warned. :) --[[Jp]]

Another possible issue, see ordered comments below:
<pre>
private class PatternVector {
	public double calcXPos(double x, double h) {
		return x+Math.sin(calcH(h))*length;	<!---#3 calcXPos uses calcH which adds the heading delta again.
							This second addition of the delta will really mess things up if
							you're "playing the pattern forward" for more than a tick or two.
	}
	public double calcYPos(double y, double h) {return y+Math.cos(calcH(h))*length;}
	public double calcH(double h) {return h+hchange;}
}
	
private class PatternMatchingGun extends Gun {
	private Point2D.Double calcEnemyPos(double when, Enemy e, int startofpattern) {
		...
		for(int a=startofpattern;a<=(diff+startofpattern);a++) {
			if(history.size()>a) {
				p=(PatternVector) history.get(a);
				ix=p.calcXPos(ix,head);	<!---#2 Use calcXPos() to project ix
				iy=p.calcYPos(iy,head);
				head=p.calcH(head);	<---#1 Add the vector's heading delta to the current heading.
			}
		}
		return new Point2D.Double(ix,iy);
	}
}
</pre>
Hope that helps. --[[Corbos]]

On second thought, i guess your order is actually correct - add it for ix, then add it to head after you project ix. No more debugging at a glance for me. --[[Corbos]]

Aha! After altering the calcEnemyPos() function so that it actually draws where I think the other bot will end up, I discovered that Spinbot's guesstimated trajectory was curving the wrong way. I was adding the heading change where I should have been subtracting it. Now that that's fixed, it gets a much better hitrate. It's still not massively good, but it's actually pattern matching, I believe. --[[Jp]]

I'm relatively new to robocode (since August). Can anyone find out what's wrong with this gun???
<pre>
import robocode.*;
import java.awt.Color;

public class Knowledge extends AdvancedRobot
{
	static int n;
	static String headDelta = new String();
	static String velocity = new String();
	int lastHeading=0;
	int direction=1;
	int everyTick=20;

/**
	 * run: Knowledge's default behavior
	 */
	public void run() {
		setTurnRadarRightRadians(Double.POSITIVE_INFINITY);
		// After trying out your robot, try uncommenting the import at the top,
		// and the next line:
		setColors(Color.WHITE,Color.BLACK,new Color(0,255,0));
		
		setAdjustGunForRobotTurn(true);
		setAdjustRadarForGunTurn(true);
		setAdjustRadarForRobotTurn(true);
		doNothing();
	}

public void onScannedRobot(ScannedRobotEvent e) {
		
		headDelta += (char)(e.getHeadingRadians()-lastHeading);
		velocity += (char)(e.getVelocity());
		n++;
		if(n>100){
			String lastHeadDelta=headDelta.substring(n-8,n-1);
			String lastVelocity=velocity.substring(n-8,n-1);
			int lastSimilarHead=headDelta.indexOf(lastHeadDelta,25)+7;
			int lastSimilarVelocity=velocity.indexOf(lastVelocity,25)+7;
			
			double enemyBearing = getHeading() + e.getBearing();
			double enemyX = getX() + e.getDistance() * Math.sin(Math.toRadians(enemyBearing));
			double enemyY = getY() + e.getDistance() * Math.cos(Math.toRadians(enemyBearing));
			double bulletDistance=0;
			double time=0;
			double firePower=0;
			
			while(true){
				time++;
				double deltaX=Math.sin(e.getHeadingRadians() - ((int)(headDelta.charAt(lastSimilarHead)))) * (int)(velocity.charAt(lastSimilarVelocity));
				double deltaY=Math.cos(e.getHeadingRadians() - ((int)(headDelta.charAt(lastSimilarHead)))) * (int)(velocity.charAt(lastSimilarVelocity));
				enemyX+=deltaX;
				enemyY+=deltaY;

if(distance(enemyX,enemyY,getX(),getY())<bulletDistance){
					double vel=distance(enemyX,enemyY,getX(),getY())/time;
					firePower=(20-vel)/3;
					double dx = enemyX - getX();
					double dy = enemyY - getY();
					double theta = Math.atan2(dx, dy);		
					turnGunRightRadians(normalRelativeAngle(theta - getGunHeading()));			
					break;
				}else{
					bulletDistance+=11;
					lastSimilarHead++;
					lastSimilarVelocity++;
				}
			}
			fire(firePower);
		}
		setTurnRadarLeftRadians(getRadarTurnRemainingRadians());
	}

public double normalRelativeAngle(double angle) {
		//taken from OddBot
		return ((angle + 15.7079633) % 6.2831853) - Math.PI;
	}
	
	public double distance( double x1,double y1, double x2,double y2 ) {
 double xo = x2-x1;
 double yo = y2-y1;
 double h = Math.sqrt( xo*xo + yo*yo );
 return h;
 }
}
</pre>
I keep getting a StringIndexOutOfBoundsException. Why? --Starrynte

I think it is because you don't check if lastSimilarHead is greater than the length of headDelta (and velocity). You can check for it with the while condition so it is something like this:
<pre>while(lastSimilarHead < headDelta.length){ ... }</pre>
On a side note, I would recommend storing getX(), getY(), and getGunHeading() to myX, myY, and myGunHeading because RoboCode does limit the number of calls to the get...() methods. Good luck with your robot! -- [[Kinsen]]

Has anyone ever tried to do PM with the change in gun heading (when you are aiming)??? --Starrynte

Do you mean like the change in absolute bearing between you and the enemy? I've never done one myself, but I think that's what an "angular pattern matcher" is. [[Teancum]] is the only page where I can find that phrase on the wiki. If that's not what you mean, could you clarify a little? -- [[Voidious]]

Yeah, the NanoBot PatternMatchers do what you're describing. For example, NanoLauLectrik. --[[David Alves]]

The Nano pattern matchers do it on tangential velocity, not gun turn.  The problem with gun turn pattern matching is that it depends almost entirely on distance, so it would take a very long time to build up a useful history. --[[Simonton]]

If you keep your gun aimed directly at them, they should amount to the same thing, I thought; if you're not, then matching on gun turn seems pretty useless to me. Then again, I've never made one, so I could be wrong... -- [[Voidious]]

I just discovered two errors in the code above. First, I was subtracting getGunHeading() from theta instead of getGunHeadingRadians(). Also, i wasn't setting lastHeading to e.getHeadingRadians(). It probably won't help the StringIndexOutOfBoundsException though... --[[Starrynte]]

What's TangentialVelocity? --[[Starrynte]]

Oops, I think I posted up there with out signing it.  Fixed.  Voidious: When we're talking about pattern matching on gun turn, I assume that would be "gun offset from pointing directly at him right now."  But either way, the radians you turn your gun is vastly different depending on whether the enemy is 50 "pixels" away or 500, even if his movement is the same.  Therefore, in a pattern matcher, you would have to build up data about him at almost every possible distance before matching based on gun turn would become very useful.  SO - the nano pattern matchers match based on TangentialVelocity, since that is independant from distance (see the new page for the way I'm using that term).  There - maybe that was a more complete thought.  --[[Simonton]]

[[LateralVelocity]] is the more common term around here for TangentialVelocity.  The nano pattern-matchers (primarily) pattern match on that.  I think some version of [[Teancum]] or [[FloodMini]] attempted to pattern match on wave results, but I don't know if I ever released a version that did that.  [[Teancum]] pattern-matches on [[LateralVelocity]] and [[AdvancingVelocity]]. -- [[Kawigi]]

My new PM gun can hit MyFirstRobot pretty well and SpinBot pretty well, but it can't hit Crazy at all! Does anyone know why? (code posted at [[Starrynte/Knowledge]]) --[[Starrynte]]

Actually, correct that. The "why" is probably HOT can hit MyFirstRobot and SpinBot pretty well but can't hit Crazy that well. Now my question is, does anyone know how to fix? (I'm not sure about the 'why' though) --[[Starrynte]]

I have a vague idea that the why is because i am using radians, which are *very* small, and will almost always be cast to 0 or 1. --[[Starrynte]]

Changing to degrees fixes it, kind of. It still can't really hit Crazy or PatternBot. --[[Starrynte]]

Just out of curiousity, has anyone tried to do PM with segmentation? --[[Starrynte]]

I have tried it a little bit - basically, I tried to match some segmentation data at fire time (end of the pattern) in addition to looking for a pattern of a certain length. The resulting gun was decent, but I abandoned it. It was [[Shaakious]] that had that gun, but it's currently retired / not being worked on. -- [[Voidious]]

[[SeaSerpent]]s PM gun segments its data. Every tick, it adds the latest index of the pattern to a segmented list. Then when it shoots, it only matches on indexes within the current list. Because the actual matching includes things like velocity and acceleration, it only segments on distance and wall proximity. Besides making it more accurate, segmentation also makes the gun faster because it only looks at bits of the pattern at a time. -- [[Kev]]

I think it has something to do with casting the char to an int, then the int to a double (or it could be the other way around, casting the double to an int, then the int to a char) because I set it to print the velocity that was recorded and it prints out stuff like 
<pre>
8.0
8.0
8.0
8.0
6.0
4.0
2.0
0.0
65535.0
65534.0
65533.0
65532.0
</pre>
against PatternBot --[[Starrynte]]

That's the reason I (and many more) add 8 or MaxVelocity to the char with my not-so-high-ranked (127) patternmatcher. Same goes for deltaheading or any other patternvariable by the way. - [[GrubbmGait]]

Oh - you just need to cast the char to a short (or byte), then a double.  Otherwise the ones that should be negative numbers turn out like that.  If you know about the 2's compliment binary format, casting it to a short, then a double effectively does the necessary sign-extention.  -- [[Simonton]]

Ok thanx...It still doesn't really hit MyFirstRobot --[[Starrynte]]

Okay, its long overdue, but I made my first pattern matcher from scratch that actually works. Hehe, all my other attempts (and the one by my sister), failed, generally by disinterest. But the thought of hitting Spinbot and Walls perfectly everytime, spurred me on to actually make one. --[[Chase-san]]

Welcome!  -- [[Simonton]]

And no, it wasn't SingleTick (but I made one of those too) --[[Chase-san]]

That's ok, I leave room in my affections for all PM styles ;).  -- [[Simonton]]

----

Alright folks, this is a call to push the limits of pattern matching.  For anyone who loves pattern matching, who is curious to see how well it can do, or is just looking for a new robocoding challenge, let's put our heads together & see where we can go with this.  I've moved away from the /SingleTick style for a while, and this more traditional method has a lot more potential then we've squeezed out of it so far.  Take a look at TargetingChallenge2K7/Results.  I've posted 2 scores, one for straight-up pattern matching and one with multiple choice.  Both have a couple features: they treat clockwise & couter-clockwise movements the same, and they aim at the longest match(es) ''that don't place the opponent out-of-bounds''.  You can see that multiple choice works better for non-adaptive movements, and straight-up style for wave surfers.  These could easily be combined in a VG array to push pattern mathcing's score just below the big guns in the challenge, and I bet we could get it into that group if we start playing with segmentation.  [[Kev]] is already an expert at this (see SeaSerpent).  I'll post a link on my homepage to source for the bot I used to get those scores, let's see what we can do. --[[Simonton]]

* Seems to me you will start to blur the lines between PatternMatching and VisitCountStats, especially with talking about segmentation, or with DynamicClustering if you just use attributes without segmenting. ([[Shaakious]] was a super SlowBot, but I tried to use segments with that - search for a match with also matching segments, or matching without it if there wasn't one.) You could even say that most top GuessFactor / VisitCountStats already blur the lines: attributes like "time since velocity change" (one of the most powerful) or "distance last eight ticks" (less powerful, but [[Dookious]] and [[Shadow]] use 'em) have shades of PatternMatching, in my opinion. Good luck, dudes. =) -- [[Voidious]]

* I don't mind bluring the line.  Actually the line just needs better definition :).  Segmenting doesn't make a PM gun any less PM, it's the "play-it-forward" technique, imo.  I just think pattern matching does an lot of segmentation for you, which you have to hard-code in GF guns.  But there may still need to be some hard coded into pattern matching, like wall distance (probably my next move).  -- [[Simonton]]

* Not sure I agree on that being the line - [[ABC]] has used "play it forward" to project firing angle with guns that I wouldn't consider PatternMatching ([[TronsGun]] / [[DynamicClustering]]). Seems to me like on one side you have some sort of stats system: look through a log of past states ([[TronsGun]] / DynamicClustering); look through tallied statistics based on past states ([[VisitCountStats]] / "traditional" GuessFactorTargeting); or match the last X states with a log of states (PatternMatching). On the angle projection side, you have: take the most popular angle (or GuessFactor) among matching states (VisitCountStats or [[Ali]]'s log-based gun); find the angle (or GuessFactor) that is somehow the "best" from the set of all matching states (DynamicClustering, MultipleChoice); or "play the movie forward" and shoot at the angle that hit the bot at that spot in previous situation(s). Traditional PatternMatching is the last choice on both sides, but it seems to me like the "pattern matching" part comes in the first part (stats searching), not the second (angle projection). It's funny how often we end up in these semantic debates on this wiki - I sometimes wonder how much all these labels matter =) But I do think it's helpful to clarify ideas. E.g., "GuessFactor" tends to be synonymous with VisitCountStats when it can just as easily be used in DynamicClustering - it's not really a stats system, just a great way of interpreting a firing angle. -- [[Voidious]]
** Then I'm forced to wonder where [[Engineer]] fits in with its neural network =) Maybe it's more like "maintain a data structure that points at the best angle / GuessFactor for a given state" for the "tallied statistics" description in my previous statement. Ok, done babbling for now...-- [[Voidious]]

Another thing is to look for seperate patterns in velocity and deltaheading. This made a huge difference - the difference between Decado 0.1 and Waylander 0.1, to be precise. About 6 places in the MicroRumble. Next I will try MultipleChoice . --[[Skilgannon]]

* Ok, interesting.  I'll have to give that some more research.  I tried that with /SingleTick pattern matching a while back, but it didn't help there.  -- [[Simonton]]
* I take that back, it seems the reason Waylander suffered so much was that I was using too many possible values for angle-change, so it could never find a match. Now that it's fixed it outranks Decado by quite a bit. -- [[Skilgannon]]

----

I was thinking about restarting work on my [[Rednaxela/NeuralPatternMatching|NeuralPatternMatching]], and had one thought about PatternMatching in general. Usually all of the PatternMatching I've seen seems either strictly relative, or strictly absolute. One thing I was thinking about today, is why couldn't they be combined? It shouldn't be difficult to store both relative and absolute movement in a PatternMatcher's memory, and use whatever type happens to get the highest score. In fact, you could have multiple different types of relative segments in the same PatternMatcher and whichever one pulls up the strongest corrolation on a given tick could be used. I wonder, has anyone previously combined different types of PatternMatching as I describe or has it really not been done before? -- [[Rednaxela]]

I have FINALLY managed to create a naive symbolic PM gun that can hit pattern bots 90% of the time...:) --[[Starrynte]]

Congrats! Now if only I could get my [[Rednaxela/NeuralPatternMatching|NeuralPatternMatching]] to work that well... :) -- [[Rednaxela]]

* Disclaimer: It can hit PatternBot and Spinbot 90% of the time...which may or may not imply other pattern bots --[[Starrynte]]

If my PM gun (a new one) "sometimes" works and "sometimes" doesn't, what can be the problem? To clarify: sometimes it finds the "match", yet sometimes it doesn't... --[[Starrynte]]
* Abandoning project for now...Eclipse is too frustrating for me as of now...maybe I'll continue it in a few hours --[[Starrynte]]
** Edit: Eclipse was frustrating because something went wrong, and now everything that was in my robots folder is gone, with no backups. (this includes the perfect PM gun above :( ) --[[Starrynte]]
** Ok, recoded a clone of the PM gun above, now I just have to recover my new melee bot... --[[Starrynte]]
*** Codesize successfully shrunk down to 568 (and counting), including a simple oscillator (thank you, binary operators)...now i'll see if i can add a StopAndGo movement...or segmentation...and a name! :) --[[Starrynte]]

So far all of my attempt have been based on non-relative positioning (velocity/acceleration and turning rate) because that's made the most sense to me, but I have some questions about patternmatching with LateralVelocity and AdvancingVelocity like I often see used as well. In particular, because LateralVelocity and AdvancingVelocity are measured relative to your position, and generally your own gun can't know your own future movement so I can't see how a relative patternmatcher would work effectively. It seems to me that not knowing what they will be moving relative to would make the data quite invalid. Is there something I'm missing or do people just live with this inaccuracy that to me seems quite major? -- [[Rednaxela]]

I also questioned that - I certainly wouldn't use relative data as a method to rebuild enemy movement (codesize limited environments excluded), but *matching* on the data is perfectly valid, and might pick up patterns that absolute matchers might miss due to the other bot reacting to your movement. If you want to see a quick (and 100% accurate) way to rebuild enemy data, take a look at DrussGT/HelpRequests - it's the one that [[Shadow]] uses. I just right now found that bug in my PlayItForward DC gun mentioned there (accidently used degrees for heading - aargh!!) so I'm releasing it to the rumble to see what happens =). [[Simonton]] released 2 versions of WeeklongObsession, one with relative, one with absolute, and they scored the same. To me this indicates that relative finds better patterns, to make up for its slight inaccuracy. -- [[Skilgannon]]

Hmm, interesting. I'm thinking now that I may end up making the PM gun in RougeDC, into something that matches on both relative and absolute patterns as well as perhaps eventually slight segmentation and rebuilds with absolute movement only... That would probably complement the normal DC/GF gun I have rather nicely... :) -- [[Rednaxela]]

Rebuilding lots of patterns using velocity/acceleration and deltaheading can get pretty slow! I'm not sure if you quite understand the method that [[Shadow]] (and currently DrussGT - we'll have to see if it helps) use - instead of 'rebuilding' the movement they made last time in this new position, we project our own location to be in the same 'relative' position to the recorded co-ordinates and just see where their co-ordinates go as time progresses from that point. You check what the angle offset is from your 'relative' location, and that's what the angle offset is in this new situation as well. You can even do boundary checking on their final location by projecting from your 'actual' location at that offset from the absolute bearing, using the distance of your 'relative' location to their co-ordinates when the bullet hits them. -- [[Skilgannon]]

Yep, I do understand that, though it's slightly incompatible with my precise botwidth calculations that I'm fond of, but do halfway between that method and the slow one by using iterative integer addition based around a similar principal, in place of all the trig, which should run pretty fast too. -- [[Rednaxela]]

Summary:
Consciousness check: 6 + 8 =
This change is a minor edit. Send email notification that PatternMatching has been changed.
(Visit Preferences to set your user name.)

View other revisions
Robo Home | Changes | Preferences | AllPages