Archived talk:Pattern Matching 20071114
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:
if ((getGunHeat()/getGunCoolingRate()) < 4)
{
...
...
(patternmatching stuff)
...
...
}
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
(getGunHeat()/getGunCoolingRate() < 4)
instead of just
(getGunHeat() < .4)
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 (char)e.getVelocity() and (char)(e.getHeading - lastHeading). 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 (int)stringRecordingOfVelocity.charAt(++endOfMatch); and (int)stringRecordingOfVelocity.charAt(endOfMatch); 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 deltaX = Math.sin(e.getHeadingRadians + Math.toRadians(nextHeadingChange)) * nextVelocity; 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 (observedHeadingChange - recordedHeadingChange)/maximumPossibleHeadingChange. 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:
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);
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?
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));}
}
}
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:
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);
}
}
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???
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;
}
}
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:
while(lastSimilarHead < headDelta.length){ ... }
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
SeaSerpents 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
8.0 8.0 8.0 8.0 6.0 4.0 2.0 0.0 65535.0 65534.0 65533.0 65532.0
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
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
