Robo Home | Oscillators | Changes | Preferences | AllPages

When I was building NanoLauLectrik 1.0, I found that the following movement.

 setAhead(Math.sin(n/12)*Math.cos(n/6)*200) //n is the moment in time

was performing far worst against pattern matchers that the movement

 setAhead(Math.sin(n/12)*Math.cos(n/7)*200) //Note? that it only changes the 6 for the 7

I got quite curious, because I didn't expected such a subtle change to have a great efect on its performance. I plotted some graphs to investigate, and I found that the main difference was the lenght of the full period of the movement (the full period is the number of ticks it takes for the movement to exactly repeat again).

 for a = 12 and b = 6 the full period is 75 
 for a = 12 and b = 7 the full period is 528

I tested the performance for different periods and it seems that the longer the full period, the better the movement. Of course, there are some more considerations, so it's not enough to just increase a to POSITIVE_INFINITY :-)

So, the second step was: How could I calculate the lenght of the period? I found a formula you can use to calculate it (note that it works both for multiplicative and additive complex oscillators):

 Full Period Lenght = 2 * PI * b * (a/m.c.d(a,b))          m.c.d is the maximum common divisor of a and b.

For example:

 m.c.d(12,7) = 1 -> FPL = 2 * PI * 7 * (12/1) = 527,7
 m.c.d(12,6) = 6 -> FPL = 2 * PI * 6 * (12/6) = 75,3

So you can easily see that the best combination of a,b is the one where a and b are relative prime numbers. An easy way to get it is to make sure that either a or b are primes (3,5,7,11,13,etc).

Since these kinds of effects (great changes of performance produced by small changes in parameters) had happened to me in more complex movements, I guess that this kind of (or similar) logic applies to different types of movements... so be careful which parameters you choose.

-- Albert

Yep, prime's are best for periods - though not completely needed. As long as A and B have no common factors you get the same results: A = {2,4,8,16,32} and B = {3,9,27,54,81} would work fine as neither has factors of each other - it also allows the powers of 2 to use shifts to save code space ( >> 4 is smaller than / 16.) Multiplying the trig functions aren't necessary either, addition or subtraction also works - just get out your graphing calculator and come up with a good random looking sine wave that doesn't have a mean value over small areas of the function around 0, 1 or -1 so that no aim, or full lead bots don't get free pot shots. If I drop color and get the 4 bytes promised by PEZ, I'll do a real good function for Moebius 1.4. Also, don't forget about the virtues of a * random() thrown in ;)

-- Miked0801

Yes, that's what "relatively prime" means. :) Oh, and 54 doesn't belong in the B set, since it obviously has 2 as a factor.-- nano

You never got those 4 bytes? No, the e-mail bounced. I used the address you have listed on your profile at the repository. Please send me an e-mail and I'll reply back with dieted Moebius 1.3. -- PEZ

Well, I placed it in Moebius/Code instead. -- PEZ

SillyBot uses 13 and 17, and then only multiplies it by 40, so he has some slow movements, too. -- Kawigi

Comment. You say the period of repetition is 527.7 for NanoLauLectrik. This is true mathematically, but in robocode it's a little bit different. The values we're using are discrete (decimals aren't used). This means that you can't really identify the repetition at frame 528, because the values are slightly different. Is my reasoning wrong? I don't think the rounding of the shifted values will always go the same way, which would confused pattern matchers and give them only somewhat better aim, they wouldn't have a dead lock until the period of repetition had an integral value. Is this line of reasoning reasonable? -- Kuuran

The effect you describe is probably true, but I don't think it has a great effect. If you plot the values you will see that the period is clearly identifiable by inspection, regardless of the rounding. Pattern matchers are not looking for exact matches, but close matches, so I think they will have no problem to identify the period. Also, usually pattern matcher don't use match lenghts of 500+, thus this problem should have no effect on them. I think the advantage of having long full-periods is just that they provide for more complex movement, with a bigger number of patterns. -- Albert

Could you explain the basics please? As I understand it n is an integer that is being incremented and you are using the product of a sin with a cos of a term using n to generate a move. Why would you do this rather than simply use the random function? What is the benefit of using a periodic term to generate movement? Sorry this question is so basic. --Tad

Well that was sort of the point, Albert. The individual patterns also repeat when the whole period repeats, and I think they might be shifted on the graph just enough that they're unrecognizable for several more occurances of the period. At least, that's the only reason I see to explain why pattern matchers are still improving their aim against NanoLauLectrik and Moebius in something like round 50 of a battle. By then they should've had the pattern memorized.

As for your question, Tad. The basic idea behind perpendicular oscillators is they screw the hell out of simple targeting (linear/circular), which random movement may not do. There is a type of random movement somewhere on the wiki which chooses intelligently and probably does a better job, but this sin/cos oscillator is meant for nanos, which could never fit that. The use of sin/cos with a high period is to foil pattern matchers from seeing the simple oscillation. There are also advantages to staying around the same spot, particularly with wall collisions. But the answer is, really, there is no answer. The reason there are multiple movement strategies is because all of them have flaws. -- Kuuran

About learning about 50+ rounds - I can think of many additional reasons for it to happen: Heading change has an strong influence on the patterns (because it affects the perpendicular velocity), also walls (that create an stop and go movement), also collisions with the enemy bot, and the energy level (disabled bots). All this elements affect the basic patterns to create new ones, so bots need a longer time to learn. -- Albert

Wow. I've never really written a pattern matcher before, and it's quite amazing to me that a pattern patcher can match a period of 75 ticks, nevermind 528. How do pattern matchers compensate for when the nanos hit walls? Wouldn't the oscillator pattern break down? -- Vuen

It would just create a new pattern :-) And in reality, a pattern-matcher wouldn't need to figure out a pattern that's 528 long against an opponent that has a period of 528 ticks, it would just need to find the right pattern in the past (regardless of length of the period). The point is finding the right part of the period (a longer match length makes you more likely to find the right match, though). About how we compensate when the enemy hits a wall, it's interesting. Many of my bots have figured out if it was projecting its opponent into a wall, and would figure out when they would hit a wall, and would fire a faster bullet that would hit them exactly at this time (it looks alot like ChaseBullets against Walls). A more sophisticated robot (TheArtOfWar might do this) would keep track of how its enemy reacts to walls - if it curves parallel to the walls (hardest version to predict probably), or if it bounces off the walls (and if it does, whether or not it hits walls, or how close it gets before bouncing), or if it gets stuck against the wall, and how many ticks it usually sticks there... There are lots of potential ways to intelligently deal with this, and it goes beyond pattern-matching a little and into movement analysis (which is, I suppose, what pattern-matching is). Another approach (which is what I think Lacrimas does) is to put the distance from the wall into the parameters are pattern-matched - but it isn't quite as sophisticated, maybe, as I don't think Iiley is actually using this to project movement (what he matches and how he chooses a bearing are basically unrelated). -- Kawigi

Robo Home | Oscillators | Changes | Preferences | AllPages
Edit text of this page | View other revisions
Last edited May 18, 2006 15:08 EST by Danb00 (diff)